1
$\begingroup$

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.

$\endgroup$
  • 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$ – Brian Borchers Oct 12 '17 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 '17 at 1:07
0
$\begingroup$

$$\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, both $a^T \gt 0$, $c^T \gt 0$ 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.

$\endgroup$

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.