约束优化最优性条件ppt课件.ppt

《约束优化最优性条件ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章约束优化最优性条件约束优化问题一阶最优性条件二阶最优性条件约束优化问题约束非线性优化问题：目标函数，约束函数，等式约束优化问题，线性约束优化问题，二次规划…(p)定义1可行点，可行域X约束条件定义2全局（总体）极小点，全局严格极小点定义3局部极小点，局部严格极小点假设是一个局部极小点，如果有使得则我们可将第个约束条件去掉，且仍是去掉第个约束条件所得到的问题的局部极小点。我们称第个约束在处是非积极的。定义4对任何有效约束），称集合是在点的积极集合（或有效集合），是在点的积极约束（或是在点的非积极约束

2、（或非有效约束）。假定已知问题在解处的积极约束我们只需求解如下的等式约束优化问题一阶最优性条件可行域上一个点是否为局部极小点取决于目标函数在该点以及附近其它可行点上的值。可行方向在推导最优性条件起十分重要的作用。下面给出各种可行方向的定义。定义1设如果存在使得则称是在处的可行方向。在处的所有可行方向的集合记为定义2设如果则称是在处的线性化可行方向。在处的所有线性化可行方向的集合记为定义3设如果存在序列则称是在处的序列可行方向。在处的所有序列可行方向的集合记为和使得且有和引理1设如果所有的约束函数都在处可

3、微，则有现在考虑如下只有不等式约束情形：引理2设是问题的局部极小点，如果和都在处可微，则必有证明对任何存在和使得且和由于而且是局部极小点，对充分大的必有从上式可得由于的任意性…引理3（Farkas引理）设是两个非负整数，和是中的向量，则线性方程组和不等式组：（1）无解当且仅当存在实数和非负实数使得（2）Farkas(1902)该引理形式上是线性系统和线性表达式，这两者必有一个且只有一个成立，所以该引理也被称为择一性引理。GeneralFarkasLemma证明留做思考题定理1（Kuhn-Tucker定理

4、）是问题(p)的一个局部极小点，如果则必存在使得(1)(2)(cq1)设该定理由Kuhn和Tucker(1951)给出.与(1)有着密切联系的一个函数是其中由这一函数的思想可追溯到Lagrange(1760-1761),故它常被称为Lagrange函数，被称为Lagrange乘子.定义如果且存在使得(1)-(2)成立，则称是问题(p)的Kuhn-Tucker点(简称K-T点)，称是在处的Lagrange乘子.因为Karush(1939)也类似地考虑了约束优化的最优性条件，所以也有人把上面的定理称为Kar

5、ush-Kuhn-Tucker定理，把K-T点称为K-K-T点.HW:8.6,8.7(P264)HW:8.6,8.7(P264)在K-T中的条件称为互补条件，它要求和至少有一个为零.如果我们则称严格互补条件成立。前面定理中的条件(cq1)被称为约束规范条件。如果约束规范条件(cq1)不成立，则问题(p)的局部极小点不一定是K-T点。Fletcher(1987)给出下面的反例。是全局极小点。所以(cq1)不成立。因而不可能存在和使得成立.上面例子说明约束规范条件的重要性。由于条件(cq1)不容易直接验证，

6、人们给出一些更强的，但容易验证的约束规范条件。所有的都是线性函数.(cq2)根据定义，推论设是问题(p)的一个局部极小点，如果(cq2)成立，则必定是一个K-T点.Mangasarian和Fromowitz(1967)给出的约束规范条件(cq3)1)线性无关；2)集合：非空。引理4更强的约束规范条件(cq4)线性无关。引理5定理2设是问题(p)的一个局部极小点，如果(cq4)成立，则必定是一个K-T点.(cq4)易于检验，上面的定理是一个最常见的也是最有用的关于一阶最优性条件的结果。前面所讨论的都是关于

7、必要性，下面讨论充分性条件。定理3设如果和都在处可微且则是问题(p)的局部严格极小点.证明若不然，则存在使得且有不妨设令易证根据定义矛盾！推论设如果和都在处可微且则是问题(p)的局部严格极小点.在不作任何约束规范的假定下，John(1948)给出如下的必要性条件:定理4设在包含可行域的某一开集上连续可微，如果是问题(p)的局部极小点，则必存在使得证明如果线性相关，则显然定理为真。故假定线性无关。如果是一非空集合，则利用引理4和定理1可知是一K-T点，从而定理成立。下面假定是空集，则必存在使得且有令即证。

8、满足上面定理结论的点称为FritzJohn点。我们称下面的加权的Lagrange函数为FritzJohn函数。显然，FritzJohn点是FritzJohn函数的稳定点。注意到如果则FritzJohn函数可看成是Lagrange函数的倍.但当FritzJohn函数和目标函数无关，这时仅描述了约束函数，不能显示原问题的最优性。二阶最优性条件假定(1)(2)由(1)，(cq1)和Farkas引理知是一K-T点,记是相应的Lagrange乘子。由