Subgradient Based Optimization Method

@(Numerical Optimization)[Subgradient]

$Subgradient \; Based \; Optimization \; Method$

对于凸优化问题来说，目标函数可以分为可导或者不可导两种情况。对于目标函数可导的情况，在优化的过程中可以使用$Gradients$信息，构建局部逼近，然后完成目标函数的优化。但是对于不可导情况，导数无法获得，需要使用其他的方法来完成目标函数的优化。
$Subgradient$方法就是多种方法种的一个。下面首先介绍$Subgradient$的定义，然后给出对于不同情况的计算方法。在了解这些之后，我们将看到在$Subgradient$的定义下，如何修正原有的优化条件。之后会介绍如何使用$Subgradient$方法来处理无约束和有约束问题，即如何确定步长和收敛判断。最后会给出使用$Subgradient$的其他方法。

$Subgradient\;的定义$

$Subgradient$可以看做是对$Gradient$的一个扩展，在可导的凸函数上有下面的不等式：

$$\begin{equation} f(y) \ge f(x) + \nabla f(x) ^ T (y-x) \; ( \forall \; y \in \; Domain \; ) \end{equation}$$
从这个不等式可以知道，凸函数在任意一点都可以获得整个函数的下界。类似于这个公式，可以定义如下的不等式：
$$f(y) \ge f(x) + \mu ^ T \; (y-x) \; ( \forall \; y \in \; Domain \; )$$
所有满足这个不等式的$\; \mu \;$都称为函数$f(x)$的$\; Subgradient \;$。从这个定义可以看出，$Subgradient$是对$Gradient$的扩展，目的仍然是要找到整个凸函数的下界估计。
类似的还有另外一个不等式：
$$f(y) \le f(x) + g ^T (y-x) \; (\forall \; y \in Domain)$$
满足这个定义的向量$g$称为$Supergradient$。

$Subgradient \; Calculus \; and \; Calculation$

$Subdifferential\;$的定义

在给出$Subgradient$的定义后可以看到，满足这个条件的向量$\mu$可能有很多，因此给出如下的定义：

$$\partial f(x) \; = \; \{ \; \mu \; | \; f(y) \ge f(x) + \mu ^ T (y-x) \quad \forall y \in Domain \; \}$$
这个定义给出所有满足$Subgradient$定义的向量$\mu$的集合，称为$Subdifferential$，用符号$\partial f(x)$表示这个集合。
对于可导的凸函数而言，$Subdifferential$中只包括一个元素，那就是$Gradient$；另外如果某个函数的$Sbudifferential$只包含一个元素，首先这个函数可导，其他这个元素必然是函数的$Gradient$。这个就是可导函数的$Subdifferential$。
但是对于不可导的凸函数而言，$Subdifferential$中必然不为空。

Subgradient计算样例

以$|x|$为例，给出$Subgradient$的计算方法。函数$|x|$在0处不可导，对于大于0的情况，其$Subgradient$为1，对于小于0的情况，其$Subgradient$为-1，在0这点，其$Subgradient$可以是任意一个介于-1和+1之间的值。
因为对于不可导的函数来说，一般是在某个点上不可导，而且在这个点的左右都会是可导的，在函数点可导的情况下，其$Subgradient$就是导数本身，因此在这个不可导点的$Subgradient$是任意的介于相邻导数的向量。

Weak and Strong Subgradient Calculus

对于不可导凸函数的某些点来说，其$Subdifferential$中可能包括多个元素，对于所有这些$Subgradient$是否要全部计算，可以分出$Weak \; Subgradient \; Calculus$和$Strong \; Subgradient \; Calculus$。
对于$Weak \; Subgradient \; Calculus$来说，只需要计算出$Subdifferential$种的任意一个元素即可。对于$Strong \; Subgradient \; Calculus$，则需要给出所有的$Subgradient$。
很明显$Strong \; Subgradient \; Calculus$有这很高的复杂度，因为需要给出所有可能的$Subgradient$。但是在实际中并不需要这么做，使用$Strong \; Subgradient \; Calculus$只是用于最优条件的证明。在实际中，仅需要使用$Weak \; Subgradient \; Calculus$即可。

Subgradient的计算方法

$Subgradient$的定义仅给出了定义，实际中需要优化的目标函数可能有各种形式，下面给出对应的计算方法，这里给出的都是$Subdifferential$的计算方法。

基本规则

Scaling ： $\partial(\alpha \; f) = \alpha \; \partial f$
Addition : $\partial(f_1 + f_2) = \partial f_1 + \partial f_2$
Affine Transformaton：if $g(x) = f(A x + b)$, then $\partial g(x) = A ^ T \; \partial f(Ax + b)$
这些都是比较简单且实用的计算规则

