[PDF] Lagrange Multipliers and the Karush-Kuhn-Tucker conditions

View - Download Lagrange Multipliers and the Karush-Kuhn-Tucker conditions

Previous PDF

Next PDF

Lagrange Multipliers and the

Karush-Kuhn-Tucker conditions

March 20, 2012

Optimization

Goal: Want to nd the maximum or minimum of a function subject to some constraints.

Formal Statement of Problem:

Given functionsf,g1;:::;gmandh1;:::;hldened on some domain

Rnthe optimization problem has the formmin

x2 f(x)subject togi(x)08iandhj(x) = 08j

In these notes..

We will derive/state sucient and necessary for (local) optimality when there are1no constraints,

2only equality constraints,

3only inequality constraints,

4equality and inequality constraints.

Unconstrained Optimization

Unconstrained Minimization

Assume:

Letf: !Rbe a continuously dierentiable function. Necessary and sucient conditions for a local minimum: x is a local minimum off(x)if and only if1fhas zero gradient atx:r xf(x) =02and the Hessian offatwis positive semi-denite:v t(r2f(x))v0;8v2Rnwhere r

2f(x) =0

B BB@@

2f(x)@x

21@2f(x)@x

1@xn.........

2f(x)@x

n@x1@2f(x)@x 2n1 C CCA

Unconstrained Maximization

Assume:

Letf: !Rbe a continuously dierentiable function. Necessary and sucient conditions for local maximum: x

is a local maximum off(x)if and only if1fhas zero gradient atx:rf(x) =02and the Hessian offatxis negative semi-denite:v

t(r2f(x))v0;8v2Rnwhere r

2f(x) =0

B BB@@

2f(x)@x

21@2f(x)@x

1@xn.........

2f(x)@x

n@x1@2f(x)@x 2n1 C CCA

Constrained Optimization:

Equality Constraints

Tutorial Example

Problem:

This is the constrained optimization problem we want to solvemin x2R2f(x)subject toh(x) = 0where f(x) =x1+x2andh(x) =x21+x222

Tutorial example - Cost function

x 1x 2x

1+x2=2x

1+x2=1x

1+x2= 0x

1+x2= 1x

1+x2= 2iso-contours off(x)f(x) =x1+x2

Tutorial example - Feasible region

x 1x 2x

1+x2=2x

1+x2=1x

1+x2= 0x

1+x2= 1x

1+x2= 2iso-contours off(x)feasible region:h(x) = 0h(x) =x21+x222

Given a pointxFon the constraint surfacex

1x

2feasible pointxF

Given a pointxFon the constraint surfacex

1x

2xFindxs.t.h(xF+x) = 0andf(xF+x)< f(xF)?

Condition to decrease the cost function

x 1x 2r xf(xF)At any point ~xthe direction of steepest descent of the cost functionf(x)is given byrxf(~x).

Condition to decrease the cost function

x 1x

2xHeref(xF+x)< f(xF)To movexfromxsuch thatf(x+x)< f(x)must havex(rxf(x))>0

Condition to remain on the constraint surface

x 1x 2r xh(xF)Normalsto the constraint surfa cea regiven b yrxh(x)

Condition to remain on the constraint surface

x 1x 2r xh(xF)Note the direction of the normal is arbitrary as the constraint be imposed as eitherh(x) = 0orh(x) = 0

Condition to remain on the constraint surface

x 1x

2Direction orthogonal torxh(xF)To move a smallxfromxand remain on the constraint surface

we have to move in a direction orthogonal torxh(x).

To summarize...

IfxFlies on the constraint surface:

settingxorthogonal torxh(xF)ensuresh(xF+x) = 0.

Andf(xF+x)< f(xF)only if

x(rxf(xF))>0

Condition for a local optimum

Consider the case when

r xf(xF) =rxh(xF) whereis a scalar.

When this occurs

Ifxis orthogonal torxh(xF)then

x(rxFf(x)) =xrxh(xF) = 0 Cannot move fromxFtoremain on the constraint surface and decrease (or increase) the cost function This case corresponds to a constrained local optimum!

Condition for a local optimum

Consider the case when

r xf(xF) =rxh(xF) whereis a scalar.

When this occurs

Ifxis orthogonal torxh(xF)then

x(rxFf(x)) =xrxh(xF) = 0 Cannot move fromxFtoremain on the constraint surface and decrease (or increase) the cost function .This case corresponds to a constrained local optimum!

Condition for a local optimum

x 1x

2critical pointcritical point

A constrained local optimum occurs atxwhenrxf(x)and r xh(x)are parallel that isrxf(x) =rxh(x)

From this fact Lagrange Multipliers make sense

Remember our constrained optimization problem ismin

x2R2f(x)subject toh(x) = 0Dene theLagrangianasL(x;) =f(x) +h(x)Thenxa local minimum()there exists a uniques.t.1r

