第4章--最优性条件

第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 见例5。4.3.2 二阶最优性条件设，如果，则由引理3知为(2)的严格局部极小点(因为满足充分条件)；如果由引理2知不是(2)的局部极小点(因为不满足必要条件)。 考虑约束优化问题(2)，如果在处一阶必要条件满足，即 (9a) (9b)此时如何判断是否为局部极小点？所得判断条件称为二阶最优性条件。同讨论一阶最优性条件一样，需要讨论更高一阶的可行方向集。 设在（2）中，二次连续可微；下面讨论(2)的二阶最优性条件。定义6：设为（2）的K-T点，为其一对应Lagrange乘子，如果，且则称是集合在处的线性化零约束方向。处的所有线性化零约束方向的集合记为。即线性化零约束方向引入的原因： 如果为(2)的K-T点，则由(9b)知 （10）又因为，故有 （11）此外，由 （12）将(11)和(12)代入(10)得： 。此时考虑二阶最优性条件即要考虑集合中的方向，而该集合又包含在中，故引入了线性零约束方向。线性零约束方向集的特征： 定义7：设为（2）的K-T点，为其一对应Lagrange乘子，如果存在序列和，其中，使得对，有 且有和，则称是集合在处的序列零约束方向。在处的所有序列零约束方向的集合记为。即 据定义有：，另外，类似于引理1可证下面引理。 引理4： 引理5：若为（2）的满足K-T条件的局部极小点，为其一对应Lagrange乘子。则必有，其中是(2)的Lagrange函数中固定后所得关于的函数的Hesse矩阵在的值(是一阶方阵)，即 证明 利用目标函数在处的二阶Taylor展开，序列零约束方向的定义及局部极小点的定义可证。定理5（二阶必要条件）：设为（2）的局部极小点，为其一对应Lagrange乘子。如果 (13)则必有 。 定理6（二阶充分条件）：设是(2)的K-T点，为其一对应Lagrange乘子。如果 则是（2）的严格局部极小点。 定义8：设是(2)的K-T点，为其一对应Lagrange乘子。称，或为处的强积极约束。称为处的强积极约束指标集。 则有 推论1：设是(2)的K-T点，为其一对应Lagrange乘子。如果对一切满足的非零方向都有则是（2）的严格局部极小点。 令 则 (14) (15) 实质: (2)的Lagrange 函数中固定乘子后，所得函数的梯度在点的值即为(14)；所得函数的Hesse矩阵在点的值即为(15)。从而：一阶必要条件定理1即为：为(2)的局部极小点的必要条件是存在Lagrange乘子, 使得为函数的驻点(约束规范成立)；二阶必要条件定理5即为：为(2)的局部极小点的必要条件是存在Lagrange乘子, 使得为函数的驻点，同时的Hesse矩阵在的值在集合上为半正定矩阵(约束规范成立)；二阶充分条件定理6即为：为(2)的局部极小点的充分条件是存在Lagrange乘子, 使得为函数的驻点，同时的Hesse矩阵在的值在集合上为正定矩阵。注：设为对称矩阵，如果对任意的，有则称矩阵为集合上的半正定矩阵，或称矩阵在集合上半正定。如果对任意的，有。则称矩阵为集合上的正定矩阵，或称矩阵在集合上正定。例8 考虑下列非线性规划问题其中为实参数，试讨论是否为该问题的局部最优解。目标函数和约束函数在的梯度：，设 解得，Lagrange函数为它关于x的Hesse矩阵是：在点处，有求集合的元素d，令解得，可取任何实数。这时有（1） 当时，对每一个向量，有因此是局部最优解。（2） 当时，对每一个向量，有在不满足局部最优的二阶必要条件，因此不是局部最优解。（3） 当时，利用二阶条件给不出结论，可用其它方法进行判断。这时，原问题即为利用约束条件，从目标函数中消去一个变量，转化为无约束优化问题易知是局部最优解。4.4约束优化问题的鞍点最优性条件1. 预备知识 考虑具有一般约束的优化问题(2)： (2)s.t. 其中，则(2)的lagrange函数为：，其中令 则(2)的Lagrange对偶为：定义1 设，且，若有,且，则称为（2）的Lagrange函数的鞍点。注：为（2）的Lagrange函数的鞍点当且仅当，且。2 鞍点最优性条件引理1 设是（2）的 Lagrange函数的鞍点，则为（2）的可行解，且满足证明 利用鞍点的定义即可证明。 引理2 若为满秩矩阵，即，则，其中，。定理3(鞍点定理)（i）设是（2）的 Lagrange函数的鞍点，则和分别为（2）和其对偶问题的最优解。（ii）设为凸函数；是线性函数，即，且满足。如果为（2）的最优解，则存在，且，使是（2）的 Lagrange函数的鞍点。证明 利用鞍点的定义、引理1和弱对偶定理可证明(i)；利用引理2和已知知强对偶定理成立，从而(2)的对偶问题存在最优解，可证和共同构成(2)的Lagrange函数的鞍点。注：由结论(i)知鞍点是(2)的最优解的充分条件；由结论(ii)知，仅在凸规划和约束规范成立时，鞍点存在才是(2)有最优解的必要条件。3. 鞍点与K-T点的关系约束问题