Applied Mathematics for Computer Science

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
λ
====== 第十五课 ====== 
最优化方法 3

内容

线性规划\\
非线性优化\\
主要参考书：\\

线性规划，张建中，许绍吉，科学出版社\\
最优化理论与方法，袁亚湘，孙文瑜，科学出版社\\

二、非线性最优化\\
引言\\
最优化的问题的一般形式为\\
Min f(x)\\
s.t. x∈X\\
f(x)为目标函数，X⊂E<sup>n</sup>为可行域。\\
如X=En，则以上最优化问题为无约束最优化问题。\\
约束最优化问题通常写为\\
Min f(x)\\
s.t. ci(x)=0, i∈E,\\
ci(x)≥0, i∈I,\\
其中E, I分别为等式约束的指标集和不等式约束的指标集，ci(x)是约束函数。\\

1. 无约束非线性最优化\\
非线性的数据无处不在\\

1.1 无约束问题的最优条件\\
min f(x), x∈R<sup>n</sup>的最优性条件\\
局部极小 若存在δ>0，使得对所有满足 || x-x* ||<δ的x, 都有\\
f(x)>f(x*),\\
则称x * 为f的局部极小点。\\
如所有满足 || x-x*||<δ的x，都有f(x)>f( x*),\\
则称x * 为f的严格局部极小点。\\
全局极小 若存在δ>0，使得对所有x, 都有f ( x)>=f ( x*),\\

则称x * 为f的总体极小点。\\
如所有x，都有f ( x) > f ( x*),\\
则称x * 为f的严格总体极小点。\\

min f(x) ,x∈R<sup>n</sup>

设g(x)= ∇f(x),G(x)=Δf(x)分别为f的一阶和二阶导数。

定理（一阶必要条件）：设f：D⊂R<sup>n</sup>→R<sup>1</sup>在开集D上连续可微，
若x<sup>*</sup>∈D是局部最小点，则 g(x<sup>*</sup>)›=0

定理（二阶必要条件）：设f：D⊂R<sup>n</sup>→R<sup>1</sup>在开集D上二阶连续可微，
若x<sup>*</sup>∈D是局部最小点，则 g(x<sup>*</sup>)=0，G(x<sup>*</sup>)›=0


1.1 无约束问题的最优条件\\
g(x*)= 0, 则x称为函数f的平稳点。平稳点有可能是极小点，也可能为极大点，\\
也可能不是极值点（鞍点）。\\
定理（二阶充分条件）：设f：D⊂R<sup>n</sup>→R<sup>1</sup>在开集D上二阶连续可微，\\
若x*∈D是严格局部极小点的充分条件是，则g(x*)=0, 且G (x*)为正定矩阵。\\
定理（凸充分性定理）：设f：D⊂R<sup>n</sup>→R<sup>1</sup>是凸函数且一阶连续可微，\\
若x*是总体极小点的充要条件是g(x*)=0。\\
什么是凸函数？\\


1.2 最优化方法的结构
迭代优化方法的基本思想：
  - 给定一个初始点x<sub>0</sub>,
  - 按照某一迭代规则产生一个点列{x<sub>k</sub>} 
          * 当{x<sub>k</sub>}是有穷点列时，其最后一个点是最优化模型问题的最优解。
          * 当{x<sub>k</sub>}是无穷点列时，其极限点为最优解。


一个好的算法应具备的典型特征为：
  - 迭代点{x<sub>k</sub>}能稳定地接近局部极小点x*的邻域，然后迅速收敛于x*
  - 当给定的某种收敛准则满足时，迭代即终止。



优化方法的结构
给定初始点x<sub>0</sub>\\
1. 确定搜索方向d<sub>k</sub>，即依照一定规则构造 f 在x<sub>k</sub>的下降方向为搜索方向\\
2. 确定步长因子α<sub>k</sub>，使目标函数值有某种意义下降\\
3. 令x<sub>k+1</sub>=x<sub>k</sub>+α<sub>k</sub>d<sub>k</sub>, \\
            a). 若x<sub>k+1</sub>满足某种终止条件，则停止迭代，得到近似最优解，\\
            b) 否则，重复以上步骤\\

{{:keynote:xx2.png|}}

收敛速度\\

 收敛速度也是衡量最优化方法有效性的重要方面。\\
   若存在实数 α及一个与迭代次数k无关的常数q>0，使得 
 {{:keynote:xx1.png|}}          

