I have the quadratic program $$\max\quad \mu^Tx+r_fx_0-\gamma \sum\limits_{i=1}^n |x_i-y_i|-\frac{\lambda}{2}x^TVx$$ $$\text{s.t. }\quad \mathbb{1}^Tx+x_0=1$$ where $\mu$, $r_f$, $\gamma$, $\lambda$, and all $y_i$ are known constants and $V$ is positive definite symmetric. I need to reformulate the problem into the standard form $$\min \quad f^Tx+\frac{1}{2}x^THx$$ $$\text{s.t.} \quad Ax \leq b, \;\;A_{eq}x=b_{eq}, \;\;l\leq x \leq u$$ I've tried to negate the objective function and make a few substitutions but I can't seem to identify $H$, $f$, $A_{eq}$, $b_{eq}$, $A$, and $b$. Can someone help?


A common trick is to introduce variables $t_i$ that satisfy $|x_i - y_i| \leq t_i$. In other words, \begin{equation} \tag{$\spadesuit$} t_i \geq x_i - y_i \quad \text{and} \quad t_i \geq -(x_i - y_i). \end{equation} You can replace each term $|x_i - y_i|$ in the objective function with $t_i$, and add the constraints $(\spadesuit)$ to your list of constraints. The resulting quadratic program is close to being in the standard form you gave.

The vector of optimization variables is now $\begin{bmatrix} x \\ t \end{bmatrix}$. To get closer to the standard form, let \begin{equation} A = \begin{bmatrix} I & -I \\ -I & -I \end{bmatrix}, \end{equation} where $I$ is the identity matrix, and let \begin{equation} b = \begin{bmatrix} y \\ -y \end{bmatrix}. \end{equation} The constraint $Ax \leq b$ is equivalent to \begin{equation} x - t \leq y \quad \text{and } -x - t \leq -y. \end{equation} So the inequality constraints have been expressed in the standard form. The equality constraints can be handled in a similar way.

| cite | improve this answer | |
  • $\begingroup$ I've seen this trick in linear programming for minimizing the $l_1$ norm. The problem is I need the exact standard form given above so it can be put into a preexisting solver. $\endgroup$ – Wintermute Nov 29 '14 at 22:38
  • $\begingroup$ @mtiano Ok, I just gave some more details about that. $\endgroup$ – littleO Nov 29 '14 at 23:12

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.