çº¦æ Ÿä¼˜åŒ–é—®é¢˜åŸºç¡€2

Report
无约束数值优化基础
最优化问题
• 最优化问题的数学定义
– 目标函数是光滑的
– 变量可以是向量
目标函数的光滑特性
• 为了简单起见,我们考虑光滑函数,因为
– 光滑函数是各阶可微的
• 首先函数是连续的
• 且函数可微
• 且各阶导数连续且可微
• 由于函数连续可微,提供了(不为垂直的)
切线方向
几个相关概念
• 不连续函数
• 连续函数但不可微
• 连续可微函数但不光滑
向量变量
• 一般情况下变量是用特征向量的形式表示
• 向量如何求导
– Partial derivative
– Vector value
数值最优化
• 没有闭式解
• 函数信息昂贵
– 变量个数小,但函数计算复杂
– 变量个数巨大
• 思路
– 从某点出发
– 根据局部信息,作一些迭代
– 判断是否达到了解
解
• 为什么我们要定义一个函数的解?
– 全局极值
• 在整个变量域,难找,也不必要
– 局部极值
• 某个开区间,容易找,通常情况下称为解
• 特殊的局部极值
– 严格局部极小值
– 孤立局部极小值
课堂测试(1)
• 以下哪些说法是对的
– 严格局部极小值都是孤立局部极小值
– 严格局部极小值不都是孤立局部极小值
– 孤立局部极小值都是严格局部极小值
– 孤立局部极小值不都是严格局部极小值
如何判断一个局部极值
• 在f(x)是二阶连续可微的情况下,x*是局部
极值
– 必要条件
– 充分条件
算法(1)
• 数值最优化算法的基本思想
– 从给定的x0出发
– 产生一系列的x1,x2,x3…xK
– 当收敛条件达到时
• 结束算法
– 单调性要求:f(x1)>f(x2)>f(x3)…
• 两种策略
– Line search线搜索
• 选择一个方向,再选择步长
– Trust region信赖域
• 定一个范围,根据这个区域内的近似模型选择方向
算法(2)
Choose a,x0,
While(not convergent) do
choose ak,pk
xk+1=xk+akpk
k=k+1
end
Line search:先确定pk,再确定ak
Trust region: 先确定ak最大范围r,在确定pk
最后确定真正使用的ak
tmp0=xk,0+akpk,0
tmp1=xk,1+akpk,1
tmp2=xk,2+akpk,2
…
tmpi=xk,i+akpk,i
tmpN=xk,N+akpk,N
xk,0=tmp0
….
xk,N=tmpN
两种策略
线搜索方法
• 选择一个函数值下降的方向
– 最速下降
– Newton法
– Quasi-Newton法
• 步长
– 足够小
• 使下一次函数值有效减小
– 足够大
• 能较快收敛
Linesearch:方向的选择(1)
• 明显的一个选择:梯度
– 最速下降
• Downhill direction
优点:计算简便
缺点:对于复杂
问题收敛速度慢
对归一化敏感
Newton方法
目标:迭代至极值
初始点x0
For k=0,1,2,… do
找到正定矩阵Bk
解Bkpk=-Δf(xk)
xk+1=xk+akpk
End
Cholesky分解:B=LDLT
For j=1,2,…,n,do
cjj=ajj-Σs=1,to j-1dsl2js
dj=cjj
For i=j+1,…n,do
cij=aij-Σs=1 to j-1dslisljs
lij=cij/dj
end
end
目标:使D元素均为正,且L,D中元素
不太大
dj==max(|cjj|,(maxj<i<=n |cij|/b)2,e )
Quasi-Newton法
• 思想:找一个Hessian矩阵的近似
– 并根据每一轮的新信息进行有效更新
• BFGS:近似矩阵是对称的,且Bk与Bk+1的差
为秩=2的矩阵
课堂测试(2)
• 如果函数形式为
– 则在最速下降中,最好的步长ak为?
• 思考:最速下降、牛顿法,Quasi-Newton法
的优缺点是什么?
Linesearch:步长的选择(1)
• 希望的目标
• 实际上
– 目标函数有效减少
– 寻找合适步长的计算代价不太高
Linesearch:步长的选择(2)
Linesearch:步长的选择
• Wolfe Condition
– Sufficient decrease: Armijo condition
– Not too small: curvature condition
• Backtracking算法
– 初始化a>0,p<1,c
– 重复
• 直到满足Armijo condition
• 否则:a=pa
课堂测试(3)
• 下面哪些说法是对的,为什么?
– 最速下降法的步长初始为1
– Newton法的步长初始为1
– Quasi-newton法的步长初始为1
– 如果0<c2<c1<1,则有可能找不到满足wolfe条件的
步长
信赖域方法
• 选择一个信赖域
–在
• 在信赖域内选择一个与目标函数具有相同
特性的近似函数
• 同时选择一个方向和步长
如何选择信赖域半径
• 模型的质量:
Choose Δ0, x0,k=0
While(not convergent) do
choose pk
evaluate sk
if (sk<1/4) then
reject step xk+1=xk
Δk+1= Δk
end
Else if (sk>1/4 && ||p||=Δk) then
xk+1=xk+akpk
Δk+1= min(2Δk, Δ)
end
k=k+1
end

similar documents