Finite Pointwise Maximum

函数具有如下的形式：

$$f = \max_{i=1,2,...,m} \; f_i(x)$$
这里函数$\; f \;$是在同一个点上m个函数的最大值。
$Subgradient$的计算方式如下：
首先计算出当前点$\; f \;$的值$\; f_{max}$，然后可以找到所有函数值等于$\; f_{max} \;$的函数，那么$\; f \;$的$Subdifferential$等于所有这些函数$Subgradient$的Convex Hull。对应的数学定义如下：
$$\partial f(x) = Co \bigcup \{ \partial f_i(x) \; | \; f_i(x) = f(x) \}$$
这里给出的是$\; Strong \; Subgradient \; Calculus$
对于$\; Weak \; Subgradient \; Calculus$ 来说，只要选择任意一个取得最大值的函数$f_i(x)$，计算$f_i(x)$ 对应的一个 $Subgradient$就可以了。

Pointwise Supremum

函数定义如下：

$$f(x) = \sup_{ \alpha \; \in \; \Theta } \; f(x, \alpha)$$
对于任意一个$\; \alpha \;$来说，函数$f(x, \alpha)$都是凸函数。
那么$\partial f(x)$是所有取的上确界函数的$Subgradient$的Convex Hull。表示如下：
$\partial f(x) = Co \bigcup \{ \partial f(x, \beta) \; | \; f(x, \beta) = f(x) \}$
这里给出的是$\; Strong \; Subgradient \; Calculus$
$Weak \; Subgradient \; Calculus$的计算类似于Finite Pointwise Maximum。

Expection

如果要优化的函数如下：
$f(x) = E \; f(x, w)$，其中$f(x, w)$ 是$x$的凸函数，$w$ 是一个随机变量。对应的$Subdifferential$计算方法是，对每一个$w$，计算出函数$f(x, w)$的 $Subgradient$，然后给出期望就可以 $\partial f(x) = E \; g(w)$，可以看出使用的是$\; Weak \; Subgradient \; Calculus$。

基于Subgradient的优化条件

无约束的最优化条件

类似于导数的情况，对于$Subgradient$来说，满足如下条件即可：
$0 \in \partial f(x)$
但是在实际中很难使用这个作为终止条件，因为这需要得到全部的$Subgradient$。

KKT条件

需要优化这样的问题

$$argmin_x \; f_0(x)$$
$$s.t. \; f_i(x) \le 0 \quad (i=1, 2, ..., m)$$
对应的KKT条件如下：(假设$x ^ *$和$\lambda ^ *$分别是最优的Primal Variable和Dual Variable。
$$f_i(x ^ * ) \le 0$$
$$\lambda ^ * \succeq 0$$
$$0 \; \in \partial f_0(x ^ *) + \sum_{i=1} ^ {i=m} { \lambda^*_i \partial f_i(x ^ *)}$$
$$\lambda_i^* f_i(x ^ *) = 0 \; (i=1, 2, ..., m)$$
可以看出这个KKT条件只是对原来的一个泛化。

如何使用Subgradient

对于一个可导的凸函数，$- \nabla f(x)$ 方向可以减小函数值$f(x)$，但是对于$Subgradient$来说，这并不成立。事实上$- \partial f(x)$方向可以减小当前点与最优点$x ^ *$的距离。

Subgradient Optimization

$Subgradient$优化非常的简单，使用如下的迭代公式：

$$x_{k+1} = x_k - \alpha_k g$$
$$g \in \; \partial f(x)$$

步长的选择

对于$Subgradient$方法来说步长很重要，可以使用固定大小的步长$\; \alpha_k = \beta$，固定长度的步长$\; \alpha_k = \lambda / \| g(x_k) \| ^ 2 _2$，但是这两种步长不能取到最优值，仅仅会收敛到最优值附近的一个区间。
使用满足下面要求的步长，可以收敛到最优点：

$$\sum_{i=1} ^ { \infty } { \alpha_i ^ 2 } \lt \infty \quad \quad \sum_{i=1} ^ { \infty } { \alpha_i } = \infty \quad (1)$$
$$\lim_{k -> \infty} \alpha_k = 0 \quad \sum_{i=1} ^ { \infty } = \infty \quad (2)$$
上面这两个步长，只要满足其中1个条件，即可收敛到最优点。

Polak最优步长

当我们已经知道函数的最优值以后，可以使用如下的步长：

$$\alpha_k = \frac{f(x_k) - f(x ^ *)}{\| g(x_k) \|_2 ^ 2}$$

最优步长

但是在一般情况下函数最优值是不知道的，在这种情况下使用如下的步长：

$$\alpha_k = \frac{f(x_k) - f_{best}^{k} + \rho_k}{ \| g(x_k) \|_2 ^2}$$
$$s.t. \sum_{i=1} ^ { \infty } { \rho_i ^ 2 } \lt \infty \quad \quad \sum_{i=1} ^ { \infty } { \rho_i } = \infty$$

终止条件

对于$Subgradient$方法来说，很难选择合适的终止条件。

Subgradient加速方法

如果在每一步中仅仅使用当前点的$Subgradient$，那么收敛的速度是很慢的。在一系列的加速算法中，大多使用了之前的$Subgradient$信息。

Heavy Ball Method

使用如下的迭代公式：

$$x ^ {k+1} = x ^ { k } - \alpha_k g ^ {k} + \beta_k ( x ^ {k} - x ^ {k-1} )$$

CFM Method

$$s_k = g_k + \beta_k s_{k-1} \quad \beta_k = max(0, - \gamma_k s_{k-1} ^ T g_k / \| s_{k-1} \|_2 ^ 2 )$$
一般来说这里的$\gamma_k = 1.5$

有约束的最优化

在使用Subgradient方法时，如果是无约束的最优化，那么选择步长产生方法之后可以不停的进行迭代直到收敛，但是对于有约束的最优化来说需要使用其他的方法。

Project Subgradient Method

这个方法解决如下形式的问题；

$$minimize_x f(x)$$
$$s.t. x \in C$$
在这里要求C必须是一个凸集。然后使用如下的迭代公式：
$$x_{k+1} = \prod (x - \alpha_k g_k )$$
这里$g_k$是$Subgradient$，$\prod$表示在集合C上的投影。使用这样的方法来处理又出书的最优化问题，在选择步长（2)的时候可以收敛到最优点。
基本上来说这里的集合C都是使用线性等式来描述的。

