运筹学——非线性规划

《运筹学——非线性规划》由会员分享，可在线阅读，更多相关《运筹学——非线性规划（23页珍藏版）》请在金锄头文库上搜索。

1、第六章非线性规划第六章非线性规划 运 筹 学 运 筹 学 Prof. 梁军梁军0571-879538836.1 非线性规划问题与数学模型6.1 非线性规划问题与数学模型先看两个例子：先看两个例子：如果目标函数或约束条件方程中存在任何非线性因子存在任何非线性因子，则问题为非线性规划非线性规划。非线性规划在工程、军事、经济等许多领域都得到广泛的应用。1 非线性规划的提法非线性规划的提法例例 2-8 设平面上有设平面上有 m 个点，找覆盖这个点，找覆盖这 m 个点的最小园 盘。个点的最小园 盘。 解解 设设 m 个点为个点为,1,2,ip im， 则平面上任一点， 则平面上任一点x到这到这 m 个点

2、的距离最大者满足个点的距离最大者满足 1( )maxii mf xxp （2-28） 则以则以x为园心，为园心，( )f x为半径的园盘必覆盖这为半径的园盘必覆盖这 m 个点，于是问题 转化为求解最小半径的园盘问题个点，于是问题 转化为求解最小半径的园盘问题 1minmaxii mxp （2-29） 这是一个无约束的非线性规划问题。这是一个无约束的非线性规划问题。 非线性规划的一般形式为非线性规划的一般形式为 min( )f x(2-33) . .( )0,1,2, ( )0,1,2,ijstg xim hxjl (2-34) 式中， 目标函数式中， 目标函数( )f x， 不等式约束条件，

3、不等式约束条件( )ig x和等式约束条件和等式约束条件( )jhx至少一个是非线性函数。当不存在约束条件，即决策变量至少一个是非线性函数。当不存在约束条件，即决策变量x可取 任意点时，可取 任意点时， min( )f x(2-35) 称为无约束非线性规划问题。称为无约束非线性规划问题。 非 线 性 规 划 的 约 束 条 件 有 时 写 成 域 约 束 形 式 ， 令非 线 性 规 划 的 约 束 条 件 有 时 写 成 域 约 束 形 式 ， 令|( )0,1,2,;( )0,1,2,ijSx g xim hxjl,称称 S 为可行域，为可行域，S 中的点为可行点，上述约束非线性规划问题（

4、中的点为可行点，上述约束非线性规划问题（2.33-2.34）等价于）等价于min( ) . .f x stxS (2-36) 而无约束非线性规划问题等价于而无约束非线性规划问题等价于 min( ),nf x x(2-37) n是是 n 维欧氏空间。维欧氏空间。 非线性规划问题的非线性规划问题的求解一般通过两种途径求解一般通过两种途径来实现，一种是基于目标函数和约束条件的函数分析性质直接加以求解的来实现，一种是基于目标函数和约束条件的函数分析性质直接加以求解的解析解法解析解法，多适用于具有良好函数解析性质的少数非线性规划问题；另一种是基于循环迭代算法的，多适用于具有良好函数解析性质的少数非线性规

5、划问题；另一种是基于循环迭代算法的数值求解数值求解法，适用于大部分非线性规划问题。在进一步讨论法，适用于大部分非线性规划问题。在进一步讨论解析解法解析解法之前，先引入非线性规划问题之前，先引入非线性规划问题全局最优解全局最优解和和局部最优解局部最优解的定义。的定义。2 非线性规划的基本性质非线性规划的基本性质定义定义 2-1 全局最优解全局最优解 设设( )f x为目标函数，为目标函数，S 为可行域，为可行域，xS。若对每一个。若对每一个xS都有都有*( )()f xf x,则称则称*x为极小化问题（为极小化问题（2.3.6）的全局最优解（最小） 。定义）的全局最优解（最小） 。定义 2-2

6、局部最优解局部最优解 设设( )f x为目标函数，为目标函数，S 为可行域，为可行域，xS。若存在。若存在*x的一个的一个邻域邻域S，使得对每一个，使得对每一个xS都有都有*( )()f xf x,则称则称*x为极小化问题（为极小化问题（2-36）的局部最优解（最小） 。）的局部最优解（最小） 。 凸规划是非线性规划中一种重要的特殊情况，具有许多良好 的解析性质，可以用解析解法求解。凸规划是非线性规划中一种重要的特殊情况，具有许多良好 的解析性质，可以用解析解法求解。 定义定义 2-3 设设 S 为为n中的一个集合， 若对中的一个集合， 若对 S 中任意两点，连接它们的线段仍属于中任意两点，连

7、接它们的线段仍属于 S，即对，即对 S 中任意两点中任意两点12,x x及每个实数及每个实数 1 , 0，都有，都有 12(1)xxS则称则称 S 为凸集，为凸集，12(1)xx称为称为1x和和2x的凸组合的凸组合 定义 2-4 设 S 为定义 2-4 设 S 为n中的非空凸集，中的非空凸集，f是定义在 S 上的实函数。如果对任意的是定义在 S 上的实函数。如果对任意的12,x xS 及每个数S 及每个数（0，1） ，都有（0，1） ，都有1212(1)( )(1) ()fxxf xf x，则称，则称f为 S 上凸函数。如果对任意相异的为 S 上凸函数。如果对任意相异的12,x xS 及每个数

