非凸优化收敛性证明框架

标签：非凸 phi right frac Vert 框架 收敛性 leq left

\chapter{非凸优化}

\section{非凸优化中的重要概念}
\subsection{次微分}
\begin{definition}{Frechet次微分}
适当函数\(f\)，如果\(\forall x\in\) dom$f \(，则\)f\(在\)x\(处的Frechet次微分记为\)\overset{- }{\partial} f(x)$，它的定义是：
$$\overset{- }{\partial} f(x)=\left\lbrace v \mid \mathop{liminf}\limits_{y\neq x\quad y\rightarrow x}\frac{1}{\Vert x-y \Vert}[f(y)-f(x)-\langle v,y-x \rangle]\geq 0\right\rbrace $$
\end{definition}

\begin{note}
如果\(x\notin\) dom$f \(，定义\)\overset{- }{\partial} f(x)=\emptyset$
\end{note}

\begin{definition}{极限次微分}
适当函数\(f\)，如果\(\forall x\in\) dom$f \(，则\)f\(在\)x\(处的极限次微分记为\) \partial f(x)$，它的定义是：
$$\partial f(x)={v \in \mathbb{R}^n \mid \exists x^k \rightarrow x ,f(x^k)\rightarrow f(x),v^k\in \overset{- }{\partial} f(x^k)\rightarrow v}$$
\end{definition}
\begin{note}
\(\partial f(x)\)是一个闭集。
\end{note}
\begin{definition}{稳定点}
如果\(x\in\) dom$f $，满足\(0\in\partial f(x)\)，则称\(x\)为函数\(f\)的稳定点。
\end{definition}
\begin{theorem}{一阶最优性必要非充分条件}
如果\(x\in\) dom$f \(是函数的\)f\(的一个局部极小点，则\)x\(一定是函数\)f$的稳定点，即:
$$0\in\partial f(x)$$
\end{theorem}

\subsection{KL不等式}
\begin{definition}
\(f:\mathbb{R}^n\rightarrow \mathbb{R}\bigcup \{+\infty\}\)是一个适当下半连续函数，对于\(\eta_1,\eta_2:-\infty< \eta_1<\eta_2<+\infty\)，定义：
$$[\eta_1<f<\eta_2]=\left\lbrace x\in \mathbb{R}^n \mid \eta_1<f(x)<\eta_2\right\rbrace $$
\end{definition}

\begin{definition}{KL性质}
\(f:\mathbb{R}^n\rightarrow \mathbb{R}\bigcup \{+\infty\}\)，\(x^*\in\) dom \(\partial f\) ,如果\(\exists \eta \in (0,+\infty]\)，\(x^*\)的领域\(U\)，以及连续凹函数\(\phi :[0,\eta)\rightarrow \mathbb{R}_+\)，满足：
\begin{itemize}
\item \(\phi(0)=0\)
\item \(\phi \in C^1\)
\item \(\phi^,(s)>0,\forall s \in (0,\eta)\)
\item \(\forall x\in U \bigcap [f(x^*)<f<f(x^*)+\eta]\)，KL不等式成立：
$$\phi^{\prime(f(x)-f(x}*))dist(0,\partial f(x))\geq 1$$
\end{itemize}
则称\(f\)在\(x^*\)满足KL性质。\
进一步，如果$\forall x\in $dom \(\partial f\) 都满足KL性质，则称\(f\)是KL函数。

\end{definition}

\subsection{基本假设}
设\(f:\mathbb{R}^n\rightarrow \mathbb{R}\bigcup \{+\infty\}\)是一个适当下半连续函数，\(\{x^k\}\)是由有个算法产生的迭代点列。
\begin{assumption}{H1:充分下降假设:}
\(\forall k \in \mathbb{N}\)，$$f(x^{k+1})+a\Vert x^{k+1}-xk \Vert^2 \leq f(x^k)$$
\end{assumption}

