优化|一阶方法:求解不具有凸性和lipschitz连续性的复合问题

这篇具有很好参考价值的文章主要介绍了优化|一阶方法:求解不具有凸性和lipschitz连续性的复合问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

优化|一阶方法:求解不具有凸性和lipschitz连续性的复合问题,人工智能,算法
论文解读者:陈康明,赵田田,李朋

编者按:​

对于大多数一阶算法,我们会在收敛性分析时假设函数是凸的,且梯度满足全局 Lipschitz 条件。而本文中,对于某一类特殊函数。我们不仅不要求函数是凸的,也不再要求梯度满足全局 Lipschitz 条件。

考虑复合优化问题
( P ) min ⁡ { Ψ ( x ) = f ( x ) + g ( x ) : x ∈ C ˉ } , \begin{equation}\nonumber (\mathcal{P})\quad \min \{\Psi(x)=f(x)+g(x): x\in\bar{C}\}, \end{equation} (P)min{Ψ(x)=f(x)+g(x):xCˉ},
其中 C ˉ \bar{C} Cˉ C C C的闭包, C C C R d \mathbb{R}^{d} Rd的非空开子集。对于大多数一阶算法,我们会在收敛性分析时假设 f f f g g g都是凸函数,且 g g g的梯度满足全局 Lipschitz 条件。而本文中,我们不仅不要求函数 f f f g g g是凸函数,也不再要求 g g g的梯度的满足全局 Lipschitz 条件,而是使用适应函数g几何形状的凸性条件代替。我们重点研究了一种基于 Bregman 距离而非欧式距离的近端梯度法,该方法涵盖了标准的近端梯度法,并且在一定的合理假设下,证明了该方法全局收敛到临界点。为了展示我们的成果的潜力,我们考虑了一类具有稀疏性约束的二次逆问题,这类问题在许多基础应用中经常出现。并且应用我们的方法推导出了该类问题的新的收敛方案,这是这类重要问题的第一个全局收敛的算法。

第一部分:预备知识​

1.1 Bregman 距离

首先我们给出 kernel generating distance 的定义:

定义1.1 (kernel generating distance). 让 C C C R d \mathbb{R}^d Rd的凸的非空开集,如果函数 h : R d → ( − ∞ , + ∞ ] h: \mathbb{R}^d \rightarrow(-\infty,+\infty] h:Rd(,+]满足下面的条件,那么它被称为 kernel generating distance :
(i) h h h是适当的,下半连续的凸函数, 并且 dom ⁡ h ⊂ C ˉ \operatorname{dom} h \subset \bar{C} domhCˉ, dom ⁡ ∂ h = C \operatorname{dom} \partial h= C domh=C
(ii) 在 dom ⁡ h ≡ C \operatorname{dom} h \equiv C domhC上, h h h C 1 C^1 C1的。

我们用 G ( C ) \mathcal{G}(C) G(C)表示这类 kernel generating distance。
给定 h ∈ G ( C ) h\in\mathcal{G}(C) hG(C),我们可以通过以下方式定义一个近似度量 D h : dom ⁡ h × int ⁡ dom ⁡ h → R + D_h:\operatorname{dom} h\times\operatorname{int} \operatorname{dom} h\rightarrow\mathbb{R}_{+} Dh:domh×intdomhR+:

D h ( x , y ) : = h ( x ) − [ h ( y ) + ⟨ ∇ h ( y ) , x − y ⟩ ] D_h(x, y):=h(x)-[h(y)+\langle\nabla h(y), x-y\rangle] Dh(x,y):=h(x)[h(y)+h(y),xy⟩]

这个近似度量 D h D_h Dh就被称为 Bregman 距离,它衡量了 x x x y y y的接近程度。

由于梯度不等式,对于所有的 x ∈ dom ⁡ h , y ∈ int ⁡ dom ⁡ h x\in\operatorname{dom} h, y\in\operatorname{int} \operatorname{dom} h xdomh,yintdomh h h h是凸的当且仅当 D h ( x , y ) ≥ 0 D_h(x, y)\geq 0 Dh(x,y)0。并且如果 h h h是严格凸的,当且仅当 x = y x=y x=y时,等号成立。值得注意的是,一般情况下 D h D_h Dh 不是对称的,除非 h = ∣ ⋅ ∣ 2 h=|\cdot|^2 h=2,这样得到的就是经典欧式距离的平方。

另外,当 h h h不是凸函数时, D h D_h Dh的结构形式也是有用的。它衡量了在给定点 x ∈ dom ⁡ h x\in\operatorname{dom} h xdomh h h h的值与其在 y ∈ int ⁡ dom ⁡ h y\in\operatorname{int} \operatorname{dom} h yintdomh附近的线性近似之间的差异或者说误差。在这种情况下,前面提到的 D h ( x , y ) ≥ 0 D_h(x, y)\geq 0 Dh(x,y)0 D h ( x , y ) = 0 D_h(x, y)= 0 Dh(x,y)=0当且仅当 x = y x=y x=y都不再成立。然而, D h D_h Dh仍然具有两个简单但显著的性质,这些性质可以从基本的代数运算中得出:

