I am facing the following problem: $$\begin{equation*} \begin{aligned} & \underset{z}{\text{minimize}} & & \textbf{z}^T \textbf{Q} \textbf{z} + \textbf{b}^T \textbf{z}\\ & \text{subject to} && \textbf{Az } \leq \textbf{d} \end{aligned} \end{equation*} $$

where $\textbf{Q}\geq 0$, this is, positive semidefinite. The dimension of vector $\textbf{z}$ is $3$ and the constraint matrix $\textbf{A}$ has $8$ rows.

The Lagrangian would look like:

$$L(\textbf{z},\lambda) = \textbf{z}^T \textbf{Q} \textbf{z} + \textbf{b}^T \textbf{z} + \lambda^T(\textbf{Az } - \textbf{d}) $$

Replacing with the corresponding values I would get:

$$L (x_1, x_2, x_3, \lambda) = x_1^2 +x_2^2 + (1-|h_1|)x_1 + (1-|h_2|)x_2 + \lambda_1(-x_1+x_3 - h_1) + \lambda_2(-x_1 -x_3 + h_1) + \lambda_3(-x_2+x_3 - h_2) + \lambda_4(-x_2-x_3 + h_2) - \lambda_5 x_1 + \lambda_6 x_1 - \lambda_7 x_2 + \lambda_8 x_2$$

I must note that $h_1$ and $h_2$ are constants.

  • $\begingroup$ The first thing that comes to my mind is obtaining the dual problem but that implies the use of the pseudo-inverse and I do not know if it is possible to avoid it. $\endgroup$ – m33n Apr 27 '17 at 18:10
  • $\begingroup$ I know no dual that employs the pseudo inverse. Why don't start with the lagrangian? $\endgroup$ – user251257 Apr 27 '17 at 18:12
  • $\begingroup$ Mmm... Can you be more precise? $\endgroup$ – m33n Apr 27 '17 at 18:16
  • 1
    $\begingroup$ well you have the other equations... also for you example you can compute the pseudo inverse pretty easily. But it won't help much. In general the pseudo inverse is pretty useless when inequality constraints are involved. $\endgroup$ – user251257 Apr 27 '17 at 18:58
  • 1
    $\begingroup$ You are certainly not "required" to use the inverse of Q, as you claim above. One simply needs to find solutions to the KKT equations that present themselves---and with a singular Q, it means there are likely multiple solutions. Any technique you want to use to obtain those solutions is fine. $\endgroup$ – Michael Grant Apr 30 '17 at 19:20

Your Answer

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

Browse other questions tagged or ask your own question.