运筹学无约束非线性规划约束非线性优化

运筹学无约束非线性规划约束非线性优化第一页，共一百零二页，编辑于2023年，星期二

凸函数定义：设

为定义在n维欧氏空间E中某个凸集R上的函数，若对任何实数

以及R中的任意两点

和

，恒有：则称

为定义在R上的凸函数。则称

为定义在R上的严格凸函数。第二页，共一百零二页，编辑于2023年，星期二凸函数性质：性质1：设

为定义在凸集R上的凸函数，则对任意实数,函数也是定义在R上的凸函数。性质2：设

和为定义在凸集R上的凸函数，则其和,任是定义在R上的凸函数。第三页，共一百零二页，编辑于2023年，星期二凸函数性质：性质3：设

为定义在凸集R上的凸函数，则对任意实数,集合：是凸集。称为水平集。第四页，共一百零二页，编辑于2023年，星期二凸函数性质：推论：有限个凸函数的非负线性组合：仍为凸函数。第五页，共一百零二页，编辑于2023年，星期二函数凸性的判别：一阶条件:设R为n维欧氏空间En上的开凸集，

在R上具有一阶连续偏导数，则

为R上的凸函数的充要条件是，对任意两个不同点

和

，恒有：第六页，共一百零二页，编辑于2023年，星期二函数凸性的判别：二阶条件:设R为n维欧氏空间En上的开凸集，

在R上具有二阶连续偏导数，则

为R上的凸函数的充要条件是：的海赛矩阵在R上处处半正定。第七页，共一百零二页，编辑于2023年，星期二凸函数的极值：定理：设

为定义在凸集R上的凸函数，则它的任一极小值就是它在R上的最小点（全局极小点），而且它的极小点形成一个凸集。定理：设

为定义在凸集R上的可微凸函数，若存在点

，使得对于所有的有：则

是

的R上的最小点（全局极小点）第八页，共一百零二页，编辑于2023年，星期二凸规划：定义：若

为凸集，

是R上的凸函数，则称规划：为凸规划定义：若规划问题：其中为凸函数，为凹函数（或为凸函数），则该规划问题为凸规划。第九页，共一百零二页，编辑于2023年，星期二练习判断下述非线性规划是否是凸规划

s.t.第十页，共一百零二页，编辑于2023年，星期二下降迭代算法：迭代法的基本思想：为了求函数

的最优解，首先给定一个初始估计

，然后按照某种算法找出比

更好的解

；1.对于极小化问题：2.对于极大化问题：如此可以得到一个解的序列

。若这个解序列有极限

，即：则称它收敛于第十一页，共一百零二页，编辑于2023年，星期二下降迭代算法：下降迭代算法的步骤：选定某一初始点

，令k：=0；确定搜索方向

；从

出发，沿方向

求步长

，以产生下一个迭代点

；检查得到的新点x是否为极小值点或近似极小值点。若是，停止迭代。否则，令k：=k+1，回2步继续迭代。第十二页，共一百零二页，编辑于2023年，星期二确定最优步长求以

为变量的一元函数

的极小值点

（一维搜索）一维搜索重要性质：在搜索方向上所得最优点处的梯度和该搜索方向正交。第十三页，共一百零二页，编辑于2023年，星期二第十四页，共一百零二页，编辑于2023年，星期二迭代终止准则绝对误差：相对误差：目标函数梯度：

为事先给定的足够小的正数。第十五页，共一百零二页，编辑于2023年，星期二一维搜索一维搜索是所有非线性规划迭代算法都要遇到的共同问题，而且相对于构造搜索方向问题比较简单。因此我们在这一部分先介绍求解一维搜索问题的方法。主要有斐波那契法、0.618法、插值法、求根法（二分法）等。一维搜索主要针对单峰函数。什么是单峰函数？第十六页，共一百零二页，编辑于2023年，星期二单峰函数及其性质定义:设函数：，闭区间，若存在点，使在上严格递减，在上严格递增，则称函数为上的单峰函数，为的单峰区间，如下图第十七页，共一百零二页，编辑于2023年，星期二单峰区间和单峰函数具有如下性质：若是单峰区间上的单峰函数，极小点为，在中任取两点，，且，则（1）当时，；（2）当时，。这个性质说明了，经过函数值的比较后，我们可以把单峰函数的单峰区间进行缩小，或者或者，而仍在区间内。

