Quadratic constrained quadratic programming

Author: Jialiang Wang (jw2697), Jiaxin Zhang (jz2289), Wenke Du (wd275), Yufan Zhu (yz2899), David Berroa (deb336) (ChemE 6800 Fall 2024)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

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 (McCarl,Moskowitz et al,1977).

A Quadratically Constrained Quadratic Program (QCQP) can be defined as an optimization problem where the objective function and the constraints are quadratic. It emerged as optimisation theory grew to address more realistic, complex problems of non-linear objectives and constraints. 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 (Zenios,1993), engineering, machine learning, and agriculture because it is easier to model the relationship between variables using quadratic functions.

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 (Floudas,1995).
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 (Bao & Sahinidis,2011).
Solving quadratically constrained quadratic programming (QCQP) problems^[1]

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 (Zenios,1993).

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.

QP

A QP can be expressed in the standard form:

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{matrix}\text{min} & \left ( \frac{1}{2} \right ) x^TPx+q^Tx+r \\ \text{s.t}. & Gx \preceq h \\ & Ax=b, \end{matrix}}

where $P\in \mathbf {S} _{+}^{n}$ (the set of symmetric positive semidefinite matrices), $G\in \mathbb {R} ^{m\times n}$ , and $A\in \mathbb {R} ^{p\times n}$ . In this case, we minimize a convex quadratic function over a polyhedron.

QCQP

When the inequality constraints are also quadratic, the problem becomes a QCQP. This extends the QP formulation to:

${\begin{matrix}{\text{min}}&\left({\frac {1}{2}}\right)x^{T}P_{0}x+q_{0}^{T}x+r_{0}\\{\text{s.t}}.&\left({\frac {1}{2}}\right)x^{T}P_{i}x+q_{i}^{T}x+r_{i}\leq 0,i=1,\cdots ,m\\&Ax=b,\end{matrix}}$

where $P\in \mathbf {S} _{+}^{n}$ for $i=0,\cdots ,m$ . A QCQP minimizes a convex quadratic function over a feasible region that is defined by the intersection of ellipsoids when $P_{I}\succ 0$ .

Notably, quadratic programs are a special case of QCQP, where $P_{I}=0$ for $i=1,\cdots ,m$ , resulting in affine constraints. Similarly, linear programs (LPs) are a subset of QPs, where $P=0$ in the objective function.

There are two primary relaxation techniques for solving QCQPs:

Semidefinite Programming (SDP): SDP relaxations replace quadratic constraints with semidefinite constraints, providing a convex approximation of the problem. SDP relaxations are particularly effective for certain QCQP classes, such as those with non-positive off-diagonal elements in the data matrices, where they yield exact solutions.
Karush-Kuhn-Tucker(KKT): It builds upon the method of Lagrange multipliers by introducing necessary conditions for optimality that incorporate primal and dual variables.


Name	Brief info
KKT(Karush-Kuhn-Tucker)	KKT is a mathematical optimization method used to solve constrained optimization problems(Ghojogh, Karray et al,2021). The KKT conditions include stationarity, primal feasibility, dual feasibility, and complementary slackness, making it particularly effective for solving problems with nonlinear constraints.
SDP (Semidefinite Programming)	SDP reformulates a QCQP problem into a semidefinite programming relaxation (Freund,2004).This approach provides a tractable way to solve or approximate solutions to non-convex QCQP problems by “lifting” the problem to a higher-dimensional space and applying SDP relaxation. It is widely used in areas where global optimization or approximations to non-convex issues are necessary.

Other relaxations, such as Second-Order Cone Programming (SOCP), are exact for specific problem classes like QCQPs with zero diagonal elements in the data matrices. These relaxations often produce the same objective value as SDP relaxations. Moreover, it has been shown that for a class of random QCQPs, SDP relaxations are exact with high probability if the number of constraints grows at a controlled polynomial rate relative to the number of variables.[2]

For non-convex QCQPs, SDP or SOCP relaxations can still provide exact solutions under specific conditions, such as non-positive off-diagonal elements. Additionally, polynomial-time-checkable sufficient conditions exist for SDP relaxations to exactly solve general QCQPs. Randomized QCQPs often exhibit exact semidefinite relaxations as the number of variables and constraints increases proportionally.

Numerical Example

Example 1: KKT Approach

Considering the following numerical example:

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

Steps:

Formulate the Lagrangian and computed the Gradients
Applied the Stationarity Conditions
Determined the active constraints using complementary slackness

1. 1 Lagrangian Formulation:

The Lagrangian formulation in optimization is a mathematical framework used to solve constrained optimization problems by incorporating both the objective function and the constraints into a single scalar function, called the Lagrangian $L$ This formulation introduces Lagrange multipliers $\lambda _{i}$ for each constraint, enabling the transformation of a constrained optimization problem into an unconstrained one as follows:

$L(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\nu ^{T}(Ax-b)$

where:

$f_{0}(x)$ is the objective function to be minimized, $f_{i}(x)\leq 0$ are the inequality constraints

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 A x=b} represents the equality constraints,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 \quad \lambda_i \geq 0} are the Lagrange multipliers associated with the inequality constraints,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 \quad \nu} is the Lagrange multiplier vector for the equality constraints.

