Karush–Kuhn–Tucker (KKT) conditions
Authors: Housam Binous and Ahmed Bellagi
Karush–Kuhn–Tucker (KKT) conditions
Authors: Housam Binous and Ahmed Bellagi
Authors: Housam Binous and Ahmed Bellagi
We propose to solve the following optimization problem using the KKT conditions: Min -x^3+x y+2 s.t. x^2+y = 1; x^3-y^3 = 1; x-1/y ≤ 1; x+2 y ≤ 3;
We form the Lagrangian function: ℒ(x,μ,λ) = f(x) + g(x) + h(x)
f(x) is the objective, g(x) are the inequality constraint functions and ℎ(x) are the equality constraint functions.
μ and λ are called KKT multipliers.
Then we set the partial derivatives with respect to {x,y} equal to zero.
T
μ
T
λ
f(x) is the objective, g(x) are the inequality constraint functions and ℎ(x) are the equality constraint functions.
μ and λ are called KKT multipliers.
Then we set the partial derivatives with respect to {x,y} equal to zero.
In[]:=
F[x_,y_,μ_,λ_]:=Outer[D,{-x^3+xy+2},{x,y}]+μ1Outer[D,{x-1/y-1},{x,y}]+μ2Outer[D,{x+2y-3},{x,y}]+λ1Outer[D,{x^2+y-1},{x,y}]+λ2Outer[D,{x^3-y^3-1},{x,y}]
In[]:=
F[x,y,μ,λ]
Out[]=
-3+y+2xλ1+3λ2+μ1+μ2,x+λ1-3λ2++2μ2
2
x
2
x
2
y
μ1
2
y
First case : we set μ1 = μ2 = 0 and find two potential solutions f=1 or f=9.59997
We retain the one that provides f =1 , which is obtained for x=1 and y=0
First case : we set μ1 = μ2 = 0 and find two potential solutions f=1 or f=9.59997
We retain the one that provides f =1 , which is obtained for x=1 and y=0
In[]:=
μ1=0;μ2=0;
In[]:=
sol1=Solve[{-3+y+2xλ1+3λ2+μ20,x+λ1-3λ2+2μ20,x^2+y-10,x^3-y^3-10},{x,y,λ1,λ2},Reals]//N
2
x
2
x
2
y
Out[]=
{{x1.,y0.,λ1-1.,λ21.66667},{x-1.66714,y-1.77935,λ1-4.71453,λ2-0.67188}}
In[]:=
-x^3+xy+2/.sol1
Out[]=
{1.,9.59997}
Second case : we set g1 = g2 = 0. This case does not yield any solution.
In[]:=
μ1=.;μ2=.;
In[]:=
sol2=Solve-3+y+2xλ1+3λ2+μ1+μ20,x+λ1-3λ2-μ1+2μ20,x^2+y-10,x^3-y^3-10,x-1y1,x+2y3,{x,y,λ1,λ2,μ1,μ2},Reals
2
x
2
x
2
y
Out[]=
{}
Third case : we set g2 = 0 and μ1 = 0. This case does not yield any solution.
In[]:=
μ1=0;
In[]:=
sol3=Solve-3+y+2xλ1+3λ2+μ1+μ20,x+λ1-3λ2++2μ20,x^2+y-10,x^3-y^3-10,x+2y3,{x,y,λ1,λ2,μ2},Reals
2
x
2
x
2
y
μ1
2
y
Out[]=
{}
Fourth case : we set g1 = 0 and μ2 = 0. This case does not yield any solution.
In[]:=
μ2=0;μ1=.
In[]:=
sol4=Solve-3+y+2xλ1+3λ2+μ1+μ20,x+λ1-3λ2++2μ20,x^2+y-10,x^3-y^3-10,x-1y1,{x,y,λ1,λ2,μ1},Reals
2
x
2
x
2
y
μ1
2
y
Out[]=
{}
We find x=1 and y=0 when we call NMinimize (using a numerical technique).
This result confirms what was found previously using the KKT conditions
This result confirms what was found previously using the KKT conditions
In[]:=
NMinimize[{-x^3+xy+2,x^2+y1,x^3-y^31,x-1/y≤1,x+2y≤3},{x,y},MaxIterations10000]//Chop
Out[]=
{1.,{x1.,y0}}