IS CS-2018S2-05

题目来源：Problem 5 日期：2024-08-10 题目主题：CS-算法-优化与凸分析

解题思路

本题涵盖了优化与凸分析的多个概念，包括子梯度、子微分、范数及其在优化问题中的应用。主要思路是：

1. 理解子梯度与子微分的定义：子梯度在凸函数的最小化过程中扮演重要角色，通过掌握它们的性质，可以求解与此相关的最优化问题。
2. 计算具体函数的子微分：对于给定的函数形式，通过直接计算或者利用性质推导出子微分。
3. 分析优化问题中的条件：利用子梯度的定义和性质，尤其是最优性条件来推导出问题的最优解。

Solution

Question 1(a)

For $f(w)=|w|$ where $w\in \mathbb{R}$:

The function $f(w)=|w|$ is convex but non-differentiable at $w=0$. The subdifferential $\partial f(w)$ is defined as the set of all subgradients at $w$.

• Case 1: If $w>0$, then $f(w)=w$, which is differentiable and $\nabla f(w)=1$. Therefore, $\partial f(w)=\{1\}$.

• Case 2: If $w<0$, then $f(w)=-w$, which is differentiable and $\nabla f(w)=-1$. Therefore, $\partial f(w)=\{-1\}$.

• Case 3: If $w=0$, $f(w)$ is non-differentiable, and the subdifferential is the set of all values $g\in \mathbb{R}$ such that $f(z)\ge f(0)+g\cdot z$ for all $z$. This inequality simplifies to:

  $$|z|\ge g\cdot z\text{for all }z\in \mathbb{R}.$$

  By checking different cases for $z>0$ and $z<0$, we find that $g$ must satisfy $g\in [-1,1]$. Therefore, $\partial f(0)=[-1,1]$.

Thus,

