第4章 最优性条件.doc

《第4章 最优性条件.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第4章最优性条件§4.1最优性条件的预备知识1．极小点的定义无约束问题：(1)定义1（全局极小点）若存在使得则称为问题(1)的全局极小点。如果有则称为问题(1)的严格全局极小点。定义2（局部极小点）设，如果存在使得则称为问题(1)的局部极小点。如果有则称为问题(1)的严格局部极小点。约束问题：(2)s.t.其中都是定义在上的实值连续函数，且至少有一个是非线性的。称为目标函数，为不等式约束函数,为等式约束函数。(i)如果，称(2)为等式约束优化问题；(ii)如果，称(2)为不等式约束优化问题；(iii)如果都为线性函数，是二次函数，则称(2)为二次规划问题。若满足(2)的所有约

2、束条件，称为(2)的可行点(或可行解)。可行集（可行域）：。定义3(全局极小点)设使得成立，则称为问题(2)的全局极小点。如果有成立，则称为问题(2)的严格全局极小点。定义4(局部极小点)设，如果存在使得成立，则称为问题(2)的局部极小点。如果有成立，则称为问题(2)的严格局部极小点。2.内容安排■求全局极小点一般来说相当困难。实际上可行的只是求一个局部(或严格局部)极小点。故本课程后面所指极小点，通常指求局部极小点。■仅当问题为凸规划(即目标函数为凸函数，不等式约束函数为凸函数，等式约束函数为线性函数)时，局部极小点才是全局极小点。■按定义验证最优解是不可能的。因此有必要给

3、出只依赖于在处目标函数和约束函数信息的、且与定义等价的条件。这样的条件称其为最优性条件，它们是各种基于梯度算法的理论基础。§4.2无约束问题的最优性条件考虑无约束问题(1)，回忆当时，即单变量函数极值问题的最优性条件：必要条件：若且在处取到极值，如果在可微，则为的驻点，即满足。充分条件：若且在处可微，如果且，则在处取到极小值；如果且，则在处取到极大值。Min一阶条件二阶条件必要充分*1必要充分*2单变量优化问题凸多变量优化问题凸半正定正定*1：为全局极小点；*2：为严格局部极小点。Max一阶条件二阶条件必要充分*3必要充分*4单变量优化问题凹多变量优化问题凹半负定负定*3：为

4、全局极大点；*4：为严格局部极大点。定理1(一阶必要条件)：设为函数在的局部极小点，且在可微，则。证明利用§4.0中的定理1可证。几何解释：若为局部极小点，则在处不能有下降方向。从而，当时，为在处的一个下降方向，故若为函数在的极值点，必有。定理2(二阶必要条件)：设为函数在的局部极小点，且在二阶可微，则有，且半正定证明：利用在的二阶Taylor展开及局部极小点的定义可得。几何解释：由为局部极小点及所确定。定理3(二阶充分条件)：设是定义在上的二次可微函数，如果，且正定，则为函数在的严格局部极小点。证明利用在的二阶Taylor展开及正定矩阵的定义可得。注：满足的点称为的平稳点或

5、驻点。驻点可能是极大值点，也可能是极小值点，也可能不是极值点。但若目标函数为凸函数，则驻点就是全局极小值点；若目标函数为凹函数，则驻点就是全局极大值点。定理4(凸充分性定理)：设是定义在上的凸函数，如果，则为函数在上的全局极小点。(一阶必要条件＋凸性)证明利用可微凸函数的一阶判别条件和易证。例：利用极值条件求解解：，令，即，。得到驻点：，，，Hesse矩阵：在点处Hesse矩阵：，，和不定，根据定理2，不是极小点；负定，是极大点；正定，根据定理3，是局部极小点。§4.3约束问题的极值条件4.3.1一阶最优性条件引入记号：――等式约束指标集――不等式约束指标集定义1:对(2)的

6、任何可行解，若，称第个不等式约束在处是紧的，称集合为不等式约束中在处的紧约束指标集。称是在处的积极集合(有效约束指标集，或紧约束指标集)。可行集上一点是否为局部极小点,取决于目标函数在该点以及附近其它可行点上的值。可行方向在推导最优性条件中起十分重要的作用。各种可行方向的定义:定义2:设，，如果存在，使得，则称是集合在处的可行方向。在处的可行方向的集合记为。问题：问？()例1:考虑集合，在点处的可行方向集，则定义3:设，，如果;则称是集合在处的线性化可行方向。在处的线性化可行方向的集合记为。定义4:设，，如果存在序列和，其中，使得，且有和，则称是集合在处的序列可行方向。在处的

7、所有序列可行方向的集合记为。注：可行方向为几何概念，线性化可行方向为代数概念，序列可行方向是基于极限定义的几何概念。例2，取，则上述定义的三个可行方向集有如下关系：引理1设，如果所有的约束函数在处可微，则有。注：该结论条件可以放宽为，，在处可微，其余不等式约束函数在处连续。引理2(几何最优性条件－必要)：设是(2)的局部极小点，如果在处可微，则必有证明利用目标函数在处的一阶Taylor展开，序列可行方向的定义及局部极小点的定义可证。注：该定理也可表述为：是(2)的局部极小点，则。第一个集合表示目标函数在