《非线性规划53080》由会员分享，可在线阅读，更多相关《非线性规划53080（59页珍藏版）》请在金锄头文库上搜索。
1、非线性规划非线性规划Non-linear Programming2021/6/161非线性规划非线性规划v基本概念基本概念v凸函数和凸规划凸函数和凸规划v一维搜索方法一维搜索方法v无约束最优化方法无约束最优化方法v约束最优化方法约束最优化方法2021/6/162基本概念基本概念v非线性规划问题非线性规划问题v非线性规划方法概述非线性规划方法概述2021/6/163非线性规划问题非线性规划问题例例1曲线的最优拟合问题曲线的最优拟合问题2021/6/164例例2构件容积问题构件容积问题2021/6/165数学规划数学规划约束集或可行域约束集或可行域MP的可行解或可行点的可行解或可行点2021/6/
2、166向量化表示向量化表示当当p=0,q=0时，称为时，称为无约束非线性规无约束非线性规划划或者或者无约束最优化问题无约束最优化问题。否则，称为否则，称为约束非线性规划约束非线性规划或者或者约束约束最优化问题最优化问题。2021/6/167最优解和极小点最优解和极小点2021/6/168非线性规划方法概述非线性规划方法概述不可行方向不可行方向2021/6/169非线性规划基本迭代格式非线性规划基本迭代格式迭代法的基本格式迭代法的基本格式2021/6/1610常用停止规则常用停止规则2021/6/1611凸函数和凸规划凸函数和凸规划q凸函数及其性质凸函数及其性质q凸规划及其性质凸规划及其性质20
3、21/6/1612凸函数及其性质凸函数及其性质2021/6/16131. 1. 凸函数及其性质凸函数及其性质(a) (a) 凸函数凸函数 (b)(b)凹函数凹函数2021/6/16141. 1. 凸函数及其性质续一凸函数及其性质续一2021/6/16152021/6/16162021/6/1617凸规划及其性质凸规划及其性质约束集如果如果(MP)的约束集的约束集X是凸集，目标函数是凸集，目标函数f是是X上的凸函数，则上的凸函数，则(MP)叫做叫做非线性凸规划非线性凸规划，或简称为或简称为凸规划凸规划。2021/6/1618定理定理4.2.6凸规划的任一局部最优解都是它凸规划的任一局部最优解都是
4、它的整体最优解。的整体最优解。2021/6/1619凸规划及其性质凸规划及其性质- -例题例题例例 4.2.3 4.2.3 验证下列（验证下列（MPMP）是凸规划）是凸规划2021/6/1620一维搜索方法一维搜索方法精确一维搜索方法精确一维搜索方法0.618法法Newton法法非精确一维搜索方法非精确一维搜索方法Goldstein法法Armijo法法2021/6/16210.618法（近似黄金分割法）法（近似黄金分割法）2021/6/16220.618法例题法例题例4.3.1 用0.618法求解 的单谷区间为0,3，2021/6/16230.618法算法分析法算法分析在在0.6180.618
5、法法中中每每次次迭迭代代搜搜索索区区间间按按常常比比例例缩缩小小，所所以以要要使使给给定定的的单单谷谷区区间间减减少少到到所所要要求求的的区区间间精精度度，需需要要的的迭迭代代次次数数是是可可以以预预估估的的。另另外外若若每每次次每每次次迭迭代代按按不不同同比比例例缩缩小小搜搜索索区区间间，但但仍仍要要求求每每次次迭迭代代只只计计算算一一个个函函数数值值，且且希希望望在在搜搜索索点点个个数数相相同同的的情情况况下下使使最最终终的的搜搜索索区区间间的的长长度度最最小小，按按此此要求设计的方法是要求设计的方法是FibonacciFibonacci法法2021/6/16242. Newton法法Ne
6、wtonNewton法思想法思想2021/6/1625Newton法法2021/6/1626Newton法法- -算法分析算法分析从从任任意意初初始始点点开开始始的的NewtonNewton法法产产生生的的点点列列，一一般般来来说说不不一一定定收收敛敛，即即使使收收敛敛，其其极极限限点也不一定是点也不一定是 的极小点，只能保证它是的极小点，只能保证它是 的的驻驻点点。但但当当初初始始点点充充分分接接近近 时时，可可以证明以证明NewtonNewton法是收敛的。法是收敛的。 2021/6/1627Goldstein法法2021/6/1628Goldstein法思想法思想2021/6/1629G
7、oldstein法步骤法步骤2021/6/1630Goldstein法法- -例题例题例例4.3.3 4.3.3 用用GoldsteinGoldstein法求解法求解 取取2021/6/1631Armijo法法2021/6/1632无约束最优化方法无约束最优化方法v无约束问题的最优性条件无约束问题的最优性条件v最速下降法最速下降法v共轭方向法共轭方向法2021/6/1633无约束问题的最优化条件无约束问题的最优化条件2021/6/1634最速下降法最速下降法2021/6/1635最速下降法最速下降法- -基本思想基本思想2021/6/1636最速下降法最速下降法- -计算步骤计算步骤2021/
8、6/1637最速下降法最速下降法- -例题例题2021/6/1638最速下降法最速下降法- -算法分析算法分析随着迭代次数的增加，收敛速度越来越慢随着迭代次数的增加，收敛速度越来越慢最速下降法的相邻两个搜索方向是彼此正最速下降法的相邻两个搜索方向是彼此正交的交的具有全局收敛性具有全局收敛性2021/6/1639最速下降法最速下降法- -例题例题2021/6/1640最速下降法最速下降法- -算法分析算法分析随着迭代次数的增加，收敛速度越来越慢随着迭代次数的增加，收敛速度越来越慢最速下降法的相邻两个搜索方向是彼此正最速下降法的相邻两个搜索方向是彼此正交的交的具有全局收敛性具有全局收敛性2021/
9、6/16413 3 共轭方向法共轭方向法共轭方向法共轭方向法2021/6/1642共轭方向法续共轭方向法续2021/6/1643共轭方向法共轭方向法- -步骤步骤F-R法步骤2021/6/1644共轭方向法共轭方向法- -例题例题2021/6/1645共轭方向法共轭方向法- -算法分析算法分析F-R法具有二次终止性。对一般可微函数的法具有二次终止性。对一般可微函数的无约束优化问题，当函数满足一定的条件无约束优化问题，当函数满足一定的条件时，可以证明时，可以证明F-RF-R方法具有全局收敛性其收方法具有全局收敛性其收敛速度比最速下降法快敛速度比最速下降法快F-R法强烈依赖于一位搜索的精确性法强烈
10、依赖于一位搜索的精确性2021/6/1646约束最优化方法约束最优化方法v约束最优化问题的最优化条件约束最优化问题的最优化条件v简约梯度法简约梯度法v惩罚函数法惩罚函数法其中其中(MP)2021/6/1647约束最优化问题的最优化条件约束最优化问题的最优化条件令令K-T条件条件2021/6/16482021/6/1649简约梯度法简约梯度法(4.5.12)2021/6/1650Wolfe法步骤法步骤2021/6/1651惩罚函数法惩罚函数法思想思想：利用问题中的约束函数做出适当的带有参数的惩：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出罚函数，然后
11、在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把带参数的增广目标函数，把(MP)问题的求解转换为求解问题的求解转换为求解一系列无约束非线性规划问题。一系列无约束非线性规划问题。罚函数法罚函数法障碍函数法障碍函数法2021/6/1652罚函数法罚函数法设法适当地加大不可行点处对应的目标函数值，使设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。不可行点不能成为相应无约束极小化问题的最优解。罚函数罚函数2021/6/1653实际应用中，选取一个实际应用中，选取一个递增且趋于无穷的正罚递增且趋于无穷的正罚函数参数列函数参数列其中其中*2021/6/1654罚函数法计算步骤罚函数法计算步骤2021/6/1655障碍函数法障碍函数法在可行区域的边界上筑起一道在可行区域的边界上筑起一道“墙墙”，当迭代点靠近，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最边界时，所构造的增广目标函数值陡然增大，于是最优点就被优点就被“挡挡”在可行区域内部了。在可行区域内部了。2021/6/1656构造障碍函数构造障碍函数2021/6/1657障碍函数法步骤障碍函数法步骤2021/6/1658 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
