$$\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}$$

• 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. Apr 20, 2017 at 13:57
• Maximization is NP Hard. This is going to be rough. The positive semidefinite property only makes minimization easy, not the other way around Apr 20, 2017 at 14:09
• 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 Apr 20, 2017 at 14:10
• If you could share it, it would be very helpful. Thank you. @frogeyedpeas Apr 20, 2017 at 14:23
• @frogeyedpeas could you please link me to some algorithms so I could try to figure out a solution. Thanks a lot. Apr 24, 2017 at 10:13

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.

• Thanks a lot for the answer. Its also easily extendible to more number of quadratic constraints. Apr 24, 2017 at 17:55

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.

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