三点恒等式:对于任意 y , z ∈ int ⁡ dom ⁡ y, z \in \operatorname{int} \operatorname{dom} y,zintdom x ∈ dom ⁡ h x \in \operatorname{dom} h xdomh,我们有 D h ( x , z ) − D h ( x , y ) − D h ( y , z ) = ⟨ ∇ h ( y ) − ∇ h ( z ) , x − y ⟩ D_h(x, z)-D_h(x, y)-D_h(y, z)=\langle\nabla h(y)-\nabla h(z), x-y\rangle Dh(x,z)Dh(x,y)Dh(y,z)=h(y)h(z),xy

线性可加性:对于任意 α , β ∈ R \alpha, \beta \in \mathbb{R} α,βR,以及任意函数 h 1 h_1 h1 h 2 h_2 h2,我们有 D α h 1 + β h 2 ( x , y ) = α D h 1 ( x , y ) + β D h 2 ( x , y ) D_{\alpha h_1+\beta h_2}(x, y)=\alpha D_{h_1}(x, y)+\beta D_{h_2}(x, y) Dαh1+βh2(x,y)=αDh1(x,y)+βDh2(x,y)
对于所有 x , y ∈ dom ⁡ h 1 ∩ dom ⁡ h 2 x, y \in \operatorname{dom} h_1 \cap \operatorname{dom} h_2 x,ydomh1domh2,使得 h 1 h_1 h1 h 2 h_2 h2 y y y处可导。

1.2 L-smooth adaptable 条件我们想要选择合适的函数 h ∈ G ( C ) h\in\mathcal{G}(C) h∈G(C),并用对应的 Bregman 函数 D h D_h Dh​来代替近似点梯度法中的欧氏距离平方项。注意,本文所考虑的函数 f f f和 g g g未必是凸函数。其中 g g g满足假设:

g : R d → ( − ∞ , + ∞ ] g:\mathbb{R}^{d}\to (-\infty,+\infty] g:Rd(,+]是适当的下半连续函数,定义域满足$\text{dom}h\subset\text{dom}g , 且 , 且 ,g 在 在 C$上连续可微。

基于上述 g g g有关假设, 我们可以给出 L-smooth adaptable 的定义如下:

定义1.2 函数对 ( g , h ) (g,h) (g,h) C C C上满足 L-smooth adaptable 条件,当且仅当存在 L > 0 L>0 L>0使得 L h + g Lh+g Lh+g L h − g Lh-g Lhg C C C上都是凸函数。

结合1.1节中 Bregman 函数的定义,容易得到它的一个等价定义:

定义1.2’ 函数对 ( g , h ) (g,h) (g,h) C C C上满足 L-smooth adaptable 条件,当且仅当存在 L > 0 L>0 L>0使得KaTeX parse error: {equation} can be used only in display mode.

上述定义可看作是 L-smooth 条件的推广。如果取 C = R d C=\mathbb{R}^{d} C=Rd, h = 1 2 ∥ ⋅ ∥ 2 h=\frac{1}{2}\|\cdot\|^{2} h=212, 则对应的不等式可写为
∣ D g ( x , y ) ∣ = ∣ g ( x ) − g ( y ) − < ∇ g ( y ) , x − y > ∣ ≤ L 2 ∥ x − y ∥ 2 , ∀ x , y ∈ R d , \begin{equation}\nonumber \left|D_g(x,y)\right|=|g(x)-g(y)-\left<\nabla{g}(y),x-y\right>|\leq \frac{L}{2}\|x-y\|^{2}, \quad \forall x,y\in\mathbb{R}^{d}, \end{equation} Dg(x,y)=g(x)g(y)g(y),xy2Lxy2,x,yRd,

相当于 g g g满足 L-smooth条件。

另外,第二节的证明只需要 L h − g Lh-g Lhg是凸函数这个条件。我们把它记作L-smad 条件

第二部分:BPG 算法

2.1 BPG 算法

根据第一节的分析,我们可以作出以下初步假设:

假设2.1 (1) h ∈ G ( C ) h\in\mathcal{G}(C) hG(C), 且 C ‾ = dom h ‾ \overline{C}=\overline{\text{dom}h} C=domh;

(2) f : R d → ( − ∞ , + ∞ ] f:\mathbb{R}^{d}\to (-\infty,+\infty] f:Rd(,+]是适当的下半连续函数,定义域满足 dom f ∩ C ≠ ∅ \text{dom}f\cap{C}\neq\emptyset domfC=;

