数据科学优化方法 课件 第7、8章 共轭梯度方法、约束最优化问题的最优性理论

数据科学优化方法Optimization

Method

in

Data

Science第7章共轭梯度方法7.1共轭方向方法7.2针对正定二次函数的共轭梯度方法7.3

非线性共轭梯度方法7.4数值实验引入一个很自然的想法是构造一种介于负梯度方法和牛顿方法之间的方法，使其既可以比负梯度方法的收敛速度快，又可以避免牛顿方法高昂的计算成本.本章介绍的共轭梯度方法正是这样一种方法.关于无约束最优化问题，我们已经学习了一阶方法(负梯度方法)和二阶方法(牛顿方法).12在实际使用中，负梯度方法的收敛速度往往很慢牛顿方法的收敛速度虽然很快，但却需要计算Hesse矩阵的逆.第7章共轭梯度方法7.1共轭方向方法7.2针对正定二次函数的共轭梯度方法7.3

非线性共轭梯度方法7.4数值实验共轭方向方法7.1.1方法的引入

7.1.2共轭的定义及性质7.1.3共轭方向方法的计算步骤及性质方法的引入考虑极小化正定二次函数问题其中是对称正定矩阵.当

是对角阵时，可以很容易地将原问题转化为

个一元二次函数的最小化问题对

维问题，从出发，依次沿

个坐标轴方向作精确线搜索，便得到该问题最小值方法的引入图7.1

沿负梯度方向的迭代路径(实线)和沿坐标轴方向的迭代路径(虚线)方法的引入图7.1

沿负梯度方向的迭代路径(实线)和沿坐标轴方向的迭代路径(虚线)方法的引入当正定二次函数问题中的

不再是对角阵时，依次沿何种方向作精确线搜索能得到相同结果呢？设是实对称矩阵，则具有如下性质1.有个实特征根2.属于不同特征值的特征向量正交3.可正交对角化根据该定理，从任意初始点出发，依次沿的

个正交特征向量方向做精确线搜索，便可得到正定二次函数问题的极小值.定理7.1.谱定理方法的引入图7.2

沿负梯度方向的迭代路径(实线)和沿正交特征向量方向的迭代路径(虚线)方法的引入尽管根据谱定理可以解决正定二次函数的优化问题，但求矩阵的特征值和特征向量需要付出较高的计算成本.为了能处理一般的最优化问题，尤其是大规模最优化问题，我们必须另外寻找合适的迭代方向.研究发现，共轭方向具备所要求的性质共轭方向方法7.1.1方法的引入

7.1.2共轭的定义及性质7.1.3共轭方向方法的计算步骤及性质共轭的定义及性质设为的对称正定矩阵，是中的两个非零向量，若则称向量是的共轭方向，简称共轭的.设是中的一组非零向量，若则称向量组是的两两共轭方向，简称

共轭的.定义7.1.共轭方向共轭的定义及性质如果，则任意两个

维非零向量是

共轭的.如果

，则共轭就是通常所说的正交.设为的对称正定矩阵，如果是共轭的，则它们是线性无关的.设为的对称正定矩阵，如果是共轭的，则共轭方向方法7.1.1方法的引入

7.1.2共轭的定义及性质

7.1.3共轭方向方法的计算步骤及性质共轭方向方法的计算步骤及性质共轭方向方法：所有迭代方向都两两共轭的方法.算法7.1:共轭方向方法的计算步骤给定若满足终止准则，则停止迭代;由线搜索确定步长因子令采用某种共轭方向法计算，转步2共轭方向方法的计算步骤及性质对于极小化正定二次函数问题，由精确线搜索确定的步长因子的显式表达式为(7.2)其中定理7.2共轭方向方法的计算步骤及性质在精确线搜索条件下，共轭方向方法具有二次终止性，即对于正定二次函数，方法能够在有限步内终止.对于极小化正定二次函数问题，由任意初始点

出发，采用精确线搜索的共轭方向方法至多经

步就可收敛到目标函数的极小点.共轭方向方法的计算步骤及性质证明：因为共轭方向线性无关，故它们可以张成一个n

维空间.于是,可将写成共轭方向的线性组合上式两边左乘,由的共轭性得(7.3)共轭方向方法的计算步骤及性质下面证明系数与(7.2)定义的步长