第十八页，共一百零二页，编辑于2023年，星期二

二分法步骤如下：第一步：选取初始数据，确定初始搜索区间，给出最后区间精度。第二步：计算初始试点：，计算，并令k:=0。第三步：如果，则令ak+1=tk,bk+1=bk,tk+1=(ak+1+bk+1)/2；否则，

ak+1=ak,bk+1=tk,tk+1=(ak+1+bk+1)/2。第四步：计算精度，若(bk+1-ak+1)/(b0-a0)<δ,则停止计算，取λ*=

tk+1。否则计算新的一对试点。二分法：第十九页，共一百零二页，编辑于2023年，星期二采用二分法求解下列问题：初始区间[-1,1],精度0.15kabtf'(t)精度1-110-122010.521300.50.250.50.5400.250.125-0.250.2550.1250.25

0.125例第二十页，共一百零二页，编辑于2023年，星期二黄金分割法也称为0.618法，属于区间收缩法。首先找出包含极小点的初始搜索区间，然后按黄金分割点通过对函数值得比较不断缩小搜索区间。当然要保证极小点始终在搜索区间内，当区间长度小到精度范围之内时，可以粗略的认为区间端点的平均值就是极小点的近似值。黄金分割法适用于单峰函数。0.618法(黄金分割法)第二十一页，共一百零二页，编辑于2023年，星期二t1t2t2新搜索区间为[a,t2]新搜索区间为[t1,b]t1abab假定：已经确定了单谷区间[a,b]第二十二页，共一百零二页，编辑于2023年，星期二缩短比例满足：每次插入搜索点使得两个区间[a,t2]和[t1,b]相等；每次迭代都以相等的比例缩小区间。区间缩小比例的确定：区间缩短比例为(t2-a)/(b-a)缩短比例为(b-t1)/(b-a)t1t2ababt1t20.618法第二十三页，共一百零二页，编辑于2023年，星期二确定[a,b],计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤：否是是停止，输出t2否以[t1,b]为新的搜索区间是停止，输出t1否以[a,t2]为新的搜索区间第二十四页，共一百零二页，编辑于2023年，星期二例：解：t1t230t1、第一轮：a=0,t1=1.146,t2=1.854,b=3

t2－0>0.5第二十五页，共一百零二页，编辑于2023年，星期二3、第三轮：a=0,t1=0.438,t2=0.708,b=1.146b-t1=1.146-0.438>0.51.4160tt2t1t2－0=1.146>0.51.8540tt2t12、第二轮：a=0,t1=0.708,t2=1.146,b=1.854第二十六页，共一百零二页，编辑于2023年，星期二4、第四轮：a=0.438,t1=0.708,t2=0.876,b=1.146

b-t1=1.146-0.708<0.5输出：t*=t2=0.876为最优解，最优值为-0.079801.416tt1t2第二十七页，共一百零二页，编辑于2023年，星期二kabt1t2f(t1)f(t2)精度1-11-0.2360.236-0.653-1.12522-0.23610.2360.528-1.125-0.971.2363-0.2360.5280.0560.236-1.05-1.1250.76440.0560.5280.2360.348-1.125-1.1060.47250.0560.3480.1680.236-1.112-1.1250.29260.1680.3480.2360.279-1.125-1.1230.1870.1680.2790.111采用黄金分割法求解下列问题：初始区间[-1,1],精度0.15练习第二十八页，共一百零二页，编辑于2023年，星期二无约束优化问题的求解算法

此类无约束最优化问题的求解已被各国学者广泛地研究并取得了丰富的研究成果，至今已有许多有效算法被提出。一般说来，求解此类问题的算法被分成两大类，一类要求导数的信息，而另一类则不要求导数的信息。第一类方法包括最速下降法、广义牛顿法、共轭方向法以及变尺度方法等；第二类方法通常指搜索法，包括Hooke-Jeeves直接搜索法和随机搜索法等。考虑如下无约束优化问题第二十九页，共一百零二页，编辑于2023年，星期二梯度法（最速下降法）1.梯度法的基本原理：目标函数

有一阶连续偏导数，具有极小值点以表示极小值点的第k次近似，为了求其第k+1次近似点

，我们在

点沿方向

做射线：将

在

点处展成泰勒级数：第三十页，共一百零二页，编辑于2023年，星期二将

在

