运筹学 — 无约束非线性规划,约束非线性优化课件

1、运筹学 无约束非线性规划,约束非线性优化,第四章非线性规划,凌翔 龙建成,运筹学 无约束非线性规划,约束非线性优化,凸函数定义：,设 为定义在n维欧氏空间E中某个凸集R上的函数，若对任何实数 以及R中的任意两点 和 ，恒有：,则称 为定义在R上的凸函数。,则称 为定义在R上的严格凸函数。,运筹学 无约束非线性规划,约束非线性优化,凸函数性质：,性质1：设 为定义在凸集R上的凸函数，则对任意实数 ,函数 也是定义在R上的凸函数。,性质2：设 和 为定义在凸集R上的凸函数，则其和 ,任是定义在R上的凸函数。,运筹学 无约束非线性规划,约束非线性优化,凸函数性质：,性质3：设 为定义在凸集R上的凸函

2、数，则对任意实数 ,集合：,是凸集。,称为水平集。,运筹学 无约束非线性规划,约束非线性优化,凸函数性质：,推论：有限个凸函数的非负线性组合：,仍为凸函数。,运筹学 无约束非线性规划,约束非线性优化,函数凸性的判别：,一阶条件: 设R为n维欧氏空间En上的开凸集， 在R上具有一阶连续偏导数，则 为R上的凸函数的充要条件是，对任意两个不同点 和 ，恒有：,运筹学 无约束非线性规划,约束非线性优化,函数凸性的判别：,二阶条件: 设R为n维欧氏空间En上的开凸集， 在R上具有二阶连续偏导数，则 为R上的凸函数的充要条件是： 的海赛矩阵 在R上处处半正定。,运筹学 无约束非线性规划,约束非线性优化,凸

3、函数的极值：,定理：设 为定义在凸集R上的凸函数，则它的任一极小值就是它在R上的最小点（全局极小点），而且它的极小点形成一个凸集。,定理：设 为定义在凸集R上的可微凸函数，若存在点 ，使得对于所有的 有：,则 是 的R上的最小点（全局极小点）,运筹学 无约束非线性规划,约束非线性优化,凸规划：,定义：若 为凸集， 是R上的凸函数， 则称规划：,为凸规划,定义：若规划问题：,其中 为凸函数， 为凹函数（或 为凸函数） ，则该规划问题为凸规划。,运筹学 无约束非线性规划,约束非线性优化,练习,判断下述非线性规划是否是凸规划,s.t.,运筹学 无约束非线性规划,约束非线性优化,下降迭代算法：,迭代法

4、的基本思想：为了求函数 的最优解，首先给定一个初始估计 ，然后按照某种算法找出比 更好的解 ； 1.对于极小化问题： 2.对于极大化问题： 如此可以得到一个解的序列 。若这个解序列有极限 ，即：,则称它收敛于,运筹学 无约束非线性规划,约束非线性优化,下降迭代算法：,下降迭代算法的步骤： 选定某一初始点 ，令k：=0； 确定搜索方向 ； 从 出发，沿方向 求步长 ，以产生下一个迭代点 ；,检查得到的新点x是否为极小值点或近似极小值点。若是，停止迭代。否则，令 k：=k+1，回2步继续迭代。,运筹学 无约束非线性规划,约束非线性优化,确定最优步长,求以 为变量的一元函数 的极小值点 （一维搜索）

5、,一维搜索重要性质：在搜索方向上所得最优点处的梯度和该搜索方向正交。,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,迭代终止准则 绝对误差： 相对误差： 目标函数梯度：,为事先给定的足够小的正数。,运筹学 无约束非线性规划,约束非线性优化,一维搜索,一维搜索是所有非线性规划迭代算法都要遇到的共同问题，而且相对于构造搜索方向问题比较简单。因此我们在这一部分先介绍求解一维搜索问题的方法。 主要有斐波那契法、0.618法、插值法、求根法（二分法）等。 一维搜索主要针对单峰函数。什么是单峰函数？,运筹学 无约束非线性规划,约束非线性优化,单峰函数及其性质,定义:

6、设函数 ： ，闭区间 ，若存在点 ，使 在 上严格递减，在 上严格递增，则称函数 为 上的单峰函数， 为 的单峰区间，如下图,运筹学 无约束非线性规划,约束非线性优化,单峰区间和单峰函数具有如下性质： 若 是单峰区间 上的单峰函数，极小点为 ，在 中任取两点 ， ，且 ，则（1）当 时， ；（2）当 时， 。 这个性质说明了，经过函数值的比较后，我们可以把单峰函数 的单峰区间 进行缩小，或者 或者 ，而 仍在区间内。,运筹学 无约束非线性规划,约束非线性优化,二分法步骤如下： 第一步：选取初始数据，确定初始搜索区间 ，给出最后区间精度 。 第二步：计算初始试点： ，计算 ，并令k:=0。 第三