相等.注意到上式两边左乘,由的共轭性得因此，对比(7.2)和(7.3)，有，由此定理得证.共轭方向方法的计算步骤及性质当为对角阵，每次沿坐标轴方向迭代可以依次确定极小

点

的一个分量.在个一维极小化后，迭代点达到正定二次函数在由坐标轴张成的子空间中的极小点.下面的定理表明这一结果适用于一般的正定二次函数.共轭方向方法的计算步骤及性质对于极小化正定二次函数问题，由任意初始点

出发，采用精确线搜索的共轭方向满足(7.4)且上的极小点.定理7.3.子空间扩展定理共轭方向方法的计算步骤及性质证明：我们只给出证明思路，具体证明留作习题1.将

改写为

的线性组合，由共轭方向的定义即可证明出(7.4).2.只需证明当

时，.因为是二次函数，所以

就等于

的2阶Taylor展式，再利用第一个结论就可以证明出第二个结论.第7章共轭梯度方法7.1共轭方向方法7.2针对正定二次函数的共轭梯度方法7.3

非线性共轭梯度方法7.4数值实验针对正定二次函数的共轭梯度方法共轭梯度方法是一种共轭方向方法，由Hestenes和Stiefel独立提出.方法的最大特点在于无需预先给定共轭方向，而是随着迭代的进行不断产生共轭方向.在每次迭代中，利用上一步迭代方向和目标函数在当前迭代点的梯度方向二者的线性组合构造一个新方向，使其与前面所有迭代方向是Q共轭的.

该方法所需的存储量小，计算简便.针对正定二次函数的共轭梯度方法本节讨论针对正定二次函数的共轭梯度方法（又称线性共轭梯度方法）及性质，下节讨论针对一般非线性函数的共轭梯度方法.针对正定二次函数的共轭梯度方法7.2.1方法的推导

7.2.2方法的性质

7.2.3预处理技术方法的推导在共轭梯度方法中，迭代方向为负梯度方向和前一个迭代方向的线性组合，即为了保证由于上式可以改写为由（7.4）和（7.5），上式可进一步简化为（7.5）方法的推导由于极小化正定二次函数问题等价于求解线性方程组，因此基于上式的共轭梯度方法也被称为线性共轭梯度方法.方法的推导算法7.2:共轭梯度方法的计算步骤给定若满足终止准则，则停止迭代计算

，转步2针对正定二次函数的共轭梯度方法7.2.1方法的推导

7.2.2方法的性质7.2.3预处理技术方法的性质迭代方向是共轭的，故由定理7.2可知，方法最多在

步内收敛.向量

是相互正交的.和均在度为

的Krylov空间中，其定义如下：定理7.4方法的性质设是实对称矩阵，,取则采用精确线搜索的共轭梯度方法在步内终止,且对有共轭方向： (7.7)正交向量： (7.8)下降方向： (7.9)(7.10)(7.11)定理7.4方法的性质设是实对称矩阵，,取则采用精确线搜索的共轭梯度方法在步内终止,且对有共轭方向： (7.7)正交向量： (7.8)下降方向： (7.9)(7.10)(7.11)①②③④⑤注：定理7.4的结论要求初始迭代方向取为负梯度方向，否则生成的迭代方向可能不共轭.方法的性质例

考虑最优化问题其中，选取初始点为初始迭代方向为故有采用精确线搜索方法得步长从而于是有方法的性质证明：采用数学归纳法.当

，(7.7)成立.当

时，(7.10)和(7.11)自然成立.假设这三个等式对某个成立，证明对于

，这些等式亦成立.

对于(7.10)，先证明等式左边集合包含于等式右边集合.由归纳法假设知第二式两边左乘，得由于(7.12)故方法的性质再利用归纳法假设(7.10)，可得(7.13)反之，由归纳法假设(7.11)，有由(7.12)有故再利用归纳法假设(7.10)，可得(7.14)(7.13)和(7.14)表明(7.10)对k+1成立.类似地，可以证明(7.11)也对k+1成立.方法的性质接下来，证明(7.7)也对k+1成立.利用(7.5)，可得(7.15)由的定义知，当i=k时，上式右边项等于零.当i<k，首先利用归纳法假设可知

是共轭的，故由定理7.3，可得(7.16)其次，重复利用(7.10)，对i=0,1,...,k−1，有(7.17)由(7.16)和(7.17)可得方法的性质故(7.15)右边第一项为零，又由归纳法假设知(7.15)右边第二项也为零，从而

