Maximization variant of semidefinite programming (SDP)

Question

Consider the following program:

$$\max_{\pmb a} \sum_i z_i\\ u.c. \pmb a \pmb P_i\pmb a^\top\geq z_i$$

where $\pmb a \in\mathbb{R}^p$ and the $\pmb P_i$ are all symmetric positive semidefinite matrix (the eigenvalues of $\pmb P_i$ are all $\geq 0$ for all $i$) and $z_i$ is a scalar.

I am wondering if this is indeed a valid semidefinite programming problem (basically I think it can be recast as the standard form but I want to make sure I am not mistaken before I expand more effort into this angle of attack).

Edit:

Actually, to simplify the question I had left some constraints out. The actual problem is:

$$\max_{\pmb a} \sum_i^I z_i - \sum_j^J w_j\\ \pmb a \pmb P_i\pmb a^\top\geq z_i, i=1,\ldots,I\\ \quad\pmb a \pmb Q_j\pmb a^\top-w_j= 0, j=1,\ldots,J\\ \quad w_j\geq 0$$

where again, the $\pmb Q_j$ are all symmetric non negative definite. I reckon Prof. Borchers's answer below can easily be adapted to the complete program. The added constraints help make the program bounded.

Answer 1

You can obtain a semidefinite relaxation of your problem that will provide a bound on the optimal value of your problem, but it will not be an exact semidefinite formulation of your problem.

Start with the constraints

$aP_{i}a^{T} \geq z_{i}$, $i=1, 2, \ldots, n$

You can use the cyclic permutation property of the trace of a product to write this as

$\mbox{tr}(P_{i}a^{T}a) \geq z_{i}$, $i=1, 2, \ldots, n$

If you let

$A=a^{T}a$,

then your constraints are

$ \mbox{tr}(P_{i}A) \geq z_{i}$, $i=1, 2, \ldots, n$

together with

$A=a^{T}a$.

You can then relax the constraint $A=a^{T}a$ to $A \succeq 0$, to get a relaxation of your original problem:

$\max_{A,z} \sum_{i} z_{i}$

subject to

$ \mbox{tr}(P_{i}A) \geq z_{i}$, $i=1, 2, \ldots, n$

$A \succeq 0$.

This is an SDP, and its optimal value provides an upper bound on the optimal value of your original formulation.

The constraint $A=a^{T}a$ is a non-convex rank-one constraint that cannot be formulated exactly in SDP.

Answer 2

It's possible I'm misunderstanding something (and please let me know if I am), but here's another approach:

Based on your formulation, it looks like your first group of inequality constraints will always be tight. And since $Q_i \succeq 0$, there's no need for the $w_i \geq 0$ constraint.

That would allow you to rewrite the problem as $$ \max_{\pmb a} \sum_i z_i - \sum_j w_j\\ \pmb a \pmb P_i\pmb a^\top = z_i\\ \quad\pmb a \pmb Q_j\pmb a^\top = w_j, $$ which can be rewritten again as a problem without constraints: $$ \max_{\pmb a} \sum_i \pmb a \pmb P_i\pmb a^\top - \sum_j \quad\pmb a \pmb Q_j\pmb a^\top. $$

If we let $S = \sum_i P_i - \sum_j Q_j$, then the problem is equivalent to $$ \max_{\pmb a} \pmb a^\top \pmb S \pmb a, $$ which is easily solvable: If $S$ has any positive eigenvalues, the maximization problem is unbounded. Otherwise, the max is achieved at $a = 0$.