Convex optimization problem to quadratic programming problemBriefly, have the following problem: ∑ i = 0 n a i ( m a x [ F i ( x ¯ ) , 0 ] ) 2 → m i n , s . t . A x ¯ ≤ bwhere F ( 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 ∑ i = 0 n a i ( G i ) 2 → m i n s . t . G i ≥ 0 , i = 0.. n G i ≥ F i ( x ¯ ) i = 0.. n A x ¯ ≤ bwhich 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?

Question

Convex optimization problem to quadratic programming problemBriefly, have the following problem:      ∑          i      =      0        n        a    i       (  m  a  x  [      F    i    (            x      ¯        )  ,  0  ]      )    2    →  m  i  n  ,      s  .  t  .      A            x      ¯        ≤  bwhere   F  (            x      ¯        ) is a linear function,       a    i    &amp;gt;  0, n is huge comparing to the size of x.It is possible to write an equal Quadratic Programming problem, such as      ∑          i      =      0        n        a    i       (      G    i        )    2    →  m  i  n      s  .  t  .          G    i    ≥      0    ,    i  =  0..  n          G    i    ≥      F    i    (            x      ¯        )    i  =  0..  n      A            x      ¯        ≤  bwhich can be solved very efficiently with an appropriate numerical method.Unfortunately in my particular case such conversion doesn&#039;t work: it adds a lot of new restrictions, and that appropriate numerical method doesn&#039;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?

Cavalascamq · Accepted Answer

Step 1This is not really an answer. I just want to say that your optimization problem can be converted into a linear programming problem:  min  F  (            x      ¯        ) subject to   A            x      ¯        ≤  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  .Step 2Reason: If   F  (      x    0    )  =  m  &amp;lt;  0, then   max  (  F  (      x    0    )  ,  0      )    2    =  max  (  m  ,  0      )    2    =  0, which is the least possible value of   max  (  F  (            x      ¯        )  ,  0      )    2   over the whole space. Hence x0 is a feasible and global minimizer.If   F  (      x    0    )  =  m  ≥  0, then   F  (            x      ¯        )  ≥  F  (      x    0    )  ≥  0 for every             x      ¯        ∈  D  =  {            x      ¯        :  A            x      ¯        ≤  b  }. Hence   max  (  F  (            x      ¯        )  ,  0  )  =  F  (            x      ¯        )  ≥  0 for every             x      ¯        ∈  D. Therefore      min                            x          ¯                    ∈      D        max  (  F  (            x      ¯        )  ,  0      )    2    =      min                            x          ¯                    ∈      D        F  (            x      ¯            )    2    =            (              min                                            x              ¯                                ∈          D                    F      (                        x          ¯                    )      )        2    =      m    2    =  max  (  m  ,  0      )    2    .

Briefly, have the following problem: sum_{i=0}^{n}a_i(max[F_i(overlinex),0])^2 rightarrow min, s.t. A overlinex <= b

Answered question

Answer & Explanation

New Questions in Algebra I