[PDF] More on Lagrange multipliers 21-Apr-2015 The numerical

View - Download More on Lagrange multipliers

Previous PDF

Next PDF

More on Lagrange multipliers

CE 377K

April 21, 2015

REVIEW

The standard form for a nonlinear optimization problem is min xf(x) s.t.g1(x)0 g `(x)0 h

1(x) = 0

h m(x) = 0The objective function is to be minimized; all other constraints are of the formor =.From Lagrange to KarushReview

What is a convex set?

What is a convex function?

What are some useful facts about convex sets and functions?

From Lagrange to KarushReview

What is the method of Lagrange multipliers?

From Lagrange to KarushReview

OUTLINE

Interpretation of Lagrange multipliers

Solving the transit frequency setting problem with Lagrange multipliersInequality constraints

Karush-Kuhn-Tucker conditions

From Lagrange to KarushOutline

MORE PERSPECTIVES ON

LAGRANGE MULTIPLIERS

Sensitivity analysis

The numerical value of the Lagrange multiplier is useful insensitivity analysis, and shows how much the objective function would change if the constraint was changed. Assume that a constraint was changed fromh(x) = 0 toh(x) =u, so the optimal solution changes fromxtox(u). The ratio of the dierence betweenf(x(u) andf(x) to the perturbation uis approximatelywhenuis small. df(x)du =This is often called ashadow cost.From Lagrange to KarushMore perspectives on Lagrange multipliers The stationary point of min(x1x2) subject tox21+x22= 1 was x

1=x2== 1=p2

If the right-hand side of the constraint was changed slightly (say, to 1.1), u= 0:1 so the change in the objective function will be approximately

0:1=p2

From Lagrange to KarushMore perspectives on Lagrange multipliers

A geometric interpretation

At a stationary point of the Lagrangian,rL(x;) = 0. This gradient has two parts: the partial derivatives with respect toxand those with respect to. The partial derivatives with respect togive you the original constraints back and ensure the stationary point is feasible. The partial derivatives with respect toxgiverf(x) +Pm i=1irh(x) = 0 In the case of a single equality constraint, this meansrf(x) andrh(x) are parallel (or antiparallel). From Lagrange to KarushMore perspectives on Lagrange multipliers The stationary point of min(x1x2) subject tox21+x22= 1 was x

1=x2== 1=p2

For this function,rf(x) =11andrh(x) =2x1

2x2 p2 p2 From Lagrange to KarushMore perspectives on Lagrange multipliers

A penalty interpretation

The Lagrangian function is the original function, plus some multiple of the left-hand side of each constraint. These multipliers can be thought of as \penalties" for violating the constraint. At the optimal solution,L(x;) =f(x). If the penalty is too low or too high, the optimal solution will violate the constraint. From Lagrange to KarushMore perspectives on Lagrange multipliers

THE TRANSIT

FREQUENCY SETTING

PROBLEM

Here is a \modied" version without explicit upper and lower limits on the number of buses on each route. min nD(n) =X r2Rd rTr2nr s:t:X r2Rn r=NFrom Lagrange to KarushThe transit frequency setting problem

Assume there are 3 routes with this problem data:

Route 1 has demand 1, and the route requires 2 hours to traverse Route 2 has demand 8, and the route requires 1 hour to traverse Route 3 has demand 6, and the route requires 3 hours to traverse Furthermore, there are 6 buses to assign to these routes. From Lagrange to KarushThe transit frequency setting problem

The Lagrangian isL(n;) =P

r2Rd rTr2nr+(P r2RnrN) The stationary point of the Lagrangian occurs when:@L@nr= 0 for all routesr; this means eachnr=qd rTr2@L@ = 0; this meansP r2Rnr=NFrom Lagrange to KarushThe transit frequency setting problem Substituting the rst equations into the second we have X r2Rrd rTr2=N which we can solve for. Using the given data for this problem, the equation simplies to 1p +2p +3p = 6 which is solved when= 1.If the functions and values are not so nice, you can use Newton's method or the bisection method to solve for.From Lagrange to KarushThe transit frequency setting problem Substituting= 1 into each equation, we nd that the optimal solution is n

1= 1,n2= 2, andn3= 3.

The interpretation of the Lagrange multiplier= 1 is that (at the margin), adding one more bus to the eet will reduce total waiting time by approximately one hour if allocated optimally.

The requirementnr=qd

rTr2can also be interpreted in saying that the marginal impact of an additional bus on each route must be equal at the optimal solution. From Lagrange to KarushThe transit frequency setting problem

INEQUALITY

CONSTRAINTS

The theory of Lagrange multipliers dates to the 18th century; techniques for handling inequality constraints are more recent. This theory is generalized in theKarush-Kuhn-Tuckerconditions, which accounts for both inequality and equality constraints. Karush rst came up with this idea in his 1939 MS thesis. Kuhn and Tucker independently came up with the idea in 1951.

From Lagrange to KarushInequality constraints

An equivalent way of phrasing the Lagrange multiplier technique is : At an optimal solutionxto the problem minxf(x) subject tohi(x) = 0 for i2 f1;:::;mg, we have rf(x) +mX i=1 irh(x) = 0 for somei, and furthermorehi(x) = 0 for alli2 f1;:::;mg.

The Karush-Kuhn Tucker conditions are as follows:At an optimal solutionxto the problem minxf(x) subject tohi(x) = 0 for

i2 f1;:::;mgandgj(x)0 forj2 f1;:::;`gwe have rf(x) +mX i=1 irh(x) +`X j=1 jrg(x) = 0 for someiandnonnegativej, and furthermorehi(x) = 0 for alli2 f1;:::;mg,gj(x)0 forj2 f1;:::;`g,andj= 0 for any inactive constraint.

