This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
keynote:lesson15 [2010/06/29 18:57] 20921074 |
keynote:lesson15 [2023/08/19 21:02] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | λ====== 第十五课 ====== | + | λ |
+ | ====== 第十五课 ====== | ||
最优化方法 3 | 最优化方法 3 | ||
Line 168: | Line 169: | ||
d<sub>T</sub>∇<sub>xx</sub><sup>2</sup>L(x*,λ*)d>0,∀0≠d⊂S(x*,λ*),则\\ | d<sub>T</sub>∇<sub>xx</sub><sup>2</sup>L(x*,λ*)d>0,∀0≠d⊂S(x*,λ*),则\\ | ||
x*为局部严格极小点。\\ | x*为局部严格极小点。\\ | ||
+ | |||
+ | 2.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 181: | Line 226: | ||
<sup></sup> | <sup></sup> | ||
<note important>edit by20921074 余权</note> | <note important>edit by20921074 余权</note> | ||
+ | |||
+ | 变量消去法 \\ | ||
+ | 1.给出可行点//x//<sub>1</sub>,ε≥0,//k//=1 \\ | ||
+ | 2.计算{{:keynote:y1.jpg|}},其中划分使得//A//<sub>//B//</sub>非奇异;\\ | ||
+ | 计算{{:keynote:15-2.png|}}及{{:keynote:15-3.png|}} \\ | ||
+ | 3.如果{{:keynote:15-04.jpg|}},则停止;否则利用某种方式产生下降方向{{:keynote:15-05.jpg|}},即使得{{:keynote:15-06.jpg|}}; \\ | ||
+ | 4.{{:keynote:15-07.jpg|}}进行线性搜索给出//α//<sub>//k//</sub> >0,令{{:keynote:15-08.jpg|}} \\ | ||
+ | 转2步。 \\ | ||
+ | |||
+ | <note important>edit by 10607023 俞荣栋</note> | ||
+ | |||
+ | |||
+ | 梯度投影法\\ | ||
+ | 广义消去法每次迭代的变量增量由x<sub>k+1</sub>-x<sub>k</sub>两部分组成,\\ | ||
+ | {{:keynote:xx6.png|}}\\ | ||
+ | * Unordered List Item迭代方式存在不合理之处。本来希望迭代点都在可行域上,但具体迭代过程却是先远离可行域,然后再校正回可行域中。\\ | ||
+ | * Unordered List Item希望离开程度尽可能小?沿线性化方向。迭代过程可以更快的收敛。\\ | ||
+ | * | ||
+ | |||
+ | |||
+ | <note important>edit by 20921235 夏鑫</note> | ||
+ |