Quadratic constrained quadratic programming

Numerical Example 1 (KKT Approach)

Consider the following Quadratically Constrained Quadratic Programming (QCQP) problem to gain a better understanding:

${\begin{aligned}{\text{minimize}}\quad &f_{0}(x)=(x_{1}-2)^{2}+x_{2}^{2}\\{\text{subject to}}\quad &f_{1}(x)=x_{1}^{2}+x_{2}^{2}-1\leq 0,\\&f_{2}(x)=(x_{1}-1)^{2}+x_{2}^{2}-1\leq 0.\end{aligned}}$

We will solve this QCQP problem using the Karush-Kuhn-Tucker (KKT) conditions, which are necessary conditions for a solution in nonlinear programming to be optimal, given certain regularity conditions.

Step 1: Formulate the Lagrangian

The Lagrangian $L$ combines the objective function and the constraints, each multiplied by a Lagrange multiplier $\lambda _{i}$:

$L(x,\lambda _{1},\lambda _{2})=(x_{1}-2)^{2}+x_{2}^{2}+\lambda _{1}(x_{1}^{2}+x_{2}^{2}-1)+\lambda _{2}\left((x_{1}-1)^{2}+x_{2}^{2}-1\right).$

For each constraint:

- Complementary Slackness:

 $\lambda _{i}\geq 0,\quad \lambda _{i}f_{i}(x)=0,\quad {\text{for }}i=1,2.$

- Primal Feasibility:

 $f_{i}(x)\leq 0\quad {\text{for }}i=1,2.$

Step 2: Compute the Gradient of the Lagrangian

Compute the partial derivatives with respect to $x_{1}$ and $x_{2}$:

- Partial Derivative with respect to $x_{1}$:

 ${\frac {\partial L}{\partial x_{1}}}=2(x_{1}-2)+2\lambda _{1}x_{1}+2\lambda _{2}(x_{1}-1).$

- Partial Derivative with respect to $x_{2}$:

 ${\frac {\partial L}{\partial x_{2}}}=2x_{2}+2\lambda _{1}x_{2}+2\lambda _{2}x_{2}.$

Step 3: Stationarity Conditions

Set the gradients to zero:

- Equation (1):

 $2(x_{1}-2)+2\lambda _{1}x_{1}+2\lambda _{2}(x_{1}-1)=0.$

- Equation (2):

 $2x_{2}+2\lambda _{1}x_{2}+2\lambda _{2}x_{2}=0.$

From Equation (2), since $x_{2}(1+\lambda _{1}+\lambda _{2})=0$ and $\lambda _{i}\geq 0$ for $i=1,2$, it follows that:

$x_{2}=0.$

Substitute $x_{2}=0$ into the constraints:

${\begin{aligned}x_{1}^{2}-1&\leq 0\quad \Rightarrow \quad x_{1}\in [-1,1],\\(x_{1}-1)^{2}-1&\leq 0\quad \Rightarrow \quad x_{1}\in [0,2].\end{aligned}}$

Combining both constraints:

$x_{1}\in [0,1].$

Step 4: Solve the problem Using Equation (1)

Substitute $x_{2}=0$ into Equation (1):

$(x_{1}-2)+\lambda _{1}x_{1}+\lambda _{2}(x_{1}-1)=0.$

Assume $\lambda _{1}>0$ (since Constraint 1 is active):

$x_{1}^{2}-1=0\quad \Rightarrow \quad x_{1}=\pm 1.$

But from the feasible range, $x_{1}=1$.

Substitute $x_{1}=1$ into the equation:

$\lambda _{1}=1.$

This is acceptable.

Assume $\lambda _{2}=0$ because Constraint 2 is not active at $x_{1}=1$.

Step 5: Verify Complementary Slackness

- Constraint 1:

 $\lambda _{1}(x_{1}^{2}-1)=1\times (1-1)=0.$

- Constraint 2:

 $\lambda _{2}\left((x_{1}-1)^{2}+x_{2}^{2}-1\right)=0\times (-1)=0.$

Step 6: Verify Primal Feasibility

- Constraint 1:

 $x_{1}^{2}-1=1-1=0\leq 0.$

- Constraint 2:

 $(x_{1}-1)^{2}+x_{2}^{2}-1=-1\leq 0.$

