[PDF] Karush-Kuhn-Tucker Conditions Today: • KKT conditions. • Examples. • Constrained

View - Download Karush-Kuhn-Tucker Conditions

Previous PDF

Next PDF

Karush-Kuhn-Tucker Conditions

Ryan Tibshirani

Convex Optimization 10-725/36-725

1

Last time: duality

Given a minimization problem

minf(x) subject tohi(x)0; i= 1;:::m j(x) = 0; j= 1;:::r we dened the

Lagrangian

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

i=1u ihi(x) +rX j=1v j`j(x) and

Lagrange dual function

g(u;v) = minxL(x;u;v) 2

The subsequentdual p roblemis:

max u;vg(u;v) subject tou0

Important properties:

Dual problem is always convex, i.e.,gis always concave (even if primal problem is not convex) The primal and dual optimal values,f?andg?, always satisfy weak duality:f?g? Slater's condition: for convex primal, if there is anxsuch that h

1(x)<0;:::hm(x)<0and`1(x) = 0;:::`r(x) = 0

then strong duali ty holds: f?=g?. (Can be further rened to strict inequalities over the nonanehi,i= 1;:::m) 3

Outline

Today:

KKT conditions

Examples

Constrained and Lagrange forms

Uniqueness with`1penalties

4

Karush-Kuhn-Tucker conditions

Given general problem

minf(x) subject tohi(x)0; i= 1;:::m j(x) = 0; j= 1;:::r The

Ka rush-Kuhn-Tuckerconditions

o r

KKT conditions

a re:

02@f(x) +mX

i=1u i@hi(x) +rX j=1v j@`j(x)(stationarity) uihi(x) = 0for alli(complementary slackness) hi(x)0; `j(x) = 0for alli;j(primal feasibility) ui0for alli(dual feasibility) 5

Necessity

Letx?andu?;v?be primal and dual solutions with zero duality gap (strong duality holds, e.g., under Slater's condition). Then f(x?) =g(u?;v?) = min xf(x) +mX i=1u ?ihi(x) +rX j=1v ?j`j(x) f(x?) +mX i=1u ?ihi(x?) +rX j=1v ?j`j(x?) f(x?) In other words, all these inequalities are actually equalities 6

Two things to learn from this:

The pointx?minimizesL(x;u?;v?)overx2Rn. Hence the

subdierential ofL(x;u?;v?)must contain0atx=x?|this is exactly the stationa rity condition

We must havePm

i=1u?ihi(x?) = 0, and since each term here is0, this impliesu?ihi(x?) = 0for everyi|this is exactly complementary slackness Primal and dual feasibility hold by virtue of optimality. Therefore: Ifx?andu?;v?are primal and dual solutions, with zero duality

gap, thenx?;u?;v?satisfy the KKT conditions(Note that this statement assumes nothing a priori about convexity

of our problem, i.e., off;hi;`j) 7

Suciency

If there existsx?;u?;v?that satisfy the KKT conditions, then g(u?;v?) =f(x?) +mX i=1u ?ihi(x?) +rX j=1v ?j`j(x?) =f(x?) where the rst equality holds from stationarity, and the second holds from complementary slackness Therefore the duality gap is zero (andx?andu?;v?are primal and dual feasible) sox?andu?;v?are primal and dual optimal. Hence, we've shown: Ifx?andu?;v?satisfy the KKT conditions, thenx?andu?;v? are primal and dual solutions 8

Putting it together

In summary, KKT conditions:

always sucient necessary under strong duality

Putting it together:

For a problem with strong duality (e.g., assume Slater's condi- tion: convex problem and there existsxstrictly satisfying non- ane inequality contraints), x ?andu?;v?are primal and dual solutions

()x?andu?;v?satisfy the KKT conditions(Warning, concerning the stationarity condition: for a dierentiable

functionf, we cannot use@f(x) =frf(x)gunlessfis convex) 9

What's in a name?

Older folks will know these as the KT (Kuhn-Tucker) conditions: First appeared in publication by Kuhn and Tucker in 1951 Later people found out that Karush had the conditions in his unpublished master's thesis of 1939 For unconstrained problems, the KKT conditions are nothing more than the subgradient optimality condition For general problems, the KKT conditions could have been derived entirely from studying optimality via subgradients

02@f(x?) +mX

i=1N fhi0g(x?) +rX j=1N f`j=0g(x?) where recallNC(x)is the normal cone ofCatx 10

Example: quadratic with equality constraints

Consider forQ0,

min x2Rn12 xTQx+cTx subject toAx= 0 E.g., as we will see, this corresponds to Newton step for equality- constrained problemminf(x) subject toAx=b Convex problem, no inequality constraints, so by KKT conditions: xis a solution if and only if Q AT A0 x u =c 0 for someu. Linear system combines stationarity, primal feasibility (complementary slackness and dual feasibility are vacuous) 11

Example: water-lling

Example from B & V page 245: consider problem

min x2RnnX i=1log(i+xi) subject tox0;1Tx= 1 Information theory: think oflog(i+xi)as communication rate of ith channel. KKT conditions:

1=(i+xi)ui+v= 0; i= 1;:::n

u ixi= 0; i= 1;:::n; x0;1Tx= 1; u0

Eliminateu:

1=(i+xi)v; i= 1;:::n

x i(v1=(i+xi)) = 0; i= 1;:::n; x0;1Tx= 1 12 Can argue directly stationarity and complementary slackness imply x i=(

1=viifv <1=i

0ifv1=i= maxf0;1=vig; i= 1;:::n

Still needxto be feasible, i.e.,1Tx= 1, and this gives n X i=1maxf0;1=vig= 1 Univariate equation, piecewise linear in1=vand not hard to solve

This reduced problem is

called w ater-lling (From B & V page 246)2465Dua lity i 1/! x i i Figure5.7Illustrationofwater-fillingalgorithm .The heightofeachpatchis givenby!i.Theregionisfloodedtoalevel1/" whichusesatotal quantity ofwate requaltoone.The heightofthe water( shownshaded) aboveeach patchistheopt imalvalue ofx i x 1 x 2 l ww Figure5.8Twoblocks connectedbyspri ngstoeachother,andthelefta nd rightwalls.Theb lockshavewidthw>0,andcannot pene trateeac hother orthew all s.

5.5.4Mech anicsinterpretationofKKTcondition s

TheKKT conditionsc anbegivenaniceinterpretati oninmech anics(whichind eed, wasone ofLagrang e"spri marymotivations).Weillustrate theideaw ithasim ple example.Thesystemshown infigure5.8 consistso ftwoblocksattachedtoeach other,andtowallsatt heleft andrigh t,bythreespr ings .Thepositionofthe blocksaregiven byx!R 2 ,wherex 1 isthe displacemen tofthe(middleofthe)left block,andx 2 isthedis placement oftherightblock.The leftwallis atp osition0, andthe rightwallis atpositionl. Thepoten tialenergyinthesprings, asafunctionofthebl ockpositions,isgiven by f 0 (x 1 ,xquotesdbs_dbs21.pdfusesText_27

[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