Quadratic constrained quadratic programming

Introduction

A quadratically constrained quadratic program (QCQP) can be defined as an optimization problem where the objective function and the constraints are quadratic. In particular, the issue involves optimizing (or minimizing) a convex quadratic function of decision variables with quadratic constraints. This class of problems is well suited to finance, engineering, machine learning, and agriculture because it is easier to model the relationship between variables using quadratic functions.

Quadratic programming (QP) is one of the oldest topics in the field of optimization that researchers have studied in the twentieth century. The basic QP, where the objective function is quadratic and constraints are linear, paved the way for other forms, such as QCQPs, which also have quadratic constraints. QCQPs emerged as optimization theory grew to address more realistic, complex problems of non-linear objectives and constraints.

The desire to study QCQPs stems from the fact that they can be used to model practical optimization problems that involve stochasticity in risk, resources, production, and decision-making. For example, in agriculture, using QCQPs can be useful in determining the best crop to grow based on the expected profits and the uncertainties of price changes and unfavorable weather conditions. In finance, the QCQPs are applied in the portfolio's construction to maximize the portfolio's expected returns and the covariance between the assets. It is crucial to comprehend QCQPs and the ways to solve them, such as KKT conditions and SDP relaxations, to solve problems that linear models cannot effectively solve. Analyzing QCQPs is important in order to apply knowledge-based decision-making and enhance the performance and stability of optimization methods in different fields.

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.