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?

  • $\begingroup$ 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. $\endgroup$ – user1551 Dec 7 '12 at 22:27
  • $\begingroup$ @user1551 there are standart linear constraints. I edited the question. $\endgroup$ – Artem Pyanykh Dec 7 '12 at 22:47

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

  • $\begingroup$ Yes, that's right. I apologize for being not enough specific. Please, see the edited question. $\endgroup$ – Artem Pyanykh Dec 8 '12 at 14:14

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.