8、S 及每个数（0，1） ，都有（0，1） ，都有1212(1)()(1) ()fxxf xf x，则称，则称f为 S 上的严格凸函数。如果为 S 上的严格凸函数。如果f为 S 上的凸函数，则称为 S 上的凸函数，则称f为 S 上的凹函为 S 上的凹函数。 定义 2-5 若式 （2-33） 的定义 2-5 若式 （2-33） 的( )f x是凸函数， 式 （2-34） 的是凸函数， 式 （2-34） 的( )ig x是凹函数，是凹函数， ( )jhx是线性函数， 则求凸函数在凸集上的极小点问题称为凸规划。 凸规划的解析解具有以下性质。 引理 2-1 设 S 是是线性函数， 则求凸函数在凸集上的极

9、小点问题称为凸规划。 凸规划的解析解具有以下性质。 引理 2-1 设 S 是n中的凸集，中的凸集，f是定义在是定义在 S 上的凸函数， 则上的凸函数， 则f在 S 的内部连续。 引理 2-2 设在 S 的内部连续。 引理 2-2 设f是一个凸函数，是一个凸函数，xn,在,在x处处( )f x取有限 值，则取有限 值，则f在在x处沿任何方向都存在右侧导数和左侧导数（包括 ） 。处沿任何方向都存在右侧导数和左侧导数（包括 ） 。 定义定义 2-6 设函数设函数( ),nf x x存在一阶偏导数，则称向量存在一阶偏导数，则称向量 12( ),Tnffff xxxx为为( )f x在点在点12,T n

10、xx xx处的梯度。处的梯度。 为方便非线性规划的求解，还要引入函数梯度和为方便非线性规划的求解，还要引入函数梯度和Hesse矩阵概念。矩阵概念。定义定义 2-7 设函数设函数( )f x存在二阶偏导数，则称矩阵存在二阶偏导数，则称矩阵 2222 12112222 21222222 12( )nnnnnfff x xx xxfff H xxxxxxfff xxxxx 为为( )f x在点在点12,T nxx xx处的处的 Hesse 矩阵。矩阵。 由梯度和由梯度和 Hesse 矩阵的上述定义，无约束非线性规划问题 （矩阵的上述定义，无约束非线性规划问题 （2.37）的局部极小点的解析解可由以下

11、定理求出。）的局部极小点的解析解可由以下定理求出。 引理引理 2-3 局部极小点的一阶必要条件局部极小点的一阶必要条件 设函数设函数( )f x在点在点*x处可微，若处可微，若*x是局部极小点，则梯度是局部极小点，则梯度0)(xf。 引理引理 2-4 局部极小点的二阶必要条件局部极小点的二阶必要条件 设函数设函数( )f x在点在点*x处二次可微，若处二次可微，若*x是局部极小点，则梯度是局部极小点，则梯度0)(xf，并且，并且 Hesse 矩阵矩阵*()H x是半正定的。是半正定的。 上述条件均非充分条件，当上述条件均非充分条件，当x满足这些条件时无法判定满足这些条件时无法判定x是 否确为极

12、小点，要实现这一目的需要是 否确为极小点，要实现这一目的需要 Hesse 矩阵的正定性条件。矩阵的正定性条件。3 非线性规划的解析求解非线性规划的解析求解定理定理 2-2 设函数设函数( )f x在点在点*x处二次可微，若梯度处二次可微，若梯度0)(xf且且 Hesse 矩阵矩阵*()H x正定，则正定，则*x是局部极小点。是局部极小点。 应该指出，解析法求解非线性规划问题，不论是无约束还是有约束，一般均只能求解低维空间中较为简单的问题，对于较复杂的非线性规划问题，更有效的是数值迭代算法对于较复杂的非线性规划问题，更有效的是数值迭代算法。4 非线性规划问题的数值求解非线性规划问题的数值求解4

13、有约束非线性规划问题的求解有约束非线性规划问题的求解对于有约束的非线性规划问题，通常用以下三个方法三个方法处处理其约束条件进而实现数值迭代求解：第一种方法是将迭代点序列严格控制在可行域内将迭代点序列严格控制在可行域内，从而执行的迭代过程实际上为无约束优化过程；第二种方法称为序列无约束优化方法序列无约束优化方法，简称SUMT方法。该方法通过将约束项处理成制约函数项加入到目标函数中形成新的广义目标函数将约束项处理成制约函数项加入到目标函数中形成新的广义目标函数，从而将有约束问题化为广义目标函数下的无约束问题，再利用前述的无约束优化迭代算法求解。拉格朗日乘子法就是这类方法的一个特例。第三种是在迭代点附近的序列线性化或序列二次函数逼近方法在迭代点附近的序列线性化或序列二次函数逼近方法，通过运用迭代点附近的台劳展开，将有约束的非线性规划近似为极易求解的线性规划或二次规化以实现迭代求解。序列无约束优化方法中常用的制约函数基本上有两类基本上有两类，一类为罚函数罚函数，又，又称为外点法称为外点法，一类为障碍函数，又称为内点法障碍函数，又称为内点法。本课程不再介绍非线性规划的具体求解算法，相关内容可在进一步的课程（如研究生阶段的运筹学）中学习。作业：1）练习6.2，只列写模型2）练习6.5，只列写模型谢谢！谢谢！