优化问题的经典解法.doc

第4章 优化问题的经典解法Chapter 4 Classical Optimization4-1 优化问题的最优解 （Optimum solution）4-1-1 无约束最优解、约束最优解所谓优化问题的最优解 变量的最优点+ 函数的最优值（Optimum point + Optimum value）。根据优化问题是否存在约束，有无约束最优解及有约束最优解之分。1) 无约束最优解使函数取得最小Minima（最大Maxima）值的解称之，见图4-1。 图4-12) 约束最优解使函数取得最小（最大）值的可行解称之。情况要比无约束问题复杂，见二维问题的示意图4-2。 约束不起作用 一个起作用约束二个起作用约束 线性规划问题 图4-24-1-2 局部最优解解和全局最优解 （Relative or local & Absolute or global minimum）以一维问题为例，对于无约束优化问题，当目标函数不是单峰函数时，会出现多个极值点，对应的函数值为。每一个极值点在数学上称为局部最优点，它们中间的最小者才是全局最优点。对于约束优化问题，情况就要更复杂一些，目标函数、约束函数的特性都会使得可行域内出现二个以上的局部极小点，其中函数值最小者，称为全局最优点。P16 Fig3.2 , P30 图2-10清华本课程中讲述的所有优化方法目前只能求出局部最优解，而优化设计的目的是要追求全局最优解。因此，除了凸规划问题以外，要进行局部最优解之间的比较，选择出问题的全局最优解来。P124-2 凸集、凸函数与凸规划4-2-1 凸集 （Convex set）函数的凸集表现为其单峰性（Unimodal）。 对于具有凸性的函数而言，其极值点只有一个，该点即是局部极值点，也是全局最优点。为了研究函数的凸性，首先引入凸集的概念。P1213定义 在维空间中，对某集合内的任意二点和作连线。若连线上的每一个点都属于该集合，则称该集合为维空间的一个凸集，见图4-3。 图4-3Definition: A set is convex if for any points and in the set, the line segment joining these points is also in the set. The set (shown in Fig.4-5 (a) and (b) is convex.4-2-2 凸函数（Convex Function）仅有一个局部最优点(值)（也是全局最优点）的函数称为凸函数。1) 凸函数的数学定义（ Definition of Convex Function） 图4-4凸函数的数学定义可以从一元函数推出。如图4-4是一具有凸性的一元函数。可以看到，在该曲线上任取二点和连成的直线都位于曲线的上方，即直线的纵坐标值一定大于或等于对应点的函数值。这种关系可以用数学式表示如下 （曲线 弦）曲线的右端点曲线的左端点若上面不等式的 号改为 号，则函数称为严格凸函数Strictly Convex Function。对于多维问题，不等式的形式还是一样，只是 p222) 凸函数的性质 (Property)（a） 二个凸函数的和亦是一凸函数 A convex function plus a convex function is a convex function also. 和为二个任意正数（b） 若和是凸函数的二个极小点，则其连线上的一切点均为的极小点。If two points and are minimum for a function , any point in the line joining two points is also minimum.3) 凸函数的判定 (judgement of convex function)凸函数的判定有二种方法，第一种就是凸函数的定义，实用性差，只有理论价值。第二种方法是，若函数在凸集上存在二阶导数并且连续，在上为凸函数的充分必要条件是：对于任意，的矩阵处处都是半正定的; 若矩阵处处都是正定的，则是上的严格凸函数。反之不成立。 P22Let be a twice differentiable function on the open convex set. Then is convex on if and only if the Hessian matrix is positive semidefinite for every ; If is positive definite for every , then is strictly convex on . Note that the later condition is sufficient but not necessary.4-2-3 凸规划 Convex programming1) 定义 对于约束优化问题 若均为凸函数，称此问题为凸规划问题。2) 性质 凸规划问题最重要的性质是（1） 可行域为凸集；Feasible set is convex set;（2） 局部最优解就是全局最优解。Partial minimum is global one also .4-3 无约束优化问题的极值条件函数在没有任何限制的情况下取得极值的条件是1) 必要条件 (Necessary Condition)一元函数在点取得极值的必要条件是 多元函数在点取得极值的必要条件 2) 充分条件( Sufficient Condition) 一元函数在点取得极值的充分条件是 取极小值 取极大值 需要进一步求导判断 多元函数在点取得极小值的充分条件是 函数在的矩阵正定 Positive Definite4-4 等式约束优化问题的极值条件 拉格朗日乘子法 (Lagrange Multipliers)拉格朗日在1760年首次提出，可以用拉格朗日乘子法求解下面等式约束优化问题 拉格朗日法的主要思路是，借助拉格朗日乘子，将约束并入目标函数，构造一个新的无约束的Lagrange函数根据无约束优化问题的极值的条件可以得到方程组 联立求解上述个方程，就可求得和 共个变量。 最后一组公式保证了最优解满足约束条件，且拉格朗日函数的最优解等价于原优化问题的最优解，即。P17例4-1求下列约束优化问题的最优解 解 首先，构造一个Lagrange函数一般来说，在从等式约束比较多的情况下, 如果从等式中能够解出一个或者多个变量，最好的办法是，利用这些关系，把这些变量从优化问题中消去，就可以降低问题的维数和等式约束数。P19 ex.3.2Exp.4-2Solution: First eliminate by . Then ,which yields the three necessary conditionsinstead of the five equations in five unknowns which would result from the Lagrangian if written4-5 不等式约束的极值条件 Kuhn-Tucker条件 用拉格朗日乘子法可以求解等式约束优化问题。根据这个思想，Kuhn和Tucker扩展了该方法，使得可以用它来解决一般的包括等式和不等式约束的优化问题-非线性规划问题。Kuhn-Tucker条件阐述如下。对于一般的约束优化问题 如果目标函数和约束函数可微，是一个可行点，为可行点的起作用约束的集合。如果各个和 彼此线性无关Linearly Independent,是上述约束优化问题的最优解，则它必定满足下列条件如果约束优化问题只有等式约束，则K-T 条件成为可以发现，这时的K-T 条件就是拉格朗日乘子法。如果约束优化问题只有不等式约束，则K-T 条件成为K-T条件的几何解释 上式也可以写成 或 该式表示的K-T条件的几何意义是：在约束极小点处,函数的负梯度一定能表示成所有起作用约束在该点梯度的非负线性组合。或者该点函数的负梯度应落在由该点诸起作用约束的梯度在设计空间中张成的锥角内。以二维问题为例说明之。考虑在点有二个起作用约束的情况。过点作目标函数的负梯度（垂直于等值线（面），且指向函数下降的方向），及约束函数的梯度（分别垂直于约束线（面）并形成一个锥形夹角区。此时可能出现二种情况：第一，在的夹角之外。此时，总可以找到比的函数值要小，又不破坏约束的其他点。因此，点不是约束最优点;第二，在的夹角之内。此时，比的函数值小的所有点都在可行域之外。因此，点是约束最优点。(见教材P2425) 应该注意的是，K-T 条件仅仅是确认可行点是否为最优点的必要条件而非充分条件，只有当优化问题是凸规划问题时，它才是约束极值问题的充要条件。换句话说，满足该条件的可行点不一定就是最优点，而不满足该条件的可行点一定不是最优点。例 4-3 用K-T 条件判断点和哪一个是下列约束优化问题的最优点？ 解: 在点，起作用约束为，K-T条件为 满足非负条件在点，起作用约束是，K-T条件为 亦满足非负条件但, 所以是上述约束优化问题的最优点。(满足的不一定是最优)如果在最优点，和 出现线性相关，就不能保证该约束优化问题在点一定满足K-T条件。例4-4 分析下列约束优化问题的K-T条件 图4-5 解：从图4-5能很清楚地看到，该约束优化问题的最优解是，；在点，起作用约束为和, K-T条件为 这样代入K-T条件有代入，第一式成为矛盾方程因此，在最优点不满足 K-T 条件。其原因是，在点有，即，显然它们彼此线性相关。如果把目标函数改成，最优点仍为，且在点和依然彼此线性相关，但K-T条件中的第一式就成为 等式成立 因此，K-T条件的前提条件非常重要，否则判断不出是否是最优点。4-6 二维优化问题的几何解法 (Geometrical Solution)上面提到的极值条件、K-T条件都属于优化问题的解析解法。对于比较简单的二维问题，还可以用作图法（几何解法）来解。下面以一个例子来说明例 4-4 用图解法求解下列优化问题解 在设计平面上分别作可行域和目标函数等值线。可行域是由约束线和围成的。约束线没起到直接作用。作出一系列等值线就可以发现，其中一条与约束条件相切，其切点就是最优点。因为该点属于可行域，且是可行域中目标函数值最小的点。显然，最优点所在等值线的函数值就是最优值。若能够精确作图，可以精确地确定该点坐标为，最优值为。约束是该点的起作用约束，其它约束为不起作用约束。如果把本例中的所有约束都取消，即为无约束优化问题。它的最优点就是同心园等值线的中心，最优值为。(见图4-6) 图4-64-7 下降迭代算法与终止准则( Numerical Solution & Convergence Criterion)从上面可以看到，用几何法求解虽然直观，但仅限于二维问题。而K-T条件的主要作用是，判断用其它方法得到的可行点是否为最优点。如果通过它来求解最优点，求解过程复杂、繁琐，有时甚至求不出来。因此，一般优化问题的求解是借助于计算机，将各种优化算法编成计算程序，通过多次迭代获得近似数值解。4-7-1 数值迭代法( Numerical Iteration )1). 迭代过程及格式 数值迭代法的迭代过程是，从选定的初始点出发，按照选用的优化算法所规定的搜索方向前进一个步长，得到一个目标函数值有所下降的新的点（）。然后，再以作为新的初始迭代点，重复上述过程，又可以获得一个目标函数值有所下降的点.。如此循环下去，最后得到一个逼近理论最优点的数值解，见图4-7。数值迭代法的迭代格式为 Iteration Formula 其中，表示第次迭代Iteration ；表示第次迭代的步长（标量）Iteration Increment ；表示第次迭代的搜索方向（矢量）Searching Direction。 Initial Point, New Iteration Point 图4-72) 下降方向的选择为了保证点的搜索方向是使函数值下降的方向，必须选择在该点与目标函数的梯度方向成钝角的方向为搜索方向，即遵循所谓的“钝角原则”。选择不同的搜索方向，就形成了不同的优化算法。3) 步长因子的确定当初始点的搜索方向确定以后，迭代点的目标函数就可以表示成这是一个只有变量的函数。我们要求的是，沿方向使目标函数达到极小值的最优步长，即使的。4) 数值迭代法的特点 数值解法与解析解法完全不同，得到的解一般仅是近似解而不是精确解。循环迭代中，每一次的迭代格式相同，都是 。4-7-2 收敛准则根据迭代法的思路，只有当计算次数时，。受条件限制， 不可能趋于，何时停止计算，需要一准则来判定，该准则称为收敛准则。在优化算法中，常用三种收敛准则(1) 点距准则 Distance，前后两个迭代点之间的距离达到充分小distanceIteration error，则停止迭代； ， 即 (2) 函数下降准则 Value of function，前后两个迭代点的目标函数值的下降量达到充分小，则停止迭代； (3) 梯度准则 Gradient在迭代点，函数梯度的模达到充分小，则停止迭代。 以上准则亦可联合使用，以应付一些特殊情况。Review 4l Convex programmingConvex set; Convex function; Convex programmingLocal minimum is global one also.l K-T ConditionFor problem If is local minimum and gradients constraints ar