Quadratic constrained quadratic programming

Numerical Example

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