《最优化方法》课程复习考试.doc

最优化方法复习提要第一章 最优化问题与数学预备知识1. 1 模型无约束最优化问题 约束最优化问题（） 即 其中称为目标函数，称为决策变量，称为可行域，称为约束条件1. 2 多元函数的梯度、Hesse矩阵及Taylor公式定义 设如果维向量，有则称在点处可微，并称为在点处的微分如果在点处对于的各分量的偏导数都存在，则称在点处一阶可导，并称向量为在点处一阶导数或梯度定理1 设如果在点处可微，则在点处梯度存在，并且有定义 设是给定的维非零向量，如果存在，则称此极限为在点沿方向的方向导数，记作定理2 设如果在点处可微，则在点处沿任何非零方向的方向导数存在，且，其中定义 设是上的连续函数，是维非零向量如果，使得，有（）则称为在点处的下降（上升）方向定理3 设，且在点处可微，如果非零向量，使得（）0，则是在点处的下降（上升）方向定义 设如果在点处对于自变量的各分量的二阶偏导数都存在，则称函数在点处二阶可导，并称矩阵为在点处的二阶导数矩阵或Hesse矩阵定义 设，记，如果在点处对于自变量的各分量的偏导数都存在，则称向量函数在点处是一阶可导的，并且称矩阵为在点处的一阶导数矩阵或Jacobi矩阵，简记为例2 设，求在任意点处的梯度和Hesse矩阵解 设，则，因，故得又因，则例3 设是对称矩阵，称为二次函数，求在任意点处的梯度和Hesse矩阵解 设，则，从而再对求偏导得到，于是例4 设，其中二阶可导，试求解 由多元复合函数微分法知 定理4 设，且在点的某邻域内具有二阶连续偏导数，则在点处有Taylor展式证明 设，则按一元函数Taylor公式在处展开，有从例4得知令，有根据定理1和定理4，我们有如下两个公式，1. 3 最优化的基本术语定义 设为目标函数，为可行域，（1） 若，都有，则称为在上的全局（或整体）极小点，或者说，是约束最优化问题的全局（或整体）最优解，并称为其最优值（2） 若，都有，则称为在上的严格全局（或整体）极小点（3） 若的邻域使得，都有，则称为在上的局部极小点，或者说，是约束最优化问题的局部最优解（4） 若的邻域使得，都有，则称为在上的严格局部极小点第二章 最优性条件2.1 无约束最优化问题的最优性条件定理1 设在点处可微，若是问题的局部极小点，则定义 设在处可微，若，则称为的平稳点定理2 设在点处具有二阶连续偏导数，若是问题的局部极小点，则，且半正定定理3 设在点处具有二阶连续偏导数，若，且正定，则是问题的严格局部极小点注：定理2不是充分条件，定理3不是必要条件例1 对于无约束最优化问题，其中，显然，令，得的平稳点，而且易见为半正定矩阵但是，在的任意邻域，总可以取到，使，即不是局部极小点例2 对于无约束最优化问题，其中，易知，从而得平稳点，并且显然不是正定矩阵但是，在处取最小值，即为严格局部极小点例3 求解下面无约束最优化问题，其中，解 因为，所以令，有解此方程组得到的平稳点从而，由于和是不定的，因此和不是极值点是负定的，故不是极值点，实际上它是极大点是正定的，从而是严格局部极小点定理4 设是凸函数，且在点处可微，若，则为的全局极小点推论5 设是凸函数，且在点处可微则为的全局极小点的充分必要条件是例4 试证正定二次函数有唯一的严格全局极小点，其中为阶正定矩阵证明 因为为正定矩阵，且，所以得的唯一平稳点又由于是严格凸函数，因此由定理4知，是的严格全局极小点2.2 等式约束最优化问题的最优性条件定理1 设在点处可微，在点处具有一阶连续偏导数，向量组线性无关若是问题的局部极小点，则，使得称为Lagrange函数，其中称为Lagrange乘子向量易见，这里定理2 设和在点处具有二阶连续偏导数，若，使得，并且，只要，便有，则是问题的严格局部极小点例1 试用最优性条件求解 解 Lagrange函数为，则，从而得的平稳点和，对应有和由于因此并且，有利用定理2，所得的两个可行点和都是问题的严格局部极小点2.3 不等式约束最优化问题的最优性条件定义 设，若，使得，则称为集合在点处的可行方向这里令 ，定理1 设是非空集合，在点处可微若是问题的局部极小点，则 对于 （1）其中令，其中是上述问题（1）的可行点定理2 设是问题（1）的可行点，和在点处可微，在点处连续，如果是问题（1）的局部极小点，则 ，其中定理3 设是问题（1）的可行点，和在点处可微，在点处连续，若是问题（1）的局部极小点，则存在不全为0的非负数，使 （称为Fritz John点）如果在点处也可微，则存在不全为0的非负数，使 （称为Fritz John点）例1 设 试判断是否为Fritz John点解 因为，且，所以为使Fritz John条件成立，只有才行取即可，因此是Fritz John点定理4 设是问题（1）的可行点，和在点处可微，在点处连续，并且线性无关若是问题（1）的局部极小点，则存在，使得 （称为K-T点）如果在点处也可微，则存在，使得 （称为K-T点）例2 求最优化问题 的K-T点解 因为，所以K-T条件为若，则，这与矛盾故，从而；若，则，这与矛盾故，从而；由于，且为问题的可行点，因此是K-T点定理5 设在问题（1）中，和是凸函数，是可行点，并且和在点处可微若是问题（1）的K-T点，则是问题（1）的全局极小点2.4 一般约束最优化问题的最优性条件考虑等式和不等式约束最优化问题 （1）其中并把问题（1）的可行域记为定理1 设为问题（1）的可行点，和在点处可微，在点处具有一阶连续偏导数，在点处连续，并且向量组线性无关若是问题（1）的局部极小点，则 ，这里，定理2 设为问题（1）的可行点，和在点处可微，在点处具有一阶连续偏导数，在点处连续若为问题（1）的局部极小点，则存在不全为0的数和，且，使 （称为Fritz John点）若在点处也可微，则存在不全为0的数和，且，使 （称为Fritz John点）例1 设 试判断是否为Fritz John点解 ，且，且，因此为使Fritz John条件成立，只有才行所以取，即知是Fritz John点定理3 设为问题（1）的可行点，和在点处可微，在点处具有一阶连续偏导数，在点处连续，且向量组线性无关若是问题（1）的局部极小点，则存在数和，使 （称为K-T点）如果在点处也可微，则存在数和，使 （称为K-T点）令 ，称与为广义Lagrange乘子向量或K-T乘子向量令为广义Lagrange函数称为广义Lagrange函数则K-T条件为定理4 设在问题（1）中，和是凸函数，是线性函数，是可行点，并且和在点处可微若是问题（1）的K-T点，则是问题（1）的全局极小点例2 求解最优化问题 解 广义Lagrange函数为因为，所以K-T条件及约束条件为下面分两种情况讨论（1） 设，则有由此可解得，但不是可行点，因而不是K-T点（2） 设，则有由此可得，解得或。从而或于是或（这与矛盾）或由此可知是问题的K-T点，但不是问题的K-T点易见，是上的凸函数，是上的凹函数，是线性函数，因此由定理4知，是问题的全局最优解定理5 设为问题（1）的可行点，和在点处具有二阶连续偏导数，并且存在乘子向量和使K-T条件成立，即若对于任何满足的向量，都有，则是问题（1）的严格局部极小点例3 求解最优化问题 其中常数解 该问题的广义Lagrange函数为因为 所以问题的K-T条件及约束条件为由第1式、第3式知，从而由第二式解得于是再由第1式知，且，即得，从而，解得，于是所以是问题的K-T点又由于在点处关于的Hesse矩阵是一个阶对角矩阵，其对角线上第个元素为，因此是正定矩阵根据定理5，为问题的严格局部极小点第三章 常用优化算法介绍3.1 一维搜索 给定，令定义 如果求得步长，使得 （3.1.1）则称这样的一维搜索为最优一维搜索或精确一维搜索叫做最优步长定理1 对于问题，设是可微函数，是从出发沿方向作最优一维搜索得到的，则有 定义 如果选取，使目标函数沿方向取得适当的可接受的下降量，即使得下降量是我们可接受的，则称这样的一维搜索为可接受一维搜索或非精确一维搜索定义 设，并且如果对于有，那么称是问题的搜索区间定义 设，若存在，使得在上严格单调减少，在上严格单调增加，则称是的单谷区间，是上的单谷函数或单峰函数定理2 设为的单谷区间，且，那么（1）若，则是的单谷区间；（2）若，则是的单谷区间算法3-1（进退法）Step1 选取初始数据。给定初始点，初始步长，加倍系数（一般取），计算，置Step2 试探令，计算Step3 比较目标函数值若，转Step4，否则，转Step5Step4 加步探索令，转Step2Step5 反向搜索若，转换搜索方向，转Step2；否则，停止迭代令 输出搜索区间3.2 0.618法与Fibonacci法考虑假定的一个搜索区间已确定，并设在上为单谷函数算法3-2（0.618法）Step1 选取初始数据确定初始搜索区间和允许误差Step2 计算最初两个试探点：，求出，并置Step3 检查？是，停止计算，输出；否则，转Step4Step4 比较函数值若，转Step5；若，转Step6Step5 向左搜索令并计算，转Step7Step6 向右搜索令并计算，转Step7Step7 置，转Step3定义 Fibonacci数是指满足下述条件的数列： （3.2.1）用数学归纳法可以证明，Fibonacci数可由下式表示： （3.2. 2）算法3-3（Fibonacci法）Step1 选取初始数据给定初始搜索区间和允许误差，辨别系数 ，求搜索次数，使Step2 计算最初两个试探点：，求函数值和，并置Step3 检查？是，转Step4；否，转Step5Step4 向左搜索令并计算和，转Step6Step5 向右搜索令并计算和，转Step6Step6 置，若，转Step3；若，转Step7Step7 令，计算和。若，则令；否则，令，停止计算，极小点含于区间3.3 Newton法考虑假定具有三阶连续导数算法3-4（Newton法）Step1 给定初始点，允许误差，置Step2 检查？是，输出，停止计算；否，转Step3Step3 计算点 ，置，转Step23.4 最速下降法考虑无约束最优化问题 ， （3.4.1）其中具有一阶连续偏导数算法3-5（最速下降法）Step1 选取初始数据选取初始点，给定允许误差，令Step2 检查是否满足终止准则计算，若，迭代终止，为问题（3.4.1）的近似最优解；否则，转Step3Step3 进行一维搜索取，求和，使得，令，返回Step2特别地，考虑 ， （3.4.2）其中为正定矩阵，设第次迭代点为，从点出发沿作一维搜索，得，其中为最优步长根据定理3.1.1，有而，所以，从而，而正定，即，故由上式解出 （3.4.3）于是 （3.4.4）这是最速下降法用于问题（3.4.2）的迭代公式例1 用最速下降法求解问题 ， （3.4.5）其中取初始点，允许误差解 问题（3.4.5）中的是正定二次函数，且在点处的梯度第一次迭代：令搜索方向，从点出发沿作一维搜索，由（3.4.3）式和（3.4.4）式有，第二次迭代：令，从点出发沿作一维搜索，按（3.4.4）式得第三次迭代：令，按（3.4.4）式求得第四次迭代：令，按（3.4.4）式求得第五次迭代：令，按（3.4.4）式求得此时，已满足精度要求，故得问题（3.4.5）的近似最优解实际上问题（3.4.5）的最优解为3.5 Newton法算法3-6（Newton法）Step1 选取初始数据选取初始点，给定允许误差，令Step2 检查是否满足终止准则计算，若，迭代终止，为问题（3.4.1）的近似最优解；否则，转Step3Step3 构造Newton方向计算，取Step4 求下一个迭代点令，返回Step2例2 用Newton法求解问题（3.4.5），仍取初始点，允许误差解 ，故，由于 ，迭代结束，得为问题（3.4.5）的最优解算法3-7（阻尼Newton法）Step1 选取初始数据选取初始点，给定允许误差，令Step2 检查是否满足终止准则计算，若，迭代终止，为问题（3.4.1）的近似最优解；否则，转Step3Step3 构造Newton方向计算，取Step4 进行一维搜索求和，使得，令，返回Step2例3 用阻尼Newton法求解下面问题：， （3.5.1）其中取初始点，允许误差解 第一次迭代：，故 ，于是，Newton方向 ，从出发沿作一维搜索，即求的最优解，得到令第二次迭代：，从出发沿作一维搜索，即求的最优解，得到令此时，得问题（3.5.1）的最优解为，这是惟一的最优解3.6 共轭梯度法定义 设为正定矩阵若中的向量组满足，则称是共轭的算法3-8（共轭方向法）给定一个正定矩阵Step1 选取初始数据选取初始点，给定允许误差Step2 选取初始搜索方向计算，求出，使，令Step3 检查是否满足终止准则若，迭代终止；否则，转Step4Step4 进行一维搜索求和，使得，Tep5 选取搜索方向求使，令，返回Step3如果用共轭方向法求解正定二次函数的无约束最优化问题， （3.6.1）其中为正定矩阵，（此时算法中的正定矩阵应与二次函数的正定矩阵一致），那么容易推出迭代公式为 （3.6.2）对于问题（3.4.1）的求解，我们还有如下一些方法Fletcher-Reeves（FR）公式：；Dixon-Myers（DM）公式：；Polak-Ribiere-Polyak（PRP）公式：算法3-9（FR共轭梯度法）Step1 选取初始数据选取初始点，给定允许误差Step2 检查是否满足终止准则计算，若，迭代终止，为（3.4.1）的近似最优解；否则，转Step3Step3 构造初始搜索方向计算Step4 进行一维搜索求和，使得，令，返回Step2Tep5 检查是否满足终止准则计算，若，迭代终止，为（3.4.1）的近似最优解；否则，转Step6Step6 检查迭代次数若，令，返回Step3；否则，转Step7Step7 构造共轭方向用FR公式取，令，返回Step4 注意，如果算法3-9的Step7中的形式改为DM公式或PRP公式，则分别得到DM共轭梯度法和PRP共轭梯度法例4 用FR共轭梯度法求解问题（3.5.1），仍取初始点，允许误差解 因为，所以令，从出发，沿进行一维搜索，得从而由FR公式有 ，因此，新的搜索方向为从出发，沿进行一维搜索，得此时得问题（3.5.1）的最优解为3.7 坐标轮换法考虑无约束最优化问题 ， （3.7.1）其中算法3-10（坐标轮换法）Step1 选取初始数据选取初始点，给定允许误差，令Step2 进行一维搜索从出发，沿坐标轴方向进行一维搜索，求和，使得，Step3 检查迭代次数若，转Step4；否则，令，返回Step2Step4 检查是否满足终止准则若，迭代终止，得为问题（3.7.1）的近似最优解；否则，令，返回Step2例4 用坐标轮换法求解问题 ， （3.7.2）其中取初始点，允许误差解 从点出发沿进行一维搜索，易得；从点出发沿进行一维搜索，得；再从点出发沿进行一维搜索，得；从点出发沿进行一维搜索，得；再从点出发沿进行一维搜索，得；从点出发沿进行一维搜索，得；再从点出发沿进行一维搜索，得；从点出发沿进行一维搜索，得；迭代终止，得问题（3.7.2）的近似最优解为其实问题（3.7.2）的最优解为3.8 Powell法算法3-11（Powell法）Step1 选取初始数据选取初始点，个线性无关的初始搜索方向，给定允许误差，令Step2 进行基本搜索令，依次沿进行一维搜索对一切，记，Step3 检查是否满足终止准则取加速方向，若，迭代终止，得为问题的近似最优解；否则，转Step4Step4 确定搜索方向按 （3.8.1）确定，若 （3.8.2）成立，转Step5；否则，转Step6Step5 调整搜索方向从点出发沿方向作一维搜索求出，使得令，再令，返回Step2Step6 不调整搜索方向令，返回Step2例5 用Powell法求解问题（3.7.2），仍取初始点，初始搜索方向组，给定允许误差解 第一次迭代：同例1一样，得，。因为，所以要确定调整方向由于，按（3.8.1）式有，因此，并且又因，故（3.8.2）式不成立于是，不调整搜索方向组，并令第二次迭代：取，从点出发沿作一维搜索，得接着从点出发沿方向作一维搜索，得由此有加速方向因为，所以要确定调整方向因，故按（3.8.1）式易知，并且由于，因此（3.8.2）式成立。于是，从点出发沿作一维搜索，得。同时，以替换，即下一次迭代的搜索方向组取为第三次迭代：取，类似地可求得，因为 ，所以迭代终止，得问题（3.7.2）的最优解为 3.9罚函数法一、外法函数法考虑约束非线性最优化问题 （3.9.1）其中都是定义在上的实值连续函数记问题（3.9.1）的可行域为对于等式约束问题 （3.9.2）定义罚函数，其中参数是很大的正常数这样，可将问题（3.9.2）转化为无约束问题 （3.9.3）对于不等式约束问题 （3.9.4）定义罚函数，其中是很大的正数这样，可将问题（3.9.4）转化为无约束问题 （3.9.5）对于一般的约束最优化问题（3.9.1），定义罚函数 ，其中是很大的正数，具有下列形式：和是满足下列条件的实值连续函数：函数和的典型取法为，其中和是给定的常数，通常取作1或2这样，可将约束问题（3.9.1）转化为无约束问题 ， （3.9.6）其中是很大的正数，是连续函数算法3-12（外罚函数法）Step1 选取初始数据给定初始点，初始罚因子，放大系数，允许误差，令Step2 求解无约束问题以为初始点，求解无约束问题 ， （3.9.7）设其最优解为Step3 检查是否满足终止准则若，则迭代终止，为约束问题（3.9.1）的近似最优解；否则，令，返回Step2二、内罚函数法对于不等式约束问题（3.9.4），其可行域的内部为了保持迭代点始终含于，我们引入另一种罚函数，其中是很小的正数，是上的非负实值连续函数，当点趋向可行域的边界时， 显然，罚函数的作用是对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外，因此也称为障碍函数 的两种常用的形式为，及分别称为倒数障碍函数和对数障碍函数算法3-13（内罚函数法或SUMT内点法）Step1 选取初始数据给定初始内点，初始参数，缩小系数，允许误差，令Step2 求解无约束问题以为初始点，求解无约束问题 （3.9.8）设其最优解为Step3 检查是否满足终止准则若，则迭代终止，为约束问题（3.9.4）的近似最优解；否则，令，返回Step2附录5 最优化方法复习题1、设是对称矩阵，求在任意点处的梯度和Hesse矩阵解 2、设，其中二阶可导，试求解 3、设方向是函数在点处的下降方向，令，其中为单位矩阵，证明方向也是函数在点处的下降方向证明由于方向是函数在点处的下降方向，因此，从而，所以，方向是函数在点处的下降方向4、是凸集的充分必要条件是的一切凸组合都属于证明充分性显然下证必要性设是凸集，对用归纳法证明当时，由凸集的定义知结论成立，下面考虑时的情形令，其中，且不妨设（不然，结论成立），记，有，又，则由归纳假设知，而，且是凸集，故5、设为非空开凸集，在上可微，证明：为上的凸函数的充要条件是证明必要性设是上的凸函数，则及，有，于是 ，因为开集，在上可微，故令，得，即充分性若有，则，取，从而，将上述两式分别乘以和后，相加得，所以为凸函数6、证明：凸规划的任意局部最优解必是全局最优解证明 用反证法设为凸规划问题的局部最优解，即存在的某个邻域，使若不是全局最优解，则存在，使由于为上的凸函数，因此，有当充分接近1时，可使，于是，矛盾从而是全局最优解7、设为非空凸集，是具有一阶连续偏导数的凸函数，证明：是问题的最优解的充要条件是：证明 必要性若为问题的最优解反设存在，使得，则是函数在点处的下降方向，这与为问题的最优解矛盾故充分性若反设存在，使得，因为凸集，在上可微，故令，得，这与已知条件矛盾，故是问题的最优解8、设函数具有二阶连续偏导数，是的极小点的第次近似，利用在点处的二阶Taylor展开式推导Newton法的迭代公式为证明由于具有二阶连续偏导数，故且是对称矩阵，因此是二次函数为求的极小点，可令，即，若正定，则上式解出的的平稳点就是的极小点，以它作为的极小点的第次近似，记为，即，这就得到了Newton法的迭代公式.9、叙述常用优化算法的迭代公式（1）0.618法的迭代公式：（2）Fibonacci法的迭代公式：（3）Newton一维搜索法的迭代公式： （4）最速下降法用于问题的迭代公式：（5）Newton法的迭代公式：（6）共轭方向法用于问题的迭代公式：10、已知线性规划：（1）用单纯形法求解该线性规划问题的最优解和最优值；（2）写出线性规划的对偶问题；（3）求解对偶问题的最优解和最优值解 （1）引进变量，将给定的线性规划问题化为标准形式：311100601-220101011*-100120-21-1000020210-1403000125011-100120-30000-1-20所给问题的最优解为，最优值为（2）所给问题的对偶问题为： （1）（3）将上述问题化成如下等价问题：引进变量，将上述问题化为标准形式： （2）-3-1-11002-12-1*010-1-1-210011-60-10-200000-2-301-1031-210101