优化问答的经典编辑解法

,.第4章 优化问题的经典解法Chapter4ClassicalOptimization感谢阅读4-1优化问题的最优解（Optimumsolution）精品文档放心下载4-1-1无约束最优解、约束最优解X*所谓优化问题的最优解变量的最优点x*,x*,x*T+函数的最优值f12n（Optimumpoint+Optimumvalue）。根据优化问题是否存在约束，有无约束最优解精品文档放心下载及有约束最优解之分。无约束最优解使函数取得最小Minima（最大Maxima）值的解称之，见图4-1。谢谢阅读4-1约束最优解使函数取得最小（最大）值的可行解称之。情况要比无约束问题复杂，见二维问题的示感谢阅读意图4-2。,.约束不起作用 一个起作用约束二个起作用约束 线性规划问题4-24-1-2局部最优解解和全局最优解（Relativeorlocal&Absoluteorglobal精品文档放心下载minimum）以一维问题为例，对于无约束优化问题，当目标函数不是单峰函数时，会出现多个极谢谢阅读值点x*,x*,x*,，对应的函数值为f(x*),f(x*),f(x*),。每一个极值点在数学上称为感谢阅读1 2 3 1 2 3局部最优点，它们中间的最小者才是全局最优点。对于约束优化问题，情况就要更复杂一些，精品文档放心下载目标函数、约束函数的特性都会使得可行域内出现二个以上的局部极小点，其中函数值最小感谢阅读者，称为全局最优点。P16Fig3.2,P30图2-10清华精品文档放心下载本课程中讲述的所有优化方法目前只能求出局部最优解，而优化设计的目的是要追求全局最优解。因此，除了凸规划问题以外，要进行局部最优解之间的比较，选择出问题的全局最优解来。P12感谢阅读4-2凸集、凸函数与凸规划4-2-1凸集（Convexset）函数的凸集表现为其单峰性（Unimodal）。对于具有凸性的函数而言，其极值点只有感谢阅读一个，该点即是局部极值点，也是全局最优点。为了研究函数的凸性，首先引入凸集的概念。感谢阅读P12~13,.定义在n维空间Rn中，对某集合D内的任意二点X(1)和X(2)作连线。若连线上的每精品文档放心下载一个点都属于该集合D，则称该集合D为n维空间的一个凸集，见图4-3。谢谢阅读X2X2X2X2X1X1aX1bX1图4-3Definition:AsetDisconvexifforanypointsxandxintheset,theline12segmentjoiningthesepointsisalsointheset.Theset(showninFig.4-5(a)and(b))isconvex.谢谢阅读4-2-2凸函数（ConvexFunction）谢谢阅读仅有一个局部最优点(值)（也是全局最优点）的函数称为凸函数。谢谢阅读1) 凸函数的数学定义（DefinitionofConvexFunction）谢谢阅读4-4凸函数的数学定义可以从一元函数推出。如图4-4是一具有凸性的一元函数。可以看精品文档放心下载到，在该曲线上任取二点x(1)和x(2)连成的直线都位于曲线的上方，即直线的纵坐标值一定谢谢阅读Iftwopoints,.大于或等于对应点的函数值。这种关系可以用数学式表示如下感谢阅读f(1(1)f(x(2))x(1))x(2)f(x(1)（曲线弦）010曲线的右端点1曲线的左端点若上面不等式的号改为<号，则函数f(x)称为严格凸函数StrictlyConvexFunction。对于多维问题，不等式的形式还是一样，只是xXxxxTp2212n凸函数的性质(Property)（a）二个凸函数的和亦是一凸函数Aconvexfunctionplusaconvexfunctionisaconvexfunctionalso.谢谢阅读f(X)f(X)f(X）感谢阅读1 2f(X)

af

(X)

bf

(

X

)

a和b

为二个任意正数1

2（b）若X(1)和X(2)是凸函数f(X)的二个极小点，则其连线上的一切点均为f(X)谢谢阅读的极小点。X(1)andX(2)areminimumforafunctionf(X),any精品文档放心下载pointinthelinejoiningtwopointsisalsominimum.谢谢阅读凸函数的判定(judgementofconvexfunction)感谢阅读凸函数的判定有二种方法，第一种就是凸函数的定义，实用性差，只有理论价值。精品文档放心下载第二种方法是，若函数f(X)在凸集D上存在二阶导数并且连续，f(X)在D上为凸谢谢阅读函数的充分必要条件是：对于任意XD，f(X)的Hession矩阵处处都是半正定的;若感谢阅读Hession矩阵处处都是正定的，则f(X)是D上的严格凸函数。反之不成立。 P22感谢阅读Letf(X)beatwicedifferentiablefunctionontheopenconvexsetn.DR,.Thenf(X)isconvexonDifandonlyiftheHessianmatrixH(X)ispositivesemidefiniteforeveryXD;IfH(X)ispositivedefiniteforeveryXD,thenf(X)isstrictlyconvexonD.Notethatthelaterconditionissufficientbutnotnecessary.谢谢阅读4-2-3凸规划Convexprogramming谢谢阅读1)定义对于约束优化问题minf(X)s.t. g(X)0 u1,2,,m精品文档放心下载uh(X)0 v1,2,,pn精品文档放心下载vf(X),g(X),h(X)均为凸函数，称此问题为凸规划问题。精品文档放心下载性质凸规划问题最重要的性质是（1）可行域为凸集；Feasiblesetisconvexset;谢谢阅读（2）局部最优解就是全局最优解。Partialminimumisglobalonealso.感谢阅读4-3无约束优化问题的极值条件函数在没有任何限制的情况下取得极值的条件是必要条件(NecessaryCondition)感谢阅读一元函数f(x)在x点取得极值的必要条件是精品文档放心下载0'(x0)0多元函数f(X)在X 点取得极值的必要条件精品文档放心下载0fx1f0f(X)x02fxn,.充分条件(SufficientCondition)精品文档放心下载一元函数f(x)在x 点取得极值的充分条件是精品文档放心下载0f"(x)0取极小值0f"(x)0取极大值0f"(x)0需要进一步求导判断0多元函数f(X)在X点取得极小值的充分条件是精品文档放心下载0函数f(X)在X的Hession 矩阵正定PositiveDefinite精品文档放心下载04-4等式约束优化问题的极值条件——拉格朗日乘子法(LagrangeMultipliers)谢谢阅读拉格朗日在1760年首次提出，可以用拉格朗日乘子法求解下面等式约束优化问题谢谢阅读minf(X)XRns.t.h(X)0v1,2......pnv拉格朗日法的主要思路是，借助拉格朗日乘子i1,2,...,p，将约束并入目标函数i(X)，构造一个新的无约束的Lagrange函数感谢阅读L(X,)f(X)ph(X)精品文档放心下载v v1根据无约束优化问题的极值的条件可以得到方程组L(X,)f(X)ph(X)0i1,2,...,nvxxv1vxiiiL(X,)h(X)0v1,2,...,pvv联立求解上述np个方程，就可求得*,x*****x,........x12n12n最后一组公式保证了最优解满足约束条件h(X*)0v1,2,...,p，且拉格朗日函数的最v优解等价于原优化问题的最优解，即L(X*,*)f(X*)。P17感谢阅读,.4-1求下列约束优化问题的最优解minf(X)x24x21 2s.t. h(X)x2x61 2解 首先，构造一个Lagrange函数Lx24x2(x2x 6)精品文档放心下载1 2 1 2L2x0,L8x20,Lx2x60.x1x21212一般来说，在从等式约束比较多的情况下,如果从等式中能够解出一个或者多个变量，谢谢阅读最好的办法是，利用这些关系，把这些变量从优化问题中消去，就可以降低问题的维数和等感谢阅读式约束数。P19ex.3.2Exp.4-2minf(X)x22x2x2精品文档放心下载123s..th(X)x23xxx21011123h(X)xx40223Solution:Firsteliminatexbyx4x.Then332L(x,x,)x22x2(4x)2(x23xxx21),121221123whichyieldsthethreenecessaryconditionsL2x2x3x0x1121L4x2(4x)3x2x0x22122Lx23xxx2101123insteadofthefiveequationsinfiveunknownswhichwouldresultfromtheLagrangianifwritten谢谢阅读,.L(x,x,,)x22x2(4x)2(x23xxx21)(xx4)谢谢阅读1 2 1 2 1 2 2 1 1 1 2 3 2 2 3感谢阅读4-5不等式约束的极值条件——Kuhn-Tucker条件感谢阅读用拉格朗日乘子法可以求解等式约束优化问题。根据这个思想，Kuhn和Tucker扩展精品文档放心下载了该方法，使得可以用它来解决一般的包括等式和不等式约束的优化问题---非线性规划问题。感谢阅读Kuhn-Tucker条件阐述如下。对于一般的约束优化问题minf(X)s..t gu(X)0 u1,2,...,m精品文档放心下载hv(X)0 v1,2,...,pn感谢阅读如果目标函数和约束函数f(X),g(X),h(X)可微，X*是一个可行点，感谢阅读Ijg(X*)0,j=1,2,...,m为可行点X*的起作用约束的集合。如果各个g(X*),jI和jjh(X*),v1,2,...pn彼此线性无关LinearlyIndependent,X*是上述约束优化问谢谢阅读v题的最优解，则它必定满足下列条件f(X*)x ji jI

g(X*)pjxviv1

h(X*)v 0 i1,2,...,nxig(X*)0 jIj 0 jIjh(X*)0 v1,2,...,pn感谢阅读v如果约束优化问题只有等式约束，则K-T条件成为f(X*)ph(X*)0i1,2,...,nxvv1vxiih(X*)0v1,2,...,pnv可以发现，这时的K-T条件就是拉格朗日乘子法。,.如果约束优化问题只有不等式约束，则K-T条件成为精品文档放心下载f(X*)g(X*)i1,2,...,nj0xjxijIig(X*)0jIj0jIjK-T条件的几何解释上式也可以写成f(X*)g(X*)0或f(X*)g(X*)jjjjjIjI该式表示的K-T条件的几何意义是：在约束极小点X*处,函数f(X)的负梯度一定能表示成感谢阅读所有起作用约束在该点梯度的非负线性组合。或者该点函数的负梯度f(X*)应落在由该点谢谢阅读诸起作用约束的梯度在设计空间中张成的锥角内。以二维问题为例说明之。感谢阅读考虑在点X*有二个起作用约束g(X*)0 g(X*)0的情况。过点X*作目标函数的负精品文档放心下载1 2梯度（垂直于等值线（面） ，且指向函数下降的方向） f(X*)，及约束函数的梯度精品文档放心下载g(X*) g(X*)（分别垂直于约束线（面））并形成一个锥形夹角区。此时可能出现二种感谢阅读1 2情况：第一，f(X*)在g(X*) g(X*)的夹角之外。此时，总可以找到比X*的函数值要精品文档放心下载1 2小，又不破坏约束的其他点。因此，点X*不是约束最优点;精品文档放心下载第二，f(X*)在g(X*) g(X*)的夹角之内。此时，比X*的函数值小的所有点都精品文档放心下载1 2在可行域之外。因此，点X*是约束最优点。(见教材P24~25)感谢阅读应该注意的是，K-T条件仅仅是确认可行点是否为最优点的必要条件而非充分条件，只有当优化问题是凸规划问题时，它才是约束极值问题的充要条件。换句话说，满足该条件的可行点不一定就是最优点，而不满足该条件的可行点一定不是最优点。感谢阅读例4-3用K-T条件判断点x1和x3哪一个是下列约束优化问题的最优点？12minf(x)1x2s..tg(x)(1x)01g(x)x302,.解:fgg112x2xx1x在x1点，起作用约束为g，K-T条件为112(1)(1)02满足非负条件11在x3点，起作用约束是g，K-T条件为222(3)06亦满足非负条件22但f(x)f(x),所以x3是上述约束优化问题的最优点。(满足的不一定是最优)212如果在最优点X*g(X*),uI和h(X*),v1,2,...pn出现线性相关，就uv不能保证该约束优化问题在X*点一定满足K-T条件。谢谢阅读4-4分析下列约束优化问题的K-T条件minf(X)(x3)2x212s.t. g(X)(1x)3x 0谢谢阅读1 1 2(X)x02 1(X)x03 24-5解：从图4-5能很清楚地看到，该约束优化问题的最优解是X*x*,x*T1,0T，12f(X*)4；在X*点，起作用约束为g(X*)0和g(X*)0,K-T条件为13ff2xg3(1x)22(x3)x1x12x1121gggx11x30x31212,.这样代入K-T条件有2(x3)3(1x）012112x(1)0213(1x)3021x0201,2，第一式成为矛盾方程代入X*1,0T40因此，在最优点不满足K-T条件。其原因是，在X*T点有g(X*)0,1，1g(X*)0,1，即g(X)g(X)，显然它们彼此线性相关。如果把目标函数T**313T改成f(X)(x1)2x2，最优点仍为X*x*,x*T，且在X*点g(X*)1,012121和g(X*)依然彼此线性相关，但K-T条件中的第一式就成为32(x1)3(1x）20等式成立111因此，K-T条件的前提条件非常重要，否则判断不出是否是最优点。谢谢阅读4-6二维优化问题的几何解法(GeometricalSolution)谢谢阅读上面提到的极值条件、K-T条件都属于优化问题的解析解法。对于比较简单的二维问题，谢谢阅读还可以用作图法（几何解法）来解。下面以一个例子来说明精品文档放心下载4-4用图解法求解下列优化问题minf(X)

x21

x22

4x1

4s.t. g(X)xx20精品文档放心下载1 1 2(X)xx2102 2 1(X)x03 1(X)x04 2解 在设计平面xox上分别作可行域和目标函数等值线。可行域是由约束线精品文档放心下载1 2g1(X)0,g2(X)0和g3(X)0围成的。约束线g4(X)0没起到直接作用。作出一谢谢阅读,.系列等值线就可以发现，其中一条与约束条件g(X)0相切，其切点就是最优点。因为精品文档放心下载2该点属于可行域，且是可行域中目标函数值最小的点。显然，最优点所在等值线的函数值就谢谢阅读是最优值。若能够精确作图，可以精确地确定该点坐标为X*x*,x*T0.58,1.34T，12最优值为f(X*)3.812。约束g(X)是该点的起作用约束，其它约束为不起作用约束。精品文档放心下载2如果把本例中的所有约束都取消，即为无约束优化问题。它的最优点就是同心园等值谢谢阅读线的中心X*0,0T，最优值为f(X*)0。(见图4-6)精品文档放心下载X24g13g22A1Xg41234X1g31FXFX9FX3.8124-64-7 下降迭代算法与终止准则(NumericalSolution&ConvergenceCriterion)谢谢阅读从上面可以看到，用几何法求解虽然直观，但仅限于二维问题。而K--T条件的主要作谢谢阅读用是，判断用其它方法得到的可行点是否为最优点。如果通过它来求解最优点，求解过程复谢谢阅读杂、繁琐，有时甚至求不出来。因此，一般优化问题的求解是借助于计算机，将各种优化算精品文档放心下载法编成计算程序，通过多次迭代获得近似数值解。4-7-1数值迭代法(NumericalIteration)谢谢阅读,.1).迭代过程及格式数值迭代法的迭代过程是，从选定的初始点X0出发，按照选用的优化算法所规定的感谢阅读搜索方向S0前进一个步长0，得到一个目标函数值有所下降的新的点X1感谢阅读f(X1)f(X0)）。然后，再以X1作为新的初始迭代点，重复上述过程，又可以获得一个目标函数值有所下降的点X2...。如此循环下去，最后得到一个逼近理论最优点的数值解，精品文档放心下载见图4-7。数值迭代法的迭代格式为IterationFormula精品文档放心下载X(k1)X(k)(k)S(k) k1,2K精品文档放心下载其中，k表示第k次迭代Iterationk；(k)表示第k次迭代的步长（标量）Iteration精品文档放心下载Increment；S(k)表示第k次迭代的搜索方向（矢量）SearchingDirection。谢谢阅读X(k)InitialPoint,X(k1) NewIterationPoint精品文档放心下载4-7下降方向S(k)的选择为了保证X(k)点的搜索方向是使函数值下降的方向，必须选择在该点与目标函数的梯谢谢阅读度方向成钝角的方向为搜索方向S(k)，即遵循所谓的“钝角原则”。选择不同的搜索方向，感谢阅读就形成了不同的优化算法。步长因子*的确定k当初始点X(k)的搜索方向S(k)确定以后，迭代点X(k1)的目标函数就可以表示成感谢阅读,.f(X(k1))f(X(k)S(k))f()感谢阅读k这是一个只有变量的函数。我们要求的是，沿S(k)方向使目标函数达到极小值的最优感谢阅读步长，即使f'(*)0的*。谢谢阅读k数值迭代法的特点数值解法与解析解法完全不同，得到的解一般仅是近似解而不是精确解。循环迭代中，感谢阅读每一次的迭代格式相同，都是 X(k1)X(k)(k)S(k)。精品文档放心下载4-7-2收敛准则根据迭代法的思路，只有当计算次数k时，XkX*。受条件限制，k不可能感谢阅读趋于，何时停止计算，需要一准则来判定，该准则称为收敛准则。在优化算法中，常用感谢阅读三种收敛准则(1)点距准则DistanceXX1Iterationerror，(k)(k1)则停止迭代；X(k1)X(K