most recent 30 from http://mathoverflow.net 2013-05-19T01:33:12Z http://mathoverflow.net/feeds/user/29762 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115751/convex-optimization-problem-to-qpp Artem Pyanykh 2012-12-07T21:57:16Z 2012-12-09T18:11:27Z

<p>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$.</p> <p>It is possible to write an equal Quadratic Programming problem, such as</p> <p>$$ \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 $$</p> <p>which can be solved very efficiently with an appropriate numerical method.</p> <p>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. </p> <p>I tried to figure out another equal QPP, which adds fewer new constraints, but nothing came across my mind. Is there another way?</p> <p><strong>Edit</strong>: I need some time to apply both methods to my particular problem. I'll try to report on result as soon as I can.</p>

http://mathoverflow.net/questions/115751/convex-optimization-problem-to-qpp Artem Pyanykh 2012-12-08T16:38:26Z 2012-12-08T16:38:26Z

@fedja all $a_i$ is positive; n can be huge comparing to size of vector $\hat x$, e.g. size($x$) = s, then n is around $c p^s$, where c p is some positive constants.

http://mathoverflow.net/questions/115751/convex-optimization-problem-to-qpp Artem Pyanykh 2012-12-08T14:08:40Z 2012-12-08T14:08:40Z

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