约束优化算法：拉格朗日乘子法

拉格朗日乘子法精品资料约束优化问题的标准形式为：minf ( x), xrnn其中f , gi , hj : rrs.tgi ( x)0,i h j (x)0, j1,2,., m1,2,.,l约束优化算法的基本思想是：通过引入效用函数的方法将约束优化问题转换为无约束问题，再利用优化迭代过程不断地更新效用函数，以使得算法收敛。1. 罚函数法罚函数法（内点法）的主思想是：在可行域的边界上筑起一道很高的“围墙”， 当迭代点靠近边界时， 目标函数陡然增大，以示惩罚， 阻止迭代点穿越边界，这样就可以将最优解“挡” 在可行域之内了。它只适用于不等式约束：minf (x), xrns.t.gi0, i1,2,., m它的可行域为：d xrn| gi (x)0, i1,2,., m对上述约束问题，其其可行域的内点可行集d0的情况下，引入效用函数：minb( x, r )f ( x)rb (x) 、m其中 b(x)1m或 b( x)| ln(gi (x) |i 1gi ( x)i 1算法的具体步骤如下：给定控制误差0，惩罚因子的缩小系数0c1 。步骤 1：令 k1 ，选定初始点x(0)d 0 ，给定r10 （一般取10 ） 。步骤 2：以x(k ) 为初始点，求解无约束kminb( x, r )f ( x)rk b(x)m其中 b(x)1m或 b( x)| ln(gi (x) | ，得最优解x(k )x( r )i 1gi ( x)i 1k步骤 3 ：若r b( x( k) )，则 x( k ) 为其近似最优解，停；否则，令rkcrk , kk1 ，转步骤 2.2. 拉格朗日乘子法( k )( k ) tt（1） ） ph 算法：（约数为等式的情况引入）效用函数为minm ( x, u,k )f ( x)uh(x)k h(x)h(x)判断函数为khx( k)( k )当k(x)时迭代停止。步骤 1 ：选定初始点x(0) ，初始拉格朗日乘子向量u (1) ，初始罚因子及其放大系数c1 ，1控制误差0 与常数(0,1) ，令 k1。步骤 2 ：以x(k1)为初始点，求解无约束问题：minm ( x, u ( k ) ,)f ( x)u ( k ) t h(x)h(x)t h(x)kk得到无约束问题最优解x(k )步骤 3 ：当hx( k)时，x( k ) 为所求的最优解，停；否则转步骤4.步骤 4 ：当hx(k )/hx( k )时，转步骤5；否则令k 1ck ，转步骤5.( k步骤 5 ：令 u1)u( k )h( x( k ) ), kk1 ，转步骤 1。k（2） ）phr 算法（一般约束形式的松弛变量法和指数形式法） 松弛变量法：1122m (u, v,)f (x)max0, uigi ( x)ui22llv h (x)h 2 (x)jjjj 12 j 1乘子的修正公式为：v( k 1)v( k )h ( x( k ) ), j1,.,ljjju(k 1)max 0,u(k )g ( x( k) ),i1,.,miii判断函数为：lmh 2 ( x( k) )maxg ( x( k ) ),(k )ui21/2kjij 1i 1( k )当k(x)时迭代停止。3. 乘子法 matlab程序及其作用3.1 al _ main 函数3.1.1 程序（ 1）：乘子法效用函数程序函数功能：将约束优化问题，根据效用函数方法，将其转变成无约束问题。function f=al_obj(x)% 拉格朗日增广函数%n_equ等式约束个数%n_inequ不等式约束个数global r_al pena n_equ n_inequ;%全局变量h_equ=0; h_inequ=0; h,g=constrains(x);% 等式约束部分for i=1:n_equh_equ=h_equ+h(i)*r_al(i)+(pena/2)*h(i).2;end% 不等式约束部分for i=1:n_inequh_inequ=h_inequ+(0.5/pena)*(max(0,(r_al(i)+pena*g(i).2-r_al(i).2);end% 拉格朗日增广函数值f=obj(x)+h_equ+h_inequ;3.1.2 程序（ 2）：判断函数函数功能：判断是否符合约束条件% the compare function is the stop condition function f=compare(x)global r_al pena n_equ n_inequ; h_equ=0;h_inequ=0;h,g=constrains(x);% 等式部分for i=1:n_equh_equ=h_equ+h(i).2;end% 不等式部分for i=1:n_inequh_inequ=h_inequ+(max(-g(i),r_al(i+n_equ)/pena).2;end f=sqrt(h_equ+h_inequ);3.1.3 程序（ 3）al 算法主程序函数功能：对无约束的效用函数利用拟牛顿算法求解其最优解，更新乘子。function x,fval=al_main(x_al,r_al,n_equ,n_inequ)% 本程序为拉格朗日乘子算法示例算法% 函数输入：%x_al: 初始迭代点%r_al ：初始拉格朗日乘子%n-equ: 等式约束个数%n_inequ: 不等式约束个数% 函数输出%x ：最优函数点%fval: 最优函数值%=程序开始=global r_al pena n_equ n_inequ;% 参数（全局变量） pena=10;% 惩罚系数c_scale=2;% 乘法系数乘数cta=0.5;% 下降标准系数e_al=0.005;% 误差控制范围max_itera=25;out_itera=1;% 迭代次数%=算法迭代开始=while out_iteramax_itera x_al0=x_al; r_al0=r_al;% 判断函数compareflag=compare(x_al0);% 无约束的拟牛顿法bfgs x,fval=fminunc(al_obj,x_al0);x_al=x;% 得到新迭代点