第7章 约束问题的优化方法
第7章 约束问题的优化方法
§7.1 可行方向法
7.1.1 可行方向法的基本思想
可行方向法是一类算法,可看作无约束下降算法的自然推广。典型策略是从可行点出发，沿着下降可行方向进行搜索，求出使目标函数值下降的新的可行点．
考虑只含线性约束的非线性规划问题：
e
Ex b Ax x f =≥ s.t.)
( min （1） )(x f 为非线性函数，n m R A ?∈，n l R E ?∈，m R b ∈，l R e ∈.
注1：线性约束规格保证了优化问题（1）的可行方向集、线性化可行方向集以及序列化可行方向集是等同的。
当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。
目前已经提出许多可行方向法，用来处理具有线性约束的非线性规划问题。 搜索方向选择方式不同形成不同的可行方向法： （1）Zoutendijk 可行方向法 （2）Rosen 梯度投影法 （3）Wolfe 既约梯度法
可行方向的判定：
定理1：设x
?是问题（1）的可行解，在点x ?处有11?b x A =，22?b x A >，其中 ??????=21A A A ，??
?
???=21b b b
则非零向量d 为x
?处的可行方向的充要条件是 01≥d A ，0=Ed
证明：
必要性：设非零向量d 是x
?处的可行方向．根据可行方向的定义，0>?δ，使得对每个),0(δλ∈．有d x
λ+?为可行点，即b d x A ≥+)?(λ，e d x E =+)?(λ. ??
?
???≥??????++=+??????=+21221121?)?()?(b b d A x A d A b d x A A d x A λλλλ 由于0>λ，由上式得到01≥d A ．
又由e d x
E =+)?(λ得到0=Ed .
充分性：设01≥d A ，0=Ed .
由于22?b x
A >，则0>?δ，使得对于所有的),0(δλ∈,成立22)?(b d x A ≥+λ. 根据假设及11?b
x A =，得到11)?(b d x A ≥+λ. 上述两式组合起来就是b d x A ≥+)?(λ. 又由0=Ed 及e x
E =?可知 e d x
E =+)?(λ 表明d x
λ+?是可行点，因此d 是x ?处的可行方向． 7.1.2 Zoutendijk 可行方向法
Zoutendijk 子问题：
根据定理1，如果非零向量d 同时满足0)?(
f T , 01≥d A ，0=Ed ,则d 是x ?处的下降可行方向．
Zoutendijk 可行方向法把确定搜索方向归结为求解线性规划问题
n
j | |d Ed d A d x f j T ,,2,1,1 0
0 s.t.)( min 1 =≤=≥? （2）
在（2）式中，显然0=d 是可行解，可推知目标函数最优值必定小于或等于零．如果目标函数最优值小于零，则得到下降可行方向d ；否则，如果目标函数最优值为零，则x 是K-T 点．
定理2：考虑问题（1），设x 是可行解，在点x 处有11b x A =，22b x A >，其中
??????=21A A A ，??
?
???=21b b b
则x 为K-T 点的充要条件是问题（2）的目标函数最优值为零．
一维搜索步长的确定： 设)
(k d
为)
(k x
处一个下降可行方向．后继点迭代公式：
)()()1(k k k k d x x λ+=+
k λ的取值原则：
(l)保持迭代点)()()1(k k k k d x x λ+=+的可行性； (2)使目标函数值尽可能减小．
根据上述原则，可以通过求解一维搜索问题来确定步长：
)( )( s.t.)( min )
()
()()()()(≥=+≥++λλλλ e
d x E b d x A d x f k k k k k k （3）
由于)(k d 是可行方向，因此，(3)式中第2个约束是多余的．
在点)
(k x
处，把不等式约束区分为起作用约束和不起作用约束：1)
(1b x
A k =，2)(2b x A k > (3)式中第1个约束可以写成
??
?
???≥?
?????++21)(2)(2)(1)(1b b d A x A d A x A k k k k λλ （4） 由于)
(k d
为可行方向，0)
(1≥k d
A ，0≥λ，以及1)(1b x A k =，因此1)(1)(1b d A x A k k ≥+λ自然成立．约束条件（4）简化为
2)(2)(2b d A x A k k ≥+λ
问题（3）简化为
s.t.)
( min 2)(2)(2)()(≥≥++λλλb d A x A d x f k k k k （5）
根据（5）式的约束条件，容易求出λ的上限，令
)(2
2
?k x A b b
-= )(2
?k d A d = 由2)
(2b x
A k >知0? . (5)式的约束条件写成：???≥≥0 ??λλb d 由此得到λ的上限： ?????≥∞?? ????????<=0? 0?,0?|??min max d ， d d d b i i i 不大于λ 问题（3）最终简化成： max )()(0 s.t.) ( min λλλ≤≤+k k d x f （6） 给定问题（1）和一个可行点以后，可以通过求解问题（2）得到下降可行方向，通过求解问题（6）确定沿此方向进行一维搜索的步长． 初始可行点的确定： 为求（1）式的一个可行点，引入人工变量（向量）ξ和η，解辅助线性规划 , s.t.) ( min 1 1 ≥=+=++∑∑==ηξηξηξe Ex b Ax l i i m i i （7） 如果（7）式的最优解)0,0,(),,(x x =ηξ，那么x 就是（1）式的一个可行解． 可行方向法的计算步骤： (l)给定初始可行点) 1(x ，置1=k . (2)在点) (k x 处把A 和b 分解成???? ??21A A 和?? ? ???21b b ，使得 1)(1b x A k =，2)(2b x A k > 计算)()(k x f ?． (3)求解线性规划问题 n j | |d Ed d A d x f j T k ,,2,1,1 0 0 s.t.)( min 1)( =≤=≥? 得到最优解) (k d . (4)如果0)()()(=?k T k d x f ，则停止计算，) (k x 为K-T 点，否则，进行步骤（5）. (5)计算λ的上限max λ，在],0[max λ上作一维搜索： max )()(0 s.t.) ( min λλλ≤≤+k k d x f 得到最优解k λ，令 )()()1(k k k k d x x λ+=+ (6)置1:+=k k ，返回步骤（2）. 例：用Zoutendijk 可行方向法解下列问题： , 02 012 s.t.6 42 min 212121212221≥≥+--≥++-+--+x x x x x x x x x x 取初始可行点T x )0,0() 1(=. 第1次迭代：T x f )4,2()() 1(--=?，在) 1(x 处，起作用约束和不起作用约束的系数矩阵及右端分别为 ??????=10011A ，??????---=11122A ；??????=001b ，?? ? ???--=212b 先求在) 1(x 处的下降可行方向： j ||d d A d x f j T 2,1,1 0 s.t.)( min 1)1(=≤≥? 即 1 1 11 0, s.t.4 2 min 212121≤≤≤≤≥--d - d -d d d d 由单纯形方法求得最优解：?? ? ???=11)1(d 再求步长1λ: ? ? ????--=????????????---==21111112?)1(2d A d ?? ????--=????????????----??????--=-=2100111221?)1(22x A b b 122,11min max =? ?? ?? ?----=λ 解一维搜索问题 1 0 s.t.662)( min 2)1()1(≤≤+-=+λλλλd x f 得到：11=λ 令 ?? ????=+=11) 1(1)1() 2(d x x λ 第2次迭代：T x f )2,0()()2(-=?，在) 2(x 处，起作用约束和不起作用约束的系数矩阵 及右端分别为 ??????---=11121A ，??????=10012A ；??????--=211b ，?? ? ???=002b 求在) 2(x 处的下降可行方向： 1 1 11 0 0 2 s.t.2 min 2121212 ≤≤≤≤≥-≥+-d - d -d -d d d -d 由单纯形方法求得最优解：?? ????-=11) 2(d 沿) 2(d 搜索，求步长2λ: ??????-=??????-??????==11111001?)2(2d A d ?? ????--=????????????-??????=-=1111100100?)2(22x A b b 1max =λ 解一维搜索问题 1 0 s.t.222)( min 2)2()2(≤≤+-=+λλλλd x f 得到：2 12= λ. 令 ?? ? ? ??=+=2/32/1)2(2)2()3(d x x λ 第3次迭代：T x f )1,1()()3(--=? []111--=A ，??????????-=1001122A ；)2(1-=b ，???? ? ?????-=0012b 求在) 3(x 处的下降可行方向： 1 1 11 0 s.t. min 212121≤≤≤≤≥---d - d -d -d d d 由单纯形方法求得最优解：?? ????=00)3(d 根据定理1，T x )2 3 ,21() 3(=是K-T 点。 该例是凸规划，) 3(x 是最优解，目标函数最优值2/3min =f . 将可行方向法推广到非线性约束情形： 考虑不等式约束问题 m i x g x f i ,,1 ,0)( s.t.) ( min =≥ （8） 定理3：设x 是问题（8）的可行解，}0)(|{==x g i I i 是在x 处起作用约束下标集，又设函数)(x f ,))((I i x g i ∈在x 处可微，函数))((I i x g i ?在x 处连续，如果 0)(? ,0)( 则d 是下降可行方向． 根据定理3，求下降可行方向归结为求解LP 问题 n j d I i z d x g z d x f z j T i T ,,1,1|| ,0)( 0)( s.t. min =≤∈≥+?≤-? （9） 设（9）式的最优解为),(d z ．如果0 定理4：设x 是问题（9）的可行解，}0)(|{==x g i I i ，则x 是Fritz John 点的充要条件是问题（9）的目标函数最优值等于零． 步长k λ的确定，仍然需要求解一维搜索问题 max )()(0 s.t.) ( min λλλ≤≤+k k d x f 其中 },,1 ,0)(|sup{)()(max m i d x g k k i =≥+=λλλ （10） 计算步骤： (l)给定初始可行点) 1(x ，置1=k . (2)令}0)(|{)(==k i x g i I ，解线性规划问题 n j d I i z d x g z d x f z j T k i T k ,,1,1|| ,0)( 0)( s.t. min )()( =≤∈≥+?≤-? 得最优解),()(k k d z ，若0=k z ，则停止计算，) (k x 为Fritz John 点；否则，进行步骤（3）. (3)求解一维搜索问题 max )()(0 s.t.) ( min λλλ≤≤+k k d x f 其中max λ由（10）式确定，得到最优解k λ． （4）令)()()1(k k k k d x x λ+=+，置1:+=k k ，返回步骤（2）. Zoutendijk 算法的收敛问题： 不能保证Zoutendijk 方法迭代产生的序列收敛于K-T 点． Topkis-Veinott 修正 Topkis 和Veinott 把求方向的线性规划改成 n j d m i x g z d x g z d x f z j i T i T ,,1,1|| ,,1 ),()( 0 )( s.t. min =≤=-≥+?≤-? 紧约束和非紧约束在确定下降可行方向中均起作用，并且在接近非紧约束边界时，不至发生方向突然改变． 修正方法计算步骤： (l)给定初始可行点) 1(x ，置1=k . (2)解线性规划问题 n j d m i x g z d x g z d x f z j k i T k i T k ,,1,1|| ,,1 ),()( 0 )( s.t. min ) ()()( =≤=-≥+?≤-? 得最优解),()(k k d z . (3)若0=k z ，则停止计算，) (k x 为Fritz John 点；否则，进行步骤（4）. (4)求解一维搜索问题 max )()(0 s.t.) ( min λλλ≤≤+k k d x f 其中max λ由（10）式确定，得到最优解k λ． （5）令)()()1(k k k k d x x λ+=+，置1:+=k k ，返回步骤（2）. Topkis-Veinott 修正方法的收敛性: 定理5: 考虑问题（8），设函数),,1( )( ),(m i x g x f i =连续可微，又设}{)(k x 是Topkis-Veinott 算法产生的序列，则}{)(k x 的任一聚点是Fritz John 点． §7.2 惩罚函数法 7.2.1 惩罚函数法的基本思想 惩罚函数法的基本思想：借助罚函数把约束问题转化为无约束问题，进而用无约束最优化方法来求解． 考虑约束问题 l j x h m i x g x f j i ,,1 ,0)( ,,1 ,0)( s.t.)( min ===≥ （1） 求解的一种途径是由目标函数和约束函数组成辅助函数，把原来的约束问题转化为极小化辅助函数的无约束问题． 对于等式约束问题： l j x h x f j ,,1 ,0)( s.t.) ( min == （2） 可定义辅助函数 ∑=+=l j j x h x f x F 1 21)()(),(σσ 参数σ是很大的正数． （2）式转化为无约束问题 ),( min 1σx F （3） 求解问题（3）能够得到问题(2)的近似解． 对于不等式约束问题： m i x g x f i ,,1 ,0)( s.t.) ( min =≥ （4） 定义辅助函数 ∑=-+=m i i x g x f x F 1 22)}](,0[max{)(),(σσ （4）式转化为无约束问题 ),( min 2σx F （5） 通过（5）式求得（4）式的近似解． 一般情形（（1）式）： 可定义辅助函数 )()(),(x P x f x F σσ+= 其中 ∑∑==+=m i l j j i x h x g x P 1 1 ))(())(()(?φ 连续函数φ和?满足条件：???? ???≠>==<>≥=0 ,0)(0 ,0)(0 ,0)(0 ,0)(y y y y y y y y ??φφ 函数φ和?的典型取法： αφ)}](,0[max{x g i -= β?|)(|x h j = 1,≥βα为给定常数．通常取作2==βα . 约束问题（1）转化为无约束问题 )()(),(min x P x f x F σσ+= （6） )(x P σ称为罚项，σ称为罚因子，而),(σx F 称为罚函数。 当x 为可行点时，0)(=x P ，有)(),(x f x F =σ； 当x 不是可行点时，)(x P σ是很大的正数，它的存在是对点脱离可行域的一种惩罚，作用是在极小化过程中迫使迭代点靠近可行域． 求解问题（6）能够得到约束问题（1）的近似解。 σ越大，近似效果越好。 7.2.2 乘子法 1 乘子法的基本思想 考虑只有等式约束问题（2）. 运用乘子法事先需要定义增广Lagrange 函数（乘子罚函数）: ) ()(2 )()( )(2 )()(),,(1 2 1 x h x h x h v x f x h x h v x f v x T T l j j l j j j σ σ σφ+ -=+ -=∑∑== (7) ),,(σφv x 与Lagrange 函数的区别在于增加罚项 )()(2 x h x h T σ ;与罚函数的区别在于增加了 乘子项)(x h v T -． 注1：增广Lagrange 函数与Lagrange 函数及罚函数具有不同的性态，即 对于),,(σφv x ，只要取足够大的罚因子σ，不必趋向无穷大，就可通过极小化 ),,(σφv x ，求得问题（2）的局部最优解． 为证明上述结论，先给出如下假设： 设x 是等式约束问题（2）的一个局部最优解，且满足二阶充分条件，即存在乘子 T l v v v ),,(1 =，使得 0)(=-?v A x f l j x h j ,,1 ,0)( == 且对每一个满足),,1(0)(l j x h d j T ==?的非零向量d ，有 0),(2>?d v x L d x T 其中 ))(,),((1x h x h A l ??= ，)()(),(x h v x f v x L T -= 定理1：设x 和v 满足问题（2）的局部最优解的二阶充分条件，则存在0'≥σ，使得对 所有的'σσ>，x 是),,(σφv x 的严格局部极小点．反之，若存在点) 0(x ，使得 l j x h j ,,1 ,0)()0( == 且对于某个) 0(v ， ) 0(x 是),,()0(σφv x 的无约束极小点，又满足极小点的二阶充分条件，则) 0(x 是问题（2）的严格局部最优解． 证明：需要用到矩阵理论的相关知识和二阶充分条件的定义。 注2：根据定理1，如果知道最优乘子v ，那么只要取充分大的罚因子σ，不需趋向无穷大，就能通过极小化),,(σφv x 求出问题（2）的解． 注3：确定最优乘子v 一般方法： 先给定充分大的σ和Lagrange 乘子的初始估计v ，然后在迭代过程中修正v ，力图使v 趋向v . 修正v 的公式： 设在第k 次迭代中，Lagrange 乘子向量的估计为) (k v ，罚因子取σ，得到),,() (σφk v x 的 极小点) (k x ．这时有 ∑==?--?=?l j k j k j k j k k k x x h x h v x f v x 1 )()()() () () (0)())(()(),,(σσφ 对问题（2）最优解x ，当)(,),(1x h x h l ?? 线性无关，应有 ∑==?-?l j j j x h v x f 1 0)()( 假如x x k =) (，则必有 )()()(k j k j j x h v v σ-= 一般来说，) (k x 并非是x ，因此该等式并不成立．但由此可以给出修正乘子v 的公式， 令 l j x h v v k j k j k j ,,1 ),()()()1( =-=+σ （7） 然后再进行第k +1次迭代，求),,()1(σφ+k v x 的极小点． 这样做下去，可望v v k →) (, 从而x x k →)(． 如果}{)(k v 不收敛，或者收敛太慢，则增大参数σ，再进行迭代． 收敛快慢一般用)(/)() 1()(-k k x h x h 来衡量． 2 等式约束问题乘子法计算步骤 （1）给定初始点) 0(x ，乘子向量初始估计) 1(v ，参数σ，允许误差0>ε，常数1>α, )1 ,0(∈β，置1=k . （2）以) 1(-k x 为初点，解无约束问题 ),,( min )(σφk v x 得解) (k x . （3）若ε<)()(k x h ,则停止计算，得到点) (k x ；否则，进行步骤（4）. （4）若β≥-)(/)() 1()(k k x h x h ，则置ασσ=:，转步骤（5）；否则，进行步骤（5）. （5）用（7）式计算),,1( ) 1(l j v k j =+，置1:+=k k ，转步骤（2）. 例1：用乘子法求解下列问题： 1)( s.t.22 min 212 12 221=-+=-+x x x h x x x x 增广Lagrange 函数 22121212 221)1(2 )1(22),,(-++ -+--+=x x x x v x x x x v x σ σφ 取罚因子2=σ，令Lagrange 乘子的初始估计1) 1(=v ，由此出发求最优乘子及问题的最优 解. 以下用解析方法求函数),,(σφv x 的极小点． 第1次迭代：容易求得),,() 1(σφv x 的极小点为 ?? ????=4/32/1)1(x 第k 次迭代：取乘子) (k v ，增广Lagrange 函数),,() (σφk v x 的极小点为 ?? ????++=4/)2(6/)2()()() (k k k v v x 现在通过修正) (k v 求) 1(+k v ，由（7）式，有 6 2 )14262(2)()()()() () () () 1(+=-+++-=-=+k k k k k k k v v v v x h v v σ 易证当∞→k 时，序列{} )(k v 收敛，且 5 2 lim )(= ∞ →k k v 同时52) (1 → k x ，53) (2→k x ，得到最优乘子5 2=v . 问题的最优解 ?? ? ???=5/35/2x 注4：在实际计算中，应注意σ的取值． 如果σ太大，则会给计算带来困难； 如果σ太小，则收敛减慢，甚至出现不收敛情形. 3 不等式约束问题的乘子法 考虑只有不等式约束的问题(4).为利用关于等式约束问题得到的结果，引入变量j y ，把问题（4）化为等式约束问题 m j y x g x f j j ,,1 ,0)( s.t.) ( min 2 ==- 这样可定义增广Lagrange 函数 ∑∑==-+ --=m j j j m j j j j y x g y x g w x f w y x 1 221 2 ))((2 ))(()(),,,(~ σ σφ 问题（4）转化为求解 ),,,(~ min σφw y x (8) 将),,,(~ σφw y x 关于y 求极小，由此解出y ，并代入（8）式，将其化为只关于x 求极小的问题．为此求解 ),,,(~ min σφw y x y 用配方法将),,,(~ σφw y x 化为 }2)])((1[2 {)( ] ))((2 ))(([)(),,,(~ 2 2122 21 2σσσσσσφj j j m j j j j m j j j j w w x g y x f y x g y x g w x f w y x ---+=-+--+=∑∑==（9） 为使),,,(~ σφw y x 关于j y 取极小，j y 取值如下： 当0)(≥-j j w x g σ时，))((1 2 j j j w x g y -= σσ 当0)(<-j j w x g σ时，0=j y 综合以上两种情形，即 })(,0max{1 2 j j j w x g y -= σσ 将上式代入（9）式，由此定义增广Lagrange 函数 ∑=--+ =m j j j j w x g w x f w x 1 22}))](,0{[max(21 )(),,(σσ σφ 将问题（4）转化为求解无约束问题： ),,( min σφw x 4 一般约束问题的乘子法 对于既含有不等式约束又含有等式约束的问题（1），定义增广Lagrange 函数 ∑∑∑===+ ---+ =l j j l j j j m j j j j x h x h v w x g w x f v w x 1 21 1 22)(2 )( } ))](,0{[max(21 )(),,,(σ σσ σφ 在迭代中，与只有等式约束问题类似，取定充分大的参数σ，通过修正第k 次迭代中的乘子) (k w 和) (k v ，得到第1+k 次迭代中的乘子) 1(+k w 和) 1(+k v ． 乘子) (k w 和) (k v 修正公式： ?????=-==-=++l j x h v v m j x g w w k j k j k j k j k j k j ,,1 ),(,,1 )),(,0max() ()()1()()()1( σσ (10) 计算步骤与等式约束情形相同． 例2：用乘子法求解下列问题： 1 s.t.2 min 212 2 21≥++x x x x 增广Lagrange 函数为 {} {} ?? ???> -+-+≤-+--+-++=--+-+ +=σσσσσσσ σφw x x w x x w x x w x x w x x w x x w x x w x 1 ,221 ,)]1([212))]1(,0[max(21 2),,(2122 221212 2212221 22212 221 ???? ? >-+≤-+-+--=??σσσφw x x x w x x x x w x x 1 ,21 )],1([22 11212111 ?? ?? ? >-+≤-+-+--=??σσσφw x x x w x x x x w x x 1 ,41 )],1([42 12212122 令 0),,(=?σφw x x 得到),,(σφw x 的无约束极小点 σσ34)(21++= w x σ σ 342++=w x 取2=σ，1) 1(=w ，得到),,()1(σφw x 的极小点： ????? ?=??????=10/35/3)1(2)1(1) 1(x x x 修正) 1(w ，令 5 6 ))110353(21,0max()2(=-+-=w 求得),,()2(σφw x 的极小点 ?? ? ???=??????=25/825/16)2(2)2(1) 2(x x x 以此类推，设在第k 次迭代取乘子) (k w ，求得),,()(σφk w x 的极小点 ?? ????++=??????=10/)2(5/)2() ()()(2)(1) (k k k k k w w x x x 修正) (k w ，得到 )42(5 1))1(2,0max()() (2)(1)()1(+=-+-=+k k k k k w x x w w 显然，按上式迭代得到的序列}{) (k w 是收敛的. 令∞→k ，则34) (→k w 及 ?? ????→??????=3/13/2)(2)(1) (k k k x x x 注5：在乘子法中，由于参数σ不必趋向无穷大就能求得约束问题的最优解，因此不出现罚函数法中的病态． 计算经验表明，乘子法优于罚函数法，受到广大使用者的欢迎． §7.3 序列二次规划法 7.3.1 序列二次规划法的基本思想 序列二次规划法（SQP ）的基本思想： 在迭代点处构造一个二次规划（QP ）子问题，近似原来的约束优化问题；通过求解该QP 子问题，获得约束优化问题的一个改进迭代点；不断重复这个过程，直到求出满足一定要求的迭代点。 考虑一般的约束优化问题 l j x h m i x g x f j i ,,1 ,0)( ,,1 ,0)( s.t.)( min ===≥ （1） 直觉：利用泰勒展开在迭代点) (k x 构造QP 子问题： l j x x x h x h m i x x x g x g x x x f x x x x x f x f x f k T k j k j k T k i k i k k T k k T k k ,,1 ,0)()()( ,,1 ,0)()()( s.t.) )(()(21 ) ()()()(min )()()()()()()()(2)()()()( ==-?+=≥-?+-?-+-?+= （2） 令) (k x x d -=，则（2）等价于二次规划： l j d x h x h m i d x g x g d x f d x f d x f T k j k j T k i k i T k k T ,,1 ,0)()( ,,1 ,0)()( s.t.)()(2 1)(min )()()()()()(2 ==?+=≥?+?+?= 求出最优解为) (k d ，则新的迭代点为：)()() 1(k k k d x x +=+ 7.3.2 Lagrange-Newton 法 等式约束的Lagrange-Newton 法 求解非线性方程组0)(=x F 的Newton 迭代公式为 ?????+==+?+) ()()1() ()(0 )()(k k k k k T d x x x F d x F 可以证明：解方程组的Newton 法具有局部二次收敛性。 考虑等式约束最优化问题： l j x h x f j ,,1 ,0)( s.t.) ( min == （3） 问题（3）的Lagrange 函数为 )()(),(x h v x f v x L T -= 令)(x A 表示)(x h 在x 处的Jacobi 矩阵，即 ?????? ????????????????=??=n l l n x x h x x h x x h x x h x h x A )()()() ()(111 1 设* x 为（3）的解且)(*x A 行满秩，则存在*v 使得),(* *v x 是（3）的K-T 点，即 0)()()()(),(),(=?? ? ???-?=? ??????=x h v x A x f x h v x L v x F T x （4） 令),(),(2v x L v x W x ?=，则函数),(v x F 的Jacobi 矩阵为 ?? ? ???-0)()(),(x A x A v x W T 求解非线性方程组（4）的Newton 迭代公式为： ?? ? ???+??????=??????++)()()()()1()1(k v k k k k k d d v x v x （5） ?? ? ???)()(k v k d d 是如下线性方程组的解： ?? ????-?-=????????????-)()()(0)()(),() ()()()()()()()(k k T k k v k T k k k x h v x A x f d d x A x A v x W （6） 称由（5）-（6）式建立的求解约束最优化问题（3）的算法为Lagrange-Newton 法. Lagrange-Newton 法不易于直接用于不等式约束最优化问题，需要导出Lagrange-Newton 法的另一种形式.(与QP 挂钩) 由约束最优化问题的K-T 条件不难看出： Lagrange-Newton 法迭代公式（5）-（6）计算的) (k d 是如下QP 问题的解： 0)()( s.t.),(),(2 1)(min )()()()()()(=+?+= k k T k k x k k T k x h d x A d v x L d v x W d d q （7） 且) (k v d 是相应于等式约束的Lagrange 乘子. 求解等式约束问题（3）的Newton 法可等价地叙述为：先求二次规划（7）的K-T 点 ),()()(k v k d d ，然后由（5）式确定),()1()1(++k k v x . 对问题（7）的任何可行点d ，有 ) ()( )()(),() ()()()()()()()(k T k T k k T k T k T k k x x h v d x f d x A v d x f d v x L +?=-?=? 问题（7）等价于二次规划 0)()( s.t.)(),(2 1)(min )()()()()(=+?+= k k T k k k T k x h d x A d x f d v x W d d q （8） 二次规划问题（8）的K-T 条件为： ?? ? ????-=????????????-+)()(0)()(),()()()()()()(k k k T k k k x h x f v d x A x A v x W （9） 比较（5）、（7）、（9）式，可看出： 求解非线性方程组（4）的Lagrange-Newton 法可等价地叙述为：求QP 问题（8）的K-T 点),()1() (+k k v d ，令)()()1(k k k d x x +=+，由此产生迭代序列)},{()()(k k v x ，称此 Lagrange-Newton 法为求解等式约束问题（3）的SQP 算法. 一般约束优化问题的Lagrange-Newton 法 对一般约束优化问题，在当前点),,()()()(k k k v w x 构造如下QP 子问题： l j d x h x h m i d x g x g d x f d v w x W d d q T k j k j T k i k i T k k k k T k ,,1 ,0)()( ,,1 ,0)()( s.t.)(),,(2 1 )(min )()()()()()()()( ==?+=≥?+?+= （10） 解上述QP 子问题，得到解) (k d 及对应的乘子) 1(+k w 和) 1(+k v ，产生新的迭代点 ),,()1()1()1(+++k k k v w x ，其中)()()1(k k k d x x +=+. 该算法称为求解约束问题（1）的局部Newton-SQP 算法. 注1：子问题（10）的目标函数是问题（1）的Lagrange 函数的二次近似，而不是我们通常认为的仅是问题（1）的目标函数的二次近似. 基于Lagrange-Newton 法的局部SQP 算法步骤： （1）取初始点),,() 1()1()1(v w x ，置1=k . （2）若),,()()()(k k k v w x 满足约束问题（1）的K-T 条件（从计算角度应考察 ε （3）解QP 子问题（10），得到解),,()1()1()(++k k k v w d . （4）令)()() 1(k k k d x x +=+，1:+=k k ，转步骤（2）. 注2：遗留问题： （i ）如何求解QP 子问题（后面再讨论）？ （ii ）如果初始点取得不恰当，即使原问题可行，也可导致QP 子问题不相容。QP 子问题不相容（可行域为空）如何处理？ 例1：对于约束???≥=≥+-=0)(01)(2 2 1x x g x x g ，在点3=x 处，线性化近似约束为???≥+≥--0690 2d d ，不相容！ 7.3.3 Wilson-Han-Powell 法 在构造QP 子问题（10）时，需要计算Lagrange 函数在迭代点的Hesse 矩阵 ),,()()()(k k k k v w x W W =，这种计算工作量比较大。 借鉴无约束优化的拟牛顿法在迭代过程中利用对称正定矩阵替代Hesse 矩阵的思想，韩世平（S.P. Han ）1976年基于Lagrange-Newton 法提出了一种利用对称正定矩阵k B 替代矩阵k W 的序列二次规划法（也称为约束拟牛顿法，约束变尺度法）. Wilson 在1963年较早地考虑了Lagrange-Newton 法. 后来Powell 在1977年修正了Han 的方法，故将这种序列二次规划法称为Wilson-Han-Powell(WHP)方法． 对于一般的约束问题（1），WHP 方法需要构造如下的QP 子问题： l j d x h x h m i d x g x g d x f d B d d q T k j k j T k i k i T k k T k ,,1 ,0)()( ,,1 ,0)()( s.t.)(2 1)(min )()()()()( ==?+=≥?+?+= （11） 利用子问题（11）的解) (k d 作为搜索方向。 WHP 方法除了用矩阵k B 替代矩阵k W 外，新的迭代点不直接按)()() 1(k k k d x x +=+计算， 而是由一维搜索确定步长k λ，新的迭代点为)()()1(k k k k d x x λ+=+. 由于这些改进，WHP 方法在一定条件下具有全局收敛性. 相对于Lagrange-Newton 法（局部SQP 算法），WHP 方法称为全局SQP 算法. （11）式确定的) (k d 具有一个比较好的性质：它是许多罚函数（价值函数，Merit Function ）的下降方向. WHP 方法中一种罚函数形式如下(范数-1罚函数)： ∑∑==+-+=m i l j j i x h x g x f x P 1 1 /|])(|)}(,0max{ [)()(σσ （12） 0>σ为罚因子.利用该罚函数作一维搜索确定步长. WHP 方法的计算步骤： （1）初始化：给定初始点) 0(x ，对称正定矩阵0B ，容许误差0>ε和满足 ∑∞ =+∞ <1 k k ε 的非负序列}{k ε；取参数0>σ，0>δ，置0=k . (2)收敛性检验：求解二次规划子问题（11），得到最优解) (k d .若ε≤) (k d ，则得到原来约束优化问题的一个近似K-T 点) (k x ，算法停止；否则，转步骤（3）. （3）改进迭代点：利用（12）式的罚函数)(x P σ,按照某种线性搜索规则确定步长 ],0[δλ∈k ，使得 k k k k k k d x P d x P ελλσδλσ++≤+∈)(min )()() (] ,0[)()( 置)()()1(k k k k d x x λ+=+. (4)修正矩阵k B ：利用矩阵k B ，在) (k x 和) 1(+k x 点的其它信息，计算对称正定矩阵1+k B ； 令1:+=k k ，转步骤（2）. 注3：遗留问题： （1） 如何求解QP 子问题（11）？（后面讨论） （2） 如何修正k B 获得1+k B ？ （3） 如何处理QP 子问题不相容？ （1）k B 的修正方法： k B 的修正有多种方法： （i ）基于拟牛顿校正公式的方法 （ii ）基于增广Lagrange 函数的方法 （iii ）基于既约Hesse 矩阵的方法 只介绍基于拟牛顿校正公式的方法. 对于k B 的修正，一方面，k B 应为Lagrange 函数的Hesse 矩阵的近似；另一方面，要保持k B 的对称正定性，使得相应的QP 子问题是一个严格的凸二次规划问题. 类似于无约束问题的拟牛顿法，令 )()1()(k k k x x p -=+ ) () 1() 1() 1()()()()1()1()1()(),,( ),,(),,(k k k k k k k x k k k x k p v w x W v w x L v w x L q ++++++≈?-?= 然后可利用BFGS 等公式计算1+k B . ) ()()()()()()()(1k k T k k T k k k k T k T k k k k p B p B p p B p q q q B B -+=+ (BFGS 公式) 注4：与无约束问题不同的是：这种修正不能保证条件0)()(>k T k p q （曲率条件）成立，因此，即使k B 对称正定，也不能保证1+k B 正定. 为了克服此困难，1978年Powell 利用)(k q 和)(k p 的一个凸组合代替)(k q ，记为 ???-+≥= ,)1(2.0 ,) () () ()()()()() (其它如果k k k k k k k T k k T k k k p B q p B p p q q q θθ（13） ) ()()()() ()(8.0k T k k k T k k k T k k p q p B p p B p -=θ 修正后的BFGS 公式（称为截断BFGS 修正） ) ()()()() ()()()(1k k T k k T k k k k T k T k k k k p B p B p p B p q q q B B -+ =+ (14) （2）QP 子问题不相容的处理： Powell 提出了一种处理方法：引进辅助变量ξ，解LP ： 1 0 },,1{ ,0)()( }0)(|{ ,0)()( } 0)(|{ ,0)()( s.t. max )()()()()()()()(≤≤∈=+?≥∈=∈≥+?<∈=∈≥+?ξξξξ l j x h d x h x g I i S i x g d x g x g I i V i x g d x g k j T k j k i k k i T k i k i k k i T k i （15） 0,0==d ξ为该问题的可行解，故（15）式的最优解总是存在的，记为ξ，显然有10≤≤ξ. 显然原子问题（11）（或（10））相容当且仅当1=ξ. （i ）若0=ξ或很小，则改变初始点重新开始，此情况的发生常常因原问题 是不相容的； （ii ）若0>ξ，则将子问题（11）中的约束条件用（15）中的约束条件代替， 即子问题取为 } ,,1{ ,0)()( }0)(|{ ,0)()( }0)(|{ ,0)()( s.t.)(2 1)(min )()()()()()()()()(l j x h d x h x g I i S i x g d x g x g I i V i x g d x g d x f d B d d q k j T k j k i k k i T k i k i k k i T k i T k k T k ∈=+?≥∈=∈≥+?<∈=∈≥+??+= ξξ（16） 其中ξ取为],0(ξ中的一个定值. 例2：对于约束???≥=≥+-=0 )(0 1)(2 21x x g x x g ，在点3=x 处，求如下线性规划 1 0 096 02 s.t. max ≤≤≥+≥--ξξξd d 最优解为4/3=ξ. 若取2/1=ξ，则对应的QP 子问题（16）是相容的. 7.3.4 二次规划的求解方法 二次规划（QP ）是非线性规划中一种特殊情形，目标函数是二次函数，约束是线性函数。 许多现实问题本身可建模为二次规划。 QP 是前面讨论的SQP 的基础，在每一迭代步，均要求解一个QP 子问题。 QP 的算法较多，如： （1）Lagrange 方法 （2）起作用集方法 （3）Lemke 方法 （4）路径跟踪法 1．Lagrange 方法（求解等式约束QP 问题） 考虑QP 问题 b Ax x c Hx x T T =+ s.t.2 1 min （17） H 为n 阶对称矩阵，A 为n m ?矩阵，秩为m . 该问题的Lagrange 函数为 )(2 1),(b Ax v x c Hx x v x L T T T --+= 令0),(=?v x L x ，0),(=?v x L v ，得到方程组 0=-+v A c Hx T 0=+-b Ax 将此方程组写成 行域 φ 内，选择一个初始点 X 然后确定一个可行 得一个目标函数有所改善的可行的新点 X 即完成了 第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： s .t . min f (x ) g u (x ) ≤ 0 h v (x ) = 0 x ∈ R n u = 1, 2,..., m v = 1, 2,..., p < n 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于 这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由 m 个不等式约束条件 gu(x )≤0 所确定的可 0 搜索方向 S ，且以适当的步长沿 S 方向进行搜索，取 1 一次迭代。以新点为起始点重复上述搜索过程，每次 均按如下的基本迭代格式进行计算： X k+1=X k +α k S k (k=0,1,2,..) 逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算 不论何时终止，都可以获得比初始点好的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局 部最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集 φ(X,μ1,μ2)=F(X)+∑μ 1 G??g j X)??+∑μ2H??h k(X)?? a)可行域是凸集；b)可行域是非凸 集 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数 结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优 化问题。 m l j=1k=1 新目标函数 然后对新目标函数进行无约束极小化计算。 加权因子 间接法是结构优化设计中广泛使用的有效方法，其特点： 1）由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和数值计算的稳定性大有提高； 2）可以有效处理具有等式约束的约束优化问题； 3）目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精度，甚至导致计算失败。 无约束优化方法---鲍威尔方法 本实验用鲍威尔方法求函数f(x)=(x1-5)2+(x2-6)2 的最优解。 一、简述鲍威尔法的基本原理 从任选的初始点x⑴o出发，先按坐标轮换法的搜索方向依次沿e1.e2.e3进行一维搜索，得各自方向的一维极小点x⑴ x⑵ x⑶.连接初始点xo⑴和最末一个一维极小点x3⑴,产生一个新的矢量 S1=x3⑴-xo⑴ 再沿此方向作一维搜索，得该方向上的一维极小点x⑴. 从xo⑴出发知道获得x⑴点的搜索过程称为一环。S1是该环中产生的一个新方向，称为新生方向。 接着，以第一环迭代的终点x⑴作为第二环迭代的起点xo⑵,即 Xo⑵←x⑴ 弃去第一环方向组中的第一个方向e1，将第一环新生方向S1补在最后，构成第二环的基本搜索方向组e2,e3,S1，依次沿这些方向求得一维极小点x1⑵,x2⑵,x3⑵.连接 Xo⑵与x3⑵,又得第二环的新生方向 S2=x3⑵-xo⑵ 沿S2作一维搜索所得的极小点x⑵即为第二环的最终迭代点 二、鲍威尔法的程序 #include "stdafx.h" /* 文件包含*/ #include #include 项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、Newton 法（修正Newton 法）的程序。 [实验学时] 2学时 [实验准备] 1．掌握最速下降法的思想及迭代步骤。 2．掌握Newton 法的思想及迭代步骤； 3．掌握修正Newton 法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题：【选作一个】 1．用最速下降法求 22120min ()25[22]0.01T f X x x X ε=+==，，，． 2．用Newton 法求 22121212min ()60104f X x x x x x x =--++-， 初始点 0[00]0.01T X ε==，，． 最速下降法 Matlab 程序： clc;clear; syms x1 x2; X=[x1,x2]; fx=X(1)^2+X(2)^2-4*X(1)-6*X(2)+17; fxd1=[diff(fx,x1) diff(fx,x2)]; x=[2 3]; g=0; e=0.0005; a=1; fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); step=0; while g>e step=step+1; dk=-fan; %点x(k)处的搜索步长 ak=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2); xu=x+ak*dk; x=xu; %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf(' x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); %计算目标函数点x(k+1)处一阶导数值 fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); end %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf('\n最速下降法\n结果：\n x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); c++程序 #include 第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由m 个不等式约束条件g u (x )≤0所确定的可行域φ内，选择一个初始点0 X 然后确定一个可行搜索方向S ，且以适当的步长沿S 方向进行搜索，取得一个目标函数有所改善的可行的新点1 X 即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算： k+1k k k =+S (k=0,1,2,..)X X α逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好 的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部 最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集 1,2,...,1,2,...,u m v p n == 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。 然后对新目标函数进行无约束极小化计算。 间接法是结构优化设计中广泛使用的有效方法，其特点： 1） 由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和 数值计算的稳定性大有提高； 2） 可以有效处理具有等式约束的约束优化问题； 3） 目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精 度，甚至导致计算失败。 a) 可行域是凸集；b)可行域是非凸集 () ()()()121211 ,,m l j k j k X F X G g X H h X φμμμμ==??=++? ?????∑∑ 新目标函数 加权因子 分数: ___________任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间： 一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差， 《最优化方法》复习题 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2 {}{}.:)(min :)(max n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题 )(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最 优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法， 则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ . 13 算法迭代时的终止准则（写出三种）：_____________________________________。 第三章无约束最优化方法 本章内容及教学安排 第一节概述 第二节迭代终止原则 第三节常用的一维搜索方法 第四节梯度法 第五节牛顿法 第六节共轭方向法 第七节变尺度法 第八节坐标轮换法 第九节鲍威尔方法 第一节概述 优化问题可分为 无约束优化问题 有约束优化问题 无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想： 所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长 3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）1K K X X ε+-≤ 111/2 21K K K K n i i i X X X X ε++=??-=-≤???? ∑（） 2） 11()()()() () K K K K K f X f X f X f X or f X ε ε ++-≤-≤ 3）(1)()K f X ε+?≤ 第三节 常用的一维搜索方法 本节主要解决的是如何确定最优步长的问题。 从初始点(0)X 出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下： (1)(0)00(2)(1)11(1)() K K k k X X S X X S X X S ααα+=+=+= + 现在假设K S 已经确定，需要确定的是步长k α，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即 (1)()min ()min ()min ()K K K k k f X f X S f αα+=+= 由此可见，最佳步长*K α由一维搜索方法来确定 求*k α，使得()()()()()()min K K K K f f X S αα=+→ 一、一维搜索区间的确定 区间[,]a b 应满足 ()(*)()f a f f b α>< 天津大学《最优化方法》复习题（含答案） 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{} .:)(m in :)(m ax n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题 )(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切 )(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最 优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法， 则对{}Λ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ . 无约束最优化直接方法和间接方法的异同 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最 第四章 无约束优化方法 ——最速下降法，牛顿型方法 概述 在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这 种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的， 无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过 对约束条件的处理，转化为无约束最优化问题来求解。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。 一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度 法、共轭梯度法等。 二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯 形法等。 无约束优化问题的一般形式可描述为： 求n 维设计变量 []12T n n X x x x R =∈L 使目标函数 ()min f X ? 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 无约束优化问题的求解： 1、解析法 可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方 程 0)(min *=X f 的解。也就是求Ｘ＊使其满足 解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值 点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性 的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题 的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用 数值迭代的方法直接求解无约束极值问题。 2、数值方法 数值迭代法的基本思想是从一个初始点) 0(X 出发，按照一个可行的搜索方向)0(d ρ搜索，确定最佳的步长0α使函数值沿)0(d ρ方向下降最大，得到)1(X 点。依此一步一步地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为 ),2,1,0()()()1(Λρ=+=+k d X X K K K K α （4.2） 在上式中， ()K d r 是第是 k+1 次搜索或迭代方向，称为搜索方向（迭代方向）。 由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点)(k X 、搜索方向)(k d ρ和迭代步长K α，称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向)(k d ρ上确定最优步长K α的方法，本章我们将讨论如何确定搜索方向)(k d ρ。 最常用的数值方法是搜索方法，其基本思想如下图所示： 0)(0)(0)(*2*1*=??=??=??n x X f x X f x X f M约束优化设计
无约束优化方法程序
常用无约束最优化方法(一)
约束优化设计
单纯形法解决无约束优化问题
天津大学-研究生-最优化方法复习题
第三章 无约束最优化方法
天津大学《最优化方法》复习题(含答案)
无约束最优化直接方法和间接方
无约束最优化直接方法和间接方法的异同
无约束优化方法(最速下降法_牛顿法)