由此表明共轭梯度方法产生的迭代方向的确是共轭的，从而由定理7.2可知方法一定能在n

步内终止.

然后，证明(7.7).因为迭代方向是共轭的，故由(7.4)可得

由(7.5)可知于是.由此可得.当

时，由于，又利用(7.4)，可得.

最后，由(7.4)和(7.5)可证出(7.9).

方法的性质共轭梯度方法的收敛速度如下.定义其中和分别为矩阵最大和最小的特征根.可以证明和最速下降方法的收敛速度(定理4.6)相比，共轭梯度方法的收敛速度取决于而非7.2针对正定二次函数的共轭梯度方法7.2.1方法的推导

7.2.2方法的性质7.2.3预处理技术预处理技术我们可以通过改善矩阵

条件数的方式提高共轭梯度方法的收敛速度，这种方式被称为预处理.设

是一个非奇异矩阵，令等价于求解于是，共轭梯度方法的收敛速度将取决于

而非矩阵

的条件数.因此能选择合适的非奇异矩阵可以改善该方法的收敛速度.预处理技术定义即可得到下面的预处理共轭梯度方法7.3，并且算法7.2的性质可以推广到算法7.3.计算上需要多计算一个线性方程组预处理技术算法7.3:预处理共轭梯度方法的计算步骤给定令若满足终止准则，则停止迭代;计算解，得

，转步3第7章共轭梯度方法7.1共轭方向方法7.2针对正定二次函数的共轭梯度方法7.3

非线性共轭梯度方法7.4数值实验非线性共轭梯度方法非线性共轭梯度方法的迭代方向仍是当前的负梯度方向与上一次迭代方向的线性组合：选取不同的，便得到不同的共轭梯度方法.其中，最为著名的两个方法：FR方法PRP方法非线性共轭梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重启共轭梯度方法7.3.4其他非线性共轭梯度方法FR方法算法7.4:FR方法给定若满足终止准则，则停止迭代;用非精确线搜索求，令计算(7.21)(7.22)5.，转步2FR方法FR方法是首个非线性共轭梯度方法.该方法在线性共轭梯度方法基础上做了一处调整，即不再采用精确线搜索确定步长，而是改用非精确线搜索由于算法7.4每次迭代仅需要目标函数值和梯度值，未涉及矩阵存储和计算，故非常适合求解大规模非线性最优化问题.FR方法接下来讨论FR方法的下降性.对于FR方法，如果步长满足强Wolfe非精确线搜索准则，且，则迭代方向满足因此，是下降方向.

定理7.5注：定理说明当使用强Wolfe非精确线搜索并保证

，得到的迭代方向是下降方向.（7.23）FR方法证明：用数学归纳法证明(7.23).当,,有故(7.23)成立.假设对任意k−1，(7.23)成立.由(7.21)和(7.22)有(7.24)由强Wolfe非精确线搜索准则知FR方法由(7.25)的第一个不等式与归纳假设知由(7.25)的第二个不等式与归纳假设知即(7.23)对k也成立，从而(7.23)成立.

由于

在上单调递增，且任意有

因此，由(7.23)可知是下降方向。将上式与(7.24)相结合有(7.25)定理7.6FR方法接下来讨论FR方法的收敛性.设在水平集上，有下界，梯度函数

满足Lipschitz条件，则采用精确线搜索的FR方法产生的迭代序列，或者对某个有限有，或者FR方法证明：假定对所有k,由于故从而

是下降方向.由于是单调下降且有下界的序列，故

存在.由及L

有界,可知是有界点列，故存在收敛子列,这里是子序列的下标集.由于,故,从而由的连续性可知，对于,有类似地，也是有界点列，故存在，这里是

的子序列的下标集.于是，对于

，有（7.26）FR方法下面用反证法证明假定则存在一个方向使得对于充分小的

，有(7.27)由于

