# Reformulate a strictly convex QP problem containing absolute value term

Can the following strictly convex optimization problem be reformulated into a standard form that is also a strictly convex problem?

\begin{align} &\text{Minimize }\frac{1}{2} x^T Q x + a^T x + c^T|x| \\ &\text{subject to } Gx \leq b \end{align} where $$Q$$ is positive definite matrix, $$c^T \gt 0$$ and the rest are vectors (assume standard QP notation).

Standard form is \begin{align} &\text{Minimize }\frac{1}{2} x^T A x + b^Tx \\ &\text{subject to } Hx \leq d \end{align} where I am hoping $$A$$ is positive definite.

Background

I'm expecting the standard form to also have a positive definite matrix in the quadratic term (and maybe this is an incorrect assumption, which would explain why I'm struggling!).

There are many reference that throw out suggestions like "let $$x = y^+ - y^-$$" or "replace $$|x|$$ with $$y$$ and solve over $$x,y$$". I haven't come across any reference that explicitly states the standard-form matrices - but it is fairly easy using such hints to formulate a problem in the standard form that gives the correct solutions.

I am working under the assumption that if the original problem had $$N$$ variables, then the auxiliary variables in the standard formulation mean we need a $$2N \times 2N$$ matrix in the quadratic term that yields an equivalent objective. However- no matter how I approach it I can't find an equivalent quadratic term that is also positive definite. I'm hoping to find such a formulation so I can use Pythons quadprog optimizer (which is the Goldfarb/Idnani dual algorithm)

Goldfarb, D.; Idnani, A., A numerically stable dual method for solving strictly convex quadratic programs, Math. Program. 27, 1-33 (1983). ZBL0537.90081.

• Hint: x^{T}x=|x|^{T}|x|. You can if necessary add and then subtrace a small positive mutiple of $x^{T}x$ from the quadratic objective. – Brian Borchers Oct 12 '17 at 17:39
• Got it! I had been focused on adding/subtracting terms like $x^T \operatorname{diag}(Q) x^T$ which is overly complicated and intractable. I'll write up the final solution as an answer to my own question when I get the chance. – Zero Oct 13 '17 at 1:07

\begin{align} \text{Minimize}\quad&\frac{1}{2} x^T Q x + a^T x + c^T|x| \\ \text{subject to}\quad&Gx \leq b \end{align} where $$Q$$ is positive definite matrix, $$c^T \gt 0$$ (element-wise) and the rest are vectors (assume standard QP notation).

We begin by reformulating the problem in standard form without the absolute value sign, and we then make a further change to ensure a positive definite quadratic coefficient.

### Step 1.

Let $$y = |x|$$. Our original problem becomes:

\begin{align} \begin{array}{c} \text{Minimize} \\ (x,y) \end{array} \quad &\frac{1}{2} \left[\begin{array}{c} x \\ y \end{array}\right]^T \left[\begin{array}{cc} Q & 0 \\ 0 & 0 \end{array}\right] \left[\begin{array}{c} x \\ y \end{array}\right] + \left[\begin{array}{c} a \\ c \end{array}\right]^T \left[\begin{array}{c} x \\ y \end{array}\right] \\ \\ \text{subject to } \quad &Gx \leq b \\ \\ \text{and } \quad & \left[\begin{array}{cc} I & -I \\ -I & -I \\ \end{array}\right] \left[\begin{array}{c} x \\ y \\ \end{array}\right] \leq \left[\begin{array}{c} 0 \\ 0 \end{array}\right] \end{align}

Although it is outside the scope of the original question, a sketch proof that the extra constraints are sufficient follows:

Letting $$y = |x|$$, our objective becomes $$\frac{1}{2} x^TQx + a^Tx + b^Ty$$, the original contraints still hold and we require $$x_i = y_i$$ if $$x_i \geq 0$$ and $$-x_i = y_i$$ if $$x_i \leq 0$$. We need to write the new constraints in standard form.

If $$x_i \geq 0$$, the constraint $$x_i \leq y_i$$ is equivalent to $$x_i = y_i$$. This is because the optimizer will drive the value of $$y_i$$ as low as possible - drive it all the way to equality. Also note in this case $$-x_i \leq y_i$$ is always true.

If $$x_i \leq 0$$, we similarly have $$-x_i \leq y_i$$ equivalent to $$-x_i = y_i$$ and $$x_i \leq y_i$$ is always true.

Thus, the constraints $$x_i \leq y_i$$ and $$-x_i \leq y_i$$ are sufficient, and can be written in the standard matrix form shown above.

### Step 2.

The quadratic coefficient is clearly singular in the current form. Noting $$\quad x_i^2 = |x_i|^2 = y_i^2$$ we can re-write the quadratic term as \begin{align} \left[\begin{array}{c} x \\ y \end{array}\right]^T \left[\begin{array}{cc} Q - \delta I & 0 \\ 0 & \delta I \end{array}\right] \left[\begin{array}{c} x \\ y \end{array}\right]^T &= x^T Q x - x^T \delta I x + y^T \delta I y \\ &= x^T Q x - \sum_i x_i^2 + \sum_i y_i^2 \\ &= x^T Q x \end{align} as required.