点处展成泰勒级数：对于充分小的，只要：即可保证：这时若取：就能使目标函数值得到改善。即：第三十一页，共一百零二页，编辑于2023年，星期二2.梯度法的方向确定（负梯度方向）使上式成立的

有无限多个。为了使目标函数值能得到尽量大的改善，必须寻求使

取最小值的

。由线性代数得：为向量与的夹角。当向量与取反向时取最小值第三十二页，共一百零二页，编辑于2023年，星期二3.梯度法的步长确定（一维搜索）若

具有二阶连续偏导数，在

作

的泰勒展开对求导并令其等于零，则得到近似最佳步长：第三十三页，共一百零二页，编辑于2023年，星期二梯度法（最速下降法）考虑如下无约束优化问题：其中函数f(x)具有一阶连续偏导数。(1)最速下降法采用目标函数的负梯度方向为下降方向：(2)一维搜索确定步长(3)收敛准则第三十四页，共一百零二页，编辑于2023年，星期二例题例：试用最速下降法求下例优化问题的极小点解：取初始近似点第三十五页，共一百零二页，编辑于2023年，星期二第三十六页，共一百零二页，编辑于2023年，星期二第三十七页，共一百零二页，编辑于2023年，星期二第三十八页，共一百零二页，编辑于2023年，星期二第三十九页，共一百零二页，编辑于2023年，星期二第四十页，共一百零二页，编辑于2023年，星期二第四十一页，共一百零二页，编辑于2023年，星期二采用最速下降法求解：选初始点X(0)=(2,-2,1)T。要求做三次迭代。第四十二页，共一百零二页，编辑于2023年，星期二Newton型算法(牛顿法)第四十三页，共一百零二页，编辑于2023年，星期二第四十四页，共一百零二页，编辑于2023年，星期二牛顿方向!第四十五页，共一百零二页，编辑于2023年，星期二第四十六页，共一百零二页，编辑于2023年，星期二例考虑如下无约束优化问题：选取初始点x1=(0,0)T，目标函数在x1处的梯度和Hessian矩阵分别为：牛顿方向：令：则x*=(0.7732,-1.1546)T第四十七页，共一百零二页，编辑于2023年，星期二第五章约束极值问题最优性条件1.起作用约束:设

为非线性规划的一个可行解，满足所有条件。不起作用约束（无效约束）起作用约束（有效约束）显而易见，等式约束对所有可行点来说都是起作用约束。第四十八页，共一百零二页，编辑于2023年，星期二最优性条件2.可行下降方向:设是非线性规划的一个可行点，现考虑此点的某一方向D，若存在实数，使对任意均有：就称方向D为点的一个可行方向。第四十九页，共一百零二页，编辑于2023年，星期二

设是非线性规划的一个可行点，现考虑此点的某一方向D，若存在实数，使对任意均有：就称方向D为点的一个可行方向。只要：那么：设是非线性规划的一个可行点，对该点的任一方向D，若存在实数，使对任意均有：那么就称方向D为点的一个下降方向。第五十页，共一百零二页，编辑于2023年，星期二泰勒展开只要：即可保证：即可保证D必为

点的下降方向。如果方向D为

点的可行方向，又是这个点的下降方向，就称它是该点的可行下降方向。第五十一页，共一百零二页，编辑于2023年，星期二定理：设

是非线性规划的一个局部极小点，目标函数

在

处可微，而且：在

处可微，当在

处连续，当则在点不存在可行下降方向，从而不存在向量D同时满足：第五十二页，共一百零二页，编辑于2023年，星期二库恩-塔克条件（kuhn-Tucker,K-T条件）设

是上式非线性规划的一个极小点。1.若该点位于可行域的内部，该线性规划问题为无约束问题。2.若点位于可行域的边界上…假设点位于某个约束条件的边界上：如果点是极小点，则：与必须在一条直线上，且方向相反，否则在该点就一定存在可行下降方向。第五十三页，共一百零二页，编辑于2023年，星期二如果点有两个起作用约束，如：若点为极小值点，那么必处于和的夹角之内。否则在点一定存在可行下降方向。有一个起作用约束条件：有两个起作用约束条件：第五十四页，共一百零二页，编辑于2023年，星期二有多个起作用约束条件：将不起作用约束条件包括进上式：增加条件：库恩-塔克条件(K-T条件):注：K-T条件是确定某点为最优点的必要条件。对于凸规划，K-T条件是确定某点为最优点的充要条件第五十五页，共一百零二页，编辑于2023年，星期二为可行方向。为下降方向。为的可行下降方向。第五十六页，共一百零二页，编辑于2023年，星期二K-T条件定义：设