是由精确线搜索确定，于是有因此对于,令，并利用(7.27)得这与(7.26)矛盾.由此证明了FR方法关于FR方法的收敛速度，我们有以下结果：在定理7.6的条件下，采用精确线搜索的FR方法产生的迭代序列线性收敛到目标函数的极小点.非线性共轭梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重启共轭梯度方法7.3.4其他非线性共轭梯度方法PRP方法将算法中7.4中的计算公式进行如下替换即得到PRP方法的计算步骤.对于正定二次函数，PRP方法等价于FR方法.对于一般非线性函数，数值实验结果表明PRP方法比FR方法更加稳健且有效.由于会出现取负值情况，导致相邻迭代方向趋于相反方向，从而难以给出全局收敛定理.PRP方法将算法中7.4中的计算公式进行如下替换即得到PRP方法的计算步骤.PRP+方法将取为可以证明，对于一般非线性函数，在适当的线搜索条件下，PRP+方法的迭代方向为下降方向，且具有全局收敛性.7.3非线性共轭梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重启共轭梯度方法7.3.4其他非线性共轭梯度方法重启共轭梯度方法上节讨论了极小化正定二次函数的共轭梯度方法.本节将其推广到一般非线性函数.求解一般非线性最优化问题的共轭梯度方法被称为非线性共轭梯度方法.

重启共轭梯度方法上节讨论了极小化正定二次函数的共轭梯度方法.本节将其推广到一般非线性函数.求解一般非线性最优化问题的共轭梯度方法被称为非线性共轭梯度方法.由Taylor定理可知，目标函数在极小点某个邻域内可以较好地被正定二次函数近似.由于线性共轭梯度方法的二次终止性需要初始迭代方向取为负梯度方向，故当迭代进入到该邻域内，重新取负梯度方向为迭代方向，则其后的迭代方向接近于共轭方向.这样可以使得方法具有较快的收敛速度.重启共轭梯度方法算法7.

5:重启共轭梯度方法给定若满足终止准则，则停止迭代，;用一维线搜索求，计算

，若，令，转步2；若，令，转步2；计算，若

令转步2；否则转步3重启共轭梯度方法

非线性共轭梯度方法7.3.1FR方法7.3.2

PRP方法7.3.3重启共轭梯度方法7.3.4其他非线性共轭梯度方法其他非线性共轭梯度方法除前面介绍的FR方法和PRP方法外，本节再简要介绍其他几个具有代表性的非线性共轭梯度方法.1980年Fletcher提出的共轭下降（ConjugateDescent,CD）方法当使用强Wolfe非精确线搜索准则且

，共轭下降方法得到的迭代方向为下降方向.其他非线性共轭梯度方法除前面介绍的FR方法和PRP方法外，本节再简要介绍其他几个具有代表性的非线性共轭梯度方法.1995年戴彧虹和袁亚湘提出的DY(Dai-Yuan)方法当使用Wolfe非精确线搜索准则，该方法产生的迭代方向为下降方向，且方法具有全局收敛性.第7章共轭梯度方法7.1共轭方向方法7.2针对正定二次函数的共轭梯度方法7.3

非线性共轭梯度方法7.4数值实验数值实验在本小节中，我们应用PRP方法求解上一章的6个典型最优化问题以检验方法的有效性.迭代步长满足Armijo线搜索准则迭代的终止准则为

最大迭代次数为10000.数值实验问题

1全局最优解为，最优值为，考虑初始点，表7.1和图7.3给出了迭代点信息.可以看出，PRP方法能较快收敛到最优解。图7.3PRP方法求解问题1的迭代点轨迹表7.1PRP方法求解问题1的部分迭代点信息数值实验问题2全局最优解为，最优值为.以为初始点，PRP方法可以收敛到最优解，但速度要明显慢于BFGS方法（见图7.4和表7.2）图7.4PRP方法求解问题2的迭代点轨迹表7.2PRP方法求解问题2的部分迭代点信息数值实验问题3全局最优解为，最优值为.当初始点为时，和最速下降方法类似，PRP方法也较难收敛(见图7.5和表7.3).图7.5PRP方法求解问题3的迭代点轨迹表7.3PRP方法求解问题3的部分迭代点信息数值实验问题4全局最优解为，最优值为.当初始点时，PRP方法可以较快收敛到最优解(见图7.6和表7.4).图7.6PRP方法求解问题4的迭代点轨迹表7.4PRP方法求解问题4的部分迭代点信息数值实验问题5：全局最优解为最优值为PRP方法可以较快收敛到最优解(见表7.5).表7.5PRP方法求解问题5的迭代点信息00.9487-0.63760.191310.3438-0.94260.102520.0197-1.00006.2365e-0333.8372e-06-1.00001.2134e-0642.8249e-17-1.00008.9332e-18数值实验问题6：全局最优解为最优值为PRP方法表现差于BFGS方法，较难实现收敛.表7.6PRP方法求解问题6的迭代点信息01.581158.500051.0000

