p=x-xk=-G-1(xk)g(xk)
? 因此，可近似得到迭代关系：
xk+1=xk-G-1(xk)g(xk)
无约束非线性规划—牛顿法
? 牛顿迭代法步骤
? 初始化：给定一个初始点x0以及参数e>0；记k=0。 ? 收敛性检验：计算g(x
k
)，若||g(xk)||≤e，则算法终止；否则计算G(xk)。
k+1k+1k-1kk
? 迭代改进：计算新的迭代点x，即x=x-G(x)g(x)。k+1→k。返回收敛性检验。
无约束非线性规划—准牛顿法
? 牛顿法算法的优点是收敛速度快(利用了Hesse矩阵)。但使用
Hesse矩阵的不足之处是计算量大，Hesse矩阵可能非正定等，准牛顿法(Quasi-Newton method)是对牛顿法的改进，目前被公认为是比较有效的无约束优化方法。
? 基本思想：在迭代过程中只利用目标函数f(x)和梯度g(x)的信息，
构造Hesse矩阵的近似矩阵，由此获得一个搜索方向，生产新的迭代点。具体内容请参考相关书籍。
无约束非线性规划—Matlab函数应用
? Optimization ToolBox
Min f(x)
? Matlab提供了两个求解无约束非线性规划的函数
? [x,fval] = fminunc(fun,x0) ? [x,fval] = fminsearch(fun,x0)
? 用法相似，算法内部的搜索策略不同。fun 为f(x) 的函数形式，
x0 为初始解向量。
无约束非线性规划—Matlab函数应用
? 用法
? 创建一个matlab文件，如myfun.m
function f = myfun(x) f = f(x);
? 然后调用fminunc或fminsearch并指定初始搜索点。 x0=[x1,x2,…,xn]
[x,fval] = fminunc(@myfun,x0) 或 [x,fval] = fminsearch(@myfun,x0)
无约束非线性规划—Matlab函数应用
? 例：min f(x)=e? 解：
? 创建一个matlab文件，如myfun.m
x1
(4x12+2x22+4x1x2+2x2+1)
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); ? 调用无约束非线性规划函数
x0 = [-1,1]; % Starting guess
options = optimset('LargeScale','off'); [x,fval] = fminunc(@myfun,x0,options); 或者[x,fval] = fminsearch(@myfun,x0,options);
无约束非线性规划—Matlab函数应用
? fminunc结果：
? x =[ 0.5000 -1.0000] ? fval = 1.0983e-015 ? iterations: 8
? algorithm: 'medium-scale: Quasi-Newton line search?
? fminsearch结果：
? x =[0.5000 -1.0000] ? fval =5.1425e-010 ? iterations: 46
? algorithm: 'Nelder-Mead simplex direct search'
约束非线性规划—标准型
? 其中f(x)是目标函数，gi(x)和hj(x)为约束函数(约束条件)。
S={x|gi(x)?0 ? hj(x)=0}为可行域。
? 有约束非线性规划问题(COP)是指f(x),gi(x),hj(x)至少有一个是非线
性的，且I或??至少有一个为非空。
约束非线性规划—几个概念
? 积极(active)约束：设x
0
是COP问题的一个可行解，则它必须满足所
有约束条件。对于gi(x0)?0，或者等号成立，或者大于号成立。称等号成立的约束为积极约束(有效约束)，此时，x0处于该约束条件形成的可行域边界上；称大于号成立的约束为非积极(inactive)约束(无效约束)，此时，x0不在该约束条件形成的可行域边界上。显然所有hj(x0)约束均是积极约束。记J={j|gj(x0)=0?hj(x0)=0}，称为积极约束指标集。
约束非线性规划—几个概念
? 可行方向。设x0为COP问题的任一可行解，对某一方向d来说，若???0>0使得
对于任意??[0,?0]，均有x0+?d?S，称d为x0的一个可行方向。显然若d满足dT?gi(x)?0，dT?hj(x)=0，则d一定是可行方向。（可用一阶Taylor公式分析）。 ? 下降方向。设x0?S，对某一方向d来说，若???0>0使得对于任意??[0,?0]，均有f(x0+?d) f(x0+?d)=f(x0)+?(?f(x0))Td+o(?)可知：若d满足dT?f(x0)<0，有f(x0+?d) ? 可行下降方向。若x0的某一方向d既是可行方向又是下降方向则称其为可行下降方向。这个方向就是我们从x0出发寻求最优解的搜索方向！ 约束非线性规划—几个概念 ? 例：min f(x)=x1+x2 S.t. g(x)=1-x12-x22?0 ? 图描述了该问题的相关概念。 约束非线性规划—极小值存在条件 ? 一阶必要条件 ? 几何特征：若x 是COP问题的局部极小点且函数f(x), gi(x), hj(x)在x*处可 微，则dT?f(x*)?0。d为x*的任意可行方向。 f(x*+?d)=f(x*)+?(?f(x*))Td+o(?) * ? 代数特征(KKT定理)：若x是COP问题的局部极小点且函数f(x), gi(x), hj(x)在x*处可微，则存在实数?i?0(i?I), ?j?R(j??)，使得： ?f(x*)=?i?gi(x*)?i+?j?hj(x*)?j； gi(x*)?i=0；?i?0，?i?I *** ? 若x满足KKT条件，则称x为COP问题的一个KKT点，?i, ?j称为x处的拉格朗日乘子。 * 约束非线性规划—极小值存在条件 ? 一阶充分条件 ?S，若函数f(x), gi(x), hj(x)在x*处可微，且对于x*的任意可行方向d，有dT?f(x*)>0，则x*为COP问题的一个严格局部极小点。 * ? (凸规划问题)设f(x)为凸函数，gi(x)为凹函数，hj(x)为线性函数。对于x?S，若函数f(x), gi(x)在x*处可微，且KKT条件成立，则x*为COP问题的全局最小点。 ? 设x * 约束非线性规划—极小值存在条件 ? 二阶必要条件 是COP问题的局部极小点且满足KKT条件。若函数f(x), gi(x), hj(x)在x*处二阶可微，则必有： dT?xx2L(x*,?*,?*)d?0 其中，L(x,?,?)=f(x)-g(x)T?-h(x)T?, g(x),h(x)分别为由gi(x)和hj(x)构成的向量值函数，?,?分别为对应于g(x)和h(x)的拉格朗日乘子向量。 ? 二阶充分条件 *** ? 设x是COP问题的KKT点。?,?分别为对应于g(x)和h(x)的拉格朗日乘子向量，且函数f(x), gi(x), hj(x)在x*处二阶可微，若dT?xx2L(x*,?*,?*)d>0,则x*为COP问题的一个严格局部极小点。 ? 设x * 约束非线性规划—极小值存在条件 例：min f(x)=x12+x22 S.t. x1+x2?4 x1,x2?0 ? 解：g1(x)=x1+x2-4?0;g2(x)=x1?0;g3(x)=x2?0 ?f(x)=[2x1,2x2]T,?g1(x)=[1,1]T,?g2(x)=[1,0]T,?g3(x)=[0,1]T,得到： 2x1=?1+?2 ? ? 又(x1+x2-4)?1=0；x1?2=0；x2?3=0；?i?0 ? 若?1=0，则x1=x2=0，与题意不符； ? 若?1>0，则x1+x2-4=0，x1>0, x2>0。因此有?2=?3=0，所以x1=x2=?1/2，得x1=x2=2，x*=[2,2]T为该问题的唯一KKT点。 ? 根据凸规划充分条件知x*为全局最小点。 ? 2x2=?1+?3 约束非线性规划—可行方向法 ? 上面例题介绍了通过求解KKT方程获得问题解的方法，但KKT方 程并不总是很好求解。下面介绍几种约束优化的求解方法：可行方向法、序列无约束化法和SQP法。 ? 可行方向法的应用条件：要求所有约束均为线性约束（称为线性约 束的优化问题，LCO）。 ? 可行方向法的基本思想：当某个可行方向同时也是目标函数的下降 方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。 约束非线性规划—可行方向法 约束非线性规划—可行方向法 ? LCO问题： Min f(x) S.t. aiTx?bi, i?I ajTx=bj, j?? ? 设x0是LCO的一个可行解，若d是可行域在x0点的可行方向，则d满 足AI(x0)d?0(I(x0)={i|aiTx0=bi,i?I})，A?d=0。 ? 设x0是LCO的一个可行解，若d是可行域在x0点的下降方向，则d满 足dT?f(x0)<0。 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库决策理论与方法(2)在线全文阅读。
相关推荐：