Project Subgradient for Dual

在进行凸优化时，适时的讨论Dual可以很好的解决问题。
对于如下的Primal：

$$f_0(x)$$
$$s.t. \qquad f_i(x) \le 0 \quad (i=1, 2, ..., m)$$
对应的Dual问题如下：
$$maximize \quad g(\lambda)$$
$$s.t. \qquad \lambda \succeq 0$$
相比于优化原始的问题，我们可以直接优化Dual问题。方法非常简单，使用如下的迭代公式即可：
$$\lambda_{k+1} = ( \lambda_k - \alpha_k h )_{+}$$
$$h \; \in \; \partial (-g(\lambda_k))$$
在这里要求$\lambda$必须大于0，因此需要将所有小于0的项全部替换成0.
对于Dual函数的Subgradient，可以看出
$$g(\lambda) = argmin_x f_0(x) + \sum_{i=1}^{m} { \lambda_i f_i(x) }$$
假如$x(\lambda_k)$优化上面的函数，那么Subgradient就应该如下：
$$\partial g(\lambda) = (f_1(x^*), f_2(x^*), ..., f_m(x ^ *) )$$
在这个方法中，Primal变量不一定一直满足约束条件，Dual变量肯定一直满足约束条件，但是方法收敛的时候必定都满足约束条件。

有约束优化

基本上来说Project Subgradient Method只能用来处理约束条件是线性方程的情况，对于其他的问题则不能解决。

$$f_0(x)$$
$$s.t. \qquad f_i(x) \le 0 \quad (i=1, 2, ..., m)$$
对上面这个问题使用Subgradient方法的主要困难在于计算Subgradient，计算方法如下：
1. 如果全部约束都能满足，那么Subgradient是目标函数的Subgradient
2. 如果有约束不能满足，那么Subgradient是第一个不能满足的约束函数的Subgradient。

Primal Dual subgradient Method

在这个方法中，同时优化Primal和Dual变量，直到问题收敛。
需要优化的等式约束问题如下：

$$argmin_x \; f(x)$$
$$A x = b$$
对这个问题我们优化如下的问题：
$$argmin_x \; f(x) + (\rho/2)\| Ax - b \|_2 ^ 2$$
$$A x = b$$
其中$\rho$大于0.对Primal和Dual变量求Subgradient，然后同步更新即可。
如果有不等式约束，我们将如下的问题
$$argmin_x f(x)$$
$$f_i(x) \le 0$$
转化成：
$$argmin_x f(x) + (\rho/2)\| F(x) \|_2^2$$
$$F(x) \preceq 0$$
这就是Subgradient相关的优化方法。

Written with StackEdit.