次梯度法

背景

次导数、次微分

次导数(subderivative)、次微分(subdifferential)

定义

凸函数f:I→R在点x0的次导数,是实数c使得:

对于所有I内的x。我们可以证明,在点x0的次导数的集合是一个非空闭区间[a, b],其中a和b是单侧极限

它们一定存在,且满足a ≤ b。

所有次导数的集合[a, b]称为函数f在x0的次微分。

例子

考虑凸函数f(x)=|x|。在原点的次微分是区间[−1, 1]。x0<0时,次微分是单元素集合{-1},而x0>0,则是单元素集合{1}。

次梯度法

次梯度法,就是在不可导点用次导数替代的方法。

问题,次导数往往是一个区间,如何选择次导数。

  1. random
  2. 在区间内人工选择一个

有约束最优化

一般约束问题

次梯度法可扩展到求解求解不等式约束问题

最小化 $f{0}(x) \quad f{i}(x) \leq 0,\quad i=1,\dots ,m$
其中 $f_{i}$为凸函数。该算法与无约束优化问题具有相同的形式

$x^{(k+1)}=x^{(k)}-\alpha{k}g^{(k)}$
其中 $\alpha
{k}>0}$是步长, $g^{(k)}$是目标函数或约束函数在$x$处的次梯度

其中 $\partial f$代表 $f$ 的次微分。
如果当前点为可行点,算法采用目标函数的次梯度,否则采用任一违反约束的函数的次微分。

实战

经测试,relu、绝对值函数在0点取的梯度恒为0。
因为0是

relu的次导数是[0,1]。选择0为导数,一方面方便计算,另一方面0点是最低点,不影响优化。

abs函数的次导数是[-1,1]。同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import torch
import torch.nn.functional as F

# relu
x = torch.tensor([-1.0, 0, 3], requires_grad=True)
f_relu = F.relu(x)
print(f_relu)
gradients = torch.tensor([1, 1.0, 1.0], dtype=torch.float) #
f_relu.backward(gradients)
print(x.grad)

# abs 绝对值函数
x = torch.tensor([-1.0, 0, 0.1], requires_grad=True)
f_abs = torch.abs(x)
print(f_abs)
gradients = torch.tensor([1, 1.0, 1.0], dtype=torch.float) #
f_abs.backward(gradients)
print(x.grad)


# sign 符号函数
# clip函数?

# step 阶跃函数

疑问

  1. 次导数的定义,为什么要定义全局$I$

参考

  • 张家绮 - 分布式优化