1
$\begingroup$

How can I solve the following quadratically constrained quadratic optimization problem?

$$\max_{x} \qquad x'Ax$$ such that $$x'P_ix - k \leq 0 \qquad i=1,2$$

$A, P_i$ are positive semidefinite matrix. I know we can minimize $x' \hat{A} x$ where $\hat{A} = -A$ but this changes the problem to concave one with convex constraints. $x \in \mathbb{R^2}$. If it helps, finding the minimum of the inverse of $x' A x$ is also an option.

The objective function in that case would be $$\min_x \qquad \frac{1}{x'Ax}$$

$\endgroup$
6
  • $\begingroup$ What is meant by qcqp and qclp? You are using acronyms, which makes it hard to understand your question for people who don't know these acronyms. $\endgroup$
    – MrYouMath
    Apr 20, 2017 at 13:57
  • $\begingroup$ Maximization is NP Hard. This is going to be rough. The positive semidefinite property only makes minimization easy, not the other way around $\endgroup$ Apr 20, 2017 at 14:09
  • $\begingroup$ That said if you don't care about sub exponential worst case efficiency i can go ahead and answer with some heuristics to use ontop of a baseline algorithm $\endgroup$ Apr 20, 2017 at 14:10
  • $\begingroup$ If you could share it, it would be very helpful. Thank you. @frogeyedpeas $\endgroup$
    – Anon123
    Apr 20, 2017 at 14:23
  • $\begingroup$ @frogeyedpeas could you please link me to some algorithms so I could try to figure out a solution. Thanks a lot. $\endgroup$
    – Anon123
    Apr 24, 2017 at 10:13

2 Answers 2

2
$\begingroup$

So given your functions are positive semidefinite, there are a number of algorithms you can use (see: https://en.wikipedia.org/wiki/Quadratic_programming#cite_note-6, citation 6). But for this problem its simple enough we don't need such techniques:

Given $x \in \mathbb{R}^2$ we wish to solve

$$ \max x^T A x \\ x^T P_1 x \le k, x^T P_2 x \le k$$

This can actually be completely concretely spelled out by letting $A = \begin{pmatrix} A_{00} & A_{01} \\ A_{10} & A_{11} \end{pmatrix}$ and

$$P_1 = \begin{pmatrix} P_{001} & P_{011} \\ P_{101} & P_{111} \end{pmatrix}$$

$$P_2 = \begin{pmatrix} P_{002} & P_{012} \\ P_{102} & P_{112} \end{pmatrix}$$

Then it follows that we wish to solve

$$ \max x_0 (A_{00} x_0 + A_{01} x_1) + x_1(A_{10} x_0 + A_{11} x_1) \\ x_0 (P_{001} x_0 + P_{011} x_1) + x_1(P_{101} x_0 + P_{111} x_1) -k \le 0 \\ x_0 (P_{002} x_0 + P_{012} x_1) + x_1(P_{102} x_0 + P_{112} x_1) -k \le 0 $$

We rearrange terms here to yield:

$$ \max A_{00} x_0^2 + (A_{01}+ A_{10} )x_1x_0 + A_{11} x_1^2 \\ P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k \le 0 \\ P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k \le 0 $$

We can now directly pull out the $KKT$ conditions (a generalization of lagrange multipliers) https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

which tell us that the optimal solution $x^*$ to this problem will satisfy the conditions (assuming $f = A_{00} x_0^2 + (A_{01}+ A_{10} )x_1x_0 + A_{11} x_1^2$, $p_1 = P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k$, $p_2 = P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k $) :

Conditions:

$$\nabla f(x^*) = \mu_1 \nabla p_1(x^*) + \mu_2 \nabla p_2 (x^*)$$ $$ p_1(x^*) \le 0 $$ $$ p_2(x^*) \le 0 $$ $$ \mu_1 \ge 0, \mu_2 \ge 0$$ $$ \mu_1 p_1(x^*) = 0, \mu_2 p_2(x^*) = 0$$

Lets tackle the first line with the $\nabla$'s by unpacking it for our case:

$$ \begin{bmatrix} 2A_{00}x_0 + (A_{01} + A_{01})x_1 = \mu_1 (2P_{001}x_0 + (P_{011} + P_{011})x_1) + \mu_2 (2P_{002}x_0 + (P_{012} + P_{012})x_1) \\ 2A_{11}x_1 + (A_{01} + A_{01})x_0 = \mu_1 (2P_{112}x_1 + (P_{011} + P_{012})x_0) + \mu_2 (2P_{112}x_1 + (P_{012} + P_{012})x_0)\end{bmatrix}$$

Now look at the very last 2 equations of the form $[\mu_1 p_1(x^*) = 0, \mu_2 p_2(x^*) = 0]$

We can unpack these as well to yield

$$ \mu_1 (P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k) = 0 \\ \mu_2 (P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k)= 0 $$

combining these four, together:

$$ \begin{bmatrix} 2A_{00}x_0 + (A_{01} + A_{01})x_1 = \mu_1 (2P_{001}x_0 + (P_{011} + P_{011})x_1) + \mu_2 (2P_{002}x_0 + (P_{012} + P_{012})x_1) \\ 2A_{11}x_1 + (A_{01} + A_{01})x_0 = \mu_1 (2P_{112}x_1 + (P_{011} + P_{012})x_0) + \mu_2 (2P_{112}x_1 + (P_{012} + P_{012})x_0)\\ \mu_1 (P_{001} x_0^2 + (P_{011}+P_{101}) x_0x_1 + P_{111} x_1^2 -k) = 0 \\ \mu_2 (P_{002} x_0^2 + (P_{012} +P_{102}) x_0x_1 + P_{112} x_1^2 -k)= 0 \end{bmatrix} $$

We have 4 equations, and 4 unknowns $\mu_0, \mu_1, x_0, x_1$. This can now be algebraically solved for 36 possible combinations of $\mu_0, \mu_1, x_0, x_1$ select the one that maximizes your function.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for the answer. Its also easily extendible to more number of quadratic constraints. $\endgroup$
    – Anon123
    Apr 24, 2017 at 17:55
1
$\begingroup$

We have the following QCQP

$$\begin{array}{ll} \text{maximize} & \mathrm x^{\top} \mathrm A \, \mathrm x\\ \text{subject to} & \mathrm x^{\top} \mathrm P_1 \mathrm x \leq q_1\\ & \mathrm x^{\top} \mathrm P_2 \mathrm x \leq q_2\end{array}$$

where $\mathrm A, \mathrm P_1, \mathrm P_2 \in \mathbb R^{n \times n}$ are symmetric and positive semidefinite, and $q_1, q_2 > 0$. Note that we have a convex objective function and two convex inequality constraints. However, since we want to maximize the objective, the given QCQP is non-convex.

If $\mathrm P_1, \mathrm P_2$ were positive definite (thus, invertible), then, using the Schur complement, we would be able to write the inequality constraint $\mathrm x^{\top} \mathrm P_i \mathrm x \leq q_i$ as the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm P_i^{-1} & \mathrm x\\ \mathrm x^{\top} & q_i\end{bmatrix} \succeq \mathrm O_{n+1}$$

We would then have the LMI-constrained quadratic optimization problem

$$\begin{array}{ll} \text{maximize} & \mathrm x^{\top} \mathrm A \, \mathrm x\\ \text{subject to} & \begin{bmatrix} \mathrm P_1^{-1} & \mathrm x & & \\ \mathrm x^{\top} & q_1 & & \\ & & \mathrm P_2^{-1} & \mathrm x \\ & & \mathrm x^{\top} & q_2\end{bmatrix} \succeq \mathrm O_{2n+2}\end{array}$$

Does anyone know of any work on quadratic optimization over (convex) spectrahedra?

Take a look at Didier Henrion's lecture notes and the references therein.

$\endgroup$
2
  • $\begingroup$ So what next is this an sdp or something ? $\endgroup$ May 29 at 22:20
  • $\begingroup$ @TuongNguyenMinh No $\endgroup$ May 30 at 5:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .