Consider the quadratic program (QP)

$$\begin{array}{ll} \text{minimize} & \frac{1}{2} x^\top P x + q^\top x\\ \text{subject to} & A x = b\\ & x \in \mathbb{R}^n {\geq 0}\end{array}$$

where $P \succ 0$. Let the minimizer be $x^*$.

Without the non-negativity constraint $x \geq 0$, the optimizer $y^*$ is the solution of the KKT system

$$ \left[ \begin{matrix} P & A^\top \\ A & 0\end{matrix} \right] \left( \begin{matrix} x \\ \nu\end{matrix}\right) = \left( \begin{matrix} -q \\ b \end{matrix}\right)$$

Suppose that the inverse of $\left[ \begin{matrix} P & A^\top \\ A & 0\end{matrix} \right]$ exists and is known analytically, so that $y^*$ is known analytically as well.

Now with the non-negativity constraint $x \geq 0$, does $x^*$ have a known analytical expression (as a function of $y^*$)?


Not especially. Even in two dimensions, the nature of the problem is adequately presented. Either $y^* \geq 0$ so $y^*$ is the constrained solution or it is not. If it is, great. If not, on the new boundary imposed by the constraint, the solution can be found by solving a reduced dimensionality problem on each facet. In two dimensions, this means optimizing the quadratic form on the positive $x$-axis and then again on the positive $y$-axis. You may find that the solution is actually at the intersection of several facets, i.e. at the origin in two dimensions.

Representing the combinatorial problem of finding the subset of facets that intersect at the solution is not analytic.

  • $\begingroup$ Thanks for your comment. So not even if we optimize over the unit simplex? $\endgroup$ – user693 Apr 27 '14 at 20:06
  • 1
    $\begingroup$ No. Any version can be transformed to the unit simplex by rescaling the variables. ($Ax = b$ is already linear...) $\endgroup$ – Eric Towers Apr 27 '14 at 20:09
  • $\begingroup$ Ok, thanks. But, just out of curiosity, if $A$ has more than $1$ row how is it possible to rescale the variables to get to $1^\top x = 1$? $\endgroup$ – user693 Apr 27 '14 at 20:11
  • $\begingroup$ The equality you give is not satisfiable... and not the one you would want to satisfy. $\endgroup$ – Eric Towers Apr 27 '14 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.