7、步：如果， 则令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。否则计算新的一对试点。,二分法：,运筹学 无约束非线性规划,约束非线性优化,采用二分法求解下列问题：,初始区间-1, 1, 精度0.15,例,运筹学 无约束非线性规划,约束非线性优化,黄金分割法也称为0.618法，属于区间收缩法。 首先找出包含极小点的初始搜索区间，然后按黄金分割点通过对函数值得比较不断缩小搜索区间。 当然要保

8、证极小点始终在搜索区间内，当区间长度小到精度范围之内时，可以粗略的认为区间端点的平均值就是极小点的近似值。 黄金分割法适用于单峰函数。,0.618法(黄金分割法),运筹学 无约束非线性规划,约束非线性优化,新搜索区间为a,t2,新搜索区间为t1,b,假定：已经确定了单谷区间a,b,运筹学 无约束非线性规划,约束非线性优化,缩短比例 满足： 每次插入搜索点使得两个区间a,t2和t1,b相等； 每次迭代都以相等的比例缩小区间。,运筹学 无约束非线性规划,约束非线性优化,确定a,b,计算探索点 t1=a+ 0.382 (b-a) t2=a+0.618 (b-a),0.618法解题步骤：,停止，输出t

9、2,以t1,b为新的搜索区间,停止，输出t1,以a,t2为新的搜索区间,运筹学 无约束非线性规划,约束非线性优化,例：,解：,t1,t2,3,0,t,1、第一轮： a= 0, t1=1.146, t2=1.854, b=3,t200.5,运筹学 无约束非线性规划,约束非线性优化,3、第三轮： a = 0, t1=0.438, t2=0.708, b=1.146,b-t1=1.146-0.4380.5,1.416,t2,t1,t20=1.1460.5,t2,t1,2、第二轮： a= 0, t1=0.708, t2=1.146, b= 1.854,运筹学 无约束非线性规划,约束非线性优化,4、第四

10、轮： a = 0.438, t1=0.708, t2=0.876, b=1.146,b-t1=1.146-0.7080.5,输出：t*=t2=0.876为最优解，最优值为-0.0798,0,1.416,t,t1,t2,运筹学 无约束非线性规划,约束非线性优化,采用黄金分割法求解下列问题：,初始区间-1, 1, 精度0.15,练习,运筹学 无约束非线性规划,约束非线性优化,无约束优化问题的求解算法,此类无约束最优化问题的求解已被各国学者广泛地研究并取得了丰富的研究成果，至今已有许多有效算法被提出。一般说来，求解此类问题的算法被分成两大类，一类要求导数的信息，而另一类则不要求导数的信息。第一类方法

11、包括最速下降法、广义牛顿法、共轭方向法以及变尺度方法等；第二类方法通常指搜索法，包括Hooke-Jeeves直接搜索法和随机搜索法等。,考虑如下无约束优化问题,运筹学 无约束非线性规划,约束非线性优化,梯度法（最速下降法）,1.梯度法的基本原理：,目标函数 有一阶连续偏导数，具有极小值点,以 表示极小值点的第k次近似，为了求其第k+1次近似点 ，我们在 点沿方向 做射线：,将 在 点处展成泰勒级数：,运筹学 无约束非线性规划,约束非线性优化,将 在 点处展成泰勒级数：,对于充分小的 ，只要：,即可保证：,这时若取：,就能使目标函数值得到改善。,即：,运筹学 无约束非线性规划,约束非线性优化,2

12、.梯度法的方向确定（负梯度方向）,使上式成立的 有无限多个。为了使目标函数值能得到尽量大的改善，必须寻求使 取最小值的 。由线性代数得：,为向量 与 的夹角。,当向量 与 取反向时,取最小值,运筹学 无约束非线性规划,约束非线性优化,3.梯度法的步长确定（一维搜索）,若 具有二阶连续偏导数，在 作 的泰勒展开,对 求导并令其等于零，则得到近似最佳步长：,运筹学 无约束非线性规划,约束非线性优化,梯度法（最速下降法）,考虑如下无约束优化问题：,其中函数f(x)具有一阶连续偏导数。,(1) 最速下降法采用目标函数的负梯度方向为下降方向：,(2) 一维搜索确定步长,(3) 收敛准则,运筹学 无约束非