11.579953.800044.404721.579550.203438.465331.579647.141733.5037…………99990.00547.1535e-062.3184e-03100000.00537.1463e-062.3172e-07数据科学优化方法Optimization

Method

in

Data

Science第8章约束最优化问题的最优性理论8.1约束最优化问题的一般形式和定义8.2约束最优化问题的一阶最优性条件8.3约束最优化问题的二阶最优性条件8.4约束最优化问题的对偶问题第8章约束最优化问题的最优性理论8.1约束最优化问题的一般形式和定义8.2约束最优化问题的一阶最优性条件8.3约束最优化问题的二阶最优性条件8.4约束最优化问题的对偶问题约束最优化问题的一般形式和定义其中

，

均为

上的光滑实值函数.对满足约束条件的点称为可行点，所有可行点的集合成为可行域，记为：考虑一般形式的约束最优化问题约束最优化问题的一般形式和定义约束条件其中

，

均为

上的光滑实值函数.对满足约束条件的点称为可行点，所有可行点的集合成为可行域，记为：考虑一般形式的约束最优化问题不等式约束等式约束约束最优化问题的一般形式和定义对一般的约束最优化问题，若，有

则称为问题的全局最优解.进一步，如果则称为问题的严格全局最优解.定义8.1.全局最优解约束最优化问题的一般形式和定义对一般的约束最优化问题，若对于，存在的某个邻域，有

则称为问题的局部最优解.进一步，如果则称为问题的严格局部最优解.定义8.2.局部最优解约束最优化问题的一般形式和定义除了严格局部最优解之外还存在另外一种特殊局部最优解：孤立局部最优解注：孤立局部最优解必是严格局部最优解，反之则并不一定.对一般约束最优化问题，若存在的一个邻域，使得是内唯一局部最优解，则称是问题的孤立局部最优解定义8.3.孤立局部最优解约束最优化问题的一般形式和定义例8.1

考虑约束最优化问题约束最优化问题的一般形式和定义该问题有局部最优解和全局最优解,见图8.1，虚线为目标函数等高线，实线为可行域，实心点为全局最优解，空心点为局部最优解图8.1问题（8.1）目标函数的等高线和可行域约束最优化问题的一般形式和定义约束最优化问题的另一个重要概念是起作用约束对任何，称集合为在点处的起作用约束集（或有效约束集、积极约束集），简称起作用集，称为在点处的起作用约束，称为在点处的不起作用约束.定义8.4.起作用约束集约束最优化问题的一般形式和定义假定已知约束最优化问题的起作用集为，此时不起作用约束可以忽略，则约束最优化问题可以改写为仅含等式约束的最优化问题约束最优化问题的一般形式和定义例8.2

考虑约束最优化问题例8.2的最优解，在最优解处前两个约束起作用，后两个约束不起作用，故，去掉后两个约束问题的解不变约束最优化问题的一般形式和定义图8.2问题（8.2）目标函数的等高线和可行域约束最优化问题的一般形式和定义注：等式约束函数是线性函数、不等式约束函数是凹函数的约束构成的可行域为凸集，凸优化问题是求凸函数在凸集上的极值问题.设为凸函数，为线性函数，为凹函数，则称问题是凸优化（或凸规划）问题.定义8.5.凸优化问题约束最优化问题的一般形式和定义设是定义在凸集上的凸函数，集合中是的局部最优解，则必是的全局最优解.定理8.1注：定理表明凸优化问题的局部最优解均为全局最优解

约束最优化问题的一般形式和定义因此对于，有由此可知，存在一个任意接近的点，其对应的目标函数值更小.例如，对于收敛于的序列有.因此不是局部最优解，与已知条件矛盾，定理得证.

约束最优化问题的一般形式和定义第8章约束最优化问题的最优性理论8.1约束最优化问题的一般形式和定义8.2约束最优化问题的一阶最优性条件8.3约束最优化问题的二阶最优性条件8.4约束最优化问题的对偶问题约束最优化问题的一阶最优性条件8.2.1三个约束最优化问题的例子8.2.2可行方向和约束规范条件8.2.3一阶最优性条件例8.3

