Transcription
Chapter 16Kuhn Tucker ConditionsJosef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 1 / 22
Constraint OptimizationFind the maximum of functionf ( x, y)subject tog( x, y) c,x, y 0Example:Find the maxima off ( x, y) ( x 5)2 (y 5)2subject tox2 y 9,Josef Leydold – Mathematical Methods – WS 2021/22x, y 016 – Kuhn Tucker Conditions – 2 / 22
Graphical SolutionFor the case of two variables we can find a solution graphically.1. Draw the constraint g( x, y) c in the xy-plain (feasible region).2. Draw appropriate contour lines of objective function f ( x, y).3. Investigate which contour lines of the objective function intersectwith the feasible region.Estimate the (approximate) location of the maxima.Josef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 3 / 22
Example – Graphical Solution98765maximum in (2.2, 4.3)4321123456789Maximum of f ( x, y) ( x 5)2 (y 5)2subject to g( x, y) x2 y 9,Josef Leydold – Mathematical Methods – WS 2021/22x, y 0.16 – Kuhn Tucker Conditions – 4 / 22
Example – Graphical Solution987654maximum in (1, 1)321123456789Maximum of f ( x, y) ( x 1)2 (y 1)2subject to g( x, y) x2 y 9,Josef Leydold – Mathematical Methods – WS 2021/22x, y 0.16 – Kuhn Tucker Conditions – 5 / 22
Constraint OptimizationCompute the maximum of functionf ( x1 , . . . , x n )subject tog1 ( x 1 , . . . , x n ) c 1.gk ( x1 , . . . , x n ) c kx1 , . . . , x n 0(non-negativity constraint)Optimization problem:max f (x)subject toJosef Leydold – Mathematical Methods – WS 2021/22g(x) candx 0.16 – Kuhn Tucker Conditions – 6 / 22
Non-Negativity ConstraintUnivariate function f with non-negativity constraint.We find for the maximum x of f :I x is an interior point of the feasible region:x 0 and f 0 ( x ) 0; orI x is a boundary point of the feasible region:x 0 and f 0 ( x ) 0.Summary:f 0 ( x ) 0,Josef Leydold – Mathematical Methods – WS 2021/22x 0andx f 0 (x ) 016 – Kuhn Tucker Conditions – 7 / 22
Non-Negativity ConstraintFor the case of a multivariate function f (x) with non-negativityconstraints x j 0, we obtain such a condition for each of the variables:f x j (x ) 0,Josef Leydold – Mathematical Methods – WS 2021/22x j 0andx j f x j (x ) 016 – Kuhn Tucker Conditions – 8 / 22
Slack VariablesMaximizef ( x1 , . . . , x n )subject tog1 ( x 1 , . . . , x n ) s 1 c 1.gk ( x1 , . . . , x n ) s k c kx1 , . . . , x n 0s1 , . . . , s k 0(new non-negativity constraint)Lagrange function:kL̃(x, s, λ) f ( x1 , . . . , xn ) λi (ci gi ( x1 , . . . , xn ) si )i 1Josef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 9 / 22
Slack VariableskL̃(x, s, λ) f ( x1 , . . . , xn ) λi (ci gi ( x1 , . . . , xn ) si )i 1Apply non-negativity conditions: L̃ L̃ 0, x j 0 and x j 0 x j x j L̃ 0, sisi 0 L̃ 0 λiJosef Leydold – Mathematical Methods – WS 2021/22 L̃and si 0 si(no non-negativity constraint)16 – Kuhn Tucker Conditions – 10 / 22
Elimination of Slack VariablesBecause of L̃ λi the second line is equivalent to siλi 0,Equationssi 0andλi si 0 L̃ ci gi (x) si 0 imply λis i c i gi ( x )and consequently the second line is equivalent toλi 0,ci gi (x) 0 and λi (ci gi (x)) 0 .Therefore there is no need of slack variables any more.Josef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 11 / 22
Elimination of Slack VariablesSo we replace L̃ by Lagrange functionkL(x, λ) f ( x1 , . . . , xn ) λi (ci gi ( x1 , . . . , xn ))i 1Observe that L L̃ x j x jand L c i gi ( x ) λiSo the second line of the condition for a maximum now readsλi 0,Josef Leydold – Mathematical Methods – WS 2021/22 L L 0 and λi 0 λi λi16 – Kuhn Tucker Conditions – 12 / 22
Kuhn-Tucker ConditionskL(x, λ) f ( x1 , . . . , xn ) λi (ci gi ( x1 , . . . , xn ))i 1The Kuhn-Tucker conditions for a (global) maximum are: L 0, x j Lx j 0 and x j 0 x j L L 0, λi 0 and λi 0 λi λiNotice that these Kuhn-Tucker conditions are not sufficient.(Analogous to critical points.)Josef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 13 / 22
Example – Kuhn-Tucker ConditionsFind the maximum off ( x, y) ( x 5)2 (y 5)2subject tox2 y 9,Josef Leydold – Mathematical Methods – WS 2021/22x, y 016 – Kuhn Tucker Conditions – 14 / 22
Example – Kuhn-Tucker ConditionsLagrange function:L( x, y; λ) ( x 5)2 (y 5)2 λ(9 x2 y)Kuhn-Tucker Conditions:( A)( B)(C )L x 2( x 5) 2λxL y 2( y 5) λLλ 9 x2 y 0 0 0(N)x, y, λ 0( I ) x L x x (2( x 5) 2λx ) 0( I I ) y L y y (2( y 5) λ ) 0( I I I ) λ L λ λ (9 x 2 y ) 0Josef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 15 / 22
Example – Kuhn-Tucker ConditionsExpress equations ( I )–( I I I ) as(I)x 0 or 2( x 5) 2λx 0( I I ) y 0 or 2(y 5) λ 0( I I I ) λ 0 or 9 x2 y 0We have to compute all 8 combinations and check whether the resultingsolutions satisfy inequalities ( A), ( B), (C ), and ( N ).I If λ 0 ( I I I, left), then by ( I ) and ( I I ) there exist four solutionsfor ( x, y; λ):(0, 0; 0), (0, 5; 0), (5, 0; 0), and (5, 5; 0).However, none of these points satisfiesall inequalities ( A), ( B), (C ).Hence λ 6 0.Josef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 16 / 22
Example – Kuhn-Tucker ConditionsIf λ 6 0, then ( I I I, right) impliesy 9 x2 .I If λ 6 0 and x 0, then y 9 and because of ( I I, right),λ 8. A contradiction to ( N ).I If λ 6 0 and y 0, then x 3 and because of ( I, right),λ 32 . A contradiction to ( B).I Consequently all three variables must be non-zero.Thus y 9 x2 and λ 2(y 5) 2(4 x2 ).Substituted in ( I ) yields 2( x 5) 4(4 x2 ) x 0 andx 11 12 2.158 y 12 2 11 4.342 λ 11 2 1.317The Kuhn-Tucker conditions are thus satisfied only in point( x, y; λ) 11 1 12 11, 2 ;2Josef Leydold – Mathematical Methods – WS 2021/22 11 2 .16 – Kuhn Tucker Conditions – 17 / 22
Kuhn-Tucker ConditionsUnfortunately the Kuhn-Tucker conditions are not necessary!That is, there exist optimization problems where the maximum does notsatisfy the Kuhn-Tucker conditions.maximumJosef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 18 / 22
Kuhn-Tucker TheoremWe need a tool to determine whether a point is a (global) maximum.The Kuhn-Tucker theorem provides a sufficient condition:(1) Objective function f (x) is differentiable and concave.(2) All functions gi (x) from the constraints are differentiable andconvex.(3) Point x satisfy the Kuhn-Tucker conditions.Then x is a global maximum of f subject to constraints gi ci .The maximum is unique, if function f is strictly concave.Josef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 19 / 22
Example – Kuhn-Tucker TheoremFind the maximum off ( x, y) ( x 5)2 (y 5)2subject tox2 y 9,x, y 0The respective Hessian matrices of f ( x, y) and g( x, y) x2 y areHf 2 00 2Josef Leydold – Mathematical Methods – WS 2021/22!andHg 2 00 0!16 – Kuhn Tucker Conditions – 20 / 22
Example – Kuhn-Tucker TheoremHf 2 00 2!Hg and2 00 0!(1) f is strictly concave.(2) g is convex.(3) Point ( x, y; λ) 11 1 12 11, 2 ;2Kuhn-Tucker conditions. 11 2 satisfy theThus by the Kuhn-Tucker theorem, x (maximum we sought for.Josef Leydold – Mathematical Methods – WS 2021/22 11 1 12 11, 2 )2is the16 – Kuhn Tucker Conditions – 21 / 22
SummaryIIIIIconstraint optimizationgraphical solutionLagrange functionKuhn-Tucker conditionsKuhn-Tucker theoremJosef Leydold – Mathematical Methods – WS 2021/2216 – Kuhn Tucker Conditions – 22 / 22
Kuhn-Tucker Theorem We need a tool to determine whether a point is a (global) maximum. The Kuhn-Tucker theorem provides a sufcient condition: (1) Objective function f (x) is differentiable and concave . (2) All functions g i(x) from the constraints are differentiable and convex . (3) Point x satisfy the Kuhn-Tucker conditions.
