文章目录
7 连续优化(Continuous Optimization)
由于机器学习算法是在计算机上实现的，其中许多数学方程式都表示为数值优化方法。本章描述了训练机器学习模型的基本数值方法。训练机器学习模型通常归结为找到一组好的参数。“好”的概念是由目标函数或概率模型来决定的，我们将在本书的第二部分看到这些例子。给定一个目标函数，使用优化算法来寻找最佳值。（由于我们是在
R
D
\mathbb{R}^{D}
RD中考虑数据和模型，所以我们面临的优化问题是连续优化问题，而不是离散变量的组合优化问题。）
图 7.1本章相关概念的思维导图。主要有两个思想：梯度下降和凸优化。
本章介绍了连续优化的两个主要分支（如图7.1所示）：无约束优化和约束优化。我们将在本章中假设我们的目标函数是可微的（见第5章），因此我们可以在空间中的每个位置获得一个梯度来帮助我们找到最优值。一般情况下，机器学习中的大多数目标函数都是要被最小化的，即最优值就是最小值。直观上，梯度为目标函数每个点的上坡方向，而我们的目的是下坡（与梯度方向相反），希望找到最深的点。
图 7.2目标函数的例子。负梯度由箭头表示，全局最小值由蓝色虚线表示。
考虑图7.2中的函数。函数的全局最小值(global minimum)约为 x = − 4.5 x=−4.5 x=−4.5，对应函数值约为 − 47 −47 −47。因为函数是“平滑的”，所以有梯度指示我们应该向右还是向左走来接近最小值。不过要达到我们预期的结果还得假设没有其他局部最小值(全局最小值也是局部最小值)。图7.2中 x = 0.7 x=0.7 x=0.7附近就存在另一个局部最小值(local minimum)。
回想一下，我们可以通过计算函数的导数并将其置零来求解函数的所有驻点。对于
ℓ
(
x
)
=
x
4
+
7
x
3
+
5
x
2
−
17
x
+
3
\ell(x)=x^{4}+7 x^{3}+5 x^{2}-17 x+3
ℓ(x)=x4+7x3+5x2−17x+3
我们得到相应的梯度为
d
ℓ
(
x
)
d
x
=
4
x
3
+
21
x
2
+
10
x
−
17
\frac{\mathrm{d} \ell(x)}{\mathrm{d} x}=4 x^{3}+21 x^{2}+10 x-17
dxdℓ(x)=4x3+21x2+10x−17
因为这是一个三次方程，所以将它置零时，一般有三个解。在本例中，其中两个是最小值，一个是最大值（大约在
x
=
−
1.4
x=−1.4
x=−1.4）。为了检验一个驻点是最小值还是最大值，我们需要第二次求导并根据二阶导数在驻点的正负判断。在我们的例子中，二阶导数是
d
2
ℓ
(
x
)
d
x
2
=
12
x
2
+
42
x
+
10
\frac{\mathrm{d}^{2} \ell(x)}{\mathrm{d} x^{2}}=12 x^{2}+42 x+10
dx2d2ℓ(x)=12x2+42x+10
通过代入我们的估计值 x = − 4.5 , − 1.4 , 0.7 x=-4.5,-1.4,0.7 x=−4.5,−1.4,0.7，我们将观察到如预期的那样，中间点是最大值 ( d 2 ℓ ( x ) d x 2 < 0 ) \left(\frac{\mathrm{d}^{2} \ell(x)}{\mathrm{d} x^{2}}<0\right) (dx2d2ℓ(x)<0)，而其他两个固定点是最小值
对于复杂的函数，我们无法找到解析解，因此我们需要从某个值开始，然后遵循负梯度方向调整位置。比如图7.2中 x 0 = − 6 x_0=-6 x0=−6，负梯度表示我们应该向右走。但因为位置变化梯度也变化，所以我们只走一定的距离（这称为步长）。此外，如果我们从右边开始（例如 x 0 = 0 x_0=0 x0=0），负梯度会导致我们到达错误的最小值(局部最小)。图7.2说明了一个事实，即对于 x > − 1 x>-1 x>−1，负梯度指向图右侧的最小值，但该值不是全局最小的。
在第7.3节中，我们将学习一类称为凸函数的函数，它们对优化算法的起点没有依赖性。对于凸函数，局部最小值就是全局最小值。事实证明，许多机器学习目标函数的设计都是凸的，我们将在第12章看到一个例子。
到目前为止，本章的讨论是都是一维函数，我们可以可视化它的梯度、下降方向和最优值。在本章的其余部分，我们将在高维空间讨论这些概念。不幸的是，我们只能将一维的概念可视化，有些概念不能直接推广到更高的维度，因此在阅读时需要格外注意。
7.1 使用梯度下降法优化
我们现在考虑求解实值函数的最小值问题
min
x
f
(
x
)
\min _{\boldsymbol{x}} f(\boldsymbol{x})
xminf(x)
其中，
f
:
R
d
→
R
f: \mathbb{R}^{d} \rightarrow \mathbb{R}
f:Rd→R是一个目标函数。我们假设我们的函数
f
f
f是可微的，并且我们无法解析地找到其封闭解。
梯度下降法是一种一阶优化算法。为了用梯度下降法寻找函数的局部最小值，我们取与函数在当前点的梯度的一定比例的负值调整 x \boldsymbol{x} x。回想第5.1节，梯度指向最陡的上升方向。另一个直观的表现是考虑函数的等高线。梯度指向与我们希望优化的函数的等高线正交的方向。
让我们考虑多元函数。想象一个曲面（由函数
f
(
x
)
f(\boldsymbol{x})
f(x)描述），球从一个特定的位置
x
0
\boldsymbol{x}_0
x0被释放，它将沿着最陡峭的方向向下滚动。梯度下降利用了这一事实，即从
x
0
\boldsymbol{x}_0
x0向负梯度
−
(
(
∇
f
)
(
x
0
)
)
⊤
-\left((\nabla f)\left(\boldsymbol{x}_{0}\right)\right)^{\top}
−((∇f)(x0))⊤方向移动，则
f
(
x
0
)
f(\boldsymbol{x}_0)
f(x0)是下降最快的。在本书中，我们假设函数是可微的，并会在第7.4节中向读者介绍更一般的设定。那么，对于较小的步长(step-size)
γ
>
0
γ>0
γ>0使得：
x
1
=
x
0
−
γ
(
(
∇
f
)
(
x
0
)
)
⊤
\boldsymbol{x}_{1}=\boldsymbol{x}_{0}-\gamma\left((\nabla f)\left(\boldsymbol{x}_{0}\right)\right)^{\top}
x1=x0−γ((∇f)(x0))⊤
则
f
(
x
1
)
⩽
f
(
x
0
)
f\left(\boldsymbol{x}_{1}\right) \leqslant f\left(\boldsymbol{x}_{0}\right)
f(x1)⩽f(x0)。请注意，我们对梯度使用转置，否则维度将不匹配。
这允许我们定义一个简单的梯度下降算法：如果我们想找到函数
f
:
R
n
→
R
,
x
↦
f
(
x
)
f: \mathbb{R}^{n} \rightarrow\mathbb{R}, \boldsymbol{x} \mapsto f(\boldsymbol{x})
f:Rn→R,x↦f(x)的局部最优
f
(
x
∗
)
f\left(\boldsymbol{x}_{*}\right)
f(x∗)，我们可以指定待优化参数的初始值
x
0
\boldsymbol{x}_0
x0，然后根据
x
i
+
1
=
x
i
−
γ
i
(
(
∇
f
)
(
x
i
)
)
⊤
（
7.6
）
\boldsymbol{x}_{i+1}=\boldsymbol{x}_{i}-\gamma_{i}\left((\nabla f)\left(\boldsymbol{x}_{i}\right)\right)^{\top}\qquad （7.6）
xi+1=xi−γi((∇f)(xi))⊤（7.6）
调整参数。对于合适的步长 γ i \gamma_{i} γi，序列 f ( x 0 ) ⩾ f ( x 1 ) ⩾ … f\left(\boldsymbol{x}_{0}\right) \geqslant f\left(\boldsymbol{x}_{1}\right) \geqslant \ldots f(x0)⩾f(x1)⩾…能收敛到局部最小值。
例 7.1
考虑二维二次函数
f
(
[
x
1
x
2
]
)
=
1
2
[
x
1
x
2
]
⊤
[
2
1
1
20
]
[
x
1
x
2
]
−
[
5
3
]
⊤
[
x
1
x
2
]
f\left(\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]\right)=\frac{1}{2}\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]^{\top}\left[\begin{array}{lc}2 & 1 \\1 & 20\end{array}\right]\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]-\left[\begin{array}{l}5 \\3\end{array}\right]^{\top}\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]
f([x1x2])=21[x1x2]⊤[21120][x1x2]−[53]⊤[x1x2]
梯度为：
∇
f
(
[
x
1
x
2
]
)
=
[
x
1
x
2
]
⊤
[
2
1
1
20
]
−
[
5
3
]
⊤
(
7.8
)
\nabla f\left(\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]\right)=\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]^{\top}\left[\begin{array}{cc}2 & 1 \\1 & 20\end{array}\right]-\left[\begin{array}{l}5 \\3\end{array}\right]^{\top}\qquad (7.8)
∇f([x1x2])=[x1x2]⊤[21120]−[53]⊤(7.8)
从初始位置 x 0 = [ − 3 , − 1 ] ⊤ \boldsymbol{x}_{0}=[-3,-1]^{\top} x0=[−3,−1]⊤开始，我们迭代应用（7.6）以获得收敛到最小值的估计序列（如图7.3所示）。我们可以看到（从图中观察或通过将 x 0 \boldsymbol{x}_{0} x0代入（7.8），其中 γ = 0.085 \gamma=0.085 γ=0.085）， x 0 \boldsymbol{x}_{0} x0处的负梯度指向东北方向，得到 x 1 = [ − 1.98 , 1.21 ] ⊤ \boldsymbol{x}_{1}=[-1.98,1.21]^{\top} x1=[−1.98,1.21]⊤。重复这个步骤，我们将得到 x 2 = [ − 1.32 , − 0.42 ] ⊤ \boldsymbol{x}_{2}=[-1.32,-0.42]^{\top} x2=[−1.32,−0.42]⊤，依此类推。
图 7.3二维二次曲面的梯度下降(如热图所示)。示例7.1给出详细描述。
备注：
梯度下降可能会相对缓慢地接近最小值：其收敛速度可能会不如其他方法。利用球滚下山做类比，当山谷长而缓时，则称该问题的条件较差。对于条件较差的凸问题，梯度下降会呈“Z字形”，因为梯度方向几乎垂直于当前点到最小值点的最短路线方向；见图7.3。
7.1.1 步长
(步长也称为学习率)。
如前面所述，在梯度下降中选择一个好的步长是很重要的。如果步长太小，梯度下降可能会很慢。如果步长选择得太大，梯度下降会导致超调、无法收敛，甚至发散。我们将在下一节讨论动量的使用。这是一种平滑梯度更新不稳定和抑制振荡的方法。
自适应梯度方法能根据函数的局部性质，在每次迭代时重新调整步长。有两种简单的方法（Toussaint，2012）：
- 当采用梯度下降后函数值增大了，则表明步长过大了。这时我们可以撤消并减小步长。
- 当函数值减小时，我们可以尝试增大步长。
尽管“撤消”步骤似乎是浪费资源，但使用这种启发式方法可以保证单调收敛。
例 7.2 解线性方程组
如果我们使用欧几里德范数，当我们要求解形式为
A
x
=
b
\boldsymbol{A} \boldsymbol{x}=\boldsymbol{b}
Ax=b的线性方程组时，我们可以通过求解使平方误差
∥
A
x
−
b
∥
2
=
(
A
x
−
b
)
⊤
(
A
x
−
b
)
（
7.9
）
\|\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b}\|^{2}=(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})^{\top}(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})\qquad （7.9）
∥Ax−b∥2=(Ax−b)⊤(Ax−b)（7.9）
最小化的
x
∗
\boldsymbol{x}_*
x∗来近似求解
A
x
−
b
=
0
\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b}=\mathbf{0}
Ax−b=0
（7.9）相对于
x
\boldsymbol{x}
x的梯度为：
∇
x
=
2
(
A
x
−
b
)
⊤
A
\nabla_{\boldsymbol{x}}=2(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})^{\top} \boldsymbol{A}
∇x=2(Ax−b)⊤A
我们可以在梯度下降算法中直接使用这个梯度。然而，对于这种特殊情况，可以通过使梯度为零来找到解析解。我们将在第9章中看到更多关于平方误差问题的内容。
备注：
当梯度下降应用于解线性方程组
A
x
=
b
\boldsymbol{A} \boldsymbol{x}=\boldsymbol{b}
Ax=b时，可能会收敛缓慢。梯度下降的收敛速度取决于条件数(condition number)
κ
=
σ
(
A
)
max
σ
(
A
)
min
\kappa=\frac{\sigma(\boldsymbol{A})_{\max }}{\sigma(\boldsymbol{A})_{\min }}
κ=σ(A)minσ(A)max，即
A
\boldsymbol{A}
A的最大奇异值与最小奇异值之比（第4.5节）。条件数基本上衡量了弯曲程度最大方向与最小方向之比，这与我们的想象相符，条件差的问题是长而缓的山谷：它们在一个方向上非常弯曲，但在另一个方向上非常平坦。不直接求解
A
x
=
b
\boldsymbol{A} \boldsymbol{x}=\boldsymbol{b}
Ax=b，我们还可以求解
P
−
1
(
A
x
−
b
)
=
0
\boldsymbol{P}^{-1}(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})=\mathbf{0}
P−1(Ax−b)=0。其中
P
\boldsymbol{P}
P称为预条件(preconditioner)。我们的目标是设计
P
−
1
\boldsymbol{P}^{-1}
P−1，使的
P
−
1
A
\boldsymbol{P}^{-1}\boldsymbol{A}
P−1A有更好的条件数，但同时要求
P
−
1
\boldsymbol{P}^{-1}
P−1易于计算。有关梯度下降、预处理和收敛的更多信息，请参阅Boyd和Vandenberghe（2004，第9章）。
7.1.2 动量梯度下降
如图7.3所示，如果优化的曲面的存在缩放效果不佳的区域，那么梯度下降的收敛速度可能非常慢。改进收敛性的一个方法是给梯度下降添加记忆项。
动量梯度下降法（Rumelhart et al.，1986）引入了附加项来记忆上一次迭代中发生了什么。这种记忆可以抑制振荡，平滑梯度更新。继续用球做类比，动量项模拟了重球从斜坡滚下不会轻易改变方向的现象。其思想是使用记忆进行梯度更新，以实现滑动平均( moving average)。基于动量的方法记忆了每次迭代的更新量
Δ
x
i
\Delta \boldsymbol{x}_{i}
Δxi，下一次更新则用当前和之前梯度的线性组合确定：
x
i
+
1
=
x
i
−
γ
i
(
(
∇
f
)
(
x
i
)
)
⊤
+
α
Δ
x
i
\boldsymbol{x}_{i+1}=\boldsymbol{x}_{i}-\gamma_{i}\left((\nabla f)\left(\boldsymbol{x}_{i}\right)\right)^{\top}+\alpha \Delta \boldsymbol{x}_{i}
xi+1=xi−γi((∇f)(xi))⊤+αΔxi
Δ x i = x i − x i − 1 = α Δ x i − 1 − γ i − 1 ( ( ∇ f ) ( x i − 1 ) ) ⊤ \Delta \boldsymbol{x}_{i}=\boldsymbol{x}_{i}-\boldsymbol{x}_{i-1}=\alpha \Delta \boldsymbol{x}_{i-1}-\gamma_{i-1}\left((\nabla f)\left(\boldsymbol{x}_{i-1}\right)\right)^{\top} Δxi=xi−xi−1=αΔxi−1−γi−1((∇f)(xi−1))⊤
其中 α ∈ [ 0 , 1 ] \alpha \in[0,1] α∈[0,1]。有时我们只知道近似的梯度。在这种情况下，动量项是有用的，因为它平均了梯度的不同噪声估计（ noisy estimates）。获得近似梯度的一个特别有用的方法是使用随机近似，我们将在下面讨论。
7.1.3 随机梯度下降法
计算梯度非常耗时。然而，通常可以找到梯度的“cheap”近似值。只要近似梯度指向与真实梯度大致相同的方向，那么它就是有用的。
随机梯度下降法（Stochastic gradient descent，通常简称为SGD）是梯度下降法的一种随机近似方法，用于最小化目标函数，且目标函数应是可微函数之和。这里的“随机”一词指的是这样一个事实，即我们承认我们并不精确地知道梯度，而是只知道它的噪声近似值。通过约束近似梯度的概率分布，我们仍然可以从理论上保证SGD收敛。
在机器学习中，给定
n
=
1
,
…
,
N
n=1, \ldots, N
n=1,…,N个数据点，我们需考虑的目标函数是每个数据点
n
n
n所引起的损失
L
n
L_{n}
Ln之和。用公式表示为：
L
(
θ
)
=
∑
n
=
1
N
L
n
(
θ
)
L(\boldsymbol{\theta})=\sum_{n=1}^{N} L_{n}(\boldsymbol{\theta})
L(θ)=n=1∑NLn(θ)
其中
θ
\boldsymbol{\theta}
θ是我们感兴趣的参数向量，即，我们想要找到使
L
L
L最小化的
θ
\boldsymbol{\theta}
θ。在回归那一章中有一个例子的损失函数是负对数似然，它表示为每个样本对数似然之和：
L
(
θ
)
=
−
∑
n
=
1
N
log
p
(
y
n
∣
x
n
,
θ
)
L(\boldsymbol{\theta})=-\sum_{n=1}^{N} \log p\left(y_{n} \mid \boldsymbol{x}_{n}, \boldsymbol{\theta}\right)
L(θ)=−n=1∑Nlogp(yn∣xn,θ)
其中 x n ∈ R D \boldsymbol{x}_{n} \in \mathbb{R}^{D} xn∈RD是训练的输入， y n y_n yn是训练的目标值， θ \boldsymbol{\theta} θ是回归模型的参数。
如前所述，标准梯度下降法是一种“批量”优化方法，即选取合适的步长参数
γ
i
γ_i
γi并使用所有训练集，然后通过以下公式更新向量参数：
θ
i
+
1
=
θ
i
−
γ
i
(
∇
L
(
θ
i
)
)
⊤
=
θ
i
−
γ
i
∑
n
=
1
N
(
∇
L
n
(
θ
i
)
)
⊤
(
7.15
)
\boldsymbol{\theta}_{i+1}=\boldsymbol{\theta}_{i}-\gamma_{i}\left(\nabla L\left(\boldsymbol{\theta}_{i}\right)\right)^{\top}=\boldsymbol{\theta}_{i}-\gamma_{i} \sum_{n=1}^{N}\left(\nabla L_{n}\left(\boldsymbol{\theta}_{i}\right)\right)^{\top}\qquad (7.15)
θi+1=θi−γi(∇L(θi))⊤=θi−γin=1∑N(∇Ln(θi))⊤(7.15)
求梯度和可能需要对所有 L n L_n Ln的梯度进行计算。当训练集是巨大的或者(并且)损失函数不是简单的公式时，计算梯度和需要消耗巨大的计算资源。
考虑(7.15)中的 ∑ n = 1 N ( ∇ L n ( θ i ) ) \sum_{n=1}^{N}\left(\nabla L_{n}\left(\boldsymbol{\theta}_{i}\right)\right) ∑n=1N(∇Ln(θi))，我们可以取较小的 L n L_n Ln集合来求它们的梯度和以减少计算量。与批量梯度下降法使用 n = 1 , … , N n=1, \ldots, N n=1,…,N的所有 L n L_n Ln不同，小批量梯度下降随机选取 L n L_n Ln的子集。在极端情况下，我们还可以随机选择一个 L n L_n Ln来估计梯度。关于为什么选取数据子集是明智的，关键的见解是要认识到，为了使梯度下降收敛，我们只要求梯度是真实梯度的无偏估计。事实上，（7.15）中的 ∑ n = 1 N ( ∇ L n ( θ i ) ) \sum_{n=1}^{N}\left(\nabla L_{n}\left(\boldsymbol{\theta}_{i}\right)\right) ∑n=1N(∇Ln(θi))是梯度期望值（第6.4.1节）的经验估计。因此，对期望值的任何其他无偏经验估计，例如使用数据的任何子样本，将足以使梯度下降收敛。
备注：
当学习率以适当的速率下降时，在相对不严格的假设下，随机梯度下降必然收敛到局部最小值（Bottou，1998）。
为什么要考虑使用近似梯度？一个主要原因是硬件的限制，例如*处理器（CPU）/图形处理器（GPU）内存大小或计算时间的限制。我们可以像我们在估计经验平均数时考虑样本的大小一样（第6.4.1节），来考虑用来估计梯度的子集的大小。较大的小批量将提供准确的梯度估计，减少参数更新中的方差。此外，较大的小批量可以使代价和梯度向量化从而能使用高度优化的矩阵运算。方差的减少导致更稳定的收敛性，但每次梯度计算的计算量都很大。
相比之下，较小的小批量可以很快估计。如果我们保持较小的小批量，梯度估计中的噪声将允许我们脱离局部最优解。在机器学习中，优化方法是利用训练数据，通过最小化目标函数来进行训练的，但总体目标是提高泛化性能（第8章）。由于机器学习的目标不一定需要精确估计目标函数的最小值，所以使用小批量方法的近似梯度被广泛使用。随机梯度下降在大规模机器学习问题中非常有效（Bottou et al.，2018），例如在数百万张图像上训练深度神经网络（Dean et al.，2012），主题模型（Hoffman et al.，2013），强化学习（Mnih）或大规模高斯过程模型训练（Hensman等人，2013；Gal等人，2014）。
7.2 约束优化与拉格朗日乘子
在上一节中，我们考虑了求解函数最小值的问题：
min
x
f
(
x
)
\min _{\boldsymbol{x}} f(\boldsymbol{x})
xminf(x)
其中：
f
:
R
D
→
R
f: \mathbb{R}^{D} \rightarrow \mathbb{R}
f:RD→R
在本节中，我们将讨论有附加约束的情况。也就是说，对于实值函数
g
i
:
R
D
→
R
，
i
=
1
,
…
,
m
g_{i}: \mathbb{R}^{D} \rightarrow \mathbb{R}，i=1, \ldots, m
gi:RD→R，i=1,…,m，我们考虑约束优化问题（见图7.4）：
min
x
f
(
x
)
(
7.17
)
\min _{\boldsymbol{x}} f(\boldsymbol{x})\qquad (7.17)
xminf(x)(7.17)
subject to
g
i
(
x
)
⩽
0
for all
i
=
1
,
…
,
m
\text { subject to } \quad g_{i}(\boldsymbol{x}) \leqslant 0 \quad \text { for all } \quad i=1, \ldots, m
subject to gi(x)⩽0 for all i=1,…,m
图 7.4 约束优化示意图。无约束问题（由等高线表示）在右侧有一个最小值（由圆表示）。约束（ − 1 ≤ x ≤ 1 -1\le x\le 1 −1≤x≤1和 − 1 ≤ y ≤ 1 -1\le y\le 1 −1≤y≤1）要求最优解在方框内，所以表示最优值如星号所示。
值得指出的是，函数 f f f和 g i g_i gi在一般情况下可能是非凸的，我们将在下一节中考虑凸的情况。
将有约束优化转化为无约束优化的一种明显可行但不太实用的方法是使用指示函数( indicator function)：
J
(
x
)
=
f
(
x
)
+
∑
i
=
1
m
1
(
g
i
(
x
)
)
(
7.18
)
J(\boldsymbol{x})=f(\boldsymbol{x})+\sum_{i=1}^{m} \mathbf{1}\left(g_{i}(\boldsymbol{x})\right)\qquad(7.18)
J(x)=f(x)+i=1∑m1(gi(x))(7.18)
其中
1
(
z
)
\mathbf{1}(z)
1(z)是无限阶跃函数：
1
(
z
)
=
{
0
if
z
⩽
0
∞
otherwise
\mathbf{1}(z)=\left\{\begin{array}{ll}0 & \text { if } z \leqslant 0 \\\infty & \text { otherwise }\end{array}\right.
1(z)={0∞ if z⩽0 otherwise
如果不满足约束，将产生无限的惩罚，因此能得到与有约束优化问题同样的解。然而，这种无限阶跃函数难以优化。我们可以通过引入拉格朗日乘子(Lagrange multipliers)来解决这个问题。拉格朗日乘子的思想是用线性函数代替阶跃函数。
我们将问题（7.17）与拉格朗日法联系起来，通过引入与每个不等式约束分别对应的拉格朗日乘子
λ
i
≥
0
λ_i\ge 0
λi≥0（Boyd和Vandenberghe，2004，第4章）,得到：
L
(
x
,
λ
)
=
f
(
x
)
+
∑
i
=
1
m
λ
i
g
i
(
x
)
=
f
(
x
)
+
λ
⊤
g
(
x
)
(
7.20
)
\begin{aligned}\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) &=f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} g_{i}(\boldsymbol{x}) \\&=f(\boldsymbol{x})+\boldsymbol{\lambda}^{\top} \boldsymbol{g}(\boldsymbol{x})\end{aligned}\qquad(7.20)
L(x,λ)=f(x)+i=1∑mλigi(x)=f(x)+λ⊤g(x)(7.20)
其中我们将所有约束 g i ( x ) g_{i}(\boldsymbol{x}) gi(x)写成一个向量 g ( x ) \boldsymbol{g(x)} g(x)；把所有拉格朗日乘子也写成向量 λ ∈ R m \boldsymbol{\lambda} \in \mathbb{R}^{m} λ∈Rm。
我们现在介绍拉格朗日对偶( Lagrangian duality)的概念。一般来说，对偶优化的思想是将一组变量 x \boldsymbol{x} x（称为原始变量）的优化问题转化为另一组变量 λ \boldsymbol{\lambda} λ（称为对偶变量）的优化问题。我们将会介绍两种不同的对偶方法：在本节中，我们讨论的是拉格朗日对偶；在第7.3.3节中，我们将讨论Legendre-Fenchel对偶。
定义7.1
（7.17）的问题
min
x
f
(
x
)
\min _{\boldsymbol{x}} f(\boldsymbol{x})
xminf(x)
subject to
g
i
(
x
)
⩽
0
for all
i
=
1
,
…
,
m
\text { subject to } \quad g_{i}(\boldsymbol{x}) \leqslant 0 \quad \text { for all } \quad i=1, \ldots, m
subject to gi(x)⩽0 for all i=1,…,m
被称为原始问题，对应原始变量
x
x
x。
与它对应的拉格朗日对偶问题（Lagrangian dual problem）由下式给出：
max
λ
∈
R
m
D
(
λ
)
\max _{\boldsymbol{\lambda} \in \mathbb{R}^{m}} \mathfrak{D}(\boldsymbol{\lambda})
λ∈RmmaxD(λ)
subject to
λ
⩾
0
\text { subject to } \quad \boldsymbol{\lambda} \geqslant \mathbf{0}
subject to λ⩾0
其中
λ
\boldsymbol{\lambda}
λ为对偶变量且
D
(
λ
)
=
min
x
∈
R
d
L
(
x
,
λ
)
\mathfrak{D}(\boldsymbol{\lambda})=\min _{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
D(λ)=minx∈RdL(x,λ)
备注：
在对定义7.1的讨论中，我们使用了两个同样具有独立意义的概念（Boyd和Vandenberghe，2004）。
第一个是极大极小不等式（minimax inequality），它表示对于任何具有两个参数
φ
(
x
,
y
)
\varphi(\boldsymbol{x}, \boldsymbol{y})
φ(x,y)的函数，极大的极小值小于极小的极大值（瘦子中的胖子瘦于胖子中的瘦子），即：
max
y
min
x
φ
(
x
,
y
)
⩽
min
x
max
y
φ
(
x
,
y
)
(
7.23
)
\max _{\boldsymbol{y}} \min _{\boldsymbol{x}} \varphi(\boldsymbol{x}, \boldsymbol{y}) \leqslant \min _{\boldsymbol{x}} \max _{\boldsymbol{y}} \varphi(\boldsymbol{x}, \boldsymbol{y})\qquad(7.23)
ymaxxminφ(x,y)⩽xminymaxφ(x,y)(7.23)
这个不等式可以通过以下不等式证明：
对于任意
x
,
y
min
x
φ
(
x
,
y
)
⩽
max
y
φ
(
x
,
y
)
(
7.24
)
\text {对于任意 } \boldsymbol{x}, \boldsymbol{y} \quad \min _{\boldsymbol{x}} \varphi(\boldsymbol{x}, \boldsymbol{y}) \leqslant \max _{\boldsymbol{y}} \varphi(\boldsymbol{x}, \boldsymbol{y})\qquad(7.24)
对于任意 x,yxminφ(x,y)⩽ymaxφ(x,y)(7.24)
注意到取（7.24）左侧对于 y \boldsymbol{y} y上的最大值时不等式依然成立，因为不等式对所有 y \boldsymbol{y} y都成立。同样，我们取（7.24）右侧关于 x \boldsymbol{x} x上的最小值然后可以得到（7.23）。
第二个概念是弱对偶(weak duality)，它使用（7.23）来表示原始值总是大于或等于对偶值。这在（7.27）中有更详细的描述。
前面提到的，拉格朗日函数(7.20)是(7.18)
J
(
x
)
J(\boldsymbol{x})
J(x)中的指示函数转换为线性函数得到。所以，当
λ
≥
0
\lambda\ge 0
λ≥0时，拉格朗日函数
L
(
x
,
λ
)
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
L(x,λ)为
J
(
x
)
J(\boldsymbol{x})
J(x)(含指示函数的函数)的下界。因此，
L
(
x
,
λ
)
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
L(x,λ)关于
λ
\boldsymbol{\lambda}
λ的最大值为：
J
(
x
)
=
max
λ
⩾
0
L
(
x
,
λ
)
J(\boldsymbol{x})=\max _{\boldsymbol{\lambda} \geqslant \mathbf{0}} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
J(x)=λ⩾0maxL(x,λ)
原始问题是最小化
J
(
x
)
J(\boldsymbol{x})
J(x)，则
min
x
∈
R
d
max
λ
⩾
0
L
(
x
,
λ
)
\min _{\boldsymbol{x} \in \mathbb{R}^{d}} \max _{\boldsymbol{\lambda} \geqslant 0} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
x∈Rdminλ⩾0maxL(x,λ)
根据极大极小不等式（7.23），交换最小最大的顺序会得到一个更小的值，即：
min
x
∈
R
d
max
λ
⩾
0
L
(
x
,
λ
)
⩾
max
λ
⩾
0
min
x
∈
R
d
L
(
x
,
λ
)
\min _{\boldsymbol{x} \in \mathbb{R}^{d}} \max _{\boldsymbol{\lambda} \geqslant 0} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) \geqslant \max _{\boldsymbol{\lambda} \geqslant \mathbf{0}} \min _{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
x∈Rdminλ⩾0maxL(x,λ)⩾λ⩾0maxx∈RdminL(x,λ)
这也被称为弱对偶性。请注意，右侧的
min
x
∈
R
d
L
(
x
,
λ
)
\min _{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
minx∈RdL(x,λ)也就是对偶目标函数
D
(
λ
)
\mathfrak{D}(\boldsymbol{\lambda})
D(λ)。
与含约束的原始优化问题相比， min x ∈ R d L ( x , λ ) \min _{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) minx∈RdL(x,λ)在给定 λ \boldsymbol{\lambda} λ情况下是无约束问题。如果 min x ∈ R d L ( x , λ ) \min _{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) minx∈RdL(x,λ)易于求解，则整个问题也就迎刃而解了。我们可以从（7.20）观察到 L ( x , λ ) \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) L(x,λ)是 λ \boldsymbol{\lambda} λ仿射变换得到的。因此， min x ∈ R d L ( x , λ ) \min _{\boldsymbol{x} \in \mathbb{R}^{d}} \mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) minx∈RdL(x,λ)是 λ \boldsymbol{\lambda} λ的仿射函数的逐点最小值（pointwise minimum）。因此，即使 f ( ⋅ ) f(\cdot) f(⋅)和 g ( ⋅ ) g(\cdot) g(⋅)为非凸的（图7.2就是非凸的），则 D ( λ ) \mathfrak{D}(\boldsymbol{\lambda}) D(λ)也是凹的（ min ( ) \min() min()都是凹的）。外问题(outer problem)关于 λ λ λ的极大值也即凹函数的极大值，可以有效地计算。
PS：非凹包括凸函数以及有凸又有凹的函数
假设 f ( ⋅ ) f(\cdot) f(⋅)和 g i ( ⋅ ) g_i(\cdot) gi(⋅)是可微的，我们通过对 x \boldsymbol{x} x的拉格朗日函数进行微分并置零求得最优值，得到拉格朗日对偶问题。我们将在第7.3.1节和第7.3.2节中讨论两个具体示例，其中 f ( ⋅ ) f(·) f(⋅)和 g i ( ⋅ ) g_i(·) gi(⋅)是凸的。
备注： 等式约束(Equality Constraints)
考虑（7.17）有额外的等式约束：
min
x
f
(
x
)
\min _{\boldsymbol{x}} \quad f(\boldsymbol{x})
xminf(x)
subject to
g
i
(
x
)
⩽
0
for all
i
=
1
,
…
,
m
h
j
(
x
)
=
0
for all
j
=
1
,
…
,
n
(
7.28
)
\begin{aligned}\text { subject to } & g_{i}(\boldsymbol{x}) \leqslant 0 \text { for all } i=1, \ldots, m \\& h_{j}(\boldsymbol{x})=0 \quad \text { for all } \quad j=1, \ldots, n\end{aligned}\qquad (7.28)
subject to gi(x)⩽0 for all i=1,…,mhj(x)=0 for all j=1,…,n(7.28)
我们可以用两个不等式约束代替等式约束来建模。也就是说，对于每个等式约束 h j ( x ) = 0 h_{j}(\boldsymbol{x})=0 hj(x)=0，我们用两个约束 h j ( x ) ⩽ 0 h_{j}(\boldsymbol{x}) \leqslant 0 hj(x)⩽0和 h j ( x ) ⩾ 0 h_{j}(\boldsymbol{x}) \geqslant 0 hj(x)⩾0等价地替换它。结果表明，得到的拉格朗日乘子是无约束的。
因此，我们将（7.28）中不等式约束对应的拉格朗日乘子约束为非负，而等式约束对应的拉格朗日乘子则不加约束。
7.3 凸优化
让我们我们重点讨论一类特别有用的优化问题上，因为在这类问题上我们可以保证得到全局最优解。目标函数 f ( ⋅ ) f(·) f(⋅)是一个凸函数，且约束 g ( ⋅ ) g(·) g(⋅)和 h ( ⋅ ) h(·) h(⋅)是凸集的问题称为凸优化问题( convex optimization problem)。在这种情况下，称它具有强对偶性(strong duality)：对偶问题的最优解与原问题的最优解相同。在机器学习文献中，凸函数和凸集通常是不严格区别的，但是人们通常可以从上下文中推断出隐含的含义。
定义 7.2
如果对于任意
x
,
y
∈
C
x, y \in \mathcal{C}
x,y∈C和任意标量
0
⩽
θ
⩽
1
0 \leqslant \theta \leqslant 1
0⩽θ⩽1，有：
θ
x
+
(
1
−
θ
)
y
∈
C
\theta x+(1-\theta) y \in \mathcal{C}
θx+(1−θ)y∈C
则称
C
\mathcal{C}
C为凸集。
凸集是这样的集合：一条连接集合中任意两个元素的直线位于集合内。图7.5和7.6分别说明了凸集和非凸集。
图 7.5凸集示例
图 7.6 非凸集
图 7.7 凸函数示例
凸函数是这样的函数：函数的任意两点之间的直线位于函数的上方。图7.2显示了一个非凸函数，图7.3显示了一个凸函数。另一个凸函数如图7.7所示。
定义 7.3
令函数
f
:
R
D
→
R
f: \mathbb{R}^{D} \rightarrow \mathbb{R}
f:RD→R定义域为凸集。如果对于标量
0
⩽
θ
⩽
1
0 \leqslant \theta \leqslant 1
0⩽θ⩽1，
f
f
f定义域中的所有
x
,
y
\boldsymbol{x},\boldsymbol{y}
x,y有：
f
(
θ
x
+
(
1
−
θ
)
y
)
⩽
θ
f
(
x
)
+
(
1
−
θ
)
f
(
y
)
(
7.30
)
f(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y}) \leqslant \theta f(\boldsymbol{x})+(1-\theta) f(\boldsymbol{y})\qquad (7.30)
f(θx+(1−θ)y)⩽θf(x)+(1−θ)f(y)(7.30)
那么称
f
f
f为凸函数。
备注：凸函数取负就是凹函数。
（7.28）中涉及 g ( ⋅ ) g(·) g(⋅)和 h ( ⋅ ) h(·) h(⋅)的约束在标量值处截断函数，从而得到集合。凸函数和凸集之间的关系可以看作凸集是通过“填充”凸函数得到的集合。凸函数是一个碗状的物体，我们想象把水倒进去填满它。由此产生的填充集，称为凸函数的epigraph（函数图上以及上方的点集合），是一个凸集。
如果函数
f
:
R
n
→
R
f: \mathbb{R}^{n} \rightarrow \mathbb{R}
f:Rn→R是可微的，我们可以用它的梯度
∇
x
f
(
x
)
\nabla_{\boldsymbol{x}} f(\boldsymbol{x})
∇xf(x)来判断其凹凸性。函数
f
(
x
)
f(\boldsymbol{x})
f(x)为凸函数当且仅当，对于任意两点
x
,
y
\boldsymbol{x},\boldsymbol{y}
x,y：
f
(
y
)
⩾
f
(
x
)
+
∇
x
f
(
x
)
⊤
(
y
−
x
)
(
7.31
)
f(\boldsymbol{y}) \geqslant f(\boldsymbol{x})+\nabla_{\boldsymbol{x}} f(\boldsymbol{x})^{\top}(\boldsymbol{y}-\boldsymbol{x})\qquad (7.31)
f(y)⩾f(x)+∇xf(x)⊤(y−x)(7.31)
如果我们进一步知道函数 f ( x ) f(\boldsymbol{x}) f(x)是二次可微的，即对于 x \boldsymbol{x} x定义域中的所有值Hessian（5.147）矩阵都存在，那么函数 f ( x ) f(\boldsymbol{x}) f(x)是凸的当且仅当 ∇ x 2 f ( x ) \nabla_{\boldsymbol{x}}^{2} f(\boldsymbol{x}) ∇x2f(x)是半正定的（Boyd和Vandenberghe，2004）。
图 7.8 负的熵函数(为凸函数)以及它在
x
=
2
x = 2
x=2处的正切。
例 7.3
对于
x
>
0
x\gt 0
x>0，负熵
f
(
x
)
=
x
log
2
x
f(x)=x \log _{2} x
f(x)=xlog2x是凸函数。函数的可视化如图7.8所示，我们可以看到函数是凸的。为了说明前面定义的凸性，让我们利用两个点
x
=
2
x=2
x=2和
x
=
4
x=4
x=4进行计算。注意，为了证明
f
(
x
)
f(x)
f(x)的凸性，我们需要检查所有点
x
∈
R
x \in \mathbb{R}
x∈R。
看回定义7.3。考虑两点中间的一点（即使得 θ = 0.5 θ=0.5 θ=0.5），则(7.30)左侧为 f ( 0.5 ⋅ 2 + 0.5 ⋅ 4 ) = 3 log 2 3 ≈ 4.75 f(0.5 \cdot 2+0.5 \cdot 4)=3 \log _{2} 3 \approx 4.75 f(0.5⋅2+0.5⋅4)=3log23≈4.75。(7.30)右侧为 0.5 ( 2 log 2 2 ) + 0.5 ( 4 log 2 4 ) = 1 + 4 = 5 0.5\left(2 \log _{2} 2\right)+0.5\left(4 \log _{2} 4\right)=1+4=5 0.5(2log22)+0.5(4log24)=1+4=5。可以看到，结果满足定义。
因为
f
(
x
)
f(x)
f(x)是可微的，我们也可以使用（7.31）检验。首先计算
f
(
x
)
f(x)
f(x)的导数，得到
∇
x
(
x
log
2
x
)
=
1
⋅
log
2
x
+
x
⋅
1
x
log
e
2
=
log
2
x
+
1
log
e
2
\nabla_{x}\left(x \log _{2} x\right)=1 \cdot \log _{2} x+x \cdot \frac{1}{x \log _{e} 2}=\log _{2} x+\frac{1}{\log _{e} 2}
∇x(xlog2x)=1⋅log2x+x⋅xloge21=log2x+loge21
使用相同的两个测试点
x
=
2
x=2
x=2和
x
=
4
x=4
x=4，则（7.31）的左侧由
f
(
4
)
=
8
f(4)=8
f(4)=8给出。右测则是：
f
(
x
)
+
∇
x
⊤
(
y
−
x
)
=
f
(
2
)
+
∇
f
(
2
)
⋅
(
4
−
2
)
=
2
+
(
1
+
1
log
e
2
)
⋅
2
≈
6.9
\begin{aligned}f(\boldsymbol{x})+\nabla_{\boldsymbol{x}}^{\top}(\boldsymbol{y}-\boldsymbol{x}) &=f(2)+\nabla f(2) \cdot(4-2) \\&=2+\left(1+\frac{1}{\log _{e} 2}\right) \cdot 2 \approx 6.9\end{aligned}
f(x)+∇x⊤(y−x)=f(2)+∇f(2)⋅(4−2)=2+(1+loge21)⋅2≈6.9
我们可以通过定义来检验函数或集合是否是凸的。在实践中，我们经常使用保持凸性的操作来检查特定的函数或集合是否是凸的。这也是我们在第二章中介绍的向量空间封闭的概念，尽管细节有很大的不同。
例 7.4
凸函数的非负加权和是凸的。如果 f f f是一个凸函数， α ≥ 0 α\ge 0 α≥0是一个非负标量，那么函数 α f αf αf是凸的。我们可以通过将 α α α乘以定义7.3中方程的两边来得到这一结论，因为不等式两边乘以一个非负数并不能改变不等式。
如果
f
1
f_1
f1和
f
2
f_2
f2为凸函数，那么根据定义有：
f
1
(
θ
x
+
(
1
−
θ
)
y
)
⩽
θ
f
1
(
x
)
+
(
1
−
θ
)
f
1
(
y
)
f_{1}(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y}) \leqslant \theta f_{1}(\boldsymbol{x})+(1-\theta) f_{1}(\boldsymbol{y})
f1(θx+(1−θ)y)⩽θf1(x)+(1−θ)f1(y)
f
2
(
θ
x
+
(
1
−
θ
)
y
)
⩽
θ
f
2
(
x
)
+
(
1
−
θ
)
f
2
(
y
)
f_{2}(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y}) \leqslant \theta f_{2}(\boldsymbol{x})+(1-\theta) f_{2}(\boldsymbol{y})
f2(θx+(1−θ)y)⩽θf2(x)+(1−θ)f2(y)
两边分别相加：
f
1
(
θ
x
+
(
1
−
θ
)
y
)
+
f
2
(
θ
x
+
(
1
−
θ
)
y
)
⩽
θ
f
1
(
x
)
+
(
1
−
θ
)
f
1
(
y
)
+
θ
f
2
(
x
)
+
(
1
−
θ
)
f
2
(
y
)
\begin{array}{l}f_{1}(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y})+f_{2}(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y}) \\\leqslant \theta f_{1}(\boldsymbol{x})+(1-\theta) f_{1}(\boldsymbol{y})+\theta f_{2}(\boldsymbol{x})+(1-\theta) f_{2}(\boldsymbol{y})\end{array}
f1(θx+(1−θ)y)+f2(θx+(1−θ)y)⩽θf1(x)+(1−θ)f1(y)+θf2(x)+(1−θ)f2(y)
右边式子可以重新排列得到：
θ
(
f
1
(
x
)
+
f
2
(
x
)
)
+
(
1
−
θ
)
(
f
1
(
y
)
+
f
2
(
y
)
)
,
\theta\left(f_{1}(\boldsymbol{x})+f_{2}(\boldsymbol{x})\right)+(1-\theta)\left(f_{1}(\boldsymbol{y})+f_{2}(\boldsymbol{y})\right),
θ(f1(x)+f2(x))+(1−θ)(f1(y)+f2(y)),
即证明了凸函数之和是凸函数。
结合前面两个事实，我们发现 α f 1 ( x ) + β f 2 ( x ) \alpha f_{1}(\boldsymbol{x})+\beta f_{2}(\boldsymbol{x}) αf1(x)+βf2(x)对于 α , β ⩾ 0 \alpha, \beta \geqslant 0 α,β⩾0是凸的。对于两个以上凸函数的非负加权和，这个封闭性质可以用一个相似的参数来扩展。
备注：
不等式（7.30）有时也成为Jensen’s 不等式。实际上，凸函数非负加权和的不等式都称为Jensen不等式。
总之，约束优化问题称为凸优化问题，如果以下成立：
min
x
f
(
x
)
\min _{\boldsymbol{x}} f(\boldsymbol{x})
xminf(x)
subject to
g
i
(
x
)
⩽
0
for all
i
=
1
,
…
,
m
\text { subject to } g_{i}(\boldsymbol{x}) \leqslant 0 \quad \text { for all } \quad i=1, \ldots, m
subject to gi(x)⩽0 for all i=1,…,m
h
j
(
x
)
=
0
for all
j
=
1
,
…
,
n
h_{j}(\boldsymbol{x})=0 \quad \text { for all } \quad j=1, \ldots, n
hj(x)=0 for all j=1,…,n
其中 f ( x ) f(\boldsymbol{x}) f(x)和 g i ( x ) g_i(\boldsymbol{x}) gi(x)都为凸函数，且满足 h j ( x ) = 0 h_j(\boldsymbol{x})=0 hj(x)=0的集合为凸集。
下面，我们将描述两类被广泛应用且易于理解的凸优化问题。
7.3.1 线性规划
考虑所有函数都是线性的特殊情况，即：
min
x
∈
R
d
c
⊤
x
(
7.39
)
\min _{\boldsymbol{x} \in \mathbb{R}^{d}} \boldsymbol{c}^{\top} \boldsymbol{x}\qquad(7.39)
x∈Rdminc⊤x(7.39)
subject to
A
x
⩽
b
\text { subject to } \quad \boldsymbol{A} \boldsymbol{x} \leqslant \boldsymbol{b}
subject to Ax⩽b
其中 A ∈ R m × d \boldsymbol{A} \in \mathbb{R}^{m \times d} A∈Rm×d， b ∈ R m \boldsymbol{b} \in \mathbb{R}^{m} b∈Rm
这就是所谓的线性规划。它有
d
d
d个变量和
m
m
m个线性约束。其拉格朗日函数为：
L
(
x
,
λ
)
=
c
⊤
x
+
λ
⊤
(
A
x
−
b
)
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})=\boldsymbol{c}^{\top} \boldsymbol{x}+\boldsymbol{\lambda}^{\top}(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})
L(x,λ)=c⊤x+λ⊤(Ax−b)
其中
λ
∈
R
m
\boldsymbol{\lambda} \in \mathbb{R}^{m}
λ∈Rm是非负拉格朗日乘子向量。重新组合得到：
L
(
x
,
λ
)
=
(
c
+
A
⊤
λ
)
⊤
x
−
λ
⊤
b
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})=\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)^{\top} \boldsymbol{x}-\boldsymbol{\lambda}^{\top} \boldsymbol{b}
L(x,λ)=(c+A⊤λ)⊤x−λ⊤b
取
L
(
x
,
λ
)
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
L(x,λ)对
x
\boldsymbol{x}
x的导数并将其设为零：
c
+
A
⊤
λ
=
0
\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}=\mathbf{0}
c+A⊤λ=0
因此，拉格朗日对偶函数为：
D
(
λ
)
=
−
λ
⊤
b
\mathfrak{D}(\boldsymbol{\lambda})=-\boldsymbol{\lambda}^{\top} \boldsymbol{b}
D(λ)=−λ⊤b。根据前文，我们要最大化
D
(
λ
)
\mathfrak{D}(\boldsymbol{\lambda})
D(λ)，且除了
L
(
x
,
λ
)
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
L(x,λ)的导数为零的约束外，我们还有一个约束，即
λ
≥
0
\boldsymbol{\lambda}\ge 0
λ≥0，从而得到下面的对偶优化问题
max
λ
∈
R
m
−
b
⊤
λ
（
7.43
）
\max _{\boldsymbol{\lambda} \in \mathbb{R}^{m}}-\boldsymbol{b}^{\top} \boldsymbol{\lambda}\qquad （7.43）
λ∈Rmmax−b⊤λ（7.43）
subject to
c
+
A
⊤
λ
=
0
\text { subject to } \quad c+\boldsymbol{A}^{\top} \boldsymbol{\lambda}=\mathbf{0}
subject to c+A⊤λ=0
λ
⩾
0
\boldsymbol{\lambda} \geqslant \mathbf{0}
λ⩾0
这也是一个线性规划问题，但有 m m m个变量。我们可以选择求解原始规划问题（7.39）或其对偶规划问题（7.43），这取决于 m m m和 d d d哪个更大。其中， d d d是原始线性规划中变量的个数， m m m是约束的个数。
例 7.5线性规划
考虑有两个变量的线性规划
min
x
∈
R
2
−
[
5
3
]
⊤
[
x
1
x
2
]
\min _{\boldsymbol{x} \in \mathbb{R}^{2}}-\left[\begin{array}{l}5 \\3\end{array}\right]^{\top}\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]
x∈R2min−[53]⊤[x1x2]
subject to
[
2
2
2
−
4
−
2
1
0
−
1
0
1
]
[
x
1
x
2
]
⩽
[
33
8
5
−
1
8
]
\text { subject to } \quad\left[\begin{array}{cc}2 & 2 \\2 & -4 \\-2 & 1 \\0 & -1 \\0 & 1\end{array}\right]\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right] \leqslant\left[\begin{array}{c}33 \\8 \\5 \\-1 \\8\end{array}\right]
subject to ⎣⎢⎢⎢⎢⎡22−2002−41−11⎦⎥⎥⎥⎥⎤[x1x2]⩽⎣⎢⎢⎢⎢⎡3385−18⎦⎥⎥⎥⎥⎤
如图7.9所示。这个问题的目标函数是线性的，对应一系列线性轮廓线。图例展示了各个约束。最优值必须位于阴影（可行）区域，图中用星号表示。
图 7.9 一个线性规划的图示。无约束问题(由等高线表示)最小值在右侧。给定约束条件的最优值用星号表示。
7.3.2 二次规划
考虑凸二次目标函数的情况，其中约束是仿射的，即：
min
x
∈
R
d
1
2
x
⊤
Q
x
+
c
⊤
x
\min _{\boldsymbol{x} \in \mathbb{R}^{d}} \frac{1}{2} \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x}+\boldsymbol{c}^{\top} \boldsymbol{x}
x∈Rdmin21x⊤Qx+c⊤x
subject to
A
x
⩽
b
\text { subject to } \quad \boldsymbol{A} \boldsymbol{x} \leqslant \boldsymbol{b}
subject to Ax⩽b
其中
A
∈
R
m
×
d
,
b
∈
R
m
\boldsymbol{A} \in \mathbb{R}^{m \times d}, \boldsymbol{b} \in \mathbb{R}^{m}
A∈Rm×d,b∈Rm,
c
∈
R
d
\boldsymbol{c} \in \mathbb{R}^{d}
c∈Rd
对称方阵 Q ∈ R d × d \boldsymbol{Q}\in \mathbb{R}^{d \times d} Q∈Rd×d是正定的，因此目标函数是凸的。这就是所谓的二次规划。注意它有 d d d个变量和 m m m个线性约束。
例 7.6二次规划
考虑两个变量的二次规划：
min
x
∈
R
2
1
2
[
x
1
x
2
]
⊤
[
2
1
1
4
]
[
x
1
x
2
]
+
[
5
3
]
⊤
[
x
1
x
2
]
\min _{\boldsymbol{x} \in \mathbb{R}^{2}} \quad \frac{1}{2}\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]^{\top}\left[\begin{array}{ll}2 & 1 \\1 & 4\end{array}\right]\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]+\left[\begin{array}{l}5 \\3\end{array}\right]^{\top}\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right]
x∈R2min21[x1x2]⊤[2114][x1x2]+[53]⊤[x1x2]
subject to
[
1
0
−
1
0
0
1
0
−
1
]
[
x
1
x
2
]
⩽
[
1
1
1
1
]
\text { subject to } \quad\left[\begin{array}{cc}1 & 0 \\-1 & 0 \\0 & 1 \\0 & -1\end{array}\right]\left[\begin{array}{l}x_{1} \\x_{2}\end{array}\right] \leqslant\left[\begin{array}{l}1 \\1 \\1 \\1\end{array}\right]
subject to ⎣⎢⎢⎡1−100001−1⎦⎥⎥⎤[x1x2]⩽⎣⎢⎢⎡1111⎦⎥⎥⎤
规划结果如图所示。
目标函数是具有半正定矩阵 Q \boldsymbol{Q} Q的二次函数，产生椭圆轮廓线。最佳值必须位于阴影（可行）区域，图中用星号表示。
拉格朗日函数为：
L ( x , λ ) = 1 2 x ⊤ Q x + c ⊤ x + λ ⊤ ( A x − b ) = 1 2 x ⊤ Q x + ( c + A ⊤ λ ) ⊤ x − λ ⊤ b \begin{aligned}\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda}) &=\frac{1}{2} \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x}+\boldsymbol{c}^{\top} \boldsymbol{x}+\boldsymbol{\lambda}^{\top}(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b}) \\&=\frac{1}{2} \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x}+\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)^{\top} \boldsymbol{x}-\boldsymbol{\lambda}^{\top} \boldsymbol{b}\end{aligned} L(x,λ)=21x⊤Qx+c⊤x+λ⊤(Ax−b)=21x⊤Qx+(c+A⊤λ)⊤x−λ⊤b
求
L
(
x
,
λ
)
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
L(x,λ)关于
x
\boldsymbol{x}
x的导数并置零：
Q
x
+
(
c
+
A
⊤
λ
)
=
0
\boldsymbol{Q} \boldsymbol{x}+\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)=\mathbf{0}
Qx+(c+A⊤λ)=0
假设
Q
\boldsymbol{Q}
Q是可逆的，我们得到
x
=
−
Q
−
1
(
c
+
A
⊤
λ
)
(
7.50
)
\boldsymbol{x}=-\boldsymbol{Q}^{-1}\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)\qquad (7.50)
x=−Q−1(c+A⊤λ)(7.50)
将（7.50）代入原始拉格朗日
L
(
x
,
λ
)
\mathfrak{L}(\boldsymbol{x}, \boldsymbol{\lambda})
L(x,λ)
得到拉格朗日对偶方程
D
(
λ
)
=
−
1
2
(
c
+
A
⊤
λ
)
⊤
Q
−
1
(
c
+
A
⊤
λ
)
−
λ
⊤
b
\mathfrak{D}(\boldsymbol{\lambda})=-\frac{1}{2}\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)^{\top} \boldsymbol{Q}^{-1}\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)-\boldsymbol{\lambda}^{\top} \boldsymbol{b}
D(λ)=−21(c+A⊤λ)⊤Q−1(c+A⊤λ)−λ⊤b
因此，得到对偶优化问题：
max
λ
∈
R
m
−
1
2
(
c
+
A
⊤
λ
)
⊤
Q
−
1
(
c
+
A
⊤
λ
)
−
λ
⊤
b
\max _{\lambda \in \mathbb{R}^{m}}-\frac{1}{2}\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)^{\top} \boldsymbol{Q}^{-1}\left(\boldsymbol{c}+\boldsymbol{A}^{\top} \boldsymbol{\lambda}\right)-\boldsymbol{\lambda}^{\top} \boldsymbol{b}
λ∈Rmmax−21(c+A⊤λ)⊤Q−1(c+A⊤λ)−λ⊤b
subject to
λ
⩾
0
\text { subject to } \quad \boldsymbol{\lambda} \geqslant \mathbf{0}
subject to λ⩾0
我们将在第12章看到二次规划在机器学习中的应用。
7.3.3 Legendre-Fenchel变换和凸共轭
(共轭函数：https://www.bilibili.com/video/BV19t4y127ai)
让我们在不考虑约束的情况下重温第7.2节中对偶思想。关于凸集的一个有用的事实是，它可以由它的支持超平面(supporting hyperplanes)等价地描述。如果一个超平面与凸集相交，并且凸集只在它的一侧，则称之为凸集的支持超平面。回想一下，我们可以填充一个凸函数来得到的一个 epigraph（函数图上以及上方的点集合）是一个凸集。因此，我们也可以用支持超平面来描述凸函数。此外，支撑超平面是刚好接触到凸函数的，即是该接触点上函数的切线。回想一下，函数 f ( x ) f(\boldsymbol{x}) f(x)在给定点 x 0 \boldsymbol{x}_0 x0处的切线由该函数在该点处的梯度值 d f ( x ) d x ∣ x = x 0 \left.\frac{\mathrm{d} f(\boldsymbol{x})}{\mathrm{d} \boldsymbol{x}}\right|_{\boldsymbol{x}=\boldsymbol{x}_{0}} dxdf(x)∣∣∣x=x0确定。
综上所述，由于凸集可以等价地用其辅助超平面来描述，所以凸函数可以等价地用其梯度函数来描述。Legendre 变换形式化了这个概念。
我们从最一般的定义开始，不幸的是，这个定义有点反直觉，我们看一些特殊的情况，把定义和前面一段描述联系起来。
Legendre-Fenchel变换是从凸可微函数 f ( x ) f(\boldsymbol{x}) f(x)到依赖于切线 s ( x ) = ∇ x f ( x ) s(\boldsymbol{x})=\nabla_{\boldsymbol{x}} f(\boldsymbol{x}) s(x)=∇xf(x)的函数（傅里叶变换意义上）的变换。值得强调的是，这是函数 f ( ⋅ ) f(\cdot) f(⋅)的变换，而不是变量 x \boldsymbol{x} x或函数在 x \boldsymbol{x} x处求得的值的变换。Legendre-Fenchel变换也被称为凸共轭（convex conjugate ，原因我们将很快看到），并与对偶性密切相关（Hiriart-Urruty和Lemar’echal，2001，第5章）。
定义 7.4
函数
f
:
R
D
→
R
f: \mathbb{R}^{D} \rightarrow \mathbb{R}
f:RD→R的凸共轭函数
f
∗
f^*
f∗定义为：
f
∗
(
s
)
=
sup
x
∈
R
D
(
⟨
s
,
x
⟩
−
f
(
x
)
)
f^{*}(\boldsymbol{s})=\sup _{\boldsymbol{x} \in \mathbb{R}^{D}}(\langle\boldsymbol{s}, \boldsymbol{x}\rangle-f(\boldsymbol{x}))
f∗(s)=x∈RDsup(⟨s,x⟩−f(x))
注意，前面的凸共轭定义不需要函数 f f f是凸的或可微的。在定义7.4中，我们使用了一般内积（第3.2节），但是在本节的其余部分中，我们将考虑有限维向量之间的标准点积 ( ⟨ s , x ⟩ = s ⊤ x ) \left(\langle\boldsymbol{s}, \boldsymbol{x}\rangle=\boldsymbol{s}^{\top} \boldsymbol{x}\right) (⟨s,x⟩=s⊤x)，以避免太多的技术细节。
为了从几何角度理解7.4的定义，考虑一个简单的一维凸可微函数，例如
f
(
x
)
=
x
2
f(x)=x^2
f(x)=x2。注意，因为我们考虑的是一维问题，所以这里的超平面是一条线。我们假设这条线为
y
=
s
x
+
c
y=sx+c
y=sx+c。回想一下，我们可以用凸函数的支持超平面来描述它，所以让我们试着用函数
f
(
x
)
f(x)
f(x)的支持线来描述这个函数。固定线的梯度
s
∈
R
s∈\mathbb{R}
s∈R，对于
f
f
f图上的每个点
(
x
0
,
f
(
x
0
)
)
\left(x_{0}, f\left(x_{0}\right)\right)
(x0,f(x0))，求
c
c
c的最小值，使该线仍然过
(
x
0
,
f
(
x
0
)
)
\left(x_{0}, f\left(x_{0}\right)\right)
(x0,f(x0))。注意，"
c
c
c的最小值"指的是使斜率为
s
s
s的直线“刚好接触”函数
f
(
x
)
=
x
2
f(x)=x^2
f(x)=x2的取值。通过
(
x
0
,
f
(
x
0
)
)
\left(x_{0}, f\left(x_{0}\right)\right)
(x0,f(x0))且梯度为
s
s
s的线由下式给出
y
−
f
(
x
0
)
=
s
(
x
−
x
0
)
.
y-f\left(x_{0}\right)=s\left(x-x_{0}\right) \text { . }
y−f(x0)=s(x−x0) .
该线的
y
y
y轴截距为
−
s
x
0
+
f
(
x
0
)
−sx_0+f(x_0)
−sx0+f(x0)。因此，当
y
=
s
x
+
c
y=sx+c
y=sx+c与
f
f
f的图形相交时，
c
c
c的最小值为
inf
x
0
−
s
x
0
+
f
(
x
0
)
\inf _{x_{0}}-s x_{0}+f\left(x_{0}\right)
x0inf−sx0+f(x0)
可以看到，前面的凸共轭被定义为这个值的负数。这一段中的推导并不依赖于函数是否是凸且可微的，也适用于非凸和不可微的 f : R D → R f: \mathbb{R}^{D} \rightarrow \mathbb{R} f:RD→R。
备注：
凸可微函数，如
f
(
x
)
=
x
2
f(x)=x^2
f(x)=x2，其凸共轭不需要上确界，函数与其Legendre变换形式之间有一对一的对应关系。让我们从基本原理推导这个结论。对于凸可微函数，我们知道，在
x
0
x_0
x0处，切线与
f
(
x
0
)
f(x_0)
f(x0)接触，因此
f
(
x
0
)
=
s
x
0
+
c
f\left(x_{0}\right)=s x_{0}+c
f(x0)=sx0+c
回想一下，我们想用它的梯度
∇
x
f
(
x
)
\nabla_{x} f(x)
∇xf(x)来描述凸函数
f
(
x
)
f(x)
f(x)，而
s
=
∇
x
f
(
x
0
)
s=\nabla_{x} f\left(x_{0}\right)
s=∇xf(x0)。我们重新排列函数以得到
−
c
−c
−c的表达式：
−
c
=
s
x
0
−
f
(
x
0
)
-c=s x_{0}-f\left(x_{0}\right)
−c=sx0−f(x0)
注意
−
c
−c
−c随
x
0
x_0
x0而变化，因此也随
s
s
s而变化，这就是为什么我们可以将其视为
s
s
s的函数：
f
∗
(
s
)
:
=
s
x
0
−
f
(
x
0
)
（
7.58
）
f^{*}(s):=s x_{0}-f\left(x_{0}\right)\qquad （7.58）
f∗(s):=sx0−f(x0)（7.58）
将（7.58）与定义7.4进行比较，我们发现（7.58）是一个特例（没有上确界）。
共轭函数有很好的性质；例如，对于凸函数，再次应用Legendre变换可以使我们回到原来的函数。就像斜率是 s s s的 f ( x ) f(x) f(x)与斜率是 x x x的 f ∗ ( s ) f^*(s) f∗(s)可以相互变换一样。下面两个例子展示了凸共轭在机器学习中的常见用法
例 7.7凸共轭
为了说明凸共轭的应用，考虑二次函数
f
(
y
)
=
λ
2
y
⊤
K
−
1
y
f(\boldsymbol{y})=\frac{\lambda}{2} \boldsymbol{y}^{\top} \boldsymbol{K}^{-1} \boldsymbol{y}
f(y)=2λy⊤K−1y
其中有正定矩阵
K
∈
R
n
×
n
\boldsymbol{K} \in \mathbb{R}^{n \times n}
K∈Rn×n。我们将原变量表示为
y
∈
R
n
\boldsymbol{y} \in \mathbb{R}^{n}
y∈Rn，对偶变量表示为
α
∈
R
n
\alpha \in \mathbb{R}^{n}
α∈Rn
.应用定义7.4，我们得到了函数
f
∗
(
α
)
=
sup
y
∈
R
n
⟨
y
,
α
⟩
−
λ
2
y
⊤
K
−
1
y
(
7.60
)
f^{*}(\boldsymbol{\alpha})=\sup _{\boldsymbol{y} \in \mathbb{R}^{n}}\langle\boldsymbol{y}, \boldsymbol{\alpha}\rangle-\frac{\lambda}{2} \boldsymbol{y}^{\top} \boldsymbol{K}^{-1} \boldsymbol{y}\qquad (7.60)
f∗(α)=y∈Rnsup⟨y,α⟩−2λy⊤K−1y(7.60)
因为函数是可微的，所以我们可以通过求关于
y
\boldsymbol{y}
y的导数并将的其设为零来求最大值。
∂
[
⟨
y
,
α
⟩
−
λ
2
y
⊤
K
−
1
y
]
∂
y
=
(
α
−
λ
K
−
1
y
)
⊤
\frac{\partial\left[\langle\boldsymbol{y}, \boldsymbol{\alpha}\rangle-\frac{\lambda}{2} \boldsymbol{y}^{\top} \boldsymbol{K}^{-1} \boldsymbol{y}\right]}{\partial \boldsymbol{y}}=\left(\boldsymbol{\alpha}-\lambda \boldsymbol{K}^{-1} \boldsymbol{y}\right)^{\top}
∂y∂[⟨y,α⟩−2λy⊤K−1y]=(α−λK−1y)⊤
因此当梯度为零时，
y
=
1
λ
K
α
\boldsymbol{y}=\frac{1}{\lambda} \boldsymbol{K} \boldsymbol{\alpha}
y=λ1Kα。代入(7.60)得到：
f
∗
(
α
)
=
1
λ
α
⊤
K
α
−
λ
2
(
1
λ
K
α
)
⊤
K
−
1
(
1
λ
K
α
)
=
1
2
λ
α
⊤
K
α
f^{*}(\boldsymbol{\alpha})=\frac{1}{\lambda} \boldsymbol{\alpha}^{\top} \boldsymbol{K} \boldsymbol{\alpha}-\frac{\lambda}{2}\left(\frac{1}{\lambda} \boldsymbol{K} \boldsymbol{\alpha}\right)^{\top} \boldsymbol{K}^{-1}\left(\frac{1}{\lambda} \boldsymbol{K} \boldsymbol{\alpha}\right)=\frac{1}{2 \lambda} \boldsymbol{\alpha}^{\top} \boldsymbol{K} \boldsymbol{\alpha}
f∗(α)=λ1α⊤Kα−2λ(λ1Kα)⊤K−1(λ1Kα)=2λ1α⊤Kα
例 7.8
在机器学习中，我们经常使用函数和；例如，训练集的目标函数包括训练集中每个样本的损失之和。下面，我们推导出了损失和
ℓ
(
t
)
\ell(t)
ℓ(t)的凸共轭，其中
ℓ
:
R
→
R
\ell: \mathbb{R} \rightarrow \mathbb{R}
ℓ:R→R。这也展示了凸共轭在向量情形中的应用。设
L
(
t
)
=
∑
i
=
1
n
ℓ
i
(
t
i
)
\mathcal{L}(\boldsymbol{t})=\sum_{i=1}^{n} \ell_{i}\left(t_{i}\right)
L(t)=∑i=1nℓi(ti)，然后，
L
∗
(
z
)
=
sup
t
∈
R
n
⟨
z
,
t
⟩
−
∑
i
=
1
n
ℓ
i
(
t
i
)
\mathcal{L}^{*}(\boldsymbol{z})=\sup _{\boldsymbol{t} \in \mathbb{R}^{n}}\langle\boldsymbol{z}, \boldsymbol{t}\rangle-\sum_{i=1}^{n} \ell_{i}\left(t_{i}\right)
L∗(z)=t∈Rnsup⟨z,t⟩−i=1∑nℓi(ti)
由点积定义得到：
=
sup
t
∈
R
n
∑
i
=
1
n
z
i
t
i
−
ℓ
i
(
t
i
)
\begin{aligned}&=\sup _{t \in \mathbb{R}^{n}} \sum_{i=1}^{n} z_{i} t_{i}-\ell_{i}\left(t_{i}\right)\end{aligned}
=t∈Rnsupi=1∑nziti−ℓi(ti)
=
∑
i
=
1
n
sup
t
∈
R
n
z
i
t
i
−
ℓ
i
(
t
i
)
=\sum_{i=1}^{n} \sup _{t \in \mathbb{R}^{n}} z_{i} t_{i}-\ell_{i}\left(t_{i}\right)
=i=1∑nt∈Rnsupziti−ℓi(ti)
由共轭的定义：
=
∑
i
=
1
n
ℓ
i
∗
(
z
i
)
=\sum_{i=1}^{n} \ell_{i}^{*}\left(z_{i}\right)
=i=1∑nℓi∗(zi)
回想一下，在第7.2节中，我们使用拉格朗日乘子导出了一个对偶优化问题。此外，对于凸优化问题，我们有很强的对偶性，即原问题的解与对偶问题的解相匹配。这里描述的Legendre-Fenchel变换也可以用来导出对偶优化问题。此外，当函数是凸可微函数时，上确界是唯一的。为了进一步研究这两种方法之间的关系，让我们考虑一个等式约束的线性凸优化问题。
例 7.9
令
f
(
y
)
f(\boldsymbol{y})
f(y)和
g
(
x
)
g(\boldsymbol{x})
g(x)为凸函数，
A
\boldsymbol{A}
A为一个适当维数的实矩阵，使得
A
x
=
y
\boldsymbol{A}\boldsymbol{x}=\boldsymbol{y}
Ax=y，则：
min
x
f
(
A
x
)
+
g
(
x
)
=
min
A
x
=
y
f
(
y
)
+
g
(
x
)
\min _{\boldsymbol{x}} f(\boldsymbol{A} \boldsymbol{x})+g(\boldsymbol{x})=\min _{\boldsymbol{A} \boldsymbol{x}=\boldsymbol{y}} f(\boldsymbol{y})+g(\boldsymbol{x})
xminf(Ax)+g(x)=Ax=yminf(y)+g(x)
通过对约束
A
x
=
y
\boldsymbol{A}\boldsymbol{x}=\boldsymbol{y}
Ax=y引入拉格朗日乘子
u
\boldsymbol{u}
u，
min
A
x
=
y
f
(
y
)
+
g
(
x
)
=
min
x
,
y
max
u
f
(
y
)
+
g
(
x
)
+
(
A
x
−
y
)
⊤
u
\min _{\boldsymbol{A} \boldsymbol{x}=\boldsymbol{y}} f(\boldsymbol{y})+g(\boldsymbol{x})=\min _{\boldsymbol{x}, \boldsymbol{y}} \max _{\boldsymbol{u}} f(\boldsymbol{y})+g(\boldsymbol{x})+(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{y})^{\top} \boldsymbol{u}
Ax=yminf(y)+g(x)=x,yminumaxf(y)+g(x)+(Ax−y)⊤u
=
max
u
min
x
,
y
f
(
y
)
+
g
(
x
)
+
(
A
x
−
y
)
⊤
u
=\max _{\boldsymbol{u}} \min _{\boldsymbol{x}, \boldsymbol{y}} f(\boldsymbol{y})+g(\boldsymbol{x})+(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{y})^{\top} \boldsymbol{u}
=umaxx,yminf(y)+g(x)+(Ax−y)⊤u
其中最后一步交换max和min是因为
f
(
y
)
f( \boldsymbol{y})
f(y)和
g
(
x
)
g(\boldsymbol{x})
g(x)是凸函数。通过展开点积项并分离
x
\boldsymbol{x}
x和
y
\boldsymbol{y}
y，得到：
max
u
min
x
,
y
f
(
y
)
+
g
(
x
)
+
(
A
x
−
y
)
⊤
u
\max _{\boldsymbol{u}} \min _{\boldsymbol{x}, \boldsymbol{y}} f(\boldsymbol{y})+g(\boldsymbol{x})+(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{y})^{\top} \boldsymbol{u}
umaxx,yminf(y)+g(x)+(Ax−y)⊤u
=
max
u
[
min
y
−
y
⊤
u
+
f
(
y
)
]
+
[
min
x
(
A
x
)
⊤
u
+
g
(
x
)
]
=\max _{\boldsymbol{u}}\left[\min _{\boldsymbol{y}}-\boldsymbol{y}^{\top} \boldsymbol{u}+f(\boldsymbol{y})\right]+\left[\min _{\boldsymbol{x}}(\boldsymbol{A} \boldsymbol{x})^{\top} \boldsymbol{u}+g(\boldsymbol{x})\right]
=umax[ymin−y⊤u+f(y)]+[xmin(Ax)⊤u+g(x)]
=
max
u
[
min
y
−
y
⊤
u
+
f
(
y
)
]
+
[
min
x
x
⊤
A
⊤
u
+
g
(
x
)
]
=\max _{\boldsymbol{u}}\left[\min _{\boldsymbol{y}}-\boldsymbol{y}^{\top} \boldsymbol{u}+f(\boldsymbol{y})\right]+\left[\min _{\boldsymbol{x}} \boldsymbol{x}^{\top} \boldsymbol{A}^{\top} \boldsymbol{u}+g(\boldsymbol{x})\right]
=umax[ymin−y⊤u+f(y)]+[xminx⊤A⊤u+g(x)]
回想一下凸共轭（定义7.4）以及点积是对称的这一事实，我们得到：
max
u
[
min
y
−
y
⊤
u
+
f
(
y
)
]
+
[
min
x
x
⊤
A
⊤
u
+
g
(
x
)
]
\max _{\boldsymbol{u}}\left[\min _{\boldsymbol{y}}-\boldsymbol{y}^{\top} \boldsymbol{u}+f(\boldsymbol{y})\right]+\left[\min _{\boldsymbol{x}} \boldsymbol{x}^{\top} \boldsymbol{A}^{\top} \boldsymbol{u}+g(\boldsymbol{x})\right]
umax[ymin−y⊤u+f(y)]+[xminx⊤A⊤u+g(x)]
=
max
u
−
f
∗
(
u
)
−
g
∗
(
−
A
⊤
u
)
=\max _{\boldsymbol{u}}-f^{*}(\boldsymbol{u})-g^{*}\left(-\boldsymbol{A}^{\top} \boldsymbol{u}\right)
=umax−f∗(u)−g∗(−A⊤u)
因此，我们可以得到：
min
x
f
(
A
x
)
+
g
(
x
)
=
max
u
−
f
∗
(
u
)
−
g
∗
(
−
A
⊤
u
)
\min _{\boldsymbol{x}} f(\boldsymbol{A} \boldsymbol{x})+g(\boldsymbol{x})=\max _{\boldsymbol{u}}-f^{*}(\boldsymbol{u})-g^{*}\left(-\boldsymbol{A}^{\top} \boldsymbol{u}\right)
xminf(Ax)+g(x)=umax−f∗(u)−g∗(−A⊤u)
Legendre-Fenchel共轭对于可以表示为凸优化问题的机器学习问题是非常有用的。特别地，对于独立地应用于每个例子的凸损失函数，共轭损失是导出线性问题的一种方便方法。