求解最优化问题三个约束最优化问题的例子等式约束的优化问题解：根据一般约束最优化问题的定义可以得到以下信息：最优解以及对应点的梯度为：三个约束最优化问题的例子不难看出，在处与共线，故：其中.该例子中极大点处与共线，而其他点处并不共线.这意味着在这些点上总会有一个迭代方向使得迭代点依然在可行域之内而目标函数值有所下降.例如对于圆周的右端点(1,0)，从该点出发沿顺时针方向的迭代方向即满足要求.三个约束最优化问题的例子通过对目标函数和约束函数分别做一阶泰勒近似，也可以得到在最优解处，目标函数的梯度和等式约束的梯度共线的结论.

为了保证迭代点满足，需要迭代方向满足满，对在点做一阶泰勒近似，有因此三个约束最优化问题的例子此时可以保证迭代点依然在可行域内.类似的对目标函数同样进行一阶泰勒近似为满足迭代点处目标函数值减少，需要满足若任意迭代方向不能同时满足与，才可能是局部最优解.只有二者共线时才可能出现不能同时满足的情况.三个约束最优化问题的例子为了简化描述，引入Lagrange函数

其中，称为的Lagrange乘子.由于，因此共线条件等价于上式表明可以通过寻找Lagrange函数的稳定点来求解等式约束优化问题.

三个约束最优化问题的例子

注：由于极大点处共线条件同样成立，故而

只是是等式约束最优化问题的局部最优解的必要非充分条件.三个约束最优化问题的例子例8.4

求解最优化问题三个约束最优化问题的例子仅有一个不等式约束的优化问题解：该问题的可行域为单位圆圆周和圆内.最优解依旧是且仍然成立.区别于仅含等式的约束最优化问题，Lagrange乘子的符号在此问题下至关重要.三个约束最优化问题的例子采用例8.3中已经使用过的分析思路，如果在可行点处存在迭代方向使得下一个迭代点在可行域内且目标函数值下降则其必不是局部最优解.在该问题下需要重新思考之处在于保证迭代点为可行点的条件，具体地，当依然为可行点，因此条件变为三个约束最优化问题的例子下面可以分两个情形讨论：情形1：位于可行域内部，.令足够小时则可以保证.如若令，当时，该迭代方向同时满足与.当时则不存在满足条件的迭代方向.

三个约束最优化问题的例子情形2：位于可行域边界，.此时原条件改变为

如右图所示，上述两不等式分别确定了半个平面，而只有当

时两个半平面的交集才为空集.此时从处不存在同时满足两条件的迭代方向.此时需要要求.否则从图中可知半平面的迭代方向均可满足三个约束最优化问题的例子用Lagrange函数总结上述两种情况下的一阶最优性条件.当在点处不存在迭代方向，使得下一个迭代点依然在可行域内且目标函数值有所下降，则

被称为互补条件.该条件表明只有约束在处起作用时，才可能大于0.三个约束最优化问题的例子例8.5

求解最优化问题.三个约束最优化问题的例子包含两个不等式约束的优化问题解：该问题的可行域变为上半圆，此时最优解且两个约束均起作用.采用例8.4类似的分析方法，若在处存在迭代方向满足则一定不是该问题的局部最优解.三个约束最优化问题的例子对于该问题可以定义如下Lagrange函数其中为Lagrange乘子.于是可以推广为两个不等式的互补条件为上述三式共同构成了该问题的一阶最优性条件.三个约束最优化问题的例子验证该问题的一阶最优性条件.在

处此时令则可使，故能够满足条件.下面考虑其他几个可行点在

处两约束均起作用.迭代方向

满足条件

该点只有令条件才能成立，但，故一阶最优性条件无法同时满足三个约束最优化问题的例子在

处只有约束起作用.由于从该点出发的任意一小步均可实现，故条件可以简化为：

容易看出满足简化后的条件.再考虑一阶最优性条件，由互补条件可知，于是

等价于

显然并不存在能使该等式成立的.该点同样不满足一阶最优性条件.三个约束最优化问题的例子约束最优化问题的一阶最优性条件8.2.1三个约束最优化问题的例子8.2.2可行方向和约束规范条件8.2.3一阶最优性条件可行方向和约束规范条件以上例子的分析方式需要线性化可以近似刻画当前点附近可行域几何特征时才有意义，因此我们需要对其做出必要假设，使得在点处的线性化近似与可行域一致.此类假设被称为约束规范条件.为了定义约束规范条件我们需要先介绍两类可行方向.可行方向和约束规范条件设为一般约束最优化问题的可行点，若存在可行点序列，，和序列，使得：则称为点处的序列可行方向,简称为可行方向.处的所有可行方向的集合记为定义8.6.可行方向注：可行方向不依赖于可行域的定义形式.如果为可行方向，则也是可行方向.可行方向和约束规范条件设为问题的可行点，起作用集为.如果则称为点处的线性化可行方向.点处所有线性化可行方向的集合记为定义8.7.线性化可行方向注：线性化可行方向依赖于约束函数的具体定义.可行方向和约束规范条件例8.6

