精选优质文档-----倾情为你奉上第4章 最优性条件4.1 最优性条件的预备知识1．极小点的定义 无约束问题： (1) 定义1（全局极小点）若存在使得则称为问题(1)的全局极小点如果有则称为问题(1)的严格全局极小点 定义2 （局部极小点）设，如果存在使得则称为问题(1)的局部极小点如果有则称为问题(1)的严格局部极小点 约束问题： (2)s.t. 其中都是定义在上的实值连续函数，且至少有一个是非线性的 称为目标函数，为不等式约束函数,为等式约束函数 (i) 如果，称(2)为等式约束优化问题； (ii) 如果，称(2)为不等式约束优化问题； (iii) 如果都为线性函数，是二次函数，则称(2)为二次规划问题 若满足(2)的所有约束条件，称为(2)的可行点(或可行解) 可行集（可行域）： 定义3 (全局极小点)设使得成立，则称为问题(2)的全局极小点如果有成立，则称为问题(2)的严格全局极小点。
定义4 (局部极小点)设，如果存在使得成立，则称为问题(2)的局部极小点如果有成立，则称为问题(2)的严格局部极小点2. 内容安排■ 求全局极小点一般来说相当困难实际上可行的只是求一个局部(或严格局部)极小点故本课程后面所指极小点，通常指求局部极小点■ 仅当问题为凸规划(即目标函数为凸函数，不等式约束函数为凸函数，等式约束函数为线性函数)时，局部极小点才是全局极小点■ 按定义验证最优解是不可能的因此有必要给出只依赖于在处目标函数和约束函数信息的、且与定义等价的条件这样的条件称其为最优性条件，它们是各种基于梯度算法的理论基础4.2 无约束问题的最优性条件考虑无约束问题(1)，回忆当时，即单变量函数极值问题的最优性条件： 必要条件：若且在处取到极值，如果在可微，则为的驻点，即满足 充分条件：若且在处可微，如果且，则在处取到极小值；如果且，则在处取到极大值Min一阶条件二阶条件必要充分*1必要充分*2单变量优化问题凸多变量优化问题凸半正定正定*1：为全局极小点； *2：为严格局部极小点Max一阶条件二阶条件必要充分*3必要充分*4单变量优化问题凹多变量优化问题凹半负定负定 *3：为全局极大点； *4：为严格局部极大点。
定理1 (一阶必要条件)：设为函数在的局部极小点，且在可微，则 证明 利用4.0中的定理1可证 几何解释：若为局部极小点，则在处不能有下降方向从而，当时，为在处的一个下降方向，故若为函数在的极值点，必有 定理2 (二阶必要条件)：设为函数在的局部极小点，且在二阶可微，则有，且半正定 证明：利用在的二阶Taylor展开及局部极小点的定义可得 几何解释：由为局部极小点及所确定 定理3 (二阶充分条件)：设是定义在上的二次可微函数，如果，且正定，则为函数在的严格局部极小点 证明 利用在的二阶Taylor展开及正定矩阵的定义可得 注：满足的点称为的平稳点或驻点驻点可能是极大值点，也可能是极小值点，也可能不是极值点但若目标函数为凸函数，则驻点就是全局极小值点；若目标函数为凹函数，则驻点就是全局极大值点 定理4 (凸充分性定理)：设是定义在上的凸函数，如果，则为函数在上的全局极小点一阶必要条件＋凸性) 证明 利用可微凸函数的一阶判别条件和易证 例：利用极值条件求解解： ，令，即，得到驻点：，，，Hesse矩阵： 在点处Hesse矩阵：，，和不定，根据定理2，不是极小点；负定，是极大点；正定，根据定理3，是局部极小点。
4.3 约束问题的极值条件4.3.1 一阶最优性条件引入记号：――等式约束指标集――不等式约束指标集 定义1: 对(2)的任何可行解，若，称第个不等式约束在处是紧的，称集合为不等式约束中在处的紧约束指标集称是在处的积极集合(有效约束指标集，或紧约束指标集)可行集上一点是否为局部极小点, 取决于目标函数在该点以及附近其它可行点上的值可行方向在推导最优性条件中起十分重要的作用各种可行方向的定义: 定义2: 设，，如果存在，使得，则称是集合在处的可行方向在处的可行方向的集合记为 问题：问？()例1: 考虑集合，在点处的可行方向集，则 定义3: 设，，如果; 则称是集合在处的线性化可行方向在处的线性化可行方向的集合记为 定义4: 设，，如果存在序列和，其中，使得，且有和，则称是集合在处的序列可行方向在处的所有序列可行方向的集合记为 注：可行方向为几何概念，线性化可行方向为代数概念，序列可行方向是基于极限定义的几何概念 例2 ，取，则上述定义的三个可行方向集有如下关系： 引理1 设，如果所有的约束函数在处可微，则有 注：该结论条件可以放宽为，，在处可微，其余不等式约束函数在处连续。
引理2 (几何最优性条件－必要)：设是(2)的局部极小点，如果在处可微，则必有 证明 利用目标函数在处的一阶Taylor展开，序列可行方向的定义及局部极小点的定义可证 注：该定理也可表述为：是(2)的局部极小点，则第一个集合表示目标函数在处的一个下降方向的子集，即该下降方向的子集与序列可行方向无公共元素 定理1：设是(2)的局部极小点，如果目标函数和所有的约束函数在处可微，且 (3)则必存在和使得 （梯度条件）（4a）， （互补松弛条件）（4b） 该定理的另外一种等价表示（基于该等价表示可以看出K-T最优性条件的几何意义）： 定理: 设是(2)的局部极小点，如果目标函数和所有的约束函数在处可微，且则必存在和使得 （5）证明思路：约束规格CQFarkas定理引理2（几何形式的最优性）FJ最优性条件K-T条件（代数形式的最优性） (4a)-(4b)由Kuhn，Tuck（1951）给出，一般称为K-T条件，因Karush（1939）也类似地考虑了约束优化的最优性条件，所以也称K-K-T条件 几何意义：在局部极小点处，若某种约束规范成立，则目标函数的梯度向量位于不等式积极约束的梯度向量生成的凸锥与等式约束的梯度向量生成的线性空间的和集。
即 例3 考虑问题 s.t. 验证点是否满足K-T条件记 ，，梯度：，，先验证在此点，和都是起作用约束，目标函数和约束函数的梯度为，，设 得到，由于，故不是K-T点在此点，和都是起作用约束，目标函数和约束函数的梯度为，，设 得到，故是K-T点例4 考虑问题 s.t. 求该问题的K-T点目标函数和约束函数的梯度：，， K-T条件： 即： 可得上述方程组的一组解：由于非负，因此得到K-T点例5 考虑问题求该问题的K-T点目标函数和约束函数的梯度：，， K-T条件：解得：故为K-T点，也是全局最优点（？）注1： 此定理中目标函数和所有的约束函数在处可微，可放宽为在连续，；在可微 注2：(3)式所给条件称为约束规范(约束规格－Constraint Qualification)若约束规范不成立，则(2)的局部极小点不一定是K-T点例6 (Flether,1987) s.t. 则为局部极小点，且易验证： 所以约束规范(3)不成立。
易见不存在，使得 注3：(3)所给约束规范条件不易直接验证人们给出一些更强的，但容易验证的约束规范条件 线性函数约束规范：所有的约束函数，均为线性函数所以二次规划和线性规划在任一可行解处约束规范条件均满足) 线性无关约束规范：; 线性无关，即处紧约束的梯度向量线性无关Mangasarian和Fromowitz(1967)约束规范：(i) 线性无关；(ii)注4: 在不作任何约束规范的假定下， Fritz John (1948)给出如下的必要性条件：定理2（Fritz John条件）: 设是(2)的局部极小点，且下列条件满足： （i） 在可微； （ii）在连续 则存在不全为零的非负数，，和，使得 （6a），. （6b） 定理（Fritz John条件）: 设是(2)的局部极小点，且下列条件满足： （i） 在可微； （ii）在连续 则存在不全为零的非负数，和，使得 （7） 当时，该条件不能刻画目标函数和约束函数的关系，这是该条件没有受到重视的原因 注5: 与K-T条件密切相关的一个函数是该函数的思想可以追索到Lagrange，故它被称为Lagrange函数，称为Lagrange乘子。
定义5: 称为（2）的K-T点，如果存在非负数 和实数，使得下式成立：则称 为Lagrange（\K-T）乘子 有了K-T点的定义，则定理1所表述的一阶必要条件可重新表述为：设在（2）的某可行点处某种约束规范成立，若其为（2）的局部极小点，则必为（2）的K-T点 求问题（2）的K-T点需求解下列系统： (梯度条件) (8a) (互补松弛条件) (8b) (乘子的非负性) (8c)， (可行性) (8d) 上面讨论的都是必要条件，下面讨论充分条件 引理3(几何最优性条件－充分): 设，如果目标函数和约束函数在处可微，且则是(2)的严格局部极小点 证明类似引理2定理3: 设，如果目标函数和约束函数在处可微，且则是(2)的严格局部极小点 证明: 由引理1知，再由引理3知结论成立K-T点不一定是局部极小点，但对于凸规划而言，K-T点即为全局极小点 定理4（充分条件）: 设是(2)的K-T点，如果（2）为凸规划，即，是凸函数，，是线性函数，则是（2）的全局极小点 例7 见例54.3.2 二阶最优性条件设，如果，则由引理3知为(2)的严格局部极小点(因为满足充分条件)；如果由引理2知不是(2)的局部极小点(因。