约束非线性规划—可行方向法
? Zoutendijk可行方向法：其核心思想是通过求解下列线性规划问
题，在可行方向的某个范围内获得目标函数的最速下降方向。
Min dT?f(x0)
S.t. AI(x0)d?0, I(x0)={i|aiTx0=bi,i?I} A?d=0 ||d||∞?1
? 可以证明：当x0取得KKT点时当且仅当d
T
?f(x0)的最优值为零。
约束非线性规划—序列无约束化法
? 求解约束优化的一类重要方法是用一个无约束优化问题的序列逼
近约束优化问题，通过无约束优化问题的最优解序列逼近约束优化问题的最优解。
? 基本思想：将约束条件通过某种转换与目标函数合并形成一个无约
束优化问题。这种转换隐含着某种惩罚，即x偏离约束条件越远，受到的惩罚越大。因此也将此类方法称为罚函数法，所形成的无约束优化函数成为罚函数。
约束非线性规划—序列无约束化法
? 二次罚函数法：
? 罚函数：
? 其中(gi)-=max{0,-gi}，?称为罚参数，且当?→0时，Q(x,?)的极小值趋于f(x)
的极小值。
约束非线性规划—序列无约束化法
?
例：min f=x1+x2
S.t. x1-x22=0
? 解：对于?>0，定义二次罚函数
Min Q(x,?)=x1+x2+(2?)-1(x1-x22)2 Q’x1=1+(x1-x22)/?=0 Q’x2=1-2x2(x1-x22)/?=0
解得：x?*=(1/4-?,-1/2)T, Q*=-1/4-?/2 当?→0时得，x*=(1/4,-1/2)T, f*=-1/4
约束非线性规划—序列无约束化法
? 对数障碍函数法：
? 障碍函数：
? 其中?称为障碍参数，且当?→0时，P(x,?)的极小值趋于f(x)的极小值。 ? 该方法的适用性：COP问题仅包含不等式约束函数，且可行域存在内点。
即S0={x|g(x)>0}≠?
约束非线性规划—序列无约束化法
? 例：min{f=x/2|x?1}
? 解：构造对数障碍函数P(x,?)=x/2-?ln(x-1)
? P’x=1/2-?/(x-1)=0，得x?
=1+2?，P*=1/2+?-?ln2?
*
? 当? →0 时得x=1，f*=1/2
*
二次规划—标准型
? 若有约束非线性规划的目标函数是决策变量x的二次函数且所有约
束均为线性约束，称此类非线性规划问题为二次规划(Quadratic Programming, QP)问题。其标准型为：
二次规划—标准型
?
其中Q=QT?Rn×n（n阶对称方阵）；以aiT(i?I)为行向量的矩阵记为AI?RI×n；以ajT(j??)为行向量的矩阵记为A??R?×n；对应的向量记为bI, b?。若目标函数的Hesse矩阵Q是半正定(或正定)的，则QP问题为(严格)凸二次规划(CQP)。我们仅讨论凸二次规划问题，因为非凸二次规划的Q存在负特征根，求解很困难。
二次规划—极小点存在条件
? 充要条件
是QP问题的局部极小点当且仅当x*为一个KKT点且对于任意非
零可行方向d，有dTQd?0。
***
? 对于凸二次规划，x为全局极小点当且仅当x为局部极小点，当且仅当x为KKT点。
? 二次规划的KKT定理形式为：
Qx*+c=AIT?*+A?T?*
(AIx*-bI)?*=0
? 可行点x
*
? 二次规划的求解本质上就是求解上述KKT方程。
约束非线性规划—SQP法
? 对于非线性约束优化(COP)问题，
? 若x*是COP问题的一个局部最优解，则它对应一个纯等式约束优化
问题
约束非线性规划—SQP法
? 因此如果事先知道积极约束指标集，那么带有不等式约束优化问题
就可以转化为纯等式约束优化问题，并可用准牛顿法求解，这就是逐次二次规划(Sequential Quadratic Programming，SQP)法。
? 基本思想：在迭代点处构造一个二次规划子问题，近似原来的约束
优化问题；然后通过求解该二次规划子问题获得约束优化问题的一个改进迭代点；不断重复此过程，直到求出满足一定要求的迭代点。
约束非线性规划—SQP法
? 对于等式约束优化问题
Min f(x) S.t. h(x)=0
T
? 拉格朗日函数记为L(x,?)=f(x)-?h(x)
T
? 则?L(x,?)=(?f(x)-?h(x)?, -h(x))=0，显然问题的最优解(x*,?*)满足此式。
kk
? 设(x,?)是第k次迭代结果，根据牛顿法，有：
约束非线性规划—SQP法
? 上述迭代过程等价于如下的二次规划的迭代。设给定迭代点(x
k
,?k)，则
约束非线性规划—Matlab函数应用
? Optimization ToolBox
Min f(x) s.t. c(x)?0
ceq(x)=0 A·x?b Aeq·x=beq lb?x?ub
? [x,fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)
? fun定义目标函数,x0定义初始可行解，nonlcon定义c(x)和ceq(x)。
约束非线性规划—Matlab函数应用
? 用法
? 创建一个matlab文件，如myfun.m
function f = myfun(x) f = f(x);
? 创建另一个matlab文件，如confun.m function [c, ceq] = confun(x) c = c(x); ceq = ceq(x);
? 调用fmincon并指定初始搜索点以及其他向量、矩阵。 x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;
[x,fval]=fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@confun)
约束非线性规划—Matlab函数应用
(4x12+2x22+4x1x2+2x2+1)
S.t. x1x2-x1-x2?-1.5 x1x2?-10 ? 解：
? 创建一个matlab文件，如myfun.m function f = myfun(x)
f =exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1); ? 创建另一个matlab文件，如confun.m function [c, ceq] = confun(x)
c = [1.5 + x(1)*x(2) - x(1) - x(2); -x(1)*x(2) - 10];
? 例：min f(x)=e
x1
ceq = [];
约束非线性规划—Matlab函数应用
? 调用有约束非线性规划函数
x0 = [-1,1]; % Starting guess
options = optimset('LargeScale','off');
[x,fval]=fmincon(@objfun,x0,[],[],[],[],[],[],@confun,options) ? 运行结果：
x =[-9.5474 1.0474] fval =0.0236 iterations: 8
algorithm: 'medium-scale: SQP, Quasi-Newton, line-search'
二次规划—Matlab函数应用
? Optimization ToolBox
Min 0.5xTHx+fTx s.t. A·x?b Aeq·x=beq lb?x?ub
? [x,fval] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) ? x0定义初始可行解(可选)
二次规划—Matlab函数应用
? 用法
? 首先要将目标函数转换成二次规划标准型，从而得到H和f两个矩阵。 ? 调用quadprog并根据需要指定初始搜索点以及其他向量、矩阵。
x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;
[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
二次规划—Matlab函数应用
+x22-x1x2-2x1-6x2)
S.t. x1+x2?2 -x1+2x2?2 2x1+x2?3 x1, x2?0 ? 解：
? 改写f(x)=1/2(x12+2x22-x1x2-x1x2)-2x1-6x2
? 例：min f(x)=1/2x1
2
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库决策理论与方法(3)在线全文阅读。
相关推荐：