Differences

This shows you the differences between two versions of the page.

--- keynote:lesson15 [2010/06/29 16:43]
20921074
+++ keynote:lesson15 [2010/07/02 12:27]
10607023
@@ Line 1: / Line 1: @@
+λ
 ====== 第十五课 ======
 最优化方法 3
@@ Line 157: / Line 158: @@
 定义：设x*是K-T点，λ*称为相应的Lagrange乘子，托存在序列{d<sub>k</sub>}和{δ<sub>k</sub> >0}使得\\
 {{:keynote:yq-3.png|}} \\
-且有d<sub>k</sub>->d, δ<sub>k</sub> ->0,
+且有d<sub>k</sub>->d, δ<sub>k</sub> ->0,则称d为x*处的序列零约束方向。在x*处的所有序列零约束方向的几何为S(x*,λ*)。\\
+二阶必要性条件：\\
+设x*为局部极小点，λ*称为相应的Lagrange乘子，则必有\\
+d<sub>T</sub>∇<sub>xx</sub><sup>2</sup>L(x*,λ*)d≥0,∀d⊂S(x*,λ*).\\
+其中L(x,λ)为Lagrange函数。\\
+稍加强可得充分性条件：\\
+设x*为K-T点，λ*称为相应的Lagrange乘子。若\\
+d<sub>T</sub>∇<sub>xx</sub><sup>2</sup>L(x*,λ*)d>0,∀0≠d⊂S(x*,λ*),则\\
+x*为局部严格极小点。\\
+.2 可行方向法\\
+可行方向法即要去每次迭代产生的点x<sup>k</sup>都是约束优化问题的可行点。\\
+关键在于每一步寻找可行下降方向：\\
+d<sup>T</sup>∇f(x<sub>k</sub>)<0,d∈FD(x<sub>k</sub>,X).\\
+可行方向：设x<sup>-</sup>⊂X,0≠d⊂R<sup>n</sup>,如存在δ>0使得x<sup>-</sup>+td⊂X，则称d为x<sup>-</sup>处的可行方向。X在x<sup>-</sup>处的所有可行方向集合记为FD(x<sup>-</sup>,X)。\\
+广义消去法\\
+考虑等式约束问题：\\
+min f(x). \\
+s.t. c(**x**)=0\\
+设有变量分解x=[X<sub>B</sub>,x<sub>N</sub>]<sub>T</sub>,其中x<sub>B</sub>⊂R<sub>m</sub>, x<sub>N</sub>⊂R<sub>n-m</sub>.\\
+则c(x)=0可改写为：\\
+c(x<sub>B</sub>,x<sub>N</sub>)=0.     (1) \\
+假定可以从(1)解出x<sub>B</sub>=Φ(x<sub>N</sub>),则原问题等价于\\
+{{:keynote:yq-4.png|}}\\
+称{{:keynote:yq-5.png|}}为既约梯度。\\
+不难验证\\
+{{:keynote:yq-6.png|}}\\
+从(1)可得\\
+{{:keynote:yq-7.png|}}\\
+假设{{:keynote:yq-8.png|}}非奇异，可得到\\
+{{:keynote:yq-9.png|}}\\
+令{{:keynote:yq-10.png|}}，则发现可以将\\
+既约梯度写成Largrange函数在既约空间上的梯度\\
+{{:keynote:yq-11.png|}}\\
+或者说，有\\
+{{:keynote:yq-12.png|}}\\
+故既约梯度可看作Lagrange函数之梯度的非零部分。利用既约梯度，可以构造无约束优化问题的线搜索方向。\\
+例如可取最速下降方向:\\
+{{:keynote:yq-13.png|}}\\
+或拟牛顿方向：\\
+{{:keynote:yq-14.png|}}\\
+在无约束问题上作线性搜索，等价于对原目标函数f(x)在曲线\\
+{{:keynote:yq-15.png|}}
+上作曲线搜索。因为Φ(x)的解析表达式并不知道，故作一维搜索时，每个试探步长α>0都要用(2)来求解x<sub>B</sub>.
@@ Line 164: / Line 226: @@
 <sup></sup>
 <note important>edit by20921074 余权</note>
+变量消去法 \\
+.给出可行点//x//<sub>1</sub>，ε≥0，//k//=1 \\
+.计算{{:keynote:y1.jpg|}}，其中划分使得//A//<sub>//B//</sub>非奇异；\\
+计算{{:keynote:15-2.png|}}及{{:keynote:15-3.png|}} \\
+.如果{{:keynote:15-04.jpg|}}，则停止；否则利用某种方式产生下降方向{{:keynote:15-05.jpg|}}，即使得{{:keynote:15-06.jpg|}}； \\
+.{{:keynote:15-07.jpg|}}进行线性搜索给出//α//<sub>//k//</sub> >0，令{{:keynote:15-08.jpg|}} \\
+转2步。 \\
+<note important>edit by 10607023 俞荣栋</note>

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools