I have an optimization problem of the formMax x 1 + x 2 + x 3 + ⋯ + x n subject to x 0 2 + x 1 2 + x 2 2 + ⋯ + x n 2 + x 12 2 + x 13 2 + x 14 2 + ⋯ + x 1 n 2 + x 23 2 + ⋯ + x 2 n 2 + ⋯ + x n n − 1 2 + x 123 2 + ⋯ + x 12.. n 2 = 1 x 0 + x 1 + x 2 + ⋯ + x n + x 12 + x 13 + x 14 + ⋯ + x 1 n + x 23 + ⋯ + x 2 n + ⋯ + x n n − 1 + x 123 + ⋯ + x 12.. n = 1where x 0 , x 1 , x 2 , … , x 123 … n are unrestricted.What is the upper bound for the cost function ..? Thank you.

Question

I have an optimization problem of the formMax       x    1    +      x    2    +      x    3    +  ⋯  +      x    n  subject to       x    0    2    +      x    1    2    +      x    2    2    +  ⋯  +      x    n    2    +      x          12        2    +      x          13        2    +      x          14        2    +  ⋯  +      x          1      n        2    +      x          23        2    +  ⋯  +      x          2      n        2    +  ⋯  +      x          n      n      −      1        2    +      x          123        2    +  ⋯  +      x          12..      n        2    =  1      x    0    +      x    1    +      x    2    +  ⋯  +      x    n    +      x          12        +      x          13      +      x          14        +  ⋯  +      x          1      n        +      x          23        +  ⋯  +      x          2      n        +  ⋯  +      x          n      n      −      1        +      x          123        +  ⋯  +      x          12..      n        =  1where       x    0    ,      x    1    ,      x    2    ,  …  ,      x          123      …      n       are unrestricted.What is the upper bound for the cost function ..? Thank you.

lilao8x · Accepted Answer

It&#039;s unclear exactly how many total variables you have; call it   m. Let             1        n   be the vector with the first   n components 1, the rest 0; and 1 the vector with all components 1.Then the KKT conditions of your maximization problem are            1        n    +  2  λ  x  +  μ      1    =  0  ,where   λ and   μ are the Lagrange multipliers. Call   v the value of the objective at the critical point. Then, dotting the above by   x gives  v  +  2  λ  +  μ  =  0.Dotting by 1 gives  n  +  2  λ  +  m  μ  =  0  ,and lastly, dotting by             1        n   gives  n  +  2  λ  v  +  n  μ  =  0.Now we are left with a system of equations; they have only one nonlinear term so we can proceed by eliminating variables. Combining the first two equations gives  2  λ  (  m  −  1  )  =  n  −  m  v  ,and the first and second,  2  λ  (  n  −  v  )  =  n  −  n  v  .We can now eliminate   λ:  (  n  −  m  v  )  (  n  −  v  )  =  (  n  −  n  v  )  (  m  −  1  )      n    2    −  n  v  −  n  m  v  +  m      v    2    =  n  (  m  −  1  )  −  n  (  m  −  1  )  v  m      v    2    −  2  n  v  +  n  (  n  −  m  +  1  )  =  0.So  v  =            n      ±              n        (        m        −        1        )        (        m        −        n        )              m    .I&#039;ll leave it to you to check that the positive sign choice indeed gives a maximum.

opepayflarpws · Accepted Answer

A thought: If you stack all variables inside a vector, say   x, it should be straight forward to re-write the above problem as                                            min          x                          b          T                x                            subject to                              x          T                x        =        1                                            c          T                x        =        1        ;            This is not a convex problem. I am not sure about a closed form solution though. KKT conditions should be able to do something.

I have an optimization problem of the form Max x 1 </msub> + x

Answered question

Answer & Explanation

New Questions in High school geometry