引言
什么是优化?其本质是在将问题进行数学建模后求出最优解的过程。一般的优化问题包括:目标函数、不等式/等式约束函数(可选)、优化(决策)变量与变量空间。
- 最优化理论主要研究的内容包括解决的方法(算法),为什么方法有效(理论)以及如何实现(软件/编程)。
- 在本课程中,主要研究凸优化问题,主要因为:
- 凸优化理论已得到较为充分的研究,有很多高效且可靠的算法
- 很多现实问题可以转化为凸优化问题
- 对凸优化问题的解决思路可以指导解决更一般的问题(非凸优化)
优化问题的分类
-
连续与离散优化问题
连续优化问题是指决策变量连续取值的优化问题,例如在平面、区间等集合中取值;
- 连续优化问题中,在可微性等适当条件下,一个点的最优性信息可以通过其邻域内的其他点的信息来推断。
离散优化问题是指决策变量的可行集为离散集合,例如整数集合(整数规划)、离散点集等。
- 离散优化问题通常不能直接利用导数信息;连续松弛是重要的求解思路之一,但具体难度取决于问题结构。
-
无约束与约束优化问题
无约束优化问题是决策变量x没有约束,即可行集为Rn;约束优化问题是决策变量x有约束,即可行集为Rn的子集。
- 约束问题可以通过引入指示函数(indicator function)来转化为无约束问题。比如:
x∈Rnmin f(x)s.t. x∈C⟹x∈Rnmin f(x)+IC(x),
其中IC(x)={0,x∈C∞,x∈C。除此之外,约束优化问题还可以通过拉格朗日乘子法、罚函数法转化为无约束优化问题。
-
确定性与随机优化问题
- 确定性优化问题的目标函数和约束由给定的数据确定;求解时也可以采用随机算法。
- 随机优化问题的模型涉及随机量,利用其分布信息优化期望目标或处理随机约束。
注意问题的随机性与算法的随机性是不同的概念。
-
凸优化与非凸优化问题
- 凸优化问题是指目标函数为凸函数、可行域为凸集的优化问题。凸优化问题的任何局部解都是全局最优解。
- 非凸优化问题是指目标函数非凸、或可行域不是凸集的优化问题。非凸优化问题的局部最优解不一定是全局最优解。集合大得多,也困难得多。
在实际中,最好是解决一个凸优化问题,或是将原问题转换(近似)为一个(或一系列)凸优化问题来逐步解决。
历史上曾经将优化问题划分为线性优化与非线性优化,但之后发现线性优化能够解决的问题范围太小,于是重新划分为凸优化与非凸优化问题。
另一方面,如今神经网络的优化往往是非凸优化,这可能也需要单独作为一个研究领域。
凸性的基本概念
-
凸集:在集合C⊆Rn中,对∀x,y∈C,和0≤θ≤1,有
θx+(1−θ)y∈C.
直观理解:凸集中任意两点连线都在集合中。
-
凸函数
称函数f:Rn→R为凸函数,如果dom f(定义域)是凸集,且∀x,y∈dom f,0≤θ≤1,有
f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y).
直观理解:函数上任意两点所连接的弦落在函数以上。
- 等价地,函数为凸当且仅当其在任意直线与定义域的交集上为凸,即∀x∈dom f,v∈Rn,g(t)=f(x+tv) 是凸函数,t∈{t∣x+tv∈dom f}。【特别适用于判断高维函数的凸性】
- 特别地,对于二次型函数f(x)=x⊤Ax,x∈Rn,矩阵A的正定性决定了函数的凸性。
-
凸优化问题
x∈Dmins.t.f0(x)fi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,p
其中,
- 目标函数 f0 和不等约束函数 fi,i=1,…,m 均为凸函数
- 等式约束函数 hj,j=1,…,p 为仿射的 (即hj(x)=aj⊤x+bj)
- 优化定义域 D=dom f0∩⋂idom fi
典例:最小二乘、线性规划(下面会详细介绍)
-
局部最优与全局最优
凸优化有一个重要特性:局部最小值即为全局最小值。具体而言,严格地说,若x为可行解(x∈D),且在一个邻域内最小:
f(x)≤f(y)∀y∈D,∥x−y∥2≤ρ
则f(x)≤f(y), ∀y∈D。
-
非凸优化转为凸优化
一般的非凸优化问题主要有两个方面的途径解决:
- 局部优化方法
- 利用局部信息迭代寻找驻点或局部最小值
- 可使用多个初始点改善结果
- 通常无法得到全局最优保证或全局误差界
- 通常速度较快
- 全局优化方法
- 搜索全局最优(如粒子群优化、模拟退火);这类启发式方法通常无有限时间全局最优保证
- 最坏情况下,计算代价可能随问题规模呈指数级增长
向量与矩阵范数
向量范数
定义:若函数 ∥⋅∥:Rn→R 满足以下条件:
- 齐次性:∀v∈Rn,∀α∈R,有∥αv∥=∣α∣∥v∥;
- 三角不等式:∀v,w∈Rn,有∥v+w∥≤∥v∥+∥w∥;
- 正定性:∀v∈Rn,有 ∥v∥≥0,且∥v∥=0当且仅当v=0.
则称∥⋅∥为Rn上的向量范数.
- 常用向量范数:ℓp范数(p≥1)
∥v∥p=(i=1∑n∣vi∣p)1/p
其中v∈Rn。在实际优化问题中p最常取1,2或∞。ℓ∞范数定义为∥v∥∞=1≤i≤nmax∣vi∣。
- 当然也可以定义ℓ0“范数”:∥v∥0=i=1∑n1{vi=0},不过它并不是向量范数(齐次性不满足)。可以证明,ℓ1范数是ℓ0范数在{v∣∥v∥∞≤1}上的凸包络(最大凸下界函数)。
矩阵范数
定义与向量范数类似,只需要将定义域改为Rm×n即可。典型的矩阵范数如下:
- 核范数:矩阵的奇异值之和
∥A∥∗=i=1∑min{m,n}σi(A)=∥σ(A)∥1
由此可见核范数就是奇异值向量的ℓ1范数。相应地,也有奇异值向量ℓ0范数对应的矩阵范数:矩阵秩函数
rank(A)=i=1∑min{m,n}1{σi(A)>0}=∥σ(A)∥0.
同样在范数单位球上,核范数是秩函数的凸包络,因此其在优化中常被用来寻找低秩矩阵。
- Frobenius范数(F范数)
∥A∥F=i=1∑mj=1∑n∣aij∣2=trace(A⊤A)=i,j∑aij2
其可以看作向量ℓ2范数的推广。
- F范数具有正交不变性:∥UAV∥F=∥A∥F
- 在优化中,常用的矩阵内积是Frobenius内积:
⟨A,B⟩F=trace(A⊤B)=i=1∑mj=1∑naijbij
- 谱范数:矩阵的最大奇异值
∥A∥=σmax(A)=λmax(A⊤A)
与F范数的关系:∥A∥≤∥A∥F
补充
与向量ℓp范数类似,矩阵范数也可以用 Schatten 范数统一表示:
- Schatten p 范数:∥X∥Sp=i=1∑min{m,n}σi(X)p1/p
- 当 p=1 时,∥X∥S1=∥σ(X)∥1=∥X∥∗
- 当 p→0 时(非范数),∥X∥S0=∥σ(X)∥0=rank(X)
- 当 p→∞ 时,∥X∥S∞=∥σ(X)∥∞=σ1(X)
另外,我们还可以从向量范数诱导得到另一类矩阵范数:
∥X∥p=v=0sup∥v∥p∥Xv∥p特别地,当p=2时,这个范数就是谱范数。
范数在优化算法中的作用:
-
作为目标函数的正则项,对估计量的复杂度进行不同程度的惩罚:
| 惩罚项 |
估计量的结构 |
例子 |
| ∣β∣1 |
稀疏:多数分量为 0 |
Lasso |
| ∣X∣∗ |
低秩 |
矩阵补全 |
| ∣β∣22 |
收缩,分量一般非零 |
岭回归 |
-
作为最快下降的度量:设优化变量为矩阵W∈Rm×n(如神经网络一层的权重),目标函数在当前点的梯度G=∇f(W)∈Rm×n。范数∥⋅∥下的最速下降方向为
Δ⋆=argmin{⟨G,Δ⟩:Δ∈Rm×n, ∥Δ∥≤1}:
| 范数 |
Δ⋆ |
对应算法 |
| F 范数 |
−G/∣G∣F |
梯度下降 |
| ℓ∞(逐元素) |
−sign(G) |
符号下降(Adam) |
| 谱范数 |
−UV⊤ |
Muon |
变量为向量时,前两行即通常的梯度下降与符号下降;第三行只对矩阵变量有意义(需要对G进行紧凑奇异值分解:G=UΣV⊤,U∈Rm×r,V∈Rn×r,r=rank(G))。
紧凑SVD(也称截断SVD)与普通SVD的主要区别在于:紧凑SVD只保留了非零奇异值及对应的奇异向量。
凸性进阶
前面我们已经简单提到凸性的基本概念,这里就不重复赘述了。
凸集
仿射集
定义:若集合C⊆Rn包含经过集合中任意两点的直线,那么就称C为仿射集。【符号定义:z=θx+(1−θ)y∈C, ∀x,y∈C,θ∈R】
- C是仿射集⟺若x1,…,xk∈C,θ1+⋯+θk=1,则θ1x1+⋯+θkxk∈C。
- 若C是仿射集,给定x0∈C,则结合V=C−x0={x−x0∣x∈C}为Rn的一个线性子空间。
- 对任意仿射集C,其可以表示为某个线性方程组{x∣Ax=b}的解集
凸包与凸集
- 首先定义凸组合:对于x1,⋯,xk∈Rn,i∑θi=1,θi≥0,i=1,2,⋯,k,x=θ1x1+⋯+θkxk为这些点的凸组合。
- 对于集合C⊆Rn,它的凸包就是其所有点的凸组合:
conv(C)={i=1∑kθixi∣xi∈C,θi≥0,i=1,…,k,i∑θi=1}.
C的凸包是包含C的最小凸集。
- 一些典型的凸集:
- 范数球:{x:∥x−xc∥≤r},给定范数、球心xc和半径r≥0;
- 超平面:{x:a⊤x=b},给定a,b;
- 半空间:{x:a⊤x≤b},给定a,b;
- 仿射空间:{x:Ax=b},给定A,b;
- 多面体:{x:Ax⪯b},给定A,b(或{x:Ax⪯b,Cx=d})。【⪯表示向量分量不等号】
- 单纯形:仿射独立点集v1,v2,…,vk∈Rn(即v2−v1,⋯,vk−v1线性无关)的凸包
conv{v1,…,vk}={i∑θivi∣θ⪰0,1⊤θ=1}
- 概率单纯形:conv{e1,…,en}={ω∣ω⪰0,1⊤ω=1}(即标准基向量的凸包)
锥体
定义:对于集合C⊆Rn,若对任意x∈C,θ≥0,有θx∈C,则称C为锥体。
- 凸锥(既是锥体又是凸集):满足任意x1,x2∈C,有θ1x1+θ2x2∈C,∀θ1,θ2≥0
- 锥组合(非负线性组合):对x1,…,xk∈Rn,θ1,…,θk≥0,θ1x1+⋯+θkxk为锥组合。
- 锥包:集合中所有点的锥组合。
- 一些典型的凸锥:
-
范数锥:对于范数∥⋅∥,称C={(x,t):∥x∥≤t}⊆Rn+1为范数锥;
- 特别地,对于ℓ2范数∥⋅∥2得到的范数锥也称为二阶锥。
-
法向锥:对于凸集C和点x0∈C,法向锥定义为NC(x0)={y:y⊤(x−x0)≤0,∀x∈C}
-
半正定锥:首先定义
- n×n对称矩阵集 Sn={X∈Rn×n:X=X⊤}
- n×n对称半正定矩阵集(∀z∈Rn,z⊤Xz≥0): S+n={X∈Sn:X⪰0}
- n×n对称正定矩阵集 S++n={X∈Sn:X≻0}
可以证明S+n是凸锥。
凸集与超平面
- 超平面分割定理:假设凸集C,D非空且C∩D=∅,则有一个超平面分割它们,即存在a=0,b,使得
a⊤x≥b∀x∈C,a⊤x≤b∀x∈D
这里的分割超平面可表示为{x:a⊤x−b=0}。
- 注:这个分割超平面不一定能够严格分割这两个凸集(即超平面与两个凸集没有交集)。
- 支持超平面定理:凸集的任意边界点上有经过该点的支持超平面,即对x0∈bdC,存在a=0使得
a⊤x≤a⊤x0,∀x∈C
支持超平面表示为{x:a⊤x−a⊤x0=0},其在x0与C相切,且半空间{x:a⊤x≤a⊤x0}包含了C。
凸集保凸性运算
判断集合是否为凸集,除了采用定义之外,还可以通过保凸性运算得到。常见的保凸性运算包括:
- 集合交
- 多面体是多个半空间和超平面的交集,因此是凸集
- 交集运算可以推广到无穷个集合
- 仿射变换
- 定义:若函数f:Rn→Rm满足f(x)=Ax+b(A∈Rm×n, b∈Rm),则称f为仿射变换。
- 若C⊆Rn是凸集,函数f是仿射的,则C在f下的像
f(C)={f(x):x∈C}
是凸集,凸集D⊆Rm在f下的原像
f−1(D)={x:f(x)∈D}
也是凸集。
- 常见的仿射变换包括缩放、平移、投影、加和、部分加和等。
- 透视:若函数P:Rn×R++→Rn(R++代表正实数)满足
P(x,z)=zx,dom P={(x,z):x∈Rn,z>0}
则称P为透视。
- 若C⊆dom P是凸集,则P(C)是凸集,且若D是凸集,则P−1(D)是凸集。
- 线性分数:若函数f:Rn→Rm满足
f(x)=c⊤x+dAx+b,dom f={x∣c⊤x+d>0}
则称f为线性分数。线性分数可看作透视函数与仿射函数的复合,凸集在该函数下的像和原像均是凸集。
凸函数
凸函数的定义前面已经提到过,下面再定义两种特殊的凸函数:
- 严格凸函数:如果dom f是凸集,且∀x,y∈dom f,x=y,0≤θ≤1,有
f(θx+(1−θ)y)<θf(x)+(1−θ)f(y).
则称f为严格凸函数。
- 强凸函数:称f是m-强凸函数(m>0),如果f(x)−2m∥x∥22是凸函数。
严格凸排除了图像上的线段,而强凸进一步要求f减去一个二次函数后仍为凸,即曲率有正的下界m。【类似也可定义严格凹函数与强凹函数】
函数凸性判断
凸函数主要可通过下述凸性条件判断:
- 一阶条件:若f可微分,则f是凸的当且仅当dom f是凸集且
f(y)≥f(x)+∇f(x)⊤(y−x)∀x,y∈dom f
也就是说梯度为0的点就是全局最小点。
- 二阶条件:若f二阶可微分,则f是凸的当且仅当dom f是凸集且对任意x∈dom f
∇2f(x)⪰0
若对任意x有∇2f(x)≻0,则f严格凸【反之不然】。
- Jensen不等式:若f为凸函数,随机变量X取值于dom f且EX存在,则f(EX)≤Ef(X)。
除此之外,还可以通过简单凸函数的保凸性运算判断,包括:
-
非负加权平均/非负线性组合:若f1,⋯,fk为凸函数,ω1,⋯,ωk≥0,那么f=ω1f1+⋯+ω1fk也是凸函数。【凸函数集合为凸锥】
-
与仿射变换复合:若f为凸函数,那么g(x)=f(Ax+b)也是凸函数。
-
逐点取最大值与上确界:若f1,⋯,fk为凸函数,那么f(x)=max{f1(x),⋯,fk(x)}也为凸函数,其中domf=⋂i=1kdomfi。【当然这里max也可替换为sup】
-
部分极小化:若f(x,y)关于(x,y)联合为凸函数,那么对于非空集合C,g(x)=y∈Cinff(x,y)也为凸函数。【设g(x)>−∞】
-
透视函数:若f:Rn→R为凸函数,那么其透视函数
g(x,t)=tf(tx),domg={(x,t):tx∈domf,t>0}
为Rn+1上的凸函数。
-
与标量函数复合:令f(x)=h(g(x)),其中g:Rn→R,h:R→R,那么如果
- g凸,h凸且非降
- g凹,h凸且非升
则f是凸函数。
-
向量复合:考虑gi:Rn→R,i=1,…,k,h:Rk→R的复合函数f(x)=h(g(x))=h(g1(x),g2(x),…,gk(x)),那么如果
- gi,i=1,…,k凸,h凸且关于每个分量非降
- gi,i=1,…,k凹,h凸且关于每个分量非升
则f是凸函数。
如果domh是Rk子集,那么需要保证延拓后的h~(在延拓区域取值+∞)单调性仍然成立。
复合凸函数的典型例子:
- exp(g(x))是凸函数,如果 g是凸函数
- g(x)1是凸函数,如果g(x)>0,∀x∈dom g,且g为凹函数
- i=1∑mloggi(x)是凹函数,如果gi(x)>0,i=1,…,m且gi为凹函数
- logi=1∑mexp(gi(x))为凸函数,若每个gi为凸函数(向量复合)【这也被称为“log-sum-exp”函数,可看作max函数的平滑近似,对gi求偏导可得到softmax函数】
凸优化问题
标准的凸优化问题形式上面已经提到,这里就不再重复。【一般的优化问题标准形式就是在此基础上去掉凸函数限制,故同样作略】
下面基于此进行补充:
- 最优化问题的解
- 最优化值:f∗=inf{f0(x)∣fi(x)≤0,i=1,…,m,hi(x)=0,i=1,…,p}
- 若x是可行的且f0(x)=f∗,则x是最优点/最优解/最小值点
- 若x是可行的且f0(x)≤f∗+ϵ,则x是ϵ-次优的
- 若x是可行的,且fi(x)=0,则称第i个不等式约束在x处活跃(active)
- x是局部最优的,如果存在R>0使得x是如下问题的最优解
mins.t.f0(z)fi(z)≤0,i=1,…,m,hi(z)=0,i=1,…,p∥z−x∥2≤R
- 凸优化问题的解集
- 对于凸优化问题,由凸函数的限制可知可行域
i=0⋂mdomfi∩i=1⋂m{x:fi(x)≤0}∩i=1⋂p{x:ai⊤x=bi}
为凸集。
- 令Xopt为凸优化问题的所有最优解组成的集合,记作
Xopt=argmin s.t.f0(x)fi(x)≤0, i=1,…,mAx=b
则Xopt为凸集。
- 若f0严格凸,则最优解若存在必唯一,即Xopt至多包含一个元素。
- 优化问题等价形式
xmins.t.f0(x)fi(x)≤0,i=1,…,mAx=b
可以等价写作
xminf0(x),s.t. x∈C
其中C={x:fi(x)≤0,i=1,…,m,Ax=b}为可行集。
- 当然,上述问题也可写作无约束形式
xminf0(x)+IC(x)
其中IC(x)为指示函数(IC(x)={0∞,if x∈Cif x∈/C);
因为C为凸集时IC为凸函数,所以凸优化问题总可写成无约束形式。
- 一阶最优条件:假设凸优化问题中的目标函数f0可微分,则
- 若x,y∈dom f0,有
f0(y)≥f0(x)+∇f0(x)⊤(y−x)
- 令C为可行集,可行点x∈C是最优点的等价条件是
∇f0(x)⊤(y−x)≥0, for all y∈C
这就是一阶最优条件。直观地,从x指向任一可行点y的方向与∇f0(x)的夹角不超过90∘,即−∇f0(x)∈NC(x)【法向锥】
- 如果没有约束(C=Rn),那么就退化为∇f0(x)=0。
- 部分优化
部分优化一个凸优化问题可以保持其凸性,即若x=(x1,x2)∈Rn1×Rn2,则
x1,x2mins.t.f(x1,x2)g1(x1)≤0g2(x2)≤0⟺x1mins.t.f~(x1)g1(x1)≤0
其中f~(x1)=x2:g2(x2)≤0minf(x1,x2),若左式为凸优化问题则右式也是。
实际上部分优化的作用就是将约束条件并入目标函数的同时对优化变量进行降维。
- 引入等式约束——松弛变量
引入松弛变量可以将线性不等式约束转换为等式约束加非负约束,即原问题
mins.t.f0(x)ai⊤x≤bi,i=1,…,m
可以等价地转化为
x,smins.t.f0(x)si=bi−ai⊤x,i=1,…,msi≥0,i=1,…,m
- 放松非仿射等式约束
凸优化问题中的等式约束需要是仿射的,带非仿射等式约束的问题一般不是凸优化问题。可用以下方法将原问题扩展为凸优化问题:对
xminf0(x)s.t. x∈C
及C~⊇C,扩展问题
xminf0(x) s.t. x∈C~
称为原问题的放松(relaxation)问题,其中C~为放松后的约束集合。放松问题的最优值总是小于等于原问题的最优值;若放松问题的解属于C,则它也是原问题的解。
- 应用于凸函数hi给出的等式约束
hi(x)=0,i=1,…,p
可放松为hi(x)≤0,i=1,…,p,得到凸优化问题。
梯度下降法
迭代算法
对于一个优化问题,如果可以写出最优解的解析表达式,则称其为显式解;但是对于一般情况下,显式解无法直接求出,我们只能通过迭代的方式来逼近最优解,这种方法被称为迭代算法。
-
迭代算法的具体形式:从一个初始点x出发,按照某种规则进行迭代,得到一系列的点{x(k)}=x(1),x(2),⋯。算法经过有限步终止时,我们希望得到给定精度的近似最优解。
-
下面我们考虑迭代算法(点列)的收敛性,其定义为目标函数值趋于最优值,或迭代点趋于某个最优解。常用的收敛准则有以下几种:
- 相对最优性差距小于某个阈值,即max{∣f∗∣,1}f(x(k))−f∗≤ϵ;【其中ϵ>0为容差,f∗为最优值,其通常未知;若f∗以其估计值代替,则该不等式不再是严格的误差界】
- 无约束可微问题中,梯度范数小于某个阈值∥∇f(x(k))∥≤ϵ;
- 约束违反程度小于某个阈值(仅衡量近似可行性)
当然,满足上述收敛准则并不一定意味着接近最优,这取决于问题的假设。
-
在实际使用中,上述收敛准则里往往很难直接计算f∗或其近似,因此一般会采用停机准则作为算法的停止条件。常用的停机准则包括:
- 相邻迭代点的相对误差max{∥x(k)∥,1}∥x(k+1)−x(k)∥≤ϵ.
- 相邻两次迭代点的目标函数相对误差小于某个阈值max{∣f(x(k))∣,1}∣f(x(k+1))−f(x(k))∣≤ϵ.
这些停机准则是启发式的:相邻迭代变化小可能只是步长过小或迭代停滞,不能单独保证接近最优。因此停机准则通常与梯度范数、可行性残差及最大迭代次数一起使用。
-
下面我们进一步讨论迭代算法的(渐近)收敛速度。首先定义两种收敛阶:
-
Q-收敛速度(这里的Q表示商,Quotient):对于收敛于x∗的迭代点列{x(k)},如果满足
k→∞limx(k)−x∗qx(k+1)−x∗≜k→∞limekek+1=a
其中q>1,a∈(0,+∞)或q=1,a∈[0,1],那么就称{x(k)}满足Q-收敛。(默认要求x(k)=x∗)特别地,
- 当q=1,a∈(0,1)时,称为Q-线性收敛;【当然也允许在(0,a]之间振荡】
- 当q=1,a=0时,称为Q-超线性收敛;
- 当q=1,a=1时,称为Q-次线性收敛;
- 当q=2时,称为Q-二次收敛。【同样允许(0,a]振荡】
可以通过绘制k−logek图判断收敛速度:Q-线性收敛对应直线,Q-次线性收敛对应负对数曲线,而Q-二次收敛就对应开口向下的抛物线。
-
R-收敛速度(R表示根,Root):若存在Q-收敛于0的非负序列{tk},且有
∥x(k)−x∗∥≤tk
那么就称{x(k)}满足R-收敛。【具体的R-收敛形式与{tk}的Q-收敛形式对应】
- R-线性收敛的等价条件:存在C>0和0<q<1,使∥x(k)−x∗∥≤Cqk。
-
当然我们也可以用大O表示误差的渐近上界,如O(k1),O(k21)等。可以证明,多项式阶的上界不蕴含R-线性收敛。
-
除了渐近收敛速度外,我们还可以用迭代到指定精度所需步数衡量迭代算法的复杂度。具体而言,我们定义N(ϵ)为达到精度ϵ所需要的迭代次数,其一般也用大O表示。
- 实际上,N(ϵ)的渐近函数阶与上面的收敛阶恰好互为反函数关系。比如Q-线性(R线性)收敛对应的N(ϵ)=O(logϵ1)。
梯度下降(GD)算法
在无约束凸优化问题的迭代算法中,最常用的就是梯度下降算法。给定初始点x(0)后,其具体流程如下:
- 计算更新方向为负梯度方向:Δx=−∇f(x)
- 选择固定步长或通过线搜索确定步长ti
- 更新:x(i+1)=x(i)+tiΔx(i)
重复直至预设停止条件满足,或者达到最大迭代次数。
- 那么为什么梯度下降算法有效?我们可以考虑函数在x处的上抛物线包络:
g(y)=f(x)+∇f(x)⊤(y−x)+2t1∥y−x∥2
其中2t1∥y−x∥2可看作一个惩罚项,目的是限制更新幅度。那么当f(x)是L-smooth的(会在后面解释),且t≤L1,则g(y)≥f(y)对任意y都成立。
- 于是我们可以求g(y)的最低点:
x+=yargming(y)=yargmin[f(x)+∇f(x)⊤(y−x)+2t1∥y−x∥2]=x−t∇f(x)
这便是基于负梯度进行参数更新,可以保证梯度下降算法总会让解更优。更详细的收敛性分析后面会展开。
线搜索方法
对于步长的选择,随意选择的步长ti=t并不能保证算法收敛到最优点,并且可能导致算法收敛缓慢。更好的解决方案是采用线搜索,具体包括:
- 精确线搜索:t∈s≥0argminf(x+sΔx),前提是沿当前方向的一维最小值能够取到
- 其计算代价取决于一维子问题的结构;对一般函数,求一维最小值的计算代价可能较高,因此实际中并不常用
- 回溯线搜索
由Larry Armijo最早于1966年提出,其具体算法如下:设方向Δx满足∇f(x)⊤Δx<0(方向导数为负),那么
- 固定参数0<α≤21,0<β<1,tinit>0
- 在每次迭代中,初始化t=tinit,当
f(x+tΔx)>f(x)+αt∇f(x)⊤Δx
时,重复缩减步长t=βt,直至不等式不再成立,再更新
x+=x+tΔx
在梯度下降中,因为Δx=−f(x),因此当步长足够小时,回溯一定会停止。
- 这里α的含义:实际下降量不少于一阶近似所预测下降量的α倍(充分下降条件),一般会取一个较小的值(如0.01或10−4)。
算法收敛性分析
首先给出函数L-smooth和m-强凸的定义:
-
L-smooth:设f:Rn→R为可微凸函数,存在最优解,且∇f为Lipschitz连续:
∥∇f(x)−∇f(y)∥2≤L∥x−y∥2,∀x,y
其中L>0。
- f二阶可微时,条件可简化为0⪯∇2f(x)⪯LI。
- 可以证明,对于固定步长0<t≤L1的梯度下降算法,有
f(x(k))−f∗≤2tk∥x(0)−x∗∥22,k≥1
而对于回溯搜索也有类似结论:取α=21时,上式中t替换为t=min{tinit,Lβ}即可。
因此,目标函数值误差f(x(k))−f∗收敛阶为O(k1),对应N(ϵ)=O(ϵ1)。
-
m-强凸:若函数f满足f−2m∥x∥22为凸函数(m>0),那么就称f为m-强凸函数。
- f二阶可微时,条件可简化为∇2f(x)⪰mI。
- 同一函数可以既是L-smooth又是m-强凸,只要0<m≤L即可。对于这类函数,使用固定步长0<t≤L1的梯度下降算法,有
f(x(k))−f∗≤(1−mt)k(f(x(0))−f∗),k≥1
令γ=1−mt∈[0,1);γ=0时一步迭代即得最优解(比如二次函数)。
- 当0<γ<1时,目标函数值误差以几何速率衰减。m,L固定时,N(ϵ)=O(log(ϵ1))。
-
实际上,我们还可以将L-smooth且m-强凸函数的梯度下降收敛性与Hessian矩阵的条件数构建联系。由条件数的定义(可见CS127 Chapter 6)可知,这类函数的条件数上界就是mL。对于上述不等式,取t=L1,当0<ϵ<f(x(0))−f∗时,达到进度ϵ精度所需迭代次数
k≥mLlogϵf(x(0))−f∗.
也就是说,这类函数梯度下降的收敛速度与条件数以及初始误差有关。
梯度范数停机与算法改进
前面我们提到,对于可微凸函数,可以考虑用梯度范数小于ϵ作为停止迭代条件。【在最优解处∇f(x∗)=0】
- 对此,我们进一步限制f为m-强凸函数,那么有f(x)−f∗≤2m∥∇f(x)∥22【推导略】,于是
∥∇f(x)∥2≤2mϵ⟹f(x)−f∗≤ϵ
目前我们讨论的梯度下降算法对于条件数较小的强凸问题,收敛较快;而对于非强凸或条件数较大时,收敛可能很慢。另一方面,标准梯度法要求目标可微,因此对于非光滑问题(如深度学习反向传播)需采用其他方法。
-
针对第一个问题,1983年Nesterov提出了一个重要结论:对于任意的一阶最优化算法,可以构造函数f使得对任意1≤k≤2n−1(n为函数维度)和任意x(0),
f(x(k))−f⋆≥32(k+1)23L∥x(0)−x∗∥22
也就是说,一阶算法的收敛速度下界就是O(k21),对应N(ϵ)=O(ϵ1)。
- 那么有没有一阶算法能够达到这一下界?有!这便是Nesterov加速梯度法,其引入了动量机制,在机器学习优化中尤为常用。【下面会详细展开】
-
另外,针对非凸函数,由于其不一定存在全局最优解,所以要想使用梯度下降,需要另外定义ϵ-近似驻点:∥∇f(x)∥2≤ϵ。
- 可以证明,只要函数L-smooth且有下界(inff>−∞),那么对于固定步长tk≡t∈(0,L1],有
i=0,…,kmin∥∇f(x(i))∥2≤t(k+1)2(f(x(0))−finf)
也就是说,其梯度收敛速度为O(k1),对应N(ϵ)=O(ϵ21)。【当维数充分高时,这个收敛速度就不可改进】
梯度增强(Gradient Boosting)
可以参见机器学习算法 Ch.7 集成模型,这里就不详细展开了……
近端梯度下降与Nesterov加速
近端梯度下降
上述梯度下降算法都假定目标函数可微。那么目标函数不可微时该如何进行迭代优化呢?这里我们就要对梯度下降算法进行推广,即近端梯度下降。
- 模型:f(x)=g(x)+h(x),其中g为可微凸函数,h为正常闭凸函数(定义域非空且不取−∞,可取到最小值)。对此,我们考虑单独对g取上抛物线包络:
x+=zargmingˉt(z)+h(z)=zargming(x)+∇g(x)⊤(z−x)+2t1∥z−x∥22+h(z)=zargmin2t1{∥z−x∥22+2t∇g(x)⊤(z−x)+∥t∇g(x)∥22}+h(z)=zargmin2t1∥z−(x−t∇g(x))∥22+h(z)
- 由此我们可以定义近端映射(有且仅有一个最小值点)
proxh,t(x)=zargmin2t1∥x−z∥22+h(z)
那么近端梯度下降的算法可表示为:给定初始点x(0)∈domh,迭代公式为
x(k)=proxh,tk(x(k−1)−tk∇g(x(k−1))),k=1,2,…
也可以改写为类似标准梯度下降的形式:
x(k)=x(k−1)−tkGtk(x(k−1))
其中
Gt(x)=tx−proxh,t(x−t∇g(x))
为梯度映射。
近端映射的直观理解:求解一个距x不算太远的点,并兼顾使新点的函数值h(z)较小。
- 使用近端算子proxh,t的优点是其对很多重要的函数h有显式解,且
- proxh,t(⋅)只依赖h和t,并不依赖于函数g
- 尽管光滑部分g可能很复杂,但其梯度往往不难计算
- 收敛速度:可以证明,若g为L-smooth,近端梯度下降的收敛速度与标准梯度下降一致。
- 近端梯度下降也被称为广义梯度下降,是因为其包含下述特殊情形:
- h=0: 一般梯度下降
- h=IC: 投影梯度下降
对于给定非空闭凸集C⊆Rn,可定义投影算子
proxIC,t(x)=zargmin2t1∥x−z∥22+IC(z)=z∈Cargmin∥x−z∥22
于是梯度下降更新步骤为
x+=proxIC,t(x−t∇g(x))≜PC(x−t∇g(x))
- g=0: 近端最小化算法
考虑优化问题xminh(x),其近端最小化算法更新公式为
x+=zargmin2t1∥x−z∥22+h(z)
也就是说,其迭代每一步需求解一个强凸子问题。若该步仅近似求解,误差会进入收敛估计,不能直接套用精确算法的定理。
- 近端梯度下降的步长选择同样有回溯线搜索方法。具体而言,取0<β<1和t0>0。第k步从t=tk−1开始,先计算x+=proxh,t(v−t∇g(v)),若
g(x+)>g(v)+∇g(v)⊤(x+−v)+2t1∥x+−v∥22
则令t←βt,重新计算x+并检查;否则接受tk=t及x(k)=x+。
Nesterov加速算法
这里在近端梯度下降的基础上讨论加速算法,即加速近端梯度算法。考虑复合函数优化问题
xming(x)+h(x)
其中g可微凸、h正常闭凸。给定x(0)=x(−1)∈domh,则k≥1时,算法迭代公式为
vx(k)=x(k−1)+k+1k−2(x(k−1)−x(k−2))=proxh,tk(v−tk∇g(v))
由此可见,加速近端梯度下降中,趋势的权重随迭代步数变化(逐渐趋向1)
- 第一步迭代为普通的近端梯度下降,而之后的v都携带了部分上一步迭代的趋势(动量)
- 当h=0时,算法称为加速的梯度下降算法。