(3) g : R d → ( − ∞ , + ∞ ] g:\mathbb{R}^{d}\to (-\infty,+\infty] g:Rd(,+]是适当的下半连续函数,定义域满足 dom h ⊂ dom g \text{dom}h\subset\text{dom}g domhdomg,
g g g C C C上连续可微;

(4) ( h , g ) (h,g) (h,g)满足 L-smad 条件;

(5) v ( P ) = inf ⁡ { Ψ ( x ) : x ∈ C ‾ } > − ∞ v(\mathcal{P})=\inf\{\Psi(x):x\in\overline{C}\}>-\infty v(P)=inf{Ψ(x):xC}>.

基于以上假设,我们可以利用函数 h h h,构造求解问题 P \mathcal{P} P的 BPG 算法如下:
优化|一阶方法:求解不具有凸性和lipschitz连续性的复合问题,人工智能,算法

不妨记 T λ ( x ) : = arg min ⁡ u ∈ R d { f ( u ) + < ∇ g ( x ) , u − x > + 1 λ D h ( u , x ) } T_{\lambda}(x):=\argmin\limits_{u\in\mathbb{R}^d}\left\{f(u)+\left<\nabla{g}(x),u-x\right>+\frac{1}{\lambda}D_h(u,x)\right\} Tλ(x):=uRdargmin{f(u)+g(x),ux+λ1Dh(u,x)}

为了保证算法中的 (3.4) 式能够顺利求解,我们需要添加如下假设:

假设2.2 对任意的 λ > 0 \lambda>0 λ>0,都有 lim ⁡ ∥ u ∥ → ∞ h ( u ) + λ f ( u ) ∥ u ∥ = + ∞ . \lim\limits_{\|u\|\to\infty}\frac{h(u)+\lambda{f}(u)}{\|u\|}=+\infty. ulimuh(u)+λf(u)=+∞.

假设2.3 对任意的 x ∈ C x\in{C} xC,都有 T λ ( x ) ⊂ C T_{\lambda}(x)\sub{C} Tλ(x)C.

这两条假设都是易于实现的 [ 1 ] ^{[1]} [1]. 可以证明,在假设2.1—2.3之下,对任意的 x ∈ intdom h x\in\text{intdom}h xintdomh x ∈ intdom h x\in\text{intdom}h xintdomh, T λ ( x ) T_{\lambda}(x) Tλ(x) C C C的非空紧子集。此时,我们认为求解 (3.4) 这一步确实是可行的。

2.2 充分下降性质

在假设2.1—2.3之下,可证明算法具有充分下降性质:

引理2.1 对于任意 x ∈ intdom h x\in\text{intdom}h xintdomh λ > 0 \lambda>0 λ>0以及 x + ∈ T λ ( x ) x^{+}\in{T}_{\lambda}(x) x+Tλ(x), 都有不等式 λ Ψ ( x + ) ≤ λ Ψ ( x ) − ( 1 − λ L ) D h ( x + , x ) . \begin{equation}\nonumber \lambda\Psi(x^{+})\leq\lambda\Psi(x)-(1-\lambda{L})D_h(x^{+},x). \end{equation} λΨ(x+)λΨ(x)(1λL)Dh(x+,x).

h h h的凸性可知 D h D_h Dh是非负函数。结合引理2.1,可得如下定理:

定理2.1 如果假设2.1—2.3成立, 0 < λ L < 1 0<\lambda{L}<1 0<λL<1, { x k } \{x^k\} {xk}是 BPG 算法生成的序列,则有以下结论:

(1) 序列 { Ψ ( x k ) } \{\Psi(x^k)\} {Ψ(xk)}单调不增;

(2) ∑ k = 0 + ∞ D h ( x k , x k − 1 ) < ∞ \sum_{k=0}^{+\infty}D_h(x^{k},x^{k-1})<\infty k=0+Dh(xk,xk1)<, 因此有 D h ( x k , x k − 1 ) → 0 ( k → ∞ ) D_h(x^{k},x^{k-1})\to0 (k\to\infty) Dh(xk,xk1)0(k).

(3) min ⁡ 1 ≤ k ≤ n D h ( x k , x k − 1 ) ≤ λ n ( Ψ ( x 0 ) − Ψ ∗ 1 − λ L ) \min_{1\leq{k}\leq{n}}D_h(x^k,x^{k-1})\leq\frac{\lambda}{n}(\frac{\Psi(x^{0})-\Psi_{*}}{1-\lambda{L}}) min1knDh(xk,xk1)nλ(1λLΨ(x0)Ψ),其中 Ψ ∗ = v ( P ) > − ∞ \Psi_{*}=v(\mathcal{P})>-\infty Ψ=v(P)>.

