约束优化方法概述

1、约束优化方法 约束优化方法概述 无约束优化方法是优化方法中最基本最核心的部分。但是，在工程实际中，优化问题大都是属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。一、约束优化问题的类型 根据约束条件类型的不同可以分为三种，其数学模型分别如下： 1、不等式约束优化问题考虑问题 min f(x) s.t. gi(x) 0 i=1,2, ,m2、等式约束优化问题考虑问题 min f(x) s.t. hj(x) =0 j=1,2, ,l 3、一般约束优化问题二、约束优化方法的分类 约束优化方法按求解原理的不同可以分为直接法和间接法两类。 1、直

2、接法 只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。 其基本要点：选取初始点、确定搜索方向及适当步长。 搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。可行性：迭代点必须在约束条件所限制的可行域内，即满足 gi(x) 0, i=1,2,m 适用性：当前迭代点的目标函数值较前一点的目标函数值是下降的，即满足 F(xk+1)F(xk) 2、间接法 该方法可以求解等式约束优化问题和一般约束优化问题。其基本思想是将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进

3、行求解。如：惩罚函数法。 约束优化问题的最优解及其必要条件一、局部最优解与全局最优解 对于具有不等式约束的优化问题，若目标函数是凸集上的凸函数，则局部最优点就是全局最优点。如左图所示，无论初始点选在何处，搜索将最终达到唯一的最优点。否则，目标函数或可行域至少有一个是非凸性的，则可能出现两个或更多个局部最优点，如右图所示，此时全局最优点是全部局部最优点中函数值最小的一个。 对于具有等式约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小的一个。 对于具有一般约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小且同时满