xL(x;) =02r

L(x;) = 03y

t(r2xxL(x;))y08ys.t.rxh(x)ty= 0

From this fact Lagrange Multipliers make sense

Remember our constrained optimization problem ismin x2R2f(x)subject toh(x) = 0Dene theLagrangianasnoteL(x;) =f(x) #L(x;) =f(x) +h(x)Thenxa local minimum()there exists a uniques.t.1r xL(x;) =0 encodesrxf(x) =rxh(x)2r L(x;) = 0 encodes the equality constrainth(x) = 03y t(r2xxL(x;))y08ys.t.rxh(x)ty= 0 "Positive denite Hessian tells us we have a local minimum

The case of multiple equality constraints

The constrained optimization problem ismin

x2R2f(x)subject tohi(x) = 0fori= 1;:::;lConstruct theLagrangian(introduce a multiplier for each constraint)L(x;) =f(x) +Pl

i=1ihi(x) =f(x) +th(x)Thenxa local minimum()there exists a uniques.t.1r xL(x;) =02r

L(x;) =03y

t(r2xxL(x;))y08ys.t.rxh(x)ty= 0

Constrained Optimization:

Inequality Constraints

Tutorial Example - Case 1

Problem:

Consider this constrained optimization problemmin

x2R2f(x)subject tog(x)0where f(x) =x21+x22andg(x) =x21+x221

Tutorial example - Cost function

x 1x

2iso-contours off(x)minimum off(x)f(x) =x21+x22

Tutorial example - Feasible region

x 1x

2feasible region:g(x)0iso-contours off(x)g(x) =x21+x221

How do we recognize ifxFis at a local optimum?x

1x

2How can we recognizexF

is at a local minimum?RememberxFdenotes a feasible point.

Easy in this case

x 1x

2How can we recognizexF

is at a local minimum?Unconstrained minimum off(x)lies within the feasible region.)Necessary and sucient conditions for a constrained local minimum are the same as for an unconstrained local minimum.r xf(xF) =0andrxxf(xF)is positive denite

This Tutorial Example has an inactive constraint

Problem:

Our constrained optimization problemmin

x2R2f(x)subject tog(x)0where f(x) =x21+x22andg(x) =x21+x221Constraint is not active at the local minimum (g(x)<0): Therefore the local minimum is identied by the same conditions as in the unconstrained case.

Tutorial Example - Case 2

Problem:

This is the constrained optimization problem we want to solvemin x2R2f(x)subject tog(x)0where f(x) = (x11:1)2+ (x21:1)2andg(x) =x21+x221

Tutorial example - Cost function

x 1x

2iso-contours off(x)minimum off(x)f(x) = (x11:1)2+ (x21:1)2

Tutorial example - Feasible region

x 1x

2iso-contours off(x)feasible region:g(x)0g(x) =x21+x221

How do we recognize ifxFis at a local optimum?x

1x

2IsxFat a local minimum?RememberxFdenotes a feasible point.

How do we recognize ifxFis at a local optimum?x

1x

2How can we tell ifxF

is at a local minimum?Unconstrained local minimum off(x) lies outside of the feasible region.)the constrained local minimum occurs on the surface of the constraint surface.

How do we recognize ifxFis at a local optimum?x

1x

2How can we tell ifxF

is at a local minimum?Unconstrained local minimum off(x) lies outside of the feasible region.)Eectively have an optimization problem with anequality constraint:g(x) = 0.

Given an equality constraint

x 1x

2A local optimum occurs whenrxf(x)andrxg(x)are parallel:-rxf(x) =rxg(x)

Want a constrained local minimum...

x 1x

27Nota constrained

local minimum as r xf(xF)points in towards the feasible region)Constrained local minimum occurs whenrxf(x)andrxg(x) point in the same direction:r xf(x) =rxg(x)and >0

Want a constrained local minimum...

x 1x

2XIsa constrained

local minimum as r xf(xF)points away from the feasible region)Constrained local minimum occurs whenrxf(x)andrxg(x) point in the same direction:r xf(x) =rxg(x)and >0 Summary of optimization with one inequality constraint

Givenmin

x2R2f(x)subject tog(x)0Ifxcorresponds to a constrained local minimum thenCase 1:

Unconstrained local minimum

occursinthe feasible region.1g(x)<02r xf(x) =03r xxf(x)is a positive semi-denite matrix.Case 2:

Unconstrained local minimum

liesoutsidethe feasible region.1g(x) = 02r xf(x) =rxg(x) with >03y trxxL(x)y0for all yorthogonal torxg(x). Karush-Kuhn-Tucker conditions encode these conditions

Given the optimization problemmin

x2R2f(x)subject tog(x)0Dene theLagrangianasL(x;) =f(x) +g(x)Thenxa local minimum()there exists a uniques.t.1r

xL(x;) =02 03quotesdbs_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