实际上我们不难看出,如果函数 h h h满足假设2.1—2.3,那么 h + σ 2 ∥ ⋅ ∥ 2 h + \frac{\sigma}{2}\|\cdot\|^{2} h+2σ2一定也满足假设,其中 σ > 0 \sigma>0 σ>0. 因此不妨设 h h h是强凸函数,对应的强凸系数为 σ \sigma σ. 此时定理2.1中的 (3) 可推出 min ⁡ 1 ≤ k ≤ n ∥ x k − x k − 1 ∥ 2 ≤ λ n Ψ ( x 0 ) − Ψ ∗ σ ( 1 − λ L ) \min_{1\leq{k}\leq{n}}\|x^k-x^{k-1}\|^{2}\leq\frac{\lambda}{n}\frac{\Psi(x^{0})-\Psi_{*}}{\sigma(1-\lambda{L})} min1knxkxk12nλσ(1λL)Ψ(x0)Ψ.

2.3 收敛速度

为了证明算法的全局收敛性,本节我们设 C = R d C=\mathbb{R}^d C=Rd, 并添加了如下假设:

假设2.4 (1) dom h = R d \text{dom}h=\mathbb{R}^d domh=Rd, 且 h h h R d \mathbb{R}^d Rd上是 σ − \sigma- σ强凸的;

(2) ∇ h \nabla{h} h ∇ g \nabla{g} g R d \mathbb{R}^d Rd上都是局部 Lipschitz 连续的。

在假设2.1—2.4之下,可证明算法生成的序列 { x k } \{x^k\} {xk}是极小化 Ψ \Psi Ψ的一个类梯度下降序列。其定义如下:

定义1.3 F : R d → ( − ∞ , + ∞ ] F:\mathbb{R}^d\to(-\infty,+\infty] F:Rd(,+]是适当的下半连续函数。我们称 { x k } \{x^k\} {xk}是极小化 F F F的一个类梯度下降序列,当且仅当以下三个条件成立:

(1) 存在 ρ 1 > 0 \rho_1>0 ρ1>0, 使得 ρ 1 ∥ x k − x k − 1 ∥ 2 ≤ F ( x k ) − F ( x k − 1 ) \rho_1\|x^k-x^{k-1}\|^2\leq{F}(x ^k)-F(x^{k-1}) ρ1xkxk12F(xk)F(xk1)对所有 k k k成立;

(2) 存在 ρ 2 > 0 \rho_2>0 ρ2>0,使得对任意的 k k k都存在 ω k + 1 ∈ ∂ F ( x k + 1 ) \omega^{k+1}\in\partial{F}(x^{k+1}) ωk+1F(xk+1) ,
满足 ∥ ρ k + 1 ∥ ≤ ρ 2 ∥ x k + 1 − x k ∥ \|\rho_{k+1}\|\leq\rho_2\|x^{k+1}-x^k\| ρk+1ρ2xk+1xk

(3) 对于 { x k } \{x^k\} {xk}的聚点 x ˉ \bar{x} xˉ,
不妨设 lim ⁡ k → ∞ , k ∈ K x k = x ˉ \lim\limits_{k\to\infty,k\in\mathcal{K}}x^k=\bar{x} k,kKlimxk=xˉ.
此时有 lim sup ⁡ k → ∞ , k ∈ K F ( x k ) ≤ F ( x ˉ ) \limsup_{k\to\infty,k\in\mathcal{K}}F(x^k)\leq{F}(\bar{x}) limsupk,kKF(xk)F(xˉ).

利用类梯度下降序列的性质,我们可以证明算法的全局收敛性。记 Ψ \Psi Ψ的稳定点集合为 crit Ψ = { x ∈ R d : 0 ∈ ∂ Ψ ( x ) = ∂ f ( x ) + ∇ g ( x ) } , \begin{equation}\nonumber \text{crit}\Psi=\{x\in\mathbb{R}^d:0\in\partial\Psi(x)=\partial{f}(x)+\nabla{g}(x)\}, \end{equation} critΨ={xRd:0Ψ(x)=f(x)+g(x)},

序列 { x k } \{x^k\} {xk}所有聚点构成的集合为 ω ( x 0 ) \omega(x^0) ω(x0). 对于满足定义1.3的序列 { x k } \{x^k\} {xk}和对应的函数 F F F, 可证明 ω ( x 0 ) \omega(x^0) ω(x0) crit F \text{crit}F critF的非空紧子集,且 F F F ω ( x 0 ) \omega(x^0) ω(x0)中每点的取值是相同的。进一步,我们可得到如下结论:

定理2.2 如果假设2.1—2.4成立,且 0 < λ L < 1 0<\lambda{L}<1 0<λL<1, 则有:

(1) { x k } \{x^k\} {xk}任意聚点都是 Ψ \Psi Ψ的稳定点;