4、足等式约束与不等式约束的一个。例如：设数学模型为 该优化问题的最优点如下图所示，对于这两个局部最小点 x1*=-1 0 T, x2*=5 0 T ，其函数值不同，F(x1*)=4, F(x2*)=16 。全局最优点为 x1*=-1 0 T F*=4h(x)h(x)g(x)x1*x2*x1x2246-2二、起作用约束与不起作用约束 对于一般约束优化问题，其约束分为两类：等式约束和不等式约束。 在可行设计点x(k)处，对于不等式约束，若gi (x(k)=o，则称第i个约束gi (x)为可行点的起作用约束；否则，若gi (x(k)0 要使函数值下降，必须使g(x)值变大，则 在X 点使f(x)下降的

5、方向（-f(X ) 方向）指向约束集合内部，因此X不是极小点 。g(X )-f(X )X*-f(x*)g(x*) 定理（最优性必要条件）： （K-T条件）库恩塔克条件 问题(fg), 设S=x|gi(x) 0,x*S,I为x*点处的起作用集，设f, gi(x) ,i I在x*点可微， gi(x) ,i I在x*点连续。 向量组gi(x*), i I线性无关。 如果x*是最优点. 那么， u*i0, i I使123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)用K-T条件求解：可能的K-T点出现在下列情况： 两约束曲线的交点：g1与g2 , g1与g3

6、 , g1与g4 , g2与g3 , g2与g4 , g3与g4 。 目标函数与一条曲线相交的情况： g1，g2 , g3 , g4 对每一个情况求得满足(1)(6)的点(x1 , x2)T及乘子u1 ,u2 ,u3 ,u4 ,验证当满足可得，且ui 0时，即为一个K-T点。下面举几个情况： g1与g2交点：x=(2,1)TS ,I=1,2 则u3=u4=0 解 2、等式约束问题解的必要条件 考虑 min f(x) s.t. h(x)=0 回顾高等数学中所学的条件极值： 问题 求z=f(x,y)的极值，在(x,y)=0的条件下。 min f(x,y) S.t. (x,y)=0 引入Lagran

7、ge乘子： Lagrange函数 L(x,y;)= f(x,y)+(x,y)即若(x*,y*)是条件极值，则存在* ，使 fx(x*,y*)+ * x (x*,y*) =0 fy(x*,y*)+ * y(x*,y*) =0 (x*,y*)=0 推广到多元情况，可得到对于等式约束问题的情况： min f(x) s.t. hj(x)=0 j=1,2, ,l 若x*是(fh)的最优点. ,则存在* Rl 使 矩阵形式：分量形式： 几何意义是明显的：考虑一个约束的情况： 最优性条件即：-f(X )X h(X )h(x)f(x*)h(x*)这里 x* -极小点. f(x*)与h(x*) 共线，而X非极小

8、点.f(X )与h(X )不共线。 3、一般约束问题解的必要条件 由上述不等式约束优化与等式约束优化问题解的必要条件，可以推出一般约束优化问题最优解的条件：四、库恩-塔克条件 在优化实用计算中，为判断可行迭代点是否是约束最优点，或者对输出的可行结果进行检查，观察其是否满足约束最优解的必要条件，引入库恩-塔克条件。上式也称为约束优化问题局部最优点的必要条件。 库恩-塔克条件的几何意义是，在约束极小点处，目标函数的负梯度一定能表示为所有起作用约束在该点梯度的线性组合。- g1(x*)- g2(x*) g2(x) g1(x) F(x*) 库恩塔克条件是确定某点为最优点的必要条件，只要是最优点，且此处

9、起作用约束的梯度线性无关，它就一定满足这个条件，但一般来说，它并不是充分条件。因而满足库恩塔克条件的点不一定是最优点。但对于凸规划，库恩塔克条件是最优点存在的充要条件。例题：求 经检验x=(1,1)T是原问题的可行解，故它是K-T点。 因为f,g是凸函数，h是线性函数， 所以x*= (1,1)T是全局最优解。 在实际问题讨论中，常常会对决策变量附加非负的限制。惩罚函数法 惩罚函数法是一种使用很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式约束和等式约束经过加权转化后，与原目标函数一起构成新的目标函数惩罚函数 通过改变加权因子r(k)、m(k)的值，求得惩罚函数的一系列无约束最优

10、解，并使其不断逼近原约束优化问题得最优解。 式中 和 称为加权转化项，并根据它们在惩罚函数中的作用，分别称为障碍项和惩罚项。障碍项的作用是当迭代点在可行域内时，在迭代过程中阻止迭代点越出边界。惩罚项的作用是当迭代点在非可行域或不满足不等式约束条件时，在迭代过程之中迫使迭代点逼近约束边界或等式约束曲面。一、内点惩罚函数法简称内点法。其基本思想是将新目标函数定义在可行域内，序列迭代点在可行域内逐步逼近约束边界的最优点。内点法只能求解具有不等式约束的优化问题。对于求解只具有不等式约束的优化问题惩罚函数形式为或式中，r(k)为惩罚因子，它是从大到小且趋近于零的数列，即r 0 r1 r2 .2、关于各类

11、参数的取值问题：（1）初始点x(0)的选取 应选取一个距离约束边界较远的可行点。若初始点太靠近某约束边界，构造的惩罚函数可能会因为障碍项的值很大而变的畸形，使求解困难。（2）惩罚因子r(0)初值的选取 一般来说，太大将增加迭代次数；太小会使惩罚函数性态变坏，甚至难以收敛。一般取r(0) =1。（3）惩罚因子缩减系数的选取 惩罚因子的关系为r(k)=cr(k-1)，其中c称为缩减系数，一般取c=0.10.74)收敛条件3、流程图例: 用内点法求下列问题的约束最优解当 r 1时解：令趋于0时，例: 用内点法求该问题的约束最优解二、外点惩罚函数法 简称外点法。其基本思想是将新目标函数定义在可行域之外

12、，序列迭代点从可行域之外逐步逼近约束边界的最优点。外点法可以求解具有不等式约束和等式约束问题的优化问题。1、惩罚函数的形式 对于约束优化问题惩罚函数的形式为式中，r(k)为递增序列例: 用外点法求下列问题的约束最优解例: 用外点法求下列问题的约束最优解三、混合惩罚函数法 混合法可以求解具有不等式约束和等式约束问题的优化问题。1、惩罚函数的形式 对于约束优化问题惩罚函数的形式为式中，r (k) 为递减序列例: 用混和法求下列问题的约束最优解rk11/41/161/641/256x11.5531.11591.0401.0101.0021x21.3341.6411.7111.7271.731 以上介绍的外点法、内点法、混合法是常见的罚函