4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Dear Prof. Borchers, thank you for the illuminating answer. Sadly I don't have enough reps to up-vote it yet. One practical question. Suppose the $\pmb P_i$ matrices are rank-1 and of dimensions 20 by 20. In your experience with SDP solvers, how many constraints would you think (broad back of the envelope) would be manageable on a typical workstation/blade with 32gb of memory in say 10 hours? Thanks again. $\endgroup$ – user42397 Aug 25 '16 at 1:43
  • $\begingroup$ Some solvers have the ability to take advantage of rank-one structure in the constraint matrices, but most do not. There's no way to express this structure in the standard SDPA file format. $\endgroup$ – Brian Borchers Aug 25 '16 at 1:46
  • $\begingroup$ Storage is more often the problem then run time. For CSDP, a rule of thumb is that for a problem with $n$ by $n$ matrix variables and $m$ constraints, you need $8(m^{2}+15n^{2})$ bytes of storage (plus some lower order terms.) This assumes $O(1)$ entries per constraint matrix, but yours are fully dense. CSDP's storage for constraint matrices uses 16 bytes per entry. So, add another $16mn^{2}$ bytes for the constraint matrices. You've got $n=20$, which is tiny. If I stick in $m=10000$, then my estimate is about 8.6 Gigabytes. If I stick in $m=20000$, I'm over $32$ gigabytes. $\endgroup$ – Brian Borchers Aug 25 '16 at 1:54
  • $\begingroup$ So yes, I think it would be doable with CSDP in terms of storage. $\endgroup$ – Brian Borchers Aug 25 '16 at 1:55
  • $\begingroup$ I haven't taken into account storage for the additional slack variables (one for each of the constraints), but these shouldn't be of any practical significance (they're lower order terms in the storage requirement.) $\endgroup$ – Brian Borchers Aug 25 '16 at 1:58
2
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ Also, since the answer for this formulation turns out to be trivial, I'd guess (but I'm not sure what you're trying to model) that this formulation isn't capturing exactly what you want. You may need to add constraints or modify the objective to get something more interesting or closer to the actual thing you're interested in. $\endgroup$ – AJ Friend Sep 1 '16 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.