\begin{assumption}{H2:相对误差条件:}
\(\forall k \in \mathbb{N}\)，\(\exists w \in \partial f(x^{k+1})\),满足
$$\Vert w^{k+1}\Vert \leq b\Vert x^{k+1}-xk \Vert$$
\end{assumption}

\begin{assumption}{H3:连续条件:}
存在\(\{x_k\}\)的子列\(\{x^{k_j}\}\)和\(\overset{~}{x}\)满足：
$$x^{k_j}\rightarrow \overset{~}{x},f(x^{k_j})\rightarrow f(\overset{~}{x}),\quad(j\rightarrow \infty)$$
\end{assumption}

\section{非凸优化收敛性的证明框架}

\begin{lemma}
设\(f:\mathbb{R}^n\rightarrow \mathbb{R}\bigcup \{+\infty\}\)是一个适当下半连续函数，且在\(x^*\)处满足KL性质，用\(U,\eta,\phi:[0,\eta)\rightarrow \mathbb{R}_+\)来表示KL性质定义里面的相关概念，又设\(\delta,\rho>0\)满足\(B(x^*,\delta)\subset U,\rho \in (0,\delta)\)\
考虑一列满足H1，H2假设的点列\(\{x^k\}\)，并进一步假设:
\begin{enumerate}[(1)]
\item \(f(x^*)\leq f(x^0)\leq f(x^*)+\eta\)
\item $\Vert x^*-x0 \Vert +2\sqrt{\frac{f(x^0)-f(x)}{a}}+\frac{b}{a}\phi\left( f(x^0)-f(x)\right) <\rho $
\item \(\forall k\in \mathbb{N},x^k\in B(x^*,\rho ) \Rightarrow x^{k+1} \in B(x^*,\delta),f(x^{k+1})\geq f(x^*)\)
\end{enumerate}
则点列\(\{x^k\}\)满足：
\begin{center}
\(\forall k\in \mathbb{N},x^k\in B(x^*,\rho )\)\
\(\sum\limits_{k=0}^{+\infty}\Vert x^{k+1}-x^k \Vert < +\infty\)\
\(f(x^k)\rightarrow f(x^*),k\rightarrow \infty\)
\end{center}
且点列收敛到\(\overset{-}{x}\in B(x^*,\delta)\)且满足\(f\left( \overset{-}{x}\right) \leq f(x^*)\).\
如果点列\(\{x^k\}\)还满足H3，则\(\overset{-}{x}\)是函数\(f\)的稳定点，且\(f\left( \overset{-}{x}\right) = f(x^*)\).
\end{lemma}

\begin{proof}
初看这个引理，会感觉新加的假设(1)(2)(3)十分奇怪，其实这是根据证明过程为了得到结论而添加的假设，而这三个假设只和初始点\(x^0\)有关。\
首先，第一个假设和第三个假设是一定需要的，这是因为为了用到KL性质。\
我们先来看第二个结论，即：

\[\sum\limits_{k=0}^{+\infty}\Vert x^{k+1}-x^k \Vert < +\infty \]

也就是要证明$$\exists M \in \mathbb{R}+,\forall j \geq 0,\sum\limits^{j}\Vert x^{i+1}-xi \Vert \leq M$$
我们可以想到数学归纳法，即如果$$\sum\limits_{i=0}^{j}\Vert x^{i+1}-xi \Vert < M$$
想要通过下面的方式证明:$$\sum\limits_{i=0}^{j+1}\Vert x^{i+1}-xi \Vert =\sum\limits_{i=0}^{j}\Vert x^{i+1}-xi \Vert+\Vert x^{j+2}-x \Vert\leq M+\Vert x^{j+2}-x \Vert \leq M$$
但是显然这不可能得到证明的，我们不妨换一种思路，我们可以找到一种有关\(j\)的大于0的数列\(\{M_j\}\)，满足：

\[\sum\limits_{i=0}^{j}\Vert x^{i+1}-x^i \Vert \leq M-M_j\leq M \]