考虑如下最优化问题在点

处的可行方向和线性化可行方向可行方向和约束规范条件解：该最优化问题可行域为中心在原点，半径为1的圆周.令易知是可行点且.进一步，有故为处的可行方向.沿着该可行方向目标函数值仍会继续下降，故而必不是最优解.可行方向和约束规范条件从相反方向可得到可行序列：令则可知为可行方向.利用可行方向的性质，可以得到处可行方向的集合为：从定义8.7可知，当满足时，为线性化可行方向，故处的线性化可行方向集合为：可行方向和约束规范条件在例8.6中，.然而这一结果并非总能成立.例如，我们将该问题的约束条件改为此时可行域未改变，相应的可行方向集合未改变.由于故此时处的线性化可行方向集合,从而在点处，可行方向和约束规范条件可行点处的可行方向集合和线性化可行方向集合有如下关系：定理8.2注：从例8.6的讨论中可以知道并不一定成立证明：设满足定义8.6，即从而可以得到.下面证明..对任意，由泰勒定理有令，则可得到.可行方向和约束规范条件对任意的，有令则可得到.因此,可行方向和约束规范条件引入可行方向和线性化可行方向的目的是建立约束规范条件，从而建立最优性条件.常用的一种为KT(Kuhn-Tucker)约束规范条件：.但KT约束规范条件不容易验证.于是，我们给出如下容易验证的线性无关约束规范条件(LICQ).可行方向和约束规范条件可行方向和约束规范条件给定点和起作用集，如果线性无关，则称在点处线性无关约束规范（LICQ）成立.定义8.8.LICQ注:如果点处，LICQ条件成立，则，可行方向和约束规范条件若在可行点处LICQ条件成立，则定理8.3注:该定理说明线性无关约束规范强于KT条件.可行方向和约束规范条件设是一般约束最优化问题的局部最优解，则定理8.4证明：采用反证法.假设存在一个可行方向使得设是方向满足定义8.6的序列.由和泰勒定理可知，对充分大的k有由于，故当，有因此,给定任意以为中心的邻域,都可选取充分大的k使得在此邻域内，且,这与是局部最优解矛盾.可行方向和约束规范条件定理8.4说明局部最优解处没有可行的下降方向.

上述命题逆命题不一定成立，即使对所有可行方向

，都有也可能不是局部最优解.

可行方向和约束规范条件可行方向和约束规范条件例考虑如下约束最优化问题该问题的最优值为，对于原点，该点处的任何可行方向都必须满足故但任取点处的目标函数值都小于原点处的函数值，因此原点不是局部最优解.约束最优化问题的一阶最优性条件8.2.1三个约束最优化问题的例子8.2.2可行方向和约束规范条件8.2.3一阶最优性条件一阶最优性条件设为一般约束最优化问题的局部最优解，问题中的目标函数和约束函数均连续可微，且在点处约束规范条件LICQ成立，则存在Lagrange乘子，使得满足其中为Lagrange函数.定理8.5一阶必要条件定理中的5个条件称为KKT条件.满足KKT条件的点称为KKT点，相应的称为Lagrange乘子，称为KKT对.注：对于最优解，可能有很多满足KKT条件.然而，可以证明，当LICQ条件成立时，是唯一的.一阶最优性条件稳定条件可行条件非负条件互补条件定理中的5个条件称为KKT条件.满足KKT条件的点称为KKT点，相应的称为Lagrange乘子，称为KKT对.称为互补条件，根据该条件可将改写为当时，称为严格互补条件.

满足严格互补条件可使优化方法收敛更快一阶最优性条件一阶最优性条件

历史介绍一阶最优性条件

历史介绍对于局部最优解和给定的一个约束，就的两种情况讨论该约束不起作用，即.此时和对该约束并不敏感，微小扰动下仍为局部最优解.由互补条件可得，由此可见该Lagrange乘子表明约束对于该问题的最优解和最优值并不重要.一阶最优性条件Lagrange乘子的意义该约束起作用，即.对该约束增加一个小扰动，例如将约束修改为.假设充分小，使得扰动后的最优解起作用集和Lagrange乘子都不发生变化，此时可得从而根据有一阶最优性条件

