[PDF] Karush-Kuhn-Tucker Conditions Unconstrained Optimization. Equality Constrained Optimization.

View - Download Karush-Kuhn-Tucker Conditions

Previous PDF

Next PDF

Karush-Kuhn-Tucker Conditions

Richard Lusby

Department of Management Engineering

Technical University of Denmark

Today's Topics

(jgUnconstrained Optimization

Equality Constrained Optimization

Equality/Inequality Constrained Optimization

R Lusby (42111) KKT Conditions2/40

Unconstrained Optimization

R Lusby (42111) KKT Conditions3/40

Unconstrained Optimization

(jgProblem minimizef(x) subject to:x2RnFirst Order Necessary Conditions Ifxis a local minimizer off(x) andf(x) is continuously dierentiable in an open neighbourhood ofx, then rf(x) =0 That is,f(x) isstationa ryat xR Lusby (42111) KKT Conditions4/40

Unconstrained Optimization

(jgSecond Order Necessary Conditions Ifxis a local minimizer off(x) andr2f(x) is continuously dierentiable in an open neighbourhood ofx, then rf(x) =0 r

2f(x) is positivesemi denite Second Order Sucient Conditions

Suppose thatr2f(x) is continuously dierentiable in an open neighbourhood ofx. If the following two conditions are satised, thenx is a local minimum off(x). rf(x) =0 r

2f(x) isp ositivedenite R Lusby (42111) KKT Conditions5/40

Equality Constrained Optimization

R Lusby (42111) KKT Conditions6/40

Equality Constrained Optimization

(jgProblem minimizef(x) subject to:hi(x) = 08i= 1;2;:::m x2RnR Lusby (42111) KKT Conditions7/40

Equality Constrained Optimization

Consider the following example

(jgExample minimize2x21+x22 subject to:x1+x2= 1Let us rst consider the unconstrained case

Dierentiate with respect tox1andx2

@f(x1;x2)@x1= 4x1 @f(x1;x2)@x2= 2x2These yield the solutionx1=x2= 0Doesnot satisfy the constraint

R Lusby (42111) KKT Conditions8/40

Equality Constrained Optimization

Example Continued

(jgLet us penalize ourselves for not satisfying the constraint

This gives

L(x1;x2;1) = 2x21+x22+1(1x1x2)This is known as theLagrangian of the p roblem Try to adjust the value1so we use just the right amount of resource

1= 0!get solutionx1=x2= 0;1x1x2= 1

1= 1!get solutionx1=14

;x2=12 ;1x1x2=14

1= 2!get solutionx1=12

;x2= 1;1x1x2=12 1=43 !get solutionx1=13 ;x2=23 ;1x1x2= 0R Lusby (42111) KKT Conditions9/40

Equality Constrained Optimization

Generally Speaking

(jgGiven the following Non-Linear Program

Problem

minimizef(x) subject to:hi(x) = 08i= 1;2;:::m x2RnA solution can be found using theLagrangian

L(x;) =f(x) +mX

i=1 i(0hi(x))R Lusby (42111) KKT Conditions10/40

Equality Constrained Optimization

Why isL(x;) interesting?(jgAssumexminimizes the following minimizef(x) subject to:hi(x) = 08i= 1;2;:::m x2Rn

The following two cases are possible:1The vectorsrh1(x);rh2(x);:::;rhm(x) are linearly dependent2There exists a vectorsuch that

@L(x;)@x1=@L(x;)@x2=@L(x;)@x3=;:::;=@L(x;)@xn= 0 @L(x;)@

1=@L(x;)@

2=@L(x;)@

3=;:::;=@L(x;)@

m= 0

R Lusby (42111) KKT Conditions11/40

Case 1: Example

(jgExample minimizex1+x2+x23 subject to:x1= 1 x

21+x22= 1The minimum is achieved atx1= 1;x2= 0;x3= 0The Lagrangian is:

L(x1;x2;x3;1;2) =x1+x2+x23+1(1x1) +2(1x21x22)Observe that: @L(1;0;0;1;2)@x2= 181;2Observerh1(1;0;0) =h

1 0 0i

andrh2(1;0;0) =h

2 0 0i

R Lusby (42111) KKT Conditions12/40

Case 2: Example

(jgExample minimize2x21+x22 subject to:x1+x2= 1The Lagrangian is: L(x1;x2;1) = 2x21+x22+1(1x1x2)Solve for the following: @L(x1;x2;1@x1) = 4x11= 0 @L(x1;x2;1@x2) = 2x21= 0 @L(x1;x2;1)@= 1x1x2= 0R Lusby (42111) KKT Conditions13/40

Case 2: Example continued

(jgSolving this system of equations yieldsx1=13 ;x2=23 ;1=43

Is this a minimum or a maximum?

R Lusby (42111) KKT Conditions14/40

Graphically

(jgx 1x 2x

1+x2= 11

1

R Lusby (42111) KKT Conditions15/40

Graphically

(jgx 1x 2x

1+x2= 11

1x 1=13x

2=23rf(x) =λrh(x)R Lusby (42111) KKT Conditions15/40

Geometric Interpretation

(jgConsider the gradients offandhat the optimal pointThey must point in the same direction, though they may have

dierent lengths rf(x) =rh(x)Along with feasibility ofx, is the conditionrL(x;) = 0From the example, atx1=13 ;x2=23 ;1=43 rf(x1;x2) =h

4x12x2i

=h 43
43
i rh1(x1;x2) =h 1 1i

R Lusby (42111) KKT Conditions16/40

Geometric Interpretation

(jgrf(x) points in the direction of steepest ascentrf(x) points in the direction of steepest descentIn two dimensions:

I rf(xo) is perpendicular toa level curve of f I rhi(xo) is perpendicular tothe level curve hi(xo) = 0R Lusby (42111) KKT Conditions17/40

Equality, Inequality Constrained Optimization

R Lusby (42111) KKT Conditions18/40

Inequality Constraints

What happens if we now include inequality constraints? (jgGeneral Problem maximizef(x) subject to:gi(x)0( i)8i2I h j(x) = 0( j)8i2JGiven a feasible solutionxo, the set ofbinding constrain tsis: I=fi:gi(xo) = 0gR Lusby (42111) KKT Conditions19/40

The Lagrangian

(jgL(x;;) =f(x) +mX i=1 i(0gi(x)) +kX j=1 j(0hj(x))R Lusby (42111) KKT Conditions20/40

Inequality Constrained Optimization

(jgAssumexmaximizes the following maximizef(x) subject to:gi(x)0( i)8i2I h j(x) = 0( j)8i2J

The following two cases are possible:1rh1(x);:::;rhk(x);rg1(x);:::;rgm(x) are linearly dependent2There exist vectorsandsuch that

rf(x)kX j=1 jrhj(x)mX i=1 irgi(x) = 0 igi(x) = 0

0R Lusby (42111) KKT Conditions21/40

Inequality Constrained Optimization

(jgThese conditions are known as the Karush-Kuhn-Tucker Conditions

We look for candidate solutionsxfor which we can ndandSolve these equations using complementary slackness

At optimality some constraints will be binding and some will be slack

Slack constraints will have a correspondingiof zeroBinding constraints can be treated using the Lagrangian

R Lusby (42111) KKT Conditions22/40

Constraint qualications

(jgKKT constraint qualication rgi(xo) fori2Iare linearly independentSlater constraint qualication g

i(x) fori2Iare convex functionsA non boundary point exists:gi(x)<0 fori2IR Lusby (42111) KKT Conditions23/40

Case 1 Example

(jgThe Problem maximizex subject to:y(1x)3 y0Consider the global max: (x;y) = (1;0)After reformulation, the gradients are rf(x;y) = (1;0) rg1= (3(x1)2;1) rg2= (0;1)Considerrf(x;y)P2 i=1irgi(x;y)R Lusby (42111) KKT Conditions24/40

Graphically

(jgxy y= (1-x)31 1

R Lusby (42111) KKT Conditions25/40

Case 1 Example

(jgWe get: 1 0#quotesdbs_dbs17.pdfusesText_23

[PDF] kawasaki dakar rally bike

[PDF] kegel exercise pdf download

[PDF] keller kiliani test is used for identification of

[PDF] kepner platform bed assembly instructions

[PDF] kering 75007 paris france

[PDF] kering annual report

[PDF] key features of cisco packet tracer

[PDF] key features of the eu mexico trade agreement

[PDF] key performance indicators for finance department

[PDF] key performance indicators ppt

[PDF] keyboard alternatives

[PDF] keyboard alternatives for gaming

[PDF] keyboard symbols shortcuts

[PDF] keynote symptoms definition

[PDF] keynotes and redline symptoms of materia medica pdf