当对\(j+1\)进行分析时，就要证明$$\sum\limits_{i=0}^{j+1}\Vert x^{i+1}-xi \Vert =\sum\limits_{i=0}^{j}\Vert x^{i+1}-xi \Vert+\Vert x^{j+2}-x \Vert \leq M-M_j+\Vert x^{j+2}-x \Vert \leq M-M_{j+1} $$

\[\Rightarrow \Vert x^{j+2}-x^{j+1} \Vert \leq M_j-M_{j+1} \]

因此，我们需要找到满足上述不等式的数列\(\{M_j\}\)
而对于满足前提假设的点列\(\{x^k\}\)有这样的不等式(最后再证明这个不等式)：

\[2\Vert x^{k+1}-x^k \Vert\leq \Vert x^k-x^{k-1}\Vert+\frac{b}{a}\left[ \phi\left( f(x^k)-f(x^*)\right) - \phi\left( f(x^{k+1})-f(x^*)\right) \right] \]

只要令\(k=j+1\)再移项就有：

\[\Vert x^{j+2}-x^{j+1} \Vert \leq \left[ \Vert x^{j+1}-x^j \Vert -\frac{b}{a}\left[ \phi\left( f(x^{j+1})-f(x^*)\right)\right] \right] - \left[ \Vert x^{j+2}-x^{j+1} \Vert -\frac{b}{a}\left[ \phi\left( f(x^{j+2})-f(x^*)\right)\right]\right] \]

显然我们只需要设\(M_j=\left[ \Vert x^{j+1}-x^j \Vert -\frac{b}{a}\left[ \phi\left( f(x^{j+1})-f(x^*)\right)\right] \right]\)即可。
现在数学归纳法还差第一步，就是需要\(j=0\)时满足$$\sum\limits_{i=0}^{0}\Vert x^{i+1}-xi \Vert \leq M-M_0\leq M$$
也就是：$$\Vert x^1-x0 \Vert \leq M-M_0=M- \left[ \Vert x^1-x0 \Vert -\frac{b}{a}\left[ \phi\left( f(x^1)-f(x*)\right)\right] \right]$$

\[\Rightarrow M \geq 2\Vert x^1-x^0 \Vert+\frac{b}{a}\left[ \phi\left( f(x^1)-f(x^*)\right)\right] \]

为了得到证明，直接取\(M=2\Vert x^1-x^0 \Vert+\frac{b}{a}\left[ \phi\left( f(x^1)-f(x^*)\right)\right]\)，于是有数学归纳法得到:

\[\forall j \geq 0,\sum\limits_{i=0}^{j}\Vert x^{k+1}-x^k \Vert \leq M=2\Vert x^1-x^0 \Vert+\frac{b}{a}\left[ \phi\left( f(x^1)-f(x^*)\right)\right]< +\infty \]

下面我们证明第一个结论：$$\forall k\in \mathbb{N},x^k\in B(x^,\rho )$$
根据三角不等式我们有：
\begin{align}
\Vert x^{j+1}-x* \Vert & \leq \Vert x^0-x* \Vert+\sum\limits_{i=0}^{j}\Vert x^{i+1}-xi \Vert\
& \leq \Vert x^0-x* \Vert+2\Vert x^1-x0 \Vert+\frac{b}{a}\left[ \phi\left( f(x^1)-f(x)\right)\right]
\end{align}
我们只要取初始点\(x^0\)使得上式右端小于\(\rho\)即可，但是上式右端存在\(x^1\)，我们需要将这里的右端继续放大，使其只与\(x^0\)有关。根据H1，有$$\Vert x^1-x0 \Vert\leq \sqrt{\frac{f(x^0)-f(x)}{a}}\leq \sqrt{\frac{f(x^0)-f(x)}{a}}$$
第二个不等式用到了关系\(f(x^*)\leq f(x^1)\leq f(x^0)\).
再根据KL性质中的\(\phi^\prime \geq 0\)，得到$$\phi\left( f(x^1)-f(x)\right)\leq \phi\left( f(x^0)-f(x)\right)$$
于是：
\begin{align}
\Vert x^{j+1}-x \Vert & \leq \Vert x^0-x* \Vert+2\Vert x^1-x0 \Vert+\frac{b}{a} \phi\left( f(x^1)-f(x)\right)\
& \leq \Vert x^0-x \Vert+2\sqrt{\frac{f(x^0)-f(x)}{a}}+\frac{b}{a} \phi\left( f(x^0)-f(x)\right)
\end{align*}
因此这就需要第二个假设：\(\Vert x^0-x^* \Vert+2\sqrt{\frac{f(x^0)-f(x^*)}{a}}+\frac{b}{a} \phi\left( f(x^0)-f(x^*)\right) \leq \rho\)，就得到了第一个结论。