(2) 如果 Ψ \Psi Ψ满足 KL 性质,那么 ∑ ∥ x k + 1 − x k ∥ < ∞ \sum\|x^{k+1}-x^{k}\|<\infty xk+1xk< { x k } \{x^k\} {xk}收敛到某一个稳定点。

第三部分:数值算例

3.1 问题模型 (SQIP)

为证明算法的有效性,作者用提出的算法近似求解一个二次方程问题,问题的目标是近似寻找一个 x ∈ R d x\in \mathbb{R}^{d} xRd满足下面的一系列方程
x T A i x ≈ b i ,   i = 1 , 2 , … , m \begin{equation}\nonumber x^{T}A_{i}x \approx b_{i},~i=1,2,\ldots,m \end{equation} xTAixbi, i=1,2,,m

其中 A i ∈ R d A_{i}\in \\R^{d} AiRd是对称矩阵, b i ∈ R b_{i}\in \\R biR是包含噪声的测量值。

通常,研究的系统是欠定的,因此一般利用正则项把原始信号的一些先验信息包含进模型。正则项通常用一个函数 f f f表示,这个函数可能是非凸、非光滑、扩展值函数 (为包含约束)。当用最小平方模型来描述测量误差,那么问题能够重新描述为
(QIP)   min ⁡ { Ψ ( x ) : = 1 4 ∑ i = 1 m ( x T A i x − b i ) 2 + θ f ( x ) :   x ∈ R d } \begin{equation}\nonumber \text{(QIP)}~~\min\Big\{\Psi(x):=\frac{1}{4}\sum_{i=1}^{m}(x^{T}A_{i}x-b_{i})^{2}+\theta f(x):~x\in \\R^{d}\Big\} \end{equation} (QIP)  min{Ψ(x):=41i=1m(xTAixbi)2+θf(x): xRd}
其中 θ > 0 \theta>0 θ>0是一个惩罚参数,主要对数据的真实性和正则项 f f f之间进行平衡。
定义非凸函数 g : R d → R g:\\R^{d}\rightarrow \\R g:RdR
g ( x ) = 1 4 ∑ i = 1 m ( x T A i x − b i ) 2 . g(x)=\frac{1}{4}\sum_{i=1}^{m}(x^{T}A_{i}x-b_{i})^{2}. g(x)=41i=1m(xTAixbi)2.
函数 g g g$在 R d \R^{d} Rd是连续可微的,但是它的梯度不是全局利普希茨连续的,因此不能够采用经典的近端梯度法求解问题(QIP)。

3.2 算法求解

在这一部分,基本空间是 C ≡ R d C\equiv \R^{d} CRd,非凸函数 g : R d → R g:\R^{d}\rightarrow \R g:RdR被定义为
g ( x ) = 1 4 ∑ i = 1 m ( x T A i x − b i ) 2 . g(x)=\frac{1}{4}\sum_{i=1}^{m}(x^{T}A_{i}x-b_{i})^{2}. g(x)=41i=1m(xTAixbi)2.
对于非凸模型,我们考虑下面两种情况:

(a) 凸 l 1 l_{1} l1范数正则项,即 f : R d → R f:\R^{d}\rightarrow \R f:RdR,其中 f ( x ) = ∥ x ∥ 1 f(x)=\|x\|_{1} f(x)=x1
(b)非凸 l 0 l_{0} l0球约束。 f : R d → R f:\R^{d}\rightarrow \R f:RdR,其中 f ( x ) = δ B 0 s ( x ) f(x)=\delta_{\mathbb{B}_{0}^{s}}(x) f(x)=δB0s(x) l 0 l_{0} l0球上的指示函数,正整数 s < d s<d s<d
B 0 s = { x : ∥ x ∥ 0 ≤ s } , \mathbb{B}_{0}^{s}=\{x: \|x\|_{0}\leq s\}, B0s={x:x0s},
∥ x ∥ 0 \|x\|_{0} x0 l 0 l_0 l0范数,表示向量 x x x的非零元素个数。

为了把我们的方法应用到问题(a)和(b)中,我们首先需要选择一个合适的函数 h ∈ G ( R d ) h\in\mathcal{G}(\\R^{d}) hG(Rd)使得对于 ( g , h ) (g,h) (g,h) L-smad \textbf{L-smad} L-smad成立。这里,我们采用的 h : R d → R h:\R^{d}\rightarrow \R h:RdR
h ( x ) = 1 4 ∥ x ∥ 2 4 + 1 2 ∥ x ∥ 2 2 h(x)=\frac{1}{4}\|x\|_{2}^{4}+\frac{1}{2}\|x\|_{2}^{2} h(x)=41x24+21x22

现在,我们证明 L-smad \textbf{L-smad} L-smad成立,即存在 L > 0 L>0 L>0使得 L h − g Lh-g Lhg R d \R^{d} Rd上为凸。

