Transcription
Lagrange MultipliersConstrained optimizationLyle Ungar, University of Pennsylvania
Constrained optimizationu Whatl l l Probabilities sum to 1Regression weights non-negativeRegression weights less than a constantu Morel constraints might we want for ML?generallyFixed amount of money or time or energy availableLyle H Ungar, University of Pennsylvania2
Lagrange Mulipliers - exampleu Tomaximize f(x, y) subject to g(x, y) kfind:l l The largest value of csuch that the levelcurve f(x, y) cintersects g(x, y) k.This happens when thelines are parallel f ( x0 , y0 ) λ g ( x0 , y0 )www2.essex.edu/ wang/221/Chap14 Sec8.pptLyle H Ungar, University of Pennsylvania
Lagrange Multiplier – the ideaFindminx f(x)s.t.ci(x) 0 j 1 m-- x was (x,y) on the last slide-- c1(x) was g(x)-k on the last slideSetL(x,λ) f(x) λTc(x)At the minimum of L(x,λ)dL/dx df/dx λTdc/dx 0dL/dλ c(x) 0This makes the curves beparallelAs on the last slideLyle H Ungar, University of Pennsylvania4
Lagrange Multiplier – generalizationFindminx f(x)s.t.ci(x) 0 j 1 mSetL(x,λ) f(x) λTc(x)At the minimum of L(x,λ)dL/dx df/dx λTdc/dx 0λici(x) 0 j 1 mλi 0 j 1 mFor each λj, eitherλj 0 (the constraint is not active)orλj 0 (the constraint is active)and thusci(x) 0KKT Karush Kuhn Tucker conditionsLyle H Ungar, University of Pennsylvania5
Lagrange Multiplier Steps1. Start with the primal2. Formulate L3. Find g(λ) minx (L)solve dL/dx 04. Find max g(λ,ν) s.t. λι 0 νι 05. See if the constraints are binding6. Find x*Lyle H Ungar, University of Pennsylvania6
Lagrange Multiplier Steps1. Start with the primal2. Formulate L3. Find g(λ) minx (L)solve dL/dx 0plug back into L4. Find max g(λ,ν) s.t. λι 0try maximizing without constraints5. See if the constraints are bindingit depends on the sign of –bc6. Find x*plug λ* into relation b/aLyle H Ungar, University of Pennsylvania7
Lagrange Multipliers Visuallyfeasibleinfeasiblemin (1/2) x2s.t.2x 5 0a 2, b -5, c 1Lyle H Ungar, University of Pennsylvania8
Solvemaximizef(x,y) x ysubject tox2 y 2 – 1 0Answer: x* (x,y) ?1.2.3.4.5.Formulate L f0(x) λ f1(x)Find minx (L) g(λ)Find max g(λ)See if constraints are bindingFind x*Note that we formulate the problemin terms of minimization!!!Lyle H Ungar, University of Pennsylvania9
The answerwikipediaLyle H Ungar, University of Pennsylvania10
Formulate and solveFind values of a set of k probabilities (p1, p2, pk)that maximize their entropyminimizef(p) ?subject to?Answer: pi ?1.2.3.4.5.Formulate LFind minx (L) g(λ)Find max g(λ)See if constraints are bindingFind x*Lyle H Ungar, University of Pennsylvania11
FormulateFind values of a vector of p non-negative weightsw that minimize Σi(yi-xiw)2minimizef(w) ?subject to?Lyle H Ungar, University of Pennsylvania12
Lagrange Multiplier Steps 1. Start with the primal 2. Formulate L 3. Find g(λ) min x (L) solve dL/dx 0 plug back into L 4. Find max g(λ,ν) s.t. λ ι 0 try maximizing without constraints 5. See if the constraints are binding it depends on the sign of -bc 6. Find x* plug λ* into relation b/a
