Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
Erm... Why don't you just add the restriction $F(x)\ge 0$ and ask for $\min F(x)$? That is a standard linear programming problem, isn't it? –  fedja Dec 8 '12 at 1:17
    
@fedja Yep! Apologize for being not enougn specific. I edited the question. As for a LPP, I can't find a way to transform this problem to lunear programming problem now. –  Artem Pyanykh Dec 8 '12 at 14:08
    
Adding $F_i(x)\geq 0$ will introduce restrictions on $x$ that are not in your original problem. –  Rudi Pendavingh Dec 8 '12 at 14:28
    
In the new version, are all $a_i$ positive? –  fedja Dec 8 '12 at 15:16
    
Also, how big is $n$? –  fedja Dec 8 '12 at 15:17
show 1 more comment

2 Answers

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.

share|improve this answer
add comment

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 :).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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