引理3.1 假设 g g g h h h是上面定义的函数,那么对任意 L L L满足 L ≥ ∑ i = 1 m 3 ∥ A i ∥ 2 + ∥ A i ∥ ∣ b i ∣ , L\geq \sum_{i=1}^{m}3\|A_{i}\|^{2}+\|A_{i}\||b_{i}|, Li=1m3∥Ai2+Ai∥∣bi,
函数 L h − g Lh-g Lhg R d \R^{d} Rd上为凸函数。

为了把 2.2 2.2 2.2节的结果应用到问题(a)和(b)中,我们观察到上面的函数 h h h R d \R^{d} Rd上是 1 − 1- 1强凸,很容易看出假设 2.1 − 2.4 2.1-2.4 2.12.4是成立的。另外, g g g是实多项式函数,因此是半代数函数。函数 ∥ x ∥ 0 \|x\|_{0} x0 ∥ x ∥ 1 \|x\|_{1} x1也是半代数函数([4] 附录5)。因此,由于半代数函数的和是半代数函数,可得模型(a)和(b)的目标函数 Ψ \Psi Ψ是半代数函数,因此提出的BPG算法能够应用到模型(QIP) (a)和(b),且能够产生一个全局收敛序列收敛到 Ψ \Psi Ψ的临界点。另外,对于模型(a)和(b),全局收敛策略具有一个简明的显式迭代步,接下来会详细进行介绍。

在BPG算法中,我们需要计算Bregman近似梯度映射:
T λ ( x ) = arg ⁡ min ⁡ { f ( u ) + ⟨ ∇ g ( x ) , u − x ⟩ + 1 λ D h ( u , x ) :   u ∈ R d }    ( λ > 0 ) . T_{\lambda}(x)=\arg\min\Big\{f(u)+\langle\nabla g(x),u-x\rangle+\frac{1}{\lambda}D_{h}(u,x):~u\in \R^{d}\Big\}~~(\lambda >0). Tλ(x)=argmin{f(u)+g(x),ux+λ1Dh(u,x): uRd}  (λ>0).

对于模型 (a)和(b),我们将给出这一迭代步能够产生一个显式的解析解。

在描述之前,我们首先介绍一些简便的符号和一些余下章节将用到的著名算子。令 λ > 0 \lambda>0 λ>0并固定任意 x ∈ R d x\in \R^{d} xRd 。定义
p ≡ p λ ( x ) = λ ∇ g ( x ) − ∇ h ( x )   (为了简便,通常省略 λ 和 x ) \begin{equation}\tag{3.1} p \equiv p_{\lambda}(x)=\lambda \nabla g(x)-\nabla h(x)~~\text{(为了简便,通常省略}\lambda\text{和}x) \end{equation} ppλ(x)=λg(x)h(x)  (为了简便,通常省略λx)(3.1)

对于 ( g , h ) (g,h) (g,h),它们梯度的直接计算结果是 p λ ( x ) p_{\lambda}(x) pλ(x)。现在,忽略掉表达式 T λ T_{\lambda} Tλ中的常数项,可得
T λ ( x ) = arg ⁡ min ⁡ { λ f ( u ) + ⟨ p λ ( x ) , u ⟩ + h ( u ) :   u ∈ R d } . \begin{equation}\tag{3.2} T_{\lambda}(x)=\arg\min\Big\{\lambda f(u)+\langle p_{\lambda}(x),u\rangle+h(u):~u\in \R^{d}\Big\}. \end{equation} Tλ(x)=argmin{λf(u)+pλ(x),u+h(u): uRd}.(3.2)

接下来,我们介绍两个非常著名的算子,它们会用于计算 T λ T_{\lambda} Tλ
具有参数 τ \tau τ的软阈值算子。对任意 y ∈ R d y\in \R^{d} yRd

S τ ( y ) = arg ⁡ min ⁡ x ∈ R d { τ ∥ x ∥ 1 + 1 2 ∥ x − y ∥ 2 } = max ⁡ { ∣ y ∣ − τ , 0 } sgn ( y ) , \begin{equation}\tag{3.3} S_{\tau}(y)=\arg\min_{x\in\R^{d}}\Big\{\tau\|x\|_{1}+\frac{1}{2}\|x-y\|^{2}\Big\}=\max\{|y|-\tau,0\}\text{sgn}(y), \end{equation} Sτ(y)=argxRdmin{τx1+21xy2}=max{yτ0}sgn(y),(3.3)

