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 unfavourable weather conditions (Bose, Gayme & Low,2015).
• 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 (Karush-Kuhn Tucker) conditions and SDP (Semidefinite Programming) relaxations, to solve problems that linear models cannot effectively solve (Zenios,1993).
  1. The Karush-Kuhn-Tucker (KKT) approach is a mathematical optimisation method used to solve constrained optimisation problems. It builds upon the method of Lagrange multipliers by introducing necessary conditions for optimality that incorporate both primal and dual variables. The KKT conditions include stationarity, primal feasibility, dual feasibility, and complementary slackness, making it particularly effective for solving problems with nonlinear constraints.
  2. The Semidefinite Programming (SDP)-Based Quadratically Constrained Quadratic Programming (QCQP) method reformulates a QCQP problem into a semidefinite programming relaxation. By “lifting” the problem to a higher-dimensional space and applying SDP relaxation, this approach provides a tractable way to solve or approximate solutions to non-convex QCQP problems. It is widely used in areas where global optimization or approximations to non-convex problems are necessary.

In general, analyzing QCQPs is important in order to apply knowledge-based decision-making and enhance the performance and stability of optimization methods in different fields.

Algorithm Discussion

In mathematical optimization, a quadratically constrained quadratic program (QCQP) is a problem where both the objective function and the constraints are quadratic functions. A related but simpler case is the quadratic program (QP), where the objective function is a convex quadratic function, and the constraints are linear.

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 (Agarwal, Singh & EI,2023).

Step 1: Formulate the Lagrangian

The Lagrangian Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} combines the objective function and the constraints, each multiplied by a Lagrange multiplier Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda_i} :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    \lambda_i \geq 0, \quad \lambda_i f_i(x) = 0, \quad \text{for } i = 1, 2.   }

- Primal Feasibility:

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2} :

- Partial Derivative with respect to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} :

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2} :

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    \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):

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    2(x_1 - 2) + 2\lambda_1 x_1 + 2\lambda_2 (x_1 - 1) = 0.   }

- Equation (2):

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    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:

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    (x_1 - 1)^2 + x_2^2 - 1 = -1 \leq 0.   }

Step 7: Conclusion

- Optimal Solution:

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    x_1^* = 1, \quad x_2^* = 0.   }

- Minimum Objective Value:

 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle    f_0^*(x) = (1 - 2)^2 + 0 = 1.   }

Numerical Example 2 (SDP-Based QCQP)

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_1, x_2)} to lie inside or on a circle of radius Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{2}} . The constraint Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_2(x) = -x_1 x_2 + 1 \leq 0 \implies x_1 x_2 \geq 1} defines a hyperbolic region. To satisfy Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \quad X = x x^T = \begin{pmatrix} x_1^2 & x_1 x_2 \\ x_1 x_2 & x_2^2 \end{pmatrix}. } If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X = x x^T} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \succeq 0} (positive semidefinite) and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is rank-1.

Rewrite the objective and constraints in terms of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} :

Objective: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1^2 + x_2^2 = \langle I, X \rangle} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} is the 2x2 identity matrix.

Constraint 1: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1^2 + x_2^2 - 2 \leq 0 \implies \langle I, X \rangle - 2 \leq 0.}

Constraint 2: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} . Relax the rank constraint and consider only Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \succeq 0} :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X^*} that achieves the minimum:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X^* = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}. } Check that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X^*} is rank-1:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1^2 + x_2^2 = 1 + 1 = 2 \implies f_1(x^*) = 0 \leq 0.} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Conclusion

In conclusion, Quadratically Constrained Quadratic Programs (QCQPs) are a significant class of optimization problems extending quadratic programming by incorporating quadratic constraints (Bao,Sahinidis,2011). These problems are essential for modeling complex real-world scenarios where both the objective function and the constraints are quadratic. QCQPs are widely applicable in areas such as agriculture, finance, production planning, and machine learning, where they help optimize decisions by balancing competing factors such as profitability, risk, and resource constraints.

The study and solution of QCQPs are critical due to their ability to capture complex relationships and non-linearities, offering a more realistic representation of many practical problems than simpler linear models. Techniques such as Karush-Kuhn Tucker (KKT) conditions, semidefinite programming (SDP) relaxations, and Reformulation-Linearization Technique (RLT) provide effective tools for solving QCQPs(Elloumi & Lambert,2019), offering both exact and approximate solutions depending on the problem’s structure. These methods allow for efficient handling of the challenges posed by quadratic constraints and non-linearities.

Looking forward, there are several potential areas for improvement in QCQP algorithms. One direction is the development of more efficient relaxation techniques for solving non-convex QCQPs, especially in large-scale problems where computational efficiency becomes critical. Additionally, there is ongoing research into hybrid methods that combine the strengths of different optimization techniques, such as SDP and machine learning, to improve the robustness and speed of solving QCQPs in dynamic environments. As optimization problems become increasingly complex and data-rich, advancements in QCQP algorithms will continue to play a crucial role in making informed, optimal decisions in diverse applications.

Reference

[1] Agarwal, D., Singh, P., & El Sayed, M. A. (2023). The Karush–Kuhn–Tucker (KKT) optimality conditions for fuzzy-valued fractional optimization problems. Mathematics and Computers in Simulation, 205, 861-877.

[2] Bao, X., Sahinidis, N. V., & Tawarmalani, M. (2011). Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Mathematical programming, 129, 129-157.

[3] Bose, S., Gayme, D. F., Chandy, K. M., & Low, S. H. (2015). Quadratically constrained quadratic programs on acyclic graphs with application to power flow. IEEE Transactions on Control of Network Systems, 2(3), 278-287.

[4] Elloumi, S., & Lambert, A. (2019). Global solution of non-convex quadratically constrained quadratic programs. Optimization methods and software, 34(1), 98-114.

[5] Zenios, S. A. (Ed.). (1993). Financial optimization. Cambridge university press.