Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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?

share|improve this question
    
If you are talking about $\min[\max(F( \bar x), 0)]^2$ where $\bar{x}$ is unconstrained, you don't need any software to do it: as $F$ is linear, the answer is zero, and global minimum is attained at $\bar{x}=0$. If there are additional constraints, you may try to specify them in your question. –  user1551 Dec 7 '12 at 22:27
    
@user1551 there are standart linear constraints. I edited the question. –  Artem Pyanykh Dec 7 '12 at 22:47
add comment

1 Answer

This is not really an answer. I just want to say that your optimization problem can be converted into a linear programming problem:

$\min F(\bar{x})$ subject to $A\bar{x}\le b$.

If the minimum found is $m$ and the minimizer is $x_0$, then the minimum for your original problem is $\max(m,0)^2$ and the minimizer is $x_0$.

Reason: If $F(x_0)=m<0$, then $\max(F(x_0), 0)^2=\max(m, 0)^2=0$, which is the least possible value of $\max(F(\bar{x}), 0)^2$ over the whole space. Hence $x_0$ is a feasible and global minimizer.

If $F(x_0)=m\ge0$, then $F(\bar{x})\ge F(x_0)\ge0$ for every $\bar{x}\in D=\{\bar{x}: A\bar{x}\le b\}$. Hence $\max(F(\bar{x}), 0) = F(\bar{x})\ge0$ for every $\bar{x}\in D$. Therefore $$\min_{\bar{x}\in D} \max(F(\bar{x}), 0)^2 = \min_{\bar{x}\in D} F(\bar{x})^2 = \left(\min_{\bar{x}\in D} F(\bar{x})\right)^2 = m^2 = \max(m,0)^2.$$

share|improve this answer
    
Yes, that's right. I apologize for being not enough specific. Please, see the edited question. –  Artem Pyanykh Dec 8 '12 at 14:14
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.