From Lagrange to KarushInequality constraints

Unpacking the KKT conditions:

A multiplierjis introduced for each inequality constraint, just like a iis introduced for each equality.We distinguish between anactiveand aninactiveinequality constraint. The constraintgj(x)0 isactiveifgj(x) = 0 and inactiveifgj(x)<0.The multiplier for eachjmust be nonnegative, and zero for each inactive constraint. The second and third points warrant further explanation.

From Lagrange to KarushInequality constraints

If a constraint is inactive at the optimum solution, it is essentially irrelevant, and changing the right-hand side by a small amount will not aect the optimal solution at all.

Thereforej= 0 for any inactive constraint.

Increasing the right-hand side of the constrantgj(x) canonly improve the optimal valueof the objective function. Sojcannot be negative. (Why is this not true for equality constraints?)

From Lagrange to KarushInequality constraints

A simple example

Minimizef(x) = (x+ 5)2subject tox0.

The optimal solution is clearlyx=5. The inequality constraint is active, so= 0. Hererf(x) = 2(x+ 5) andrg(x) = 1; if we setx=5 and= 0, then rf(x) +rg(x) = 0 so this is (potentially) the optimal solution.

From Lagrange to KarushInequality constraints

A simple example

Minimizef(x) = (x5)2subject tox0.

The optimal solution is nowx= 0. The inequality constraint is active, so 0. Hererf(x) = 2(x5) andrg(x) = 1; if we setx= 0 then rf(x) +rg(x) = 0 is true when= 10. The interpretation: by changing the constraint fromx0 tox1, the objective function can be reduced by approximately 10.

From Lagrange to KarushInequality constraints

quotesdbs_dbs19.pdfusesText_25

[PDF] lagrange multiplier inequality constraint

[PDF] lagrange multiplier quadratic optimization

[PDF] lagrange multipliers pdf

[PDF] lagrangian field theory pdf

[PDF] laman race 2020

[PDF] lambda return value

[PDF] lambda trailing return type

[PDF] lana del rey age 2012

[PDF] lana del rey songs ranked billboard

[PDF] lana del rey the greatest album

[PDF] lancet diet study

[PDF] lancet nutrition

[PDF] lands end trail map pdf

[PDF] landwarnet blackboard learn

[PDF] lane bryant annual bra sale