运筹学-非线性规划.ppt

高级运筹学,非线性规划,教材及参考书,指定教材：沈荣芳，运筹学高级教程（第二版），高等教育出版社，2008.8 参考资料： 1.韩伯棠，管理运筹学（第三版），高等教育出版社，2013.12 2. FREDERICK S. HILLIER GERALD J. LIEBERMAN ，INTRODUCTION TO OPERATIONS RESEARCH ，Ninth Edition,2010 3.吴祈宗，运筹学与最优化方法（第二版），机械工业出版社，2012 4. David G. Luenberger，Linear and Nonlinear Programming，Springer，2008,非线性规划,非线性规划 在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。 一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。,非线性规划研究核心问题： 最优性条件（必要条件，充分条件，Lagrange乘子理论，灵敏性分析，对偶理论） 迭代算法,解: 设投资决策变量为,问题归结为总资金的限制条件下, 极大化总收益和总投资之比, 数学模型为,例：投资决策问题 某企业有n个项目可供选择投资, 并且至少要对其中一个项目投资. 已知该企业拥有总资金A元, 投资于第i(i=1,2,n)个项目需要花资金ai 元, 并预计收益为bi元, 试选择最佳投资方案使得总收益和总投资之比最大.,一般地，非线性规划的数学模型为,其中 X称为可行域,可行域中的点 称为可行点，f(x)称为目标函数,当 时，非线性规划模型称为无约束问题； 当 时，非线性规划模型称为有约束问题,使f(x)在X上取得最小值的点称为最优解，对应的目标函数值称为最优值,定义：如果目标函数或约束条件中至少有一个是非线性函数，则称这种规划为非线性规划问题。,为统一起见,称以下模型 min f(x) s.t. gi(x) 0 i=1，2，m （1） hj(x)=0 j=1，2，l 为标准的非线性规划模型,其中f(x),gi(x),hj(x)中至少有一个是x的非线性函数. 称gi(x) 0为不等式约束, hj(x)=0为等式约束.,满足所有约束条件的x称为可行解, 所有可行解构成的集合 称为可行域。,例: 考虑如下非线性规划问题： min f(x)= (x14)2+(y15)2 1/2 s.t. (x - 8)2 + (y - 9)2 49 x 2， x 13 x + y 24,非线性规划的最优解未必在顶点处达到； 非线性规划的最优解是一组同心圆最先与可行域相交的点，在可行域的边界上达到,二维非线性规划问题的图解分析,例：请考虑如下非线性规划问题： min f(x)= (x8)2+(y8)2 s.t. (x - 8)2 + (y - 9)2 49 x 2， x 13 x + y 24,非线性规划的最优解在可行域内部达到,可以看出, x2, x3, x4是局部最优解, 且x3还是全局最优解, x1, x2 , x3, x5是严格局部最优解, x4不是严格局部最优解.,一个全局最优解一定是局部最优解，反之不真。 对求极小化非线性规划问题，如果目标函数为凸函数，可行域为凸集， 则局部最优解一定为全局最优解。,与线性规划不同, 非线性规划有局部最优解和全局最优解之分.,凸集 定义非空集合D称为凸集, 如果对于任意的x1, x2D及任意实数a, 0a1, 有ax1+(1a)x2D.,凸集的几何意义：若一个集合是凸的，则该集合中任意两点的线段也必包含在此集合中。,凸集,不是凸集,凸集、凸函数和凸规划,(1) 集合D=xEn |Axb, x0是凸集。,例：,定理：设D1,D2是En中的凸集，则,凸函数与凹函数 定义: D为凸集, 若对任意x1,x2D及任意实数a, 0a1有 f(ax1+(1a)x2)a f(x1)+(1a)f(x2) 则称 f(x) 为凸函数; 若变为, 称f(x)为严格凸函数。,若上式中的(), 则称f(x)为凹函数/严格凹函数。,凸函数的特征是，曲线上任意两点的连线总是位于这两点间曲线的上方。,凸函数的判定 (一阶条件)：设 f(x)在凸集D上有一阶连续导数，则 f(x)是D上凸函数的充要条件是对任意两点x, z D, x z, 必有,如果上式严格成立，则是严格凸函数的充要条件。,几何意义：凸函数 f(x) 在曲线上任何一点做曲线的切线，那么f(x)都在切线上方。,(二阶条件)：设D是一个非空开凸集，设f在D上二次可微，则 f(x)是凸函数，当且仅当对所有xD, Hessian 矩阵 是半正定矩阵;,注意：Hesse矩阵在D中的每一点都是正定的，则f是严格凸的；可是，如果f是严格凸的，则Hesse矩阵在S中的每一点都是半正定的。,上述定理在检验函数的凹凸性是有效的，特别是当函数为二次函数时，Hesse矩阵不依赖点x，因此检验其凸性简化为检验一个单一矩阵的特征值的非负性。,例：检验函数f(x1, x2)=2x1+6x2-2x12-3x22+4x1x2是凸的，凹的。或者两者都不是。,解：将f 改写为下面更方便的形式：,以下通过解下面的方程来计算特征值,方程的解为,凸规划定义： 已知非线性规划 若可行域D是凸集，且f(x)是定义在D上的凸函数，则该非线性规划称为凸规划。,定理：对非线性规划，如果gj(x)(i=1,2,m)是En 上的凸函数， hj(x)(j=1,2,p)为线性函数，且f(x)为可行域D上的凸函数，则该非线性规划问题是凸规划。(作业1),定理1：设D为非空凸集，f(x)连续，考虑如下问题 (1) 如果 f 是凸函数，则局部最优解也是全局最优解； (2) 如果 f 是严格凸函数，则 x* 为唯一的全局最优解。,定理(最优性条件): 考虑凸规划 , (1) x*是最优解的充要条件是对xX, 有 (2) 若D是开集, x*是最优解的充要条件是,由定理结论(1)可知，如果某点x*是最优解，则对任意xD, 向量x-x*与函数f在点x*处的梯度向量 所成的角度小于90。.,分析：题意是要求验证非线性规划的最优解x*满足,解：显然，目标函数 是凸函数, 且约束条件为线性函数, 故此规划问题为凸规划.,点x*=(1,3)T是唯一最优解. 由于f在点(1,3)的梯度为 从图中可以看出，向量 与 所成的角度小于等于90。.,而对点 (0,0)T而言，显然不是最优解。因为,对任意非零点xD, 有-3x1-10x20, 即向量(x1-0, x2-0)T 与 所成角度大于90。, 不满足最优性条件,原点不会是最优解。为使目标函数值下降，最好的局部下降方向是,思考题： 如果某凸规划的可行域为D=x|x0，请讨论此凸规划问题的最优解的充要条件的形式。,无约束问题 一阶二阶必要和充分条件 等式约束问题 Lagrange 乘子理论 一般约束问题 一阶二阶必要和充分条件,最优性条件,二阶必要条件 ：设f: RnR1在点x*Rn 处二阶可微，如果x*是局部极小解, 则f(x*)=0, 且2f(x*)为半正定矩阵.,对无约束极值问题 min f(x)，x Rn （1） 一阶必要条件：设f: Rn R1在点x*Rn处可微，如果x* 是局部极小点, 则 f(x*)=0.,定义: 设 f: En E1在点x*处可微, 若f(x*)=0 , 称x* 函数f的驻点.,对无约束极值问题 min f(x)，x Rn （1） 定理(一阶必要条件)：设f: Rn R1在点x*Rn处可微，如果x* 是局部极小点, 则 f(x*)=0.,推论：设f: Rn R1在点x*Rn处可微，f是Rn上的凸函数，如果f(x*)=0 , 则x* 是无约束问题的全局最优解。,定理 (二阶必要条件) ：设f: RnR1在点x*Rn 处二阶可微，如果x*是局部极小解, 则f(x*)=0, 且2f(x*)为半正定矩阵.,注意：该定理仅是必要的，而不是充分的。,定理 (二阶充分条件I)： 设f: RnR1在点x*Rn 处二阶可微，如果f(x*)=0, 且2f(x*)为正定矩阵, 则x* 是无约束问题的严格局部极小解,证明: 设 为 的最小特征值. 利用二阶Taylor展式有,定理 (二阶充分条件II): 设f: EnE1在点x*En 的一个邻域 处二阶连续可微，如果 f 满足f(x*)=0, 且2f(x)在 内半正定, 则 x* 是无约束问题的局部极小解.,思考题：考虑二次函数的无约束极小化问题,其中Q为n阶对称矩阵，b为n维列向量。,等式约束极值问题 min f(x)，x Rn s.t. hi(x)=0, i=1,2, m,最优性条件,(必要条件): 定理: 设等式约束问题中函数f与hi(x)(i=1,m)是连续可微函数, x*为局部最优解且为正则点(即 线性无关, 则存在实数组 ,使得,如果函数f与hi(x)(i=1,m)是二次连续可微, 则,注：等式约束问题的一阶必要条件的直观的几何意义：,注1：定理中给出的一阶必要条件仅当约束函数满足一定条件时才成立，该条件称为约束规格,注：该定理表明等式约束极值问题的极值点处的目标函数与约束函数梯度之间通过Lagrange乘子向量存在的关系, 是Lagrange乘子法的出发点.,引入拉格朗日函数L(x,V),其中参数向量 称为拉格朗日乘子.,n+p个方程解n+p个未知量可得L的驻点, 但是否驻点就是此非规划模型的极小解，还需要充分条件的判断； 但是对于特殊的如二次规划问题，可以通过计算L对X的Hesse矩阵判定该驻点是极大值点还是极小值点.,练习: 求等式约束极值问题 (书61-62页),(充分条件): 定理: 设等式约束问题中函数f与hi(x)(i=1,m)是二次连续可微函数,则x*是一个极小点。,1. 含不等式约束的极值问题 min f(x)，x Rn s.t. gi(x) 0, i=1,2,m (3),最优性条件,设x* 是问题(3)的可行解, 约束条件gi(x) 0可分为两类, x*点的起作用约束(active constraints)：gi(x*)=0； x*点的不起作用约束(inactive constraints)：gi(x*)0.,记点x*处所有起作用约束下标的集合为I(x*), 即,如何找到在点x0处的可行方向？,如果x*为局部最优解, 则在该点处不可能存在可行下降方向.,几何意义说明如下: 设A1,A2,A3是三个二维向量.,若A1, A2, A3不在任一条直线的同一侧, 就无法找到使AiTp0 (i=1,2,3) 均满足的向量p. 这时总可以适当缩小或放大各向量Ai的长度, 使它们合成为零向量,即可找到不全为零的非负实数, 使,若均位于某直线H的同一侧, 则总可找到某一向量p, 使AiTp0(i=1,2,3);,此处的(1) (2)两式称为Krush-Kuhn-Tucker条件，简称K-K-T条件；满足K-K-T条件的点称为K-K-T点。,K-K-T条件的几何意义,2. 一般约束极值问题的KT条件 min f(x)，x Rn s.t. gi(x) 0, i=1,2,m (3) hj(x)=0, j=1,2,p,最优性条件,最优性条件,前面的定理表明, 如果局部最优解满足约束规格, 则K-K-T条件成立; 如果局部最优解不满足约束规格，则K-K-T条件可能不存在解.,Krush-Kuhn-Tucker条件是确定某点为最优解的必要条件, 只要是最优解, 且此处起作用约束的梯度线性无关, 就一定满足K-K-T条件, 但一般来说它并不是充分条件. 因而, 满足这个条件的点不一定是最优点. 下面的定理说明, 对于凸规划, Krush-Kuhn-Tucker条件不但是最优点存在的必要条件, 同时也是充分条件.,定理：设f(x),gi(x)(i=1,2,m), hj(x)(j=1,2,p)在x*处连续可微，且f(x),gi(x)(i=1,2,m)是凸函数，hj(x)是线性函数，若x*是非线性规划模型的K-K-T点，则x*是其全局极小点。,最优性条件,最优性条件,二次规划及其应用,二次规划是一个有二次目标函数和线性约束条件的优化问题, 其数学模型如下：,二次规划的K-K-T条件,引入松弛变量S, 使之成为等式S=b-AX, 并分别设与条件AXb和 X0对应的Lagrange乘子向量为u和v，则二次规划的K-K-T条件为,二次规划及其应用,由于二次规划是凸规划, 故点X*是最优解的充要条件是存在 u, v, S, X共同满足以上K-K-T条件. 于是, 原问题的最优解等价于 找以上K-K-T条件的可行解.,二次规划及其应用,至此，对二次规划的求解已经转化为线性互补问题，可以用互补转轴算 法找出二次规划的K-K-T点。,例：写出二次规划的K-K-T条件：,称为互补松弛条件，即u1,s1不能 同时为零，vi和xi不能同时为零。,二次规划及其应用,例：考虑二次规划问题,解：设与约束条件x1+x22, -x1+2x22, x10, x20对应的 Lagrange乘子向量分别用u=(u1,u2)T和v=(v1,v2)T表示，,二次规划及其应用,于是，可得K-K-T条件如下：,二次规划及其应用,线性互补问题,如何解决线性互补问题？,线性互补问题,线性互补问题,线性互补问题,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,-1,-1,0,0,1,-2,1,-1,-2,2,1,2,2,-4,-1,2,2,-2,-6,-1,-1,-1,（ ）,线性互补问题,1,0,0,0,0,1,0,0,0,0,1,0,-1,-1,-1,-1,1,1,0,1,2,2,3,2,-1,-3,-4,-2,5,6,6,-4,0,8,8,4,6,0,0,1,（ ）,线性互补问题,1,0,0,0,0,1,0,0,-5/6,-1,1/6,-2/3,-1/6,0,-1/6,-1/3,1,1,0,1,-1/2,-1,1/2,0,7/3,1,-2/3,2/3,0,0,1,0,0,14/3,4,2/3,10/3,0,0,1,（ ）,线性互补问题,3/7,-3/7,2/7,0,1,0,0,-5/14,-3/7,-1/14,-3/14,-2/7,-3/14,-11/14,5/14,1/7,1,0,0,1,0,0,14/3,4,2/3,10/3,0,0,1,（ ）,-2/7,-9/14,-1/14,1/14,3/7,4/7,2/7,5/7,0,0,0,线性互补问题,对于可微函数 f(x) 来说，为了求最优解，可以令梯度 由此求得驻点，然后再利用充分条件进行判别。但是，对于一 般的n元函数 f(x) 来说, 令 得到的常是一个非线性方 程组，求解相当困难；此外，很多实际问题往往很难求出或根 本求不出目标函数对各自变量的偏导数，从而使得一阶必要条 件很难应用。因此，除个别情形外，一般都是采用迭代法而不 是从令 求解的。,搜索算法概述,迭代算法的基本思想： 首先, 确定目标函数f(x)的极小点 x*的一个初始估计点 x(0), 然后 按照一定的迭代规则(即所谓算法)，先找到一个比 x(0)更好的点 x(1), 即 f(x(1)f(x(0), 再找比 x(1)更好的点x(2), 如此继续下去, 得 到点列x(k), k=1,2, 使得当点列x(k)是有穷点列时，其最后一个点是非线性规划问 题的最优解； 当点列x(k)是无穷点列时,它有极限点 x*，且极限点 x*就是非线 性规划问题的最优解.,下降迭代算法的一般迭代格式：,使用迭代算法求解非线性规划问题的关键在于如何构造每一轮的搜索方向和确定适当的步长！,(1) 选取某一初始迭代点 x(0);,(2) 确定搜索方向：若已得一迭代点 x(k), 且 x(k)不是极小点, 就从 x(k) 出发确定一搜索方向 p(k), 沿这一方向找到使目标函数值下降的点.,(3) 确定步长：沿 p(k) 方向前进一个步长, 得到下一迭代点 xk+1),即在由点 x(k) 出发的射线 x=x(k)+tp(k) (t0), 选定步长 t=tk, 得到下一迭代点 x(k+1)=x(k)+tkp(k), 使得 f(x(k+1)f(x(k).,(4) 检验新的迭代点是否为要求的极小点或近似极小点，如果满足要求，迭代停止；否则令 k=k+1, 转步骤(2)继续迭代.,当已知迭代点和下降方向时，要确定适当的步长，按照对步长选取的不同原则，可分为两种类型： (1) 最优一维搜索：用一定方法求得步长 tk, 使目标函数 f 从当前点 x(k) 出发沿方向 p(k) 取得最优值，即,即求步长 tk, 使得,(2) 可接受一维搜索：即寻找步长,精确一维搜索的重要性质：,图：精确一维搜索时搜索方向与 最优点处函数等值面相切,常用的终止迭代准则有： (1) 根据相继两次迭代结果的绝对误差: (2) 根据相继两次迭代结果的相对误差: (3) 根据函数梯度的模足够小:,算法的收敛性常同初始点选择有关。 （1）当点x0充分接近于最优解x*时，由某方法产生的点列才收敛于x*，则该方法叫做具有局部收敛性； （2）对任意初始点x0，由某方法产生的点列都收敛到x*，则该方法叫做具有全局收敛性； （3）若某方法经过有限轮迭代就可达到目标函数为二次函数的无约束非线性规划模型的最优解，此方法叫做具有二次收敛性.,通常，一个非线性规划算法还要求具有收敛性：设由该算法产生的迭代点列为 ，当点列为有穷点列时，其最后一个点是最优解，当点列为无穷点列时，在某种模的意义下它收敛于问题的最优解，即,各种迭代算法的迭代过程是相同的，无论是求解无约束极值问题或是求解约束极值问题，在确定最优步长的过程中往往都会遇到一元函数极值问题，以下将介绍一元函数求极值的直接方法一维搜索法,一维搜索法,对一维极小化问题,设 a, b是目标函数 的单峰区间。 其本思路是：找出已知包含最优解点的单峰区间，通过迭代逐渐缩小单峰区间的长度以达到任何所需的精度来近似确定最优点的位置。,一维搜索法主要用于严格单峰函数的一元函数。,一个区间是某函数的单峰区间意味着该区间中函数只有一个极小值.,在单峰区间上的函数，即单峰函数如下图(1)所示：,单峰函数的重要性质通过单峰区间内相异两点函数值的计算，可以划定极小值点所在位置。,设 a, b是目标函数 的单峰区间。以下介绍的两种方法不是直接找出最优点，而是通过不断缩短单峰区间长度来搜索并得到一维极小化问题的两种近似求解方法二分法、黄金分割法与斐波那契法。,对一维极小化问题,设已知单峰函数 的峰点t*(最小点)处在t=a, b区间(见下图a) 在a,b中, 任取两点t1、t2 且t1t2, 计算 和 则t*必在区间a, t2(如下图 (a), 或者t*必在t1, b中(如下图 (b).,这样反复进行，直到把区间缩小到一定精度为止。 由此可知，随着迭代次数的增加，包含t*的子区间长度越来越短，而这一工作是通过一次次计算并比较有关点处函数值来实现的。,问题：如何选取比较点的位置，可使在进行相同迭代次数之后，“浓缩”的区间长度尽可能地短？,可见,只要在a,b内任取两点,就必能把t*压缩在区间a,t2或t1,b内.若要继续缩小区间,只需再计算1个点又可缩短一部分区间长度.,二分法的具体做法如下：令I0=a,b为当前的搜索区间,二分法中取的点a1和b1的值关于当前搜索区间的中点对称，这意味着,重复运用这一算法就保证搜索的区间的长度将趋向于所需要的精度.,但是，在二分法的每次迭代时要计算两个值f(t1)和f(t2), 但最后又放弃了一个，黄金分割法通过在每次迭代中将放弃的这个值利用起来，以节省计算量。,黄金分割法的具体做法如下：令I0=a,b为当前的搜索区间,则下一步迭代的搜索区间I1 =a, t2 或t1 , b .,考虑搜索区间为I1 =a, t2 的情形，这意味着t1包含在区间I1中，在第二次迭代时选择t2等于第一次迭代时的t1，可以推出，,黄金分割法的设计保证搜索区间可以减少为上次迭代的 倍 黄金分割法比二分法收敛更快,斐波那契法,斐波那契法优点寻优收敛快, 计算次数少; 斐波那契法缺点 每步取点繁琐； 开始寻优之前计算函数值的次数需事先知道； 各步缩短率不同。,这里的二分法、黄金分割法和斐波那契法都属于用直接法解决单变量函数的优化问题的方法，即只用到函数值，而未用到函数的解析性质。 通常，直接法的收敛速度较慢，只在变量较少时才适用。但直接法的迭代步骤简单，特别是当目标函数的解析表达式十分复杂，甚至写不出具体的表达式或它们的导数很难求得，或根本不存在，就只有用直接法了.,多维无约束寻优方法,无约束极值问题可简单表述为： min f(x)，xRn,求解非线性规划问题的迭代法，关键是如何求出每步的搜索方向p(k)及步长t。由于确定p(k)及t的途径不同，从而导致不同的寻优方法。其中可分两大类: 解析法：迭代中需用到函数的一阶导数(梯度)或二阶导数; 直接法：迭代中不用函数的导数等解析性质。,x(k+1)=x(k)+p(k)且满足 fx(k+1)fx(k)，逐步迭代直至满足精度条件 fx(k+1) 1 或 fx(k+1)fx(k) 2 时迭代停止(其中1，2为给定精度)。,梯度法最速下降法 (1) 搜索方向p(k) 的确定 设p为单位向量, |p|=1. 考虑从点x(k)出发沿方向p取步长t得到邻近点x(k)+tp，,由于选择方向时只考虑到当前下降最快，未顾及到总寻优快慢，因而最速下降法又称“瞎子爬山法”。,(3) 算法终止条件： 通常用f(x(k)=0或|f(x(k)|0是充分小的正数)作为最速下降法的迭代终止条件.,最速下降法的优缺点: (1) 方法简单，每一轮迭代工作量少，所需计算的存储量也少, 且此法对初始点的选取没有特别要求。 (2) 由于梯度是局部性质，从一点的邻近来说函数值下降的快, 对于整个求解极小点过程不一定是最快的； (3) 用最速下降法寻找极小点时，搜索路径呈直角锯齿形，开头几步目标函数下降较快，但是当接近极小点时，搜索步长较小收敛速度减慢。,为了克服最速下降法的搜索路径呈锯齿形的困难，后面介绍的算法将不再沿 方向移动，而是沿 或 其中D是一个适当的矩阵，g是一个适当的向量.,梯度法牛顿法,最速下降法为最简单的梯度法，,较复杂的方法为牛顿法，,牛顿法是利用Hesse矩阵的逆矩阵左乘最速下降方向的一个偏斜最速下降方法。,最速下降法收敛速度较慢,牛顿法的收敛速度较快,给定点x(k) , 牛顿法是利用函数f在点x(k)处的二次Taylor展式的近似函数的极小点作为下一个迭代点x(k+1) 。,设f(x)在点x(k)处二阶可导, 则f(x) 在点x(k)处的二次逼近式为,牛顿法的基本思想在每一轮迭代时，用一个适当的二次函数来近似目标函数, 并用迭代点处指向近似二次函数极小点的方向来构造搜索方向, 用精确求出的这个二次函数的极小点作为目标函数极小点的近似.,以上分析说明, 如果目标函数为正定二次函数, Newton法一次迭代就可以得到最优解. Newton法是一个具有二次终止性的方法.,Newton法的收敛性问题： 对于目标函数为非二次函数的无约束非线性规划问题, 用Newton法通过有限轮迭代并不能保证可求得最优解。 可以证明, 在初始点离最优解不远的条件下, Newton法是二次收敛的. 但是, 当初始点选得离最优解太远时, Newton法并不是收敛的, 甚至连其下降性也可能保证不了。,牛顿法的优缺点 牛顿法通常比梯度法收敛快，然而需采用二阶梯度阵之逆阵，逆阵计算往往比较繁琐。,问题：如何修正牛顿法，使得其成为全局收敛的算法，并有较快的收敛速度？,修正Newton法克服了Newton法的缺点. 特别是当迭代点接近于最优解时, 此法具有收敛速度快的优点. 但是, 修正Newton法需要计算目标函数的Hesse矩阵和逆矩阵, 所以求解的计算工作量和存储量甚大, 因此修正的Newton法仍有相当的局限性. 为克服最速下降法收敛速度慢及Newton法有时失效和在维数较高时计算量大的缺点, 不少学者提出了一些更实用的其他算法, 如共轭梯度法、变尺度法等.,不用导数的无约束寻优方法,不用导数的方法又称最优化搜索法，一般情况，利用导数迭代寻优比搜索法速度快。然而利用导数寻优常常面临两个困难： 在多变量或复杂函数中，求导困难。 执行方法前准备工作太多。 因此，对使用者来说，非导数型搜索法还是常用的。,直接搜索法坐标轮换法,不用导数的无约束寻优方法,该方法使用坐标轴作为搜索方向。更准确的说，方法是沿着方向d1, d2, , dn进行搜索，其中dj是一个除了在第j位置为1的零向量。于是，沿搜索方向dj, 变量xj是变化的，而其余变量保持固定。,第1步：选取数 作为终止算法使用，并设d1, , dn是坐标向量。选取一个初始点x(0), 令y0=x(0), k=0，j=1, 转第2步.,第2步：设 是 的极小化问题的一个最优解，并设 如果jn, 用j+1代替j, 并重复步骤2；否则如果j=n, 转第3 步。,第3步：令x(k+1)=yn, 如果 则停止；否则令y0=x(k+1), 令j=1, 用k+1代替k, 重复步骤2.,例：考虑下面的问题,注意：重大的进展是最初几次迭代, 而后面的迭代进展很慢, 七次迭代后, 到达点(2.25,1.12), 相应的目标值为0.004.,后面迭代进展很慢的原因是, 因为沿着用虚线表示的“谷”出现了短的垂直移动.,可以证明： 当将坐标轮换法应用到可微函数时，将收敛于梯度为零的点； 但当f(x)无可微性时，此方法可能停止在一个非最优点。,在点x2沿任何坐标轴搜索, 不能导致目标函数值的改善 并且得到过早的终止. 这个过早终止的原因是因为 f不可微而出现“谷”引起的, 这一困难可以通过沿方向 x2-x1搜索得到克服.,加速步： 沿方向x(k+1) x(k) 搜索在应用坐标轮换法中经常使用，即使f是可微的情形也是如此。 通常使用的经验方法是每迭代p次使用一次。这一改进使得坐标轮换法常常加速收敛，特别，在沿“谷”产生锯齿形的点序列时更是如此。这一步通常称为加速步。,步长加速法或模式搜索法（Pattern Search method） 该法为改进坐标轮换法而设计，方法搜索简单（不在某方向上取极值点）。其主要分两步进行： 环绕基点的“探测搜索”，称I型搜索。 在选择的极小化方向上的“模式搜索”。又称II型搜索。,不用导数的无约束寻优方法,给定点x1, 沿坐标方向的探测搜索产生点x2，现在又沿方向x2-x1模式搜索导致电y. 下一个从y开始的探测搜索给出点x3, 下次模式搜索沿方向x3-x2进行，并给出y. 过程照此重复进行。,第1步：选取数 作为终止算法使用，并选取一个初始点x(0), 令y0=x(0), k=j=1, 转第2步.,第2步：设 是 的极小化问题的一个最优解，并设 如果j-1n, 用j+1代替j, 并重复步骤2；否则如果j-1=n, 转第3 步。,第3步：设d=xk+1 xk, 并设 是 的极小化问题的一个最优解。设 令j=1, 用k+1代替k, 重复步骤2.,例：考虑下面的问题,注意： 模式搜索通过沿几乎平行于虚线所表示的“谷”的方向移动，显著的改进了收敛性。,约束极值问题惩罚函数法,惩罚函数法和障碍函数法是把约束非线性规划问题的求解转化 为一系列无约束非线性规划问题的求解。 其基本思想是: 通过改变目标函数来达到消去约束的目的, 可以 将目标函数附加上由约束函数构成的“惩罚项”或“障碍项”, 构造 出带参数的新的辅助目标函数, 从而把约束问题的求解转化为一 系列以新函数为目标函数的无约束问题的求解, 所以也叫做序列 无约束极小化方法(Sequential Unconstrained Minimization Technique, 简称为SUMT). 常用的有SUMT外点法（又称外惩罚函数法），另一种为 SUMT内点法（又称障碍函数法）。,惩罚函数法：加到目标函数的惩罚项是对任何一个违背约束进行而加上去的。 这种方法生成一系列非可行点, 其极限就是原问题的一个最优解.,障碍函数法：加到目标函数中的障碍项是为了阻止所求得的点离开可行域而加上去的. 这种方法产生一系列的可行点, 其极限就是问题的最优解.,首先，考虑带等式约束的非线性规划问题 min f(x) s.t. hj(x)=0, j=1,2,p (I) 假定其最优解存在，可行域记为S.,函数F(x,M)对可行点不实行惩罚，对非可行点给予很大惩罚。,求解等式约束问题(I)转化为求解无约束问题,M称为惩罚因子, 为充分大的正数, P(x)称为惩罚函数，MP(x)为惩罚项。,对带不等式约束的非线性规划问题 Min f(x) s.t. gi(x) 0, i=1,2,m (III),构造函数,求解带不等式约束的非线性规划问题(III)转化为求解 无约束非线性规划问题,记可行域为S. 可以取惩罚函数P(x)为,对一般的约束非线性规划问题,一般的，惩罚函数可取为,例：考虑下面的问题,对任何 而言, 目标函数是凸函数，其必要充分条件为该函数的梯度为零，,例：考虑下面的问题,易知，此问题的最优点为(x1, x2)=(1/2, 1/2)T, 目标值为1/2.,现考虑下面的惩罚问题,定理: 对某个确定的M0, 若无约束极值问题的最优解x(M) S, 则x(M)必定是约束极值问题的最优解.,通常，无约束极值问题的最优解x(M) 通常不属于可行域S, 即是不可 行的，但当惩罚参数M取的非常大的时候，所得到的最优点从可行 域的外部趋向于原问题的最优解.,因此，惩罚函数法的做法是，如果无约束极值问题的最优解x(M)不属于S, 这时应该增大M. 一般取M为一个数列Mk, 如取,表明x(k)靠近边界,或者，也可以选取终止条件为,初始点选取在点(2,1)T, 目标函数值等于0, 惩罚参数初始值为Mk=0.1, C=10 算法在迭代四次后终止，,惩罚函数法的不足： (1) 由于要求解一系列无约束极小化问题, 工作必然增大; (2) 选取充分大的系数M，可以使惩罚问题的解任意接近于原问题的最优解。然而，在求解过程中Mk不断增大, 迭代过程收敛时, Mk 常常很大, 这就可能陷入由于病态而带来某些计算上的困难. (3) 由于Mk很大, 着重点是放在可行性上，适合于无约束最优化的大部分程序都将很快的向可行点移动。然而，可能导致导致一个有较大目标函数值的可行点，或一个不可行点, 远离最优点，出现过早的终止。,障碍函数法 与惩罚函数法类似, 障碍函数法(或SUMT内点法)也是把 一有约束极值问题转化为一系列无约束极值问题, 但不同 的是, 障碍函数法是求出一系列无约束极值问题的最优解 xk, 从原问题的可行域的内部来逼近原问题的最优解. 障碍函数法从满足约束条件的可行域的内点开始迭代, 将 原问题的目标函数和约束函数构成“障碍项”，当迭代点接 近约束区域时，函数值陡然增加，对企图穿越可行域边 界的点予以惩罚. 当迭代点愈接近边界,惩罚就越大, 从而保证迭代点的可行性.,约束极值问题障碍函数法,考虑带不等式约束的非线性规划问题,Min f(x) s.t. gi(x) 0, i=1,2,m,要求障碍函数满足：,通常取内惩罚函数为,由于r很小，因此在可行域内部距离边界较远的地方，辅助函数与目标函数f(x)的值很接近，而当x趋于边界时，辅助函数将趋于+。显然，r取值越小，辅助函数的无约束极小点越接近于原问题的极小点，但是r取值过小，将给辅助函数的极小化计算带来很大困难，因此一般都采用一个严格单调递减且趋于零的正罚参数数列rk. 对每个rk值，做出一个对应的内惩罚函数项rkB(x), 并构造定义在X0上的辅助目标函数,求解带不等式约束的非线性规划问题可以转化为一系列无约 束极值问题，即求障碍函数F(x,rk)的极小.,障碍函数迭代法步骤： 取r1 0, 给定允许误差0. 求出约束集合S的一个内点x(0) . 以x(k-1)为初始点，求解,初始内点的求法？,例：考虑下面的问题,0,障碍函数法的不足： 寻找满足gi(x) 0的点不是一件容易的事情。 当rk不断减小时, 障碍函数可能越来越病态，使得求解无约束极小问题变得很困难。甚至当迭代点逼近边界时，由于搜索方法使用离散步长，一步可能跳到区域边界之外，使得F(X,rk) 的值减小而伪造成功。 要对可行性作明确检查，以保证迭代点不离开可行区域。 障碍函数法无法处理等式约束。,混合惩罚函数法,约束极值问题Frank-Wolfe法,可行方向法是解决带约束非线性规划问题的一类基本方法. 可行方向法可以看做是无约束下降算法的自然推广，其典型策略 是从问题的可行点出发, 在可行的迭代点处不断构造适当的可行 下降方向并沿该方向进行一维搜索的方法. 该类方法对于每次迭代，要求两个主要策略： （1）选择一个下降可行方向； （2）沿着这个下降可行方向选择一个步长.,考虑带线性约束的非线性规划问题,Frank-Wolfe法是Frank和Wolfe于1956年提出的求解线性约束问题的一种算法，属于一种可行方向法. 该方法的思想是，不断利用目标函数在迭代点处的近似线性化来构造可行下降方向.,由目标函数f(x)在可行域S中可微, 对xkS, 利用f(x) 在点xk 处的一阶Taylor展式这一线性函数逼近目标函数, 有,在点xk的领域与原问题近似的线性规划问题为,设yk是近似线性规划问题的最优解。,定理：设f在可行域S上可微，xkS. 设yk是近似线性规划问题 (2)的最优解，则,该定理结论说明，利用求解近似线性规划可以产生目标函数在点xk处关于可行域的可行下降方向。,Frank-Wolfe法的思路： 先选取问题(1) 的一个初始可行点, 对每一迭代点xkS, 求解近似线性规划, 并设解得其最优解为yk.,则由定理可知, 已得到问题的KKT点xk.,否则建立f(x)在点xk处关于可行域S的可行下降方向pk=yk-xk.,从点xk出发,沿可行下降方向pk在xk和yk之间的连线上进行 有效一维搜索,