Here the example is:

$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,

the complementary slackness is 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 }
the primal feasibility is 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} .

The results for gradient computation are:

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} : 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\left(x_1-2\right)+2 \lambda_1 x_1+2 \lambda_2\left(x_1-1\right)}
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_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. }

1. 2 Stationarity Condition Application:

1.2.1 Setting the results to zero

$2(x_{1}-2)+2\lambda _{1}x_{1}+2\lambda _{2}(x_{1}-1)=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 2x_2 + 2\lambda_1 x_2 + 2\lambda_2 x_2 = 0 }
- since 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 (1 + \lambda_1 + \lambda_2) = 0} 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 \lambda_i \geq 0} for 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 = 1, 2} , so 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 = 0. }
with constrains $x_{1}\in [0,1].$

1.2.2 Substituting

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 = 0} into the constraints

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

1.2.3 Problem Solving

Substitute 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 = 0} into 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 (x_1 - 2) + \lambda_1 x_1 + \lambda_2 (x_1 - 1) = 0. }
- Assume 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_1 > 0} (since Constraint 1 is active): $x_{1}^{2}-1=0\quad \Rightarrow \quad x_{1}=\pm 1.$
But from the feasible range, 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}
- Substitute 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} into the equation: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_1 = 1. }
  - This is acceptable.
Assume 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_2 = 0} because Constraint 2 is not active at 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} .

1. 3 Verification

1.3.1 Complementary Slackness Verification

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

1.3.2 Primal Feasibility Verification

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 - 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. }

1. 4 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. }

Example 2: SDP- Based QCQP

SDP (Semidefinite Programming) here is a convex optimization technique used by relaxing the original problem into a semidefinite form.

The difference:

For a QCQP problem, the objective is typically:

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 \operatorname{minimize} f_0(x)=\frac{1}{2} x^T P_0 x+q_0^T x+r_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 \text { subject to } f_i(x)=\frac{1}{2} x^T P_i x+q_i^T x+r_i \leq 0, \quad i=1, \ldots, m \text {, }}

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 A x=b }

SDP relaxes the problem by introducing a symmetric matrix $X=x x^T$ and reformulating the problem into the semidefinite cone (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 X \succeq 0} ensures Xis positive semidefinite):

$\operatorname {minimize} \left\langle P_{0},X\right\rangle +q_{0}^{T}x+r_{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 \text { subject to }\left\langle P_i, X\right\rangle+q_i^T x+r_i \leq 0, \quad i=1, \ldots, m, }

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 x x^T, \quad A x=b,}

Considering the following numerical example:

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:

Objective:

$f_{0}(x)=x_{1}^{2}+x_{2}^{2}$ is the squared distance from the origin
A point is found in the feasible region that is as close as possible to the origin.

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_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}}
$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.

Calculation Steps:

Lifting and Reformulation
SDP Relaxation
Soler Application and Recovering
Value Optimization

1. 1 Stationarity Condition Application:

Lifted variable introduction: $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}}.$ $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 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 $X$ is rank-1
Objective and Constraints Rewrite in terms of $X$ $X$ :
- Objective: $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: $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.$

1. 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}}$

1. 2 Solver:

Solving the SDP, the feasible solution $X^{*}$ found 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 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)} .

1. 3 Value Optimization:

${\text{ The orignial QCQP's optimal value is }}x^{*}=(1,1)$

Check feasibility
- $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.}
- Results“”All constraints are satisfied.

The optimal objective value is: 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} = 1 + 1 = 2.}

Comparasion between Two Examples:

Accuracy: Both KKT and SDP methods yielded the exact solution for this convex problem. However, SDP relaxation has the added advantage of handling certain non-convexities under specific conditions, where KKT may fail.
Efficiency: KKT conditions are computationally faster, making them suitable for real-time applications. In contrast, SDP relaxations are resource-intensive, limiting their use in high-dimensional problems.
Scalability: The performance of SDP relaxations deteriorates as the problem size increases due to the reliance on matrix computations.

Application

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 and semidefinite programming (SDP) relaxations 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, DOI:10.1016/j.matcom.2022.10.024

[2] Bao, X., Sahinidis, N. V., & Tawarmalani, M. (2011). Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons (PDF). 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,DOI: 10.1109/TCNS.2015.2401172

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

[5] Freund, R. M. (2004). Introduction to semidefinite programming (SDP) (PDF). Massachusetts Institute of Technology, 8-11.

[6] Ghojogh, B., Ghodsi, A., Karray, F., & Crowley, M. (2021). KKT conditions, first-order and second-order optimization, and distributed optimization: tutorial and survey. arXiv preprint arXiv:2110.01858.

[7] McCarl, B. A., Moskowitz, H., & Furtan, H. (1977). Quadratic programming applications. Omega, 5(1), 43-55.

[8] Zenios, S. A. (Ed.). (1993). Financial optimization. Cambridge university press,doi:https://doi.org/10.1017/CBO9780511522130

External Links


Category: NonLinear Programming (NLP) - Quadratic programming

↑ Cited in the External Link
↑ Cited in the External Link

[1] Cited in the External Link

[2] Cited in the External Link

[1]

[2]