《第十一章chapter11-约束优化问题》由会员分享，可在线阅读，更多相关《第十一章chapter11-约束优化问题（71页珍藏版）》请在金锄头文库上搜索。
1、Chapter XI: Theory of Constrained Optimization Lingfeng NIU Research Center on Fictitious Economy that is, A(x) = E i I|ci(x) = 0. At a feasible point x, the inequality constraint i I is said to be active if ci(x) = 0 and inactive if the strict inequality ci (x) 0 is satisfi ed. Lingfeng NIU, FEDSCh
2、apter XI7/40 Example - A Single Equality Constraint minx1+ x2s.t. x2 1+ x 2 2 2 = 0. Lingfeng NIU, FEDSChapter XI8/40 Example - A Single Equality Constraint minx1+ x2s.t. x2 1+ x 2 2 2 = 0. Lingfeng NIU, FEDSChapter XI8/40 Example - A Single Equality Constraint The only way that a d satisfying c1(x)
3、Td = 0 and f (x)Td 0 for each i I A(x). Satisfaction of the strict complementary property usually makes it easier for algorithms to determine the active set A(x) and converge rapidly to the solution x. For a given problem (1) and solution point x, there may be many vectors for which the conditions (
4、5) are satisfi ed. When the LICQ holds, however, the optimal is unique. Lingfeng NIU, FEDSChapter XI21/40 Strict Complementarity Given a local solution xof (1) and a vector satisfying (5), we say that the strict complementarity condition holds if exactly one of i and ci(x) is zero for each index i I
5、. In other words, we have that i 0 for each i I A(x). Satisfaction of the strict complementary property usually makes it easier for algorithms to determine the active set A(x) and converge rapidly to the solution x. For a given problem (1) and solution point x, there may be many vectors for which th
6、e conditions (5) are satisfi ed. When the LICQ holds, however, the optimal is unique. Lingfeng NIU, FEDSChapter XI21/40 Strict Complementarity Given a local solution xof (1) and a vector satisfying (5), we say that the strict complementarity condition holds if exactly one of i and ci(x) is zero for
7、each index i I. In other words, we have that i 0 for each i I A(x). Satisfaction of the strict complementary property usually makes it easier for algorithms to determine the active set A(x) and converge rapidly to the solution x. For a given problem (1) and solution point x, there may be many vector
8、s for which the conditions (5) are satisfi ed. When the LICQ holds, however, the optimal is unique. Lingfeng NIU, FEDSChapter XI21/40 First-Order Optimality Conditions: Proof Step I : Relating the Tangent Cone and the First-Order Feasible Direction Set Let xbe a feasible point. The following two sta
9、tements are true. (i) T(x) F(x). (ii) If the LICQ condition is satisfi ed at x, then F(x) = T(x). Lingfeng NIU, FEDSChapter XI22/40 First-Order Optimality Conditions: Proof Step II: A Fundamental Necessary Condition If xis a local solution of (1), then we have f (x)Td 0,d T(x).(6) The reverse of thi
10、s result is not necessary true,. That is, we may have f (x)Td 0 for all d T(x), yet xis not a local minimizer. An example is the following problem minx2s.t. x2 x2 1. Lingfeng NIU, FEDSChapter XI23/40 First-Order Optimality Conditions: Proof Step III: Farkas Lemma Let the cone K be defi ned as K = By
11、 + cw|y 0, where B and C are matrices of dimension n m and n p, respectively, and y and w are vector of appropriate dimensions. Given any vector g 0 for some Lagrange multiplier satisfying (5). We say that ciis weakly active if i A(x) and i = 0 for all satisfying (5). Lingfeng NIU, FEDSChapter XI26/
12、40 Outline Introduction Constraint Qualifi cations First-Order Optimality Conditions Second-Order Optimality Conditions Duality Lingfeng NIU, FEDSChapter XI27/40 Second-Order Conditions When the fi rst-order conditions are satisfi ed, a move along any vector w from F(x ) either increases the fi rst-
13、order approximation to the objective function (that is, wTf (x) 0), or else keeps this value the same (that is, wTf (x) = 0). For the directions w F(x) for which wTf (x) = 0, we cannot determine from fi rst derivative information alone whether a move along this direction will increase or decrease th
14、e objective function f . Second-order conditions examine the second derivative terms in the Taylor series expansions of f and ci, to see whether this extra information resolves the issue of increase or decrease in f . Essentially, the second-order conditions concern the curvature of the Lagrangian f
15、unction in the “undecided” directions - the directions w F(x) for which wTf (x) = 0. Lingfeng NIU, FEDSChapter XI28/40 Second-Order Conditions When the fi rst-order conditions are satisfi ed, a move along any vector w from F(x ) either increases the fi rst-order approximation to the objective functi
16、on (that is, wTf (x) 0), or else keeps this value the same (that is, wTf (x) = 0). For the directions w F(x) for which wTf (x) = 0, we cannot determine from fi rst derivative information alone whether a move along this direction will increase or decrease the objective function f . Second-order conditions examine the second derivative terms in the
