x 2 y → max,such that x 2 + 4 x y ≤ 1 , x ≥ 0 and y ≥ 0.I think I need to use the KKT conditions here. I did however not yet succeed in solving it, so could someone please give me an example of how this should be done? And should I include the constraints x ≥ 0 and y ≥ 0 into the Lagrangian function?

Question

x    2    y  → max,such that       x    2    +  4  x  y  ≤  1  ,  x  ≥  0 and   y  ≥  0.I think I need to use the KKT conditions here. I did however not yet succeed in solving it, so could someone please give me an example of how this should be done? And should I include the constraints   x  ≥  0 and   y  ≥  0 into the Lagrangian function?

sleuteleni7 · Accepted Answer

The KKT conditions in this case for   x  ,  y that are feasible   x  ≥  0  ,  y  ≥  0  ,      x    2    +  4  x  y  ≤  1 is that   ∃  α  ,  β  ,  γ  ≥  0 (feasible dual variables for the constraints in the last parens in respective order) such that1. Stationary:   2  x  y  =  −  α  +  γ  (  2  x  +  4  y  ),       x    2    =  −  β  +  γ      x    2  , and2. Complementary slackness:   α  x  =  β  y  =  γ  (      x    2    +  4  x  y  −  1  )  =  0However, the problem is not convex therefore KKT conditions are not sufficient. In particular, the eigenvalues of the hessian of your objective are   y  ±      4          x      2        +          y      2       so that one of them is always positive (so not concave for a maximization problem) and also one is negative whenever   x  &amp;gt;  0 which is certainly feasible (so it&#039;s not even definite in either direction).But they are necessary. So you can guess which constraints are active or not and go through all permutations of this to find all KKT-satisfying points. For example, guess that the nonnegativity constraints are slack (  α  =  β  =  0) and that the other constraint is tight (      x    2    +  4  x  y  =  1). Then plugging this into the KKT conditions we get three equations:  2  x  y  =  γ  (  2  x  +  4  y  )  (  1  −  γ  )      x    2    =  0      x    2    +  4  x  y  =  1Which solve for   x  =  1      /        3   and   y  =  1      /        12   and give objective value   1      /        108  . (Hint: this is optimal.)

x 2 </msup> y → max, such that x 2 </

Answered question

Answer & Explanation

New Questions in High school geometry