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 in

MATLAB: An Introduction with Applications
6th Edition
ISBN:9781119256830
Author:Amos Gilat
Publisher:Amos Gilat
Chapter1: Starting With Matlab
Section: Chapter Questions
Problem 1P
icon
Related questions
Question

part D E

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).
Transcribed Image 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).
(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
<a(^Vg;(x* + €ad, )'d + (1 – y)V9; (x* + cad, )'d).
For a fixed y, there exists an ā > 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).
||h(x)||2<0
Transcribed Image 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 <a(^Vg;(x* + €ad, )'d + (1 – y)V9; (x* + cad, )'d). For a fixed y, there exists an ā > 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). ||h(x)||2<0
Expert Solution
steps

Step by step

Solved in 2 steps with 1 images

Blurred answer
Recommended textbooks for you
MATLAB: An Introduction with Applications
MATLAB: An Introduction with Applications
Statistics
ISBN:
9781119256830
Author:
Amos Gilat
Publisher:
John Wiley & Sons Inc
Probability and Statistics for Engineering and th…
Probability and Statistics for Engineering and th…
Statistics
ISBN:
9781305251809
Author:
Jay L. Devore
Publisher:
Cengage Learning
Statistics for The Behavioral Sciences (MindTap C…
Statistics for The Behavioral Sciences (MindTap C…
Statistics
ISBN:
9781305504912
Author:
Frederick J Gravetter, Larry B. Wallnau
Publisher:
Cengage Learning
Elementary Statistics: Picturing the World (7th E…
Elementary Statistics: Picturing the World (7th E…
Statistics
ISBN:
9780134683416
Author:
Ron Larson, Betsy Farber
Publisher:
PEARSON
The Basic Practice of Statistics
The Basic Practice of Statistics
Statistics
ISBN:
9781319042578
Author:
David S. Moore, William I. Notz, Michael A. Fligner
Publisher:
W. H. Freeman
Introduction to the Practice of Statistics
Introduction to the Practice of Statistics
Statistics
ISBN:
9781319013387
Author:
David S. Moore, George P. McCabe, Bruce A. Craig
Publisher:
W. H. Freeman