13、线性规划,约束非线性优化,例题,例：试用最速下降法求下例优化问题的极小点,解：取初始近似点,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,采用最速下降法求解：,选初始点X(0)=(2,-2,1)T。要求做三次迭代。,运筹学 无约束非线性规划,约束非线性优化,Newton型算法(牛顿法),运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规

14、划,约束非线性优化,牛顿方向!,运筹学 无约束非线性规划,约束非线性优化,运筹学 无约束非线性规划,约束非线性优化,例,考虑如下无约束优化问题：,选取初始点x1=(0,0)T，目标函数在x1处的梯度和Hessian矩阵分别为：,牛顿方向：,令：,则,x*=(0.7732, -1.1546)T,运筹学 无约束非线性规划,约束非线性优化,第五章 约束极值问题,最优性条件,1.起作用约束:设 为非线性规划的一个可行解，满足所有条件。,不起作用约束（无效约束）,起作用约束（有效约束）,显而易见，等式约束对所有可行点来说都是起作用约束。,运筹学 无约束非线性规划,约束非线性优化,最优性条件,2.可行下降

15、方向:设 是非线性规划的一个可行点，现考虑此点的某一方向D，若存在实数 ，使对任意 均有：,就称方向D为 点的一个可行方向。,运筹学 无约束非线性规划,约束非线性优化,设 是非线性规划的一个可行点，现考虑此点的某一方向D，若存在实数 ，使对任意 均有：,就称方向D为 点的一个可行方向。,只要：,那么：,设 是非线性规划的一个可行点，对该点的任一方向D，若存在实数 ，使对任意 均有：,那么就称方向D为 点的一个下降方向。,运筹学 无约束非线性规划,约束非线性优化,泰勒展开,只要：,即可保证：,即可保证D必为 点的下降方向。,如果方向D为 点的可行方向，又是这个点的下降方向，就称它是该点的可行下降

16、方向。,运筹学 无约束非线性规划,约束非线性优化,定理：设 是非线性规划的一个局部极小点，目标函数 在 处可微，而且：,在 处可微，当,在 处连续，当,则在 点不存在可行下降方向，从而不存在向量D同时满足：,运筹学 无约束非线性规划,约束非线性优化,库恩-塔克条件（kuhn-Tucker,K-T条件）,设 是上式非线性规划的一个极小点。,1.若该点位于可行域的内部，该线性规划问题为无约束问题。,2.若 点位于可行域的边界上,假设 点位于某个约束条件的边界上：,如果 点是极小点，则：,与,必须在一条直线上，且方向相反，否则在该点就一定存在可行下降方向。,运筹学 无约束非线性规划,约束非线性优化,

17、如果 点有两个起作用约束，如：,若 点为极小值点，那么 必处于 和 的夹角之内。否则在 点一定存在可行下降方向。,有一个起作用约束条件：,有两个起作用约束条件：,运筹学 无约束非线性规划,约束非线性优化,有多个起作用约束条件：,将不起作用约束条件包括进上式：,增加条件：,库恩-塔克条件(K-T条件):,注：K-T条件是确定某点为最优点的必要条件。对于凸规划， K-T条件是确定某点为最优点的充要条件,运筹学 无约束非线性规划,约束非线性优化,为可行方向。,为下降方向。,为 的可行下降方向。,运筹学 无约束非线性规划,约束非线性优化,K-T条件定义：,设 是非线性规划问题的极小值点，而且 点的所有

18、起作用 约束的梯度 线性无关，则存在 向量：,使下述条件成立：,广义拉格朗日（Lagrange）乘子。,K-T条件,运筹学 无约束非线性规划,约束非线性优化,先将该非线性规划问题写成以下形式：,写出其目标函数和约束函数的梯度：,引入拉格朗日乘子,引入拉格朗日乘子,运筹学 无约束非线性规划,约束非线性优化,K-T条件,运筹学 无约束非线性规划,约束非线性优化,约束非线性优化问题的求解方法,Zoutendijk可行方向法 Frank-Wolfe算法 MSA算法 惩罚函数法(SUMT外点法) 障碍函数法(SUMT内点法),运筹学 无约束非线性规划,约束非线性优化,Zoutendijk可行方向法,可行方向法定义 设 为非线性规划：,的一个可行解，但不是要求的极小点。为了求它的极小点或近似极小点，应在 点的可行下降方向中选取某