Quadratic Program Reformulation

Question

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?

Answer 1

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.