则称算法产生的迭代点列{x<sub>k</sub>} 具有Q-α 阶收敛速度。特别地 \\
 （a）当 α＝1，q>0 时，{x<sub>k</sub>} 具有Q- 线性收敛速度。 \\
 （b）当1<α<2，q>0 时 或者 α＝1,q=0 ， {x<sub>k</sub>}具有Q- 超线性收敛速度。\\ 
 （c）当 α＝2 ，q>0 时，{x<sub>k</sub>} 具有Q - 二阶收敛速度。\\


收敛速度
一般认为，具有超线性和二阶收敛速度的方法是比较快速的。\\
 但对于任何一个算法，收敛线和收敛速度的理论结果并不保证算法在实际执行时一定有好的实际计算结果。\\
    *  忽略了误差；函数计算不满足限制条件\\
需要选择有代表性的检验函数进行数值计算\\

<note important>EDit By xin xia</note><note important>Modify by zhu wenhua</note>

一维搜索
单变量函数的最优化。\\
x<sub>k+1</sub>=x<sub>k</sub>+α<sub>k</sub>d<sub>k</sub>\\
其关键就是构造搜索方向d<sub>k</sub>和步长因子α<sub>k</sub>，设φ(α)=f(x<sub>k</sub>+αd<sub>k</sub>),\\
这样确定α<sub>k</sub>，使得φ(α)<φ(0)。这就是关于α的一维搜索问题。\\
若α<sub>k</sub>使得目标函数沿方向达到最小，即φ(α<sub>k</sub>)=minφ(α){s.t α>0}，则称这样的\\
一维搜索为最优一维搜索（或精确一维搜索），α<sub>k</sub>为最优步长因子。\\
若取α<sub>k</sub>使得目标函数得到可以接受的下降量，则成为近似一维搜索，或不精确一维搜索。\\

实际中，精确的最优步长因子一般不能求到，求几乎精确的最优步长\\
因子需花费想到大的工作量,因而花费计算量较少的不精确一维搜索受到重视。\\

一维搜索的主要结构\\
1.确定包含问题最优解的搜索区间\\
2.再用某种分割技术或插值方法缩小这个区间，进行搜索求解\\

搜索区间：包含最优值的闭区间。\\
确定搜索区间的简单方法——进退法。\\
从一点出发，试图确定出函数值呈现“高－低－高”的三点。一个方向不成功，就退回来，再沿相反方向寻找。\\

一维区间搜索的进退法\\
确定搜索区间的简单方法——进退法。\\
1.选取初始值α<sub>0</sub>，h<sub>0</sub>，加倍系数t>1(一般t=2)，k=0；\\
2.如φ(α<sub>k</sub>+h<sub>k</sub>)<φ(α<sub>k</sub>),则h<sub>k+1</sub> = th<sub>k</sub>，α<sub>k+1</sub>=α<sub>k</sub>+h<sub>k+1</sub>，k++，返回2。\\
3.若k==0，转换搜索方向h<sub>k</sub>=-h<sub>k</sub> ，转2。\\
否则，停止迭代，输出a=min{α<sub>0</sub>,α<sub>k+1</sub>},b=max{α<sub>0</sub>,α<sub>k+1</sub>}。

<note important>edit by10921010 朱文华</note>

2. 约束非线性最优化\\
2.1约束优化最优性条件\\
约束最优化问题通常写成\\
min f(x)\\
s.t. c<sub>i</sub>(x)=0, i⊂E={1,...,m<sub>e</sub>},\\
c<sub>i</sub>(x)≥0, i⊂I={m<sub>e</sub>+1,...,m}\\

在x*处的非积极约束:\\
设x*为一个局部极小点，若不等式约束i0有,c<sub>i0</sub>(x*)>0,则可将第i0个约束去掉，且x*仍然是去掉第i0个约束条件的问题的局部极小点。称约束c<sub>i0</sub>在x*处是非积极的。\\

定义：I(x)={i | c<sub>i</sub>(x)<=0, i∈I}; A(x)=EUI(x)为x点处的积极集合。\\
一阶最优性条件\\
Kuhn-Tucker必要条件:\\
若x*是问题P的一个局部极小点，如果 {{:keynote:yq-1.png|}}线性无关，\\
则必存在λ*<sub>i</sub>(i=1,...,m),使得\\
{{:keynote:yq-2.png|}}\\
满足上述两式的点称为K-T点。 与该定理联系密切的是Lagrange函数：\\
L(x,**λ**)=f(x)-**λ**<sup>T</sup>c(x).\\
则（*）条件等价于∇<sub>x</sub>L=0。**λ**称为Lagrange乘子。\\

二阶必要条件\\
定义：设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为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.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>.














<sub></sub>
<sup></sup>
<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>
Applied Mathematics for Computer Science

User Tools

Site Tools

Page Tools