$$\partial f(w)=\{\begin{array}{ll}\{1\},& \text{if }w>0,\\ \{-1\},& \text{if }w<0,\\ [-1,1],& \text{if }w=0.\end{array}$$

Question 1(b)

For $f(\mathbf{w})=\Vert \mathbf{w}\Vert$ where $\mathbf{w}\in {\mathbb{R}}^d$:

The function $f(\mathbf{w})=\Vert \mathbf{w}\Vert$ is the sum of absolute values of the components of $\mathbf{w}$, i.e.,

$$f(\mathbf{w})=\sum _{i=1}^d|w_i|.$$

The subdifferential $\partial f(\mathbf{w})$ is the Cartesian product of the subdifferentials of each $|w_i|$ (as shown in part (a)). Therefore, each element $g_i$ of the subgradient $\mathbf{g}$ corresponding to $w_i$ satisfies:

$$g_i\in \{\begin{array}{ll}\{1\},& \text{if }{w}_i>0,\\ \{-1\},& \text{if }{w}_i<0,\\ [-1,1],& \text{if }{w}_i=0.\end{array}$$

Thus, the subdifferential is:

$$\partial f(\mathbf{w})=\left\{\mathbf{g}\in {\mathbb{R}}^d\mid g_i\in \partial |w_i|\text{ for }i=1,2,\dots ,d\right\}.$$

Question 2

For $f(w)=\frac{1}{2}(w-z{)}^2+\beta |w|$ where $w,z\in \mathbb{R}$ and $0<\beta \in \mathbb{R}$:

First, differentiate $f(w)$ to find its gradient:

$$\frac{\mathrm{d}f(w)}{\mathrm{d}w}=(w-z)+\beta \cdot g_w,$$

where $g_w\in \partial |w|$ and is defined as:

$$g_w\in \{\begin{array}{ll}\{1\},& \text{if }w>0,\\ \{-1\},& \text{if }w<0,\\ [-1,1],& \text{if }w=0.\end{array}$$

The subdifferential $\partial f(w)$ is thus:

$$\partial f(w)=(w-z)+\beta \cdot \partial |w|,$$

which gives:

$$\partial f(w)=\{\begin{array}{ll}\{w-z+\beta \},& \text{if }w>0,\\ \{w-z-\beta \},& \text{if }w<0,\\ [w-z-\beta ,w-z+\beta ],& \text{if }w=0.\end{array}$$

To minimize $f(w)$, we require $0\in \partial f(w^{\ast })$. This leads to the following conditions:

• If $w^{\ast }>0$, $w^{\ast }-z+\beta =0$, so $w^{\ast }=z-\beta$.
• If $w^{\ast }<0$, $w^{\ast }-z-\beta =0$, so $w^{\ast }=z+\beta$.
• If $w^{\ast }=0$, $0\in [w^{\ast }-z-\beta ,w^{\ast }-z+\beta ]$, so $z\in [-\beta ,\beta ]$.

Therefore, the minimizing $w^{\ast }$ is:

$$w^{\ast }=\{\begin{array}{ll}z-\beta ,& \text{if }z>\beta ,\\ z+\beta ,& \text{if }z<-\beta ,\\ 0,& \text{if }|z|\le \beta .\end{array}$$

Question 3

For $f(\mathbf{w})=\frac{1}{2}\Vert \mathbf{w}-\mathbf{z}{\Vert }_2^2+\beta \Vert \mathbf{w}\Vert$ where $\mathbf{w},\mathbf{z}\in {\mathbb{R}}^d$ and $0<\beta \in \mathbb{R}$:

The function is a sum of a smooth term $\frac{1}{2}\Vert \mathbf{w}-\mathbf{z}{\Vert }_2^2$ and a non-smooth term $\beta \Vert \mathbf{w}\Vert$.

The subdifferential $\partial f(\mathbf{w})$ is:

$$\partial f(\mathbf{w})=\mathbf{w}-\mathbf{z}+\beta \cdot \partial \Vert \mathbf{w}\Vert .$$

Given that $\partial \Vert \mathbf{w}\Vert$ has been computed in Question 1(b), the subdifferential can be expressed as:

$$\partial f(\mathbf{w})=\mathbf{w}-\mathbf{z}+\beta \mathbf{g},\text{where }\mathbf{g}\in \partial \Vert \mathbf{w}\Vert .$$

To minimize $f(\mathbf{w})$, we require $0\in \partial f({\mathbf{w}}^{\ast })$, implying:

$${\mathbf{w}}^{\ast }-\mathbf{z}+\beta {\mathbf{g}}^{\ast }=0,{\mathbf{g}}^{\ast }\in \partial \Vert {\mathbf{w}}^{\ast }\Vert .$$

For each $j$, if $w_j^{\ast }=0$, the condition for minimization is:

$$-z_j\in [-\beta ,\beta ].$$

Thus, the necessary and sufficient condition for $w_j^{\ast }=0$ is:

$$|z_j|\le \beta .$$

Question 4

Given the optimization problem at each iteration:

$${\mathbf{w}}^{(t+1)}=\underset{\mathbf{w}\in {\mathbb{R}}^d}{\mathrm{argmin}}\left\{\nabla L({\mathbf{w}}^{(t)}{)}^{\top }(\mathbf{w}-{\mathbf{w}}^{(t)})+\lambda \Vert \mathbf{w}{\Vert }_1+\frac{1}{2{\eta }_t}\Vert \mathbf{w}-{\mathbf{w}}^{(t)}{\Vert }_2^2\right\},$$

we seek to express $a\in \mathbb{R}$ such that $w_j^{(t)}-{\eta }_t\frac{\partial L}{\partial w_j}({\mathbf{w}}^{(t)})\in [-a,a]$ is necessary and sufficient for $w_j^{(t+1)}=0$.

Using the KKT (Karush-Kuhn-Tucker) conditions, we require:

$$0\in {\eta }_t\nabla L({\mathbf{w}}^{(t)}{)}_j+\lambda \partial |w_j^{(t+1)}|+w_j^{(t+1)}-w_j^{(t)},$$

where $\partial |w_j^{(t+1)}|$ is $[-1,1]$ when $w_j^{(t+1)}=0$.

This simplifies to:

$$-\lambda \le w_j^{(t)}-{\eta }_t\nabla L({\mathbf{w}}^{(t)}{)}_j\le \lambda .$$

Thus, the necessary and sufficient condition for $w_j^{(t+1)}=0$ is:

$$|w_j^{(t)}-{\eta }_t\nabla L({\mathbf{w}}^{(t)}{)}_j|\le \lambda {\eta }_t.$$

Therefore, $a=\lambda {\eta }_t$.

知识点

子梯度子微分凸优化L1范数L2范数最优性条件

解题技巧和信息

• 子梯度的计算：当函数不可微时，子梯度提供了非平滑优化中寻找最优解的工具。理解和使用子微分集合是解决非平滑优化问题的关键。
• L1 正则化的作用：在优化问题中加入 L1 范数有助于获得稀疏解，即许多解分量为零，这在特征选择中尤为重要。
• KKT 条件的应用：在含有约束的优化问题中，KKT 条件可以帮助确定解的结构，例如稀疏性条件。

重点词汇

• Subgradient 子梯度
• Subdifferential 子微分
• Convex function 凸函数
• L1 norm L1 范数
• Optimality condition 最优性条件
• Karush-Kuhn-Tucker conditions (KKT conditions) 卡鲁什-库恩-塔克条件

参考资料

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. - Chapter 3 and Chapter 5 for subgradient and subdifferential.
2. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. Springer Science & Business Media. - Chapter 14 for optimization algorithms with nonsmooth functions.