Reformulate a strictly convex QP problem containing absolute value term

Question

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.

Answer 1

$$\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 - \delta \sum_i x_i^2 + \delta \sum_i y_i^2 \\ &= x^T Q x \end{align}$$ as required.