Convex optimization problem to QPP

Question

Briefly, have the following problem: \begin{equation} \sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\ s.t.\\\\ A \bar x \leq b \end{equation} where $ F( \bar x ) $ is a linear function, $a_i \gt 0$, $n$ is huge comparing to the size of $x$.

It is possible to write an equal Quadratic Programming problem, such as

$$ \sum_{i=0}^n a_i \ ( G_i )^2 \rightarrow min \\\\ s.t. \\\\ G_i \geq {\bf 0}, \quad i = 0..n \\\\ G_i \geq F_i( \bar x ) \quad i = 0..n \\\\ A \bar x \leq b $$

which can be solved very efficiently with an appropriate numerical method.

Unfortunately in my particular case such conversion doesn't work: it adds a lot of new restrictions, and that appropriate numerical method doesn't converge.

I tried to figure out another equal QPP, which adds fewer new constraints, but nothing came across my mind. Is there another way?

Edit: I need some time to apply both methods to my particular problem. I'll try to report on result as soon as I can.

Answer 1

For what it is worth, I played a bit with the non-constrained optimization of this type and noticed a strange thing. Suppose that you want to minimize $\sum_i a_i\max (F_i(x),0)^2$. Choose any $y$. Introduce auxiliary variables $u_i$ initially set to $1$. Find the minimum of $\sum_i a_i u_i (F_i(x)-\min(0,F_i(y))^2$. Look at the corresponding point $x$ and update $u_i$ as follows: if $F_i(x)>0$, put $u_i=1$, otherwise divide $u_i$ by $4$, say. Then update $y$ to $x$ and repeat. There seems to be no particular reason why that should converge at all. However in practice 20 iterations seem to be enough for $20$ variables and $12000$ random forms. I wonder what happens if you do the same calling the QPP solver to find the restricted minimum at each stage. Note that you can easily recognize the solution once you've found it: as soon as $y$ is close to $x$ and all $u_i$ corresponding to $F_i(x)<0$ are small, we are done. Also, since we are not guaranteed against degeneracies, I added the quadratic form $a(x-y)^2$ where $a$ is changing at every step and is roughly $0.01$ times the trace of the matrix in the current quadratic minimization problem divided by the number of variables.

I guess Rudi's answer may be much better, but my naiive approach is very easy to implement :).

Answer 2

You can use second-order cone optimization (SOCO) for this. SOCO generalizes linear optimization and allows for a linear objective, for constraints that are either the usual linear equations or inequalities, but also for constraints of the form $\|x\|\leq t$, where $x\in\mathbb{R}^n$ and $t\in\mathbb{R}$. Your problem becomes:

$$\min\{ t\mid \|u\|\leq t, \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m, t\in\mathbb{R}\}. $$

The standard SOCO solvers should have no problems with this.

But actually the quadratic problem $$\min\{ u^Tu\mid \sqrt{a_i} F_i(x)\leq u_i\text{ for all }i, Ax\leq b, x\in\mathbb{R}^n, u\in\mathbb{R}^m\}. $$ should also yield to your quadratic solver.

EDIT: so $m$, the number of $F_i(x)$, is huge. Consider the following auxiliary problem: $$\min\{ \sum_{i\in I} a_i F_i(x)^2\mid Ax\leq b, x\in\mathbb{R}^n\} $$ for a subset $I\subseteq \{1,\ldots, m\}$. If the optimal $x^*$ of this problem satisfies $$F_i(x^*)\geq 0 \Longleftrightarrow i\in I$$

then $x^*$ is an optimal solution to the original problem. Such an optimal $I$ can be found by applying the Dantzig-Wolfe method for quadratic optimization (http://pages.cs.wisc.edu/~brecht/cs838docs/wolfe-qp.pdf) to the original quadratic problem. If done with care, you can avoid the explicit enumeration of all the constraints $F_i(x)\leq u_i$ - they can be kept implicit in the quadratic form $\sum_{i\in I} a_i F_i(x)^2$ throughout.