![(c) The condition of part (b) holds if any one of the following conditions holds:<br>1. The functions g; are linear.<br>2. (Arrow, Hurwitz, Uzawa [AHU61]) There exists a vector d such that<br>Vg;(x*)'d < 0,<br>V jE A(x*).<br>Hint: Let d satisfy Vg;(x*)'d < 0 for all j E A(x*), and let d, = yd+ (1–<br>y)d. From the mean value theorem, we have for some e E [0, 1]<br>9j(x* + ad,) = 9;(x*)+ aVg;(x* + cad, )'dy<br><a(^Vg;(x* + €ad, )'d + (1 – y)V9; (x* + cad, )'d).<br>For a fixed y, there exists an ā > 0 such that the right-hand side above is<br>nonpositive for a € [0,a). Thus d, e F(x*), for all y and lim,-o d, = d.<br>Hence d e F(x*).<br>3. (Slater [Sla50]) The functions g; are convex and there exists a vector a<br>satisfying<br>9;(T) < 0,<br>Vje A(x*).<br>Hint: Let d = x – x* and use condition 2.<br>4. The gradients Vg,(x*), j E A(x*), are linearly independent. Hint: Let d<br>be such that Vg;(x*)'d = -1 for all j e A(x*) and use condition 2.<br>%3D<br>(d) Consider the two-dimensional problem with two inequality constraints where<br>f(x1, x2) = xı + x2,<br>J -xị + x2<br>4.<br>-xị + x2 if x1 < 0,<br>if xi 2 0,<br>91 (X1, x2) = {<br>if x1 > 0,<br>if x1 < 0.<br>J xi - x2<br>92(X1, 22)<br>X, - X2<br>(0,0) is a local minimum, but each of the conditions 1-4<br>of part (c) is violated and there exists no Lagrange multiplier vector.<br>Show that x*<br>(e) Consider the equality constrained problem minh(x)=0 f(x), and suppose<br>that x* is a local minimum such that Vf(x*) # 0. Repeat part (d) for the<br>case of the equivalent inequality constrained problem<br>min f(x).<br>||h(x)||2<0<br>](https://s3.us-east-1.amazonaws.com/storage.unifolks.com/qimg-008/008_8qzkxp0-oj4btruw.jpeg)
Extracted text: (c) The condition of part (b) holds if any one of the following conditions holds: 1. The functions g; are linear. 2. (Arrow, Hurwitz, Uzawa [AHU61]) There exists a vector d such that Vg;(x*)'d < 0,="" v="" je="" a(x*).="" hint:="" let="" d="" satisfy="" vg;(x*)'d="">< 0="" for="" all="" j="" e="" a(x*),="" and="" let="" d,="yd+" (1–="" y)d.="" from="" the="" mean="" value="" theorem,="" we="" have="" for="" some="" e="" e="" [0,="" 1]="" 9j(x*="" +="" ad,)="9;(x*)+" avg;(x*="" +="" cad,="" )'dy="" 0="" such="" that="" the="" right-hand="" side="" above="" is="" nonpositive="" for="" a="" €="" [0,a).="" thus="" d,="" e="" f(x*),="" for="" all="" y="" and="" lim,-o="" d,="d." hence="" d="" e="" f(x*).="" 3.="" (slater="" [sla50])="" the="" functions="" g;="" are="" convex="" and="" there="" exists="" a="" vector="" a="" satisfying="" 9;(t)="">< 0,="" vje="" a(x*).="" hint:="" let="" d="x" –="" x*="" and="" use="" condition="" 2.="" 4.="" the="" gradients="" vg,(x*),="" j="" e="" a(x*),="" are="" linearly="" independent.="" hint:="" let="" d="" be="" such="" that="" vg;(x*)'d="-1" for="" all="" j="" e="" a(x*)="" and="" use="" condition="" 2.="" %3d="" (d)="" consider="" the="" two-dimensional="" problem="" with="" two="" inequality="" constraints="" where="" f(x1,="" x2)="xı" +="" x2,="" j="" -xị="" +="" x2="" 4.="" -xị="" +="" x2="" if="" x1="">< 0,="" if="" xi="" 2="" 0,="" 91="" (x1,="" x2)="{" if="" x1=""> 0, if x1 < 0.="" j="" xi="" -="" x2="" 92(x1,="" 22)="" x,="" -="" x2="" (0,0)="" is="" a="" local="" minimum,="" but="" each="" of="" the="" conditions="" 1-4="" of="" part="" (c)="" is="" violated="" and="" there="" exists="" no="" lagrange="" multiplier="" vector.="" show="" that="" x*="" (e)="" consider="" the="" equality="" constrained="" problem="" minh(x)="0" f(x),="" and="" suppose="" that="" x*="" is="" a="" local="" minimum="" such="" that="" vf(x*)="" #="" 0.="" repeat="" part="" (d)="" for="" the="" case="" of="" the="" equivalent="" inequality="" constrained="" problem="" min="" f(x).=""><>
![3.3.5 (Constraint Qualifications for Inequality Constraints)<br>The purpose of this exercise is to explore a condition that implies all of the<br>existence results for Lagrange multipliers that we have proved in this section for<br>the case of inequality constraints only. Consider the problem<br>minimize f(æ)<br>subject to g;(x) < 0,<br>j = 1,... ,r.<br>For a feasible x, let F(x) be the set of all feasible directions at x defined by<br>F(x) = {d|d 0, and for some ā > 0, g(x + ad) < 0 for all a E [0,a]}<br>and denote by F(x) the closure of F(x). Let x* be a local minimum. Show that:<br>(a)<br>Vf(x*)'d >0,<br>Vde F(x*).<br>(b) If we have F(x*) = V (x*), where<br>V (a*) = {d|V9;(x*](https://s3.us-east-1.amazonaws.com/storage.unifolks.com/qimg-008/008_bqlkxp0-4zdyeugk.jpeg)
0 such that Vf(x*)+ H;V9; (x*) = 0, H; = 0, V j ¢ A(x*). %3D j=1 Hint: Use part (a) and Farkas' Lemma (Prop. 3.3.13). "/>
Extracted text: 3.3.5 (Constraint Qualifications for Inequality Constraints) The purpose of this exercise is to explore a condition that implies all of the existence results for Lagrange multipliers that we have proved in this section for the case of inequality constraints only. Consider the problem minimize f(æ) subject to g;(x) < 0,="" j="1,..." ,r.="" for="" a="" feasible="" x,="" let="" f(x)="" be="" the="" set="" of="" all="" feasible="" directions="" at="" x="" defined="" by="" f(x)="{d|d" 0,="" and="" for="" some="" ā=""> 0, g(x + ad) < 0="" for="" all="" a="" e="" [0,a]}="" and="" denote="" by="" f(x)="" the="" closure="" of="" f(x).="" let="" x*="" be="" a="" local="" minimum.="" show="" that:="" (a)="" vf(x*)'d="">0, Vde F(x*). (b) If we have F(x*) = V (x*), where V (a*) = {d|V9;(x*")'d < 0,="" v="" j="" €="" a(x*)},="" then="" there="" exists="" a="" lagrange="" multiplier="" vector="" u*=""> 0 such that Vf(x*)+ H;V9; (x*) = 0, H; = 0, V j ¢ A(x*). %3D j=1 Hint: Use part (a) and Farkas' Lemma (Prop. 3.3.13).