3
$\begingroup$

I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP:

(QP) $\min c^T x + x^T Q x$

s.t. $Ax = b$

$l \leqslant x \leqslant u$

Which lagrangean function would be:

$\mathcal{L}(x, \pi, \lambda, \beta) = c^T x + x^T Q x + \pi^T (Ax - b) + \lambda^T (l - x) + \beta^T (x - u)$

Resulting in the following optimization problem:

$\max_{\pi, \lambda \geqslant 0, \beta \geqslant 0} \min_{x} \mathcal{L}(x, \pi, \lambda, \beta)$

With the following optimality conditions:

  1. $\nabla_x \mathcal{L} = c + 2 Q x + A^T \pi - \lambda + \beta = 0$;
  2. $\nabla_{\pi} \mathcal{L} = Ax - b = 0$;
  3. $\nabla_{\lambda} \mathcal{L} = l - x \leqslant 0$;
  4. $\nabla_{\beta} \mathcal{L} = x - u \leqslant 0$;
  5. $x^T \nabla_{x} \mathcal{L} = 0$;
  6. $\pi^T \nabla_{\pi} \mathcal{L} = 0$;
  7. $\lambda^T \nabla_{\lambda} \mathcal{L} = 0$;
  8. $\beta^T \nabla_{\beta} \mathcal{L} = 0$; And
  9. $\lambda \geqslant 0, \beta \geqslant 0$.

Taking the first optimality condition, we have that:

$Q x= - \frac{1}{2} (c + A^T \pi - \lambda + \beta)$

And thus, the QP objective function can be translated into:

$c^T x + x^T Q x = $

$c^T x - \frac{1}{2} x^T (c + A^T \pi - \lambda + \beta) = $

$\frac{1}{2} x^T (c - A^T \pi + \lambda - \beta) = $

$\frac{1}{2} (x^T c - x^T (A^T \pi) + x^T \lambda - x^T \beta) = $ (by means of the complementarity/orthogonality conditions 6, 7, and 8)

$\frac{1}{2} (x^T c - \pi^T b + \lambda^T l - \beta^T u)$

Allowing us to propose the following MILP:

(MILP) $\min \frac{1}{2} (x^T c - \pi^T b + \lambda^T l - \beta^T u)$

$A x = b$

SOS1$(l_i - x_i, \lambda_i)$ $\forall i \in {1, \dots, n}$

SOS1$(x_i - u_i, \beta_i)$ $\forall i \in {1, \dots, n}$

$l \leqslant x \leqslant u$

$\lambda \geqslant 0$

$\beta \geqslant 0$

Where the SOS1 stands for the operator Special Ordered Set Type 1, which imposes new integer variables, making the problem a MILP. The SOS1 is used for forcing the complementarity conditions by stating that

  • $l_i - x_i = 0 \vee \beta_i = 0$; And
  • $x_i - u_i = 0 \vee \lambda_i = 0$

$\forall i \in {1, \dots, n}$.

My question is, can we say that the optimal solution for the given MILP is equals to the optimal solution for the initial QP?

Thanks for the attention, case there is any missing point, please, let me know.

$\endgroup$
6
  • 3
    $\begingroup$ Presuming your derivation is correct, which I haven't checked, the KKT conditions are necessary but not sufficient if the QP is not convex. So if $Q$ is not symmetric positive semidefinite, the solution you obtain to the MILP is not necessarily even a local optimum for the QP, let alone a global optimum; i.e. .the MILP could have some "spurious" solutions. $\endgroup$ Commented Oct 2, 2023 at 13:43
  • 3
  • $\begingroup$ Thank you very much guys! $\endgroup$ Commented Oct 2, 2023 at 14:40
  • $\begingroup$ @MarkL.Stone, I am sorry, could you elaborate on "... is not necessarily even a local optimum ..."? $\endgroup$ Commented Oct 2, 2023 at 15:53
  • 1
    $\begingroup$ If the QP is not convex, a point which solves the MILP, i.e., a KKT point, might correspond to a saddle point, a local or global maximum, or a non-global local minimum. However, I wasn't accounting for a linear objective, for the MILP, as discussed in the link yetanothermathprogrammingconsultant.blogspot.com/2016/06/… provided by @RobPratt . $\endgroup$ Commented Oct 2, 2023 at 17:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.