由第二个结论和柯西收敛原理我们得到点列\(\{x^k\}\)收敛，假设\(x^k\rightarrow \overset{-}{x}\in B(x^*,\delta)\)，又根据单调有界定理，得到\(\{f(x^k)\}\)一定收敛，假设\(f(x^k)\rightarrow \beta\)。\
根据KL不等式得到$$\phi^{\prime(\beta-f(x}))\Vert w^k \Vert\geq 1$$
而\(w^k\rightarrow 0\)，则得到\(\beta= f(x^*)\)，再有下半连续得到$f\left( \overset{-}{x}\right)\leq f(x^) $

如果还满足H3，则有$$f(x^*)=f\left( \overset{-}{x}\right)=\lim\limits_{k\rightarrow +\infty}f(x^k)$$

\[x^k\rightarrow \overset{-}{x},w^k\rightarrow 0 \]

于是得到\(0\in \partial f\left( \overset{-}{x}\right)\)，则\(\overset{-}{x}\)是稳定点。

最后我们来证明上述分析中用到的:$$2\Vert x^{k+1}-xk \Vert\leq \Vert x^k-x\Vert+\frac{b}{a}\left[ \phi\left( f(x^k)-f(x)\right) - \phi\left( f(x^{k+1})-f(x)\right) \right] $$
事实上，如果\(x^{k+1}=x^k\)，结论一定成立。如果\(x^{k+1}\neq x^k\)，则根据假设$f(x^k) >f(x^{k-1})\geq f(x^*) $则由KL不等式，有：

\[\phi^\prime(f(x^k)-f(x^*))\Vert w^k \Vert\geq 1 \]

再根据H2，有：

\[\phi^\prime(f(x^k)-f(x^*))\geq\frac{1}{\Vert w^k \Vert}\geq\frac{1}{b\Vert x^k-x^{k-1} \Vert} \]

有根据\(\phi ^\prime>0\)，H1并利用拉格朗日中值定理得到：
\begin{align}
\phi(f(x^k)-f(x))-\phi(f(x^{k+1})-f(x)) &\geq \phi ^\prime(f(xk)-f(x^*))(f(xk)-f(x^{k+1}))\
&\phi ^\prime(f(xk)-f(x^))a\Vert x^{k+1}-xk \Vert ^2
\end{align*}
将上面两个结论相结合得到：

\[\frac{b}{a}\left[ \phi(f(x^k)-f(x^*))-\phi(f(x^{k+1})-f(x^*)) \right] \geq \frac{\Vert x^{k+1}-x^k \Vert ^2}{\Vert x^k-x^{k-1} \Vert} \]

两边加上\(\Vert x^k-x^{k-1} \Vert\)，再根据基本不等式得到：

\[2\Vert x^{k+1}-x^k \Vert\leq \Vert x^k-x^{k-1}\Vert+\frac{b}{a} \phi\left( f(x^k)-f(x^*)\right) - \phi\left( f(x^{k+1})-f(x^*)\right) \]

\end{proof}

标签：非凸,phi,right,frac,Vert,框架,收敛性,leq,left
From： https://www.cnblogs.com/wjma2719/p/18214342