Step 7: Conclusion

- Optimal Solution:

 $x_{1}^{*}=1,\quad x_{2}^{*}=0.$

- Minimum Objective Value:

 $f_{0}^{*}(x)=(1-2)^{2}+0=1.$

Numerical Example 2 (SDP-Based QCQP)

Consider the following Quadratically Constrained Quadratic Programming (QCQP) problem:

${\begin{aligned}{\text{minimize}}\quad &f_{0}(x)=x_{1}^{2}+x_{2}^{2}\\{\text{subject to}}\quad &f_{1}(x)=x_{1}^{2}+x_{2}^{2}-2\leq 0,\\&f_{2}(x)=-x_{1}x_{2}+1\leq 0.\end{aligned}}$ Interpretation:

The objective $f_{0}(x)=x_{1}^{2}+x_{2}^{2}$ is the squared distance from the origin. We seek a point in the feasible region that is as close as possible to the origin. The constraint $f_{1}(x)=x_{1}^{2}+x_{2}^{2}-2\leq 0$ restricts $(x_{1},x_{2})$ to lie inside or on a circle of radius ${\sqrt {2}}$. The constraint $f_{2}(x)=-x_{1}x_{2}+1\leq 0\implies x_{1}x_{2}\geq 1$ defines a hyperbolic region. To satisfy $x_{1}x_{2}\geq 1$, both variables must be sufficiently large in magnitude and have the same sign.

Step 1: Lifting and Reformulation

Introduce the lifted variable:

$x={\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}},\quad X=xx^{T}={\begin{pmatrix}x_{1}^{2}&x_{1}x_{2}\\x_{1}x_{2}&x_{2}^{2}\end{pmatrix}}.$ If $X=xx^{T}$, then $X\succeq 0$ (positive semidefinite) and $X$ is rank-1.

Rewrite the objective and constraints in terms of $X$:

Objective: $x_{1}^{2}+x_{2}^{2}=\langle I,X\rangle$, where $I$ is the 2x2 identity matrix.

Constraint 1: $x_{1}^{2}+x_{2}^{2}-2\leq 0\implies \langle I,X\rangle -2\leq 0.$

Constraint 2: $-x_{1}x_{2}+1\leq 0\implies X_{12}\geq 1.$

Step 2: SDP Relaxation

The original QCQP is non-convex due to the rank-1 condition on $X$. Relax the rank constraint and consider only $X\succeq 0$:

${\begin{aligned}{\text{minimize}}\quad &\langle I,X\rangle \\{\text{subject to}}\quad &\langle I,X\rangle -2\leq 0,\\&X_{12}\geq 1,\\&X\succeq 0.\end{aligned}}$ This is now a Semidefinite Program (SDP), which is convex and can be solved using standard SDP solvers.

Step 3: Solving the SDP and Recovering the Solution

Solving the SDP, we find a feasible solution $X^{*}$ that achieves the minimum:

$X^{*}={\begin{pmatrix}1&1\\1&1\end{pmatrix}}.$ Check that $X^{*}$ is rank-1:

$X^{*}={\begin{pmatrix}1\\1\end{pmatrix}}{\begin{pmatrix}1&1\end{pmatrix}}=x^{*}(x^{*})^{T},$ with $x^{*}=(1,1)$.

Thus, from ${\text{Thus, from }}X^{*},{\text{ we recover the solution }}x^{*}=(1,1){\text{ for the original QCQP.}}$

Check feasibility:

$x_{1}^{2}+x_{2}^{2}=1+1=2\implies f_{1}(x^{*})=0\leq 0.$ $x_{1}x_{2}=1\implies f_{2}(x^{*})=-1+1=0\leq 0.$ All constraints are satisfied.

Step 4: Optimal Value

The optimal objective value is: $f_{0}^{*}(x)=x_{1}^{*2}+x_{2}^{*2}=1+1=2.$

Conclusion

The SDP relaxation not only provides a lower bound but also recovers the global optimum for this particular QCQP. The optimal solution is $(x_{1}^{,}x_{2}^{)}=(1,1)$ with an objective value of $2$.

This example demonstrates how an SDP relaxation can be used effectively to solve a non-convex QCQP and, in some cases, recover the exact optimal solution.