其中绝对值按照分量进行计算。具有参数 τ \tau τ的硬阈值算子。对任意 y ∈ R d y\in \R^{d} yRd
H τ ( y ) = arg ⁡ min ⁡ x ∈ R d { ∥ x − y ∥ 2 :   x ∈ B 0 τ } = { y i ,    i ≤ τ , 0 ,   否则, \begin{equation}\tag{3.4} H_{\tau}(y)=\arg\min_{x\in\R^{d}}\Big\{\|x-y\|^{2}:~x\in\mathbb{B}_{0}^{\tau}\Big\}= \begin{cases} y_{i},~~i\leq \tau,\\ 0,~~\text{否则,} \end{cases} \end{equation} Hτ(y)=argxRdmin{xy2: xB0τ}={yi,  iτ,0,  否则,(3.4)

对于问题(a)和(b),我们分别建立 T λ T_{\lambda} Tλ的显式表达式。

命题3.1 ( l 1 l_{1} l1范数正则化的Bregman近似公式) 令 f = ∥ ⋅ ∥ 1 f=\|\cdot\|_{1} f=1 且对
x ∈ R d x\in\R^{d} xRd,令
v ( x ) : = S λ θ ( p λ ( x ) ) v(x):=S_{\lambda\theta}(p_{\lambda}(x)) v(x):=Sλθ(pλ(x))。那么 x + = T λ ( x ) x^{+}=T_{\lambda}(x) x+=Tλ(x)
x + = − t ∗ v ( x ) = t ∗ S λ θ ( ∇ h ( x ) − λ ∇ g ( x ) ) , x^{+}=-t^{*}v(x)=t^{*}S_{\lambda\theta}(\nabla h(x)-\lambda\nabla g(x)), x+=tv(x)=tSλθ(h(x)λg(x)), 是显示公式,其中 t ∗ t^{*} t是下面方程的唯一正实根,且具有显式公式形式。
t 3 ∥ v ( x ) ∥ 2 2 + t − 1 = 0 t^{3}\|v(x)\|_{2}^{2}+t-1=0 t3v(x)22+t1=0

接下来,我们考虑 l 0 l_{0} l0范数约束的稀疏二次逆问题。首先,我们回顾下下面的结果[5,命题4.3,79页]。

引理3.2 如果 0 ≠ a ∈ R d 0\neq a \in \R^{d} 0=aRd和正整数 s < d s<d s<d,可得 max ⁡ { ⟨ a , z ⟩ :   ∥ z ∥ 2 = 1 ,   ∥ z ∥ 0 ≤ s } = ∥ H s ( a ) ∥ 2 , \max\{\langle a,z \rangle:~\|z\|_{2}=1,~\|z\|_{0}\leq s\}=\|\mathcal{H}_{s}(a)\|_{2}, max{⟨a,z: z2=1, z0s}=Hs(a)2,
其中最优解为 z ∗ = H s ( a ) / ∥ H s ( a ) ∥ 2 z^{*}=\mathcal{H}_{s}(a)/\|\mathcal{H}_{s}(a)\|_{2} z=Hs(a)/∥Hs(a)2

命题3.2 ( l 0 l_{0} l0范数正则化的Bregman近似公式) 令 f = δ B 0 s f=\delta_{\mathbb{B}_{0}^{s}} f=δB0s x ∈ R d x\in \R^{d} xRd。那么
x + = T λ ( x ) x^{+}=T_{\lambda}(x) x+=Tλ(x)
x + = − t ∗ ∥ H s ( p λ ( x ) ) ∥ 2 − 1 H s ( p λ ( x ) ) x^{+}=-\sqrt{t^{*}}\|\mathcal{H}_{s}(p_{\lambda}(x))\|_{2}^{-1}\mathcal{H}_{s}(p_{\lambda}(x)) x+=t Hs(pλ(x))21Hs(pλ(x))
其中 t ∗ ≡ η ∗ \sqrt{t^{*}}\equiv \eta^{*} t η是下面立方方程的唯一非负实根
η 3 + η − ∥ H s ( p λ ( x ) ) ∥ 2 = 0. \begin{equation}\tag{3.5} \eta^{3}+\eta-\|\mathcal{H}_{s}(p_{\lambda}(x))\|_{2}=0. \end{equation} η3+ηHs(pλ(x))2=0.(3.5)

参考文献:
[1] Bolte, J., Sabach, S., Teboulle, M., & Vaisbourd, Y. (2018). First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal on Optimization, 28(3), 2131-2151.

[2] Bauschke, H. H., Bolte, J., & Teboulle, M. (2017). A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2), 330-348.

[3] Geiping, J., & Moeller, M. (2018). Composite optimization by nonconvex majorization-minimization. SIAM Journal on Imaging Sciences, 11(4), 2494-2528.

[4] Bolte, Jérôme, Sabach, S. , & Teboulle, M. (2014). Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1-2), 459-494.

[5] Luss, R. , & Teboulle, M. . (2012). Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint. Siam Review, 55(1), 65-98.文章来源地址https://www.toymoban.com/news/detail-531901.html