是非线性规划问题的极小值点，而且

点的所有起作用约束的梯度线性无关，则存在向量：使下述条件成立：广义拉格朗日（Lagrange）乘子。K-T条件第五十七页，共一百零二页，编辑于2023年，星期二先将该非线性规划问题写成以下形式：写出其目标函数和约束函数的梯度：引入拉格朗日乘子引入拉格朗日乘子第五十八页，共一百零二页，编辑于2023年，星期二K-T条件第五十九页，共一百零二页，编辑于2023年，星期二约束非线性优化问题的求解方法Zoutendijk可行方向法Frank-Wolfe算法MSA算法惩罚函数法(SUMT外点法)障碍函数法(SUMT内点法)第六十页，共一百零二页，编辑于2023年，星期二Zoutendijk可行方向法可行方向法定义设

为非线性规划：的一个可行解，但不是要求的极小点。为了求它的极小点或近似极小点，应在点的可行下降方向中选取某一方向

，并确定步长

，使：若满足精度要求，迭代停止，

就是所要的点。否则，从

出发继续进行迭代，直到满足要求为止。第六十一页，共一百零二页，编辑于2023年，星期二Zoutendijk可行方向法：设

点的起作用约束集非空，为求

点的可行下降方向，可由下述不等式组来确定向量

：这等价于由下面的不等式组求向量

和实数

：第六十二页，共一百零二页，编辑于2023年，星期二现在使和（对所有）的最大值极小化，即可将上述选取搜索方向的工作，转换为求解下述线性规划问题：为向量

的分量若最优解为，如果求出的，则

点不存在可行下降方向。如果求出的，则得到可行下降方向。第六十三页，共一百零二页，编辑于2023年，星期二Zoutendijk可行方向法步骤：1.确定允许误差和，选初始近似点，并令。2.确定起作用约束指标集：（1）.若，而且，停止迭代，得点。（2）.若，而且，则取搜索方向，然后转向5步。（3）.若，转下一步。3.求解线性规划：第六十四页，共一百零二页，编辑于2023年，星期二4.检查是否停止：若满足则停止迭代，得到点

；否则，以

为搜索方向，并转下一步。5.解下述一维极值问题：此处：6.令：转回2步。第六十五页，共一百零二页，编辑于2023年，星期二解下述非线性规划问题：解：取初始可行点：由于所以

不是极小点。第六十六页，共一百零二页，编辑于2023年，星期二现取搜索方向：从而分别代入约束条件和目标函数：从而第六十七页，共一百零二页，编辑于2023年，星期二求解下述线性规划问题：由此：第六十八页，共一百零二页，编辑于2023年，星期二点为可行点所以…继续迭代下去,最优解：第六十九页，共一百零二页，编辑于2023年，星期二Frank-Wolfe算法Frank和Wolfe于1956年提出求解线性约束问题的一种算法，通常简称F-W算法。考虑最优化问题其中是矩阵，秩为，是维列向量，是连续可微函数。可行域记为：(1)第七十页，共一百零二页，编辑于2023年，星期二

第七十一页，共一百零二页，编辑于2023年，星期二第七十二页，共一百零二页，编辑于2023年，星期二第七十三页，共一百零二页，编辑于2023年，星期二第七十四页，共一百零二页，编辑于2023年，星期二第七十五页，共一百零二页，编辑于2023年，星期二第七十六页，共一百零二页，编辑于2023年，星期二第七十七页，共一百零二页，编辑于2023年，星期二第七十八页，共一百零二页，编辑于2023年，星期二第七十九页，共一百零二页，编辑于2023年，星期二第八十页，共一百零二页，编辑于2023年，星期二第八十一页，共一百零二页，编辑于2023年，星期二第八十二页，共一百零二页，编辑于2023年，星期二第八十三页，共一百零二页，编辑于2023年，星期二第八十四页，共一百零二页，编辑于2023年，星期二第八十五页，共一百零二页，编辑于2023年，星期二MSA算法通常称为相继平均法（MethodofSuccessiveAverages

）。考虑下面的最优化问题

可行域记为。可以用MSA算法进行迭代求解。MSA算法第八十六页，共一百零二页，编辑于2023年，星期二假定在任意点，通过求解下面的线性