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.


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.

  • 2
    $\begingroup$ 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. $\endgroup$ Oct 12, 2017 at 17:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Zero
    Oct 13, 2017 at 1:07

1 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.

  • $\begingroup$ I imagine delta must be selected to be less than the smallest eigenvalue of Q? $\endgroup$ Feb 20, 2022 at 23:05
  • $\begingroup$ It's an algebraic relationship (not an approximation) so I don't think it matters. I've edited to keep the delta squared term on the second line of step 2 - it was incorrectly dropped. $\endgroup$
    – Zero
    Feb 21, 2022 at 13:23
  • $\begingroup$ oh i just mean like, won't we be missing our goal of a having a strictly pd quadratic coefficient matrix otherwise? $\endgroup$ Feb 21, 2022 at 22:09
  • $\begingroup$ Of course!! face palm And its trickier with numerical implementations, because if you go too small you end up rounded to 'close enough to not-positive-definite'... but you often want to avoid the difficulties of calculating eigenvalues in advance since the solver will re-do similar work anyway. $\endgroup$
    – Zero
    Feb 22, 2022 at 16:04
  • $\begingroup$ in my situation, my matrix was small enough that I can estimate its smallest eigenvalue efficiently, so your answer was still helpful for me :) I just set delta to be half of it $\endgroup$ Feb 22, 2022 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.