到了这里,关于优化|一阶方法:求解不具有凸性和lipschitz连续性的复合问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 优化问题解决:Hessian 矩阵与凸性函数的算法

    优化问题是计算机科学和数学中的一个重要领域,它涉及到寻找一个函数的最大值或最小值。在机器学习、数据挖掘和人工智能等领域,优化问题是非常常见的。这篇文章将讨论如何使用 Hessian 矩阵 和凸性函数来解决这些问题。 Hessian 矩阵是一种二阶微分矩阵,它用于表示一

    2024年02月22日
    浏览(45)
  • 深入探讨:Hessian 矩阵在凸性优化中的重要作用

    凸性优化是一种广泛应用于计算机科学、数学、经济学等领域的优化方法。它主要解决的问题是在一个凸函数空间中找到一个局部最小值或全局最小值。凸性优化的一个关键步骤是通过计算函数的二阶导数来确定函数在某一点的凸性或凹性。这里的二阶导数通常表示为 Hessi

    2024年02月19日
    浏览(38)
  • 如何用随机方法求解组合优化问题(二)

    组合问题由于其可能的解的数量十分庞大,无法用穷举法求解最优解。 局部搜索算法旨在减少复杂度的情况下寻找最优解,尽管其不一定能够找到全局最优解,但是往往可以找到满意的局部最优解。 类似于盲人爬山,无法看到全局的景象,但是有拐杖可以探测临近的区域。

    2024年02月13日
    浏览(43)
  • 如何用随机方法求解组合优化问题(三)

    皇后问题 : 在一个 (ntimes n) 的棋盘上,每行每列有且只有一个皇后棋子,每对角线至多一个皇后棋子。 如果使用回溯法,计算10皇后、20皇后问题还是可行的。 但是当皇后数增加到一百万个时,又该如何求解呢? 局部搜索算法用于求解组合优化问题,而皇后问题是组合问

    2024年02月13日
    浏览(40)
  • 如何用随机方法求解组合优化问题(四)

    这是一篇笔记,是对于B站up主马少平的视频(第四篇 如何用随机方法求解组合优化问题(四))的学习与记录。 这篇笔记还没有介绍到模拟退火算法,而是记录退火这一物理过程以及相关的公式。 最主要的内容是如何将退火过程的特点迁移到后续的算法设计中。 退火是固体

    2024年02月12日
    浏览(30)
  • 如何用随机方法求解组合优化问题(五)

    这是一篇笔记,是对于B站up主马少平的视频(第四篇 如何用随机方法求解组合优化问题(五))的学习与记录。 【回顾】:局部最优问题 在局部搜索问题中,可能会陷入局部最优解(如上图中的B、C),解决思路是: 以概率接受差解 。 【回顾】:退火过程中 从状态 (i)

    2024年02月12日
    浏览(39)
  • 如何用随机方法求解组合优化问题(一)

    优化问题 设 (x) 是决策变量, (D) 是 (x) 的定义域, (f(x)) 是指标函数, (g(x)) 是约束条件。则优化问题可以表示为求解满足 (g(x)) 的 (f(x)) 最小值问题。即: [min_{xin D}(f(x)|g(x))] 组合优化问题 如果在定义域 (D) 上,满足约束条件 (g(x)) 的解的总数是有限的,则优

    2024年02月13日
    浏览(34)
  • 如何用随机方法求解组合优化问题(七)

    这是一篇笔记,是对于B站up主马少平的视频(第四篇 如何用随机方法求解组合优化问题(七))的学习与记录。 一个商人要访问 (n) 个城市,每个城市访问一次,并且只能访问一次,最后再回到出发城市。 问如何规划才能使得行走的路径长度最短。 旅行商问题的解空间非

    2024年02月12日
    浏览(39)
  • 如何用随机方法求解组合优化问题(六)

    这是一篇笔记,是对于B站up主马少平的视频(第四篇 如何用随机方法求解组合优化问题(六))的学习与记录。 算法实现需要确定的参数: 初始温度 (t_0) ; 温度 (t) 的衰减函数,即温度的下降方法; 算法的终止准则,终止温度 (t_f) 或者终止条件; 每个温度 (t) 下的

    2024年02月12日
    浏览(40)
  • 机器学习笔记之最优化理论与方法(九)无约束优化问题——常用求解方法(下)

    上一节介绍了 牛顿法、拟牛顿法 。本节将继续以 拟牛顿法 为基础,介绍 DFP , BFGS text{DFP},text{BFGS} DFP , BFGS 方法 。 经典牛顿法缺陷与修正牛顿法 关于 经典牛顿法 中关于 下降方向 D k ( k = 1 , 2 , ⋯   , ∞ ) mathcal D_k(k=1,2,cdots,infty) D k ​ ( k = 1 , 2 , ⋯ , ∞ ) 的 数学符号 表

    2024年02月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包