令,有由此可见反映了最优值对于约束的敏感程度.如果某些起作用约束对应的Lagrange乘子为0，则微小扰动不会影响最优值，此类约束称为弱起作用约束.Lagrange乘子非零的起作用约束为强起作用约束.一阶最优性条件一阶最优性条件设和为n维向量，则集合为空集的充要条件是，存在，使得：引理8.1

Farkas引理为了证明KKT定理，我们需要引入Farkas引理.一阶最优性条件设和为n维向量，则集合为空集的充要条件是，存在，使得引理8.2.Farkas引理的推论将Farkas引理推广到一般约束最优化问题中的线性化可行下降方向集合可以得到引理8.2.证明：由于等价于故根据Farkas引理可知，存在使得其中一阶最优性条件一阶最优性条件设为一般约束最优化问题问题的局部最优解，问题中的目标函数和约束函数均连续可微，且在点处约束规范条件LICQ成立，则存在Lagrange乘子，使得满足：其中为Lagrange函数.定理8.5.一阶必要条件证明：由于是问题的局部最优解，故可行，从而成立.由定理8.4可知

.由于约束规范条件LICQ成立，故从而有由线性化可行方向的定义可知，集合是空集.一阶最优性条件利用引理8.2，存在和，使得再令，可得从而成立.一阶最优性条件一阶最优性条件例8.7

计算下列约束最优化问题的所有KKT点解：该问题的Lagrange函数为KKT条件为当或，第一个条件不能满足，故而进一步由互补条件可得，将其代入方程并考虑到，最终可求得一阶最优性条件一阶最优性条件设是一般约束最优化问题的可行点，目标函数和约束函数均连续可微，且有则是问题的严格局部最优解定理8.6.一阶充分条件注：由于，因此如果把

换成，结论依然成立.证明：采用反证法.假设不是问题的严格局部最优解，则存在一个可行点序列，其中，使得：定义由于有界，故有收敛子列.不妨设该子列为，且.由可行方向的定义有.此外：从而.令，得矛盾.一阶最优性条件第8章约束最优化问题的最优性理论8.1约束最优化问题的一般形式和定义8.2约束最优化问题的一阶最优性条件8.3约束最优化问题的二阶最优性条件8.4约束最优化问题的对偶问题约束最优化问题的二阶最优性条件？约束最优化的一阶最优性条件即KKT条件得到满足时，从出发，沿任意线性化可行方向迭代会得到或对于第二种情况我们难以判断目标函数值的变化.由此我们需要二阶最优化条件解决该问题.本节假设均为二阶连续可微函数约束最优化问题的二阶最优性条件首先对于给定的线性化可行方向集和满足KKT条件的Lagrange乘子定义线性化可行方向集的子集.在点处，线性化可行方向集合的子集定义为定义8.9也称为线性化零约束集合.不难发现，等价于

由互补条件可知，对于不起作用约束有

从而由KKT条件得约束最优化问题的二阶最优性条件约束最优化问题的二阶最优性条件设为一般约束最优化问题的局部最优解，且在点处约束规范条件LICQ成立，为相应的Lagrange乘子，则定理8.7.二阶必要条件证明：由于，故由定义8.6可知存在可行点序列，和序列，使得上式可以改写为从而有结合的定义有

约束最优化问题的二阶最优性条件另一方面，对进行二阶泰勒展开由互补条件有，同时因为，可得进一步由于是局部最优解，当k充分大时，有令，得约束最优化问题的二阶最优性条件约束最优化问题的二阶最优性条件设为一般约束最优化问题的KKT点，为相应的Lagrange乘子，若则是问题的严格局部最优解定理8.8.二阶充分条件注：定理8.8表明当时，KKT点就是一般约束最优化问题的局部最优解.证明：采用反证法.假设不是问题的严格局部最优解，则存在一个可行点序列，其中，使得：定义由于有界，故有收敛子列.不妨设该子列为，且由可行方向的定义.此外由泰勒定理有从而令，得约束最优化问题的二阶最优性条件下面就的两种情况讨论.情况1：若，则存在，使得而对于其他的，有因此，可得这与矛盾.约束最优化问题的二阶最优性条件情况2：