对于一个等式约束的凸优化问题如下： minimize f ( x ) subject to A x = b , \begin{array}{ll} \operatorname{minimize} & f(x) \\ \text { subject to } & A x=b, \end{array} minimize subject to f(x)Ax=b, 其中， f ( x ) f(x) f(x)为凸函数。 对偶上升法是一种行之有效的方法。 首先，我们将限制条件通过拉格朗日乘子写入目标中， 得到拉格朗日函数为： L ( x , y ) = f ( x ) + y T ( A x − b ) L(x, y)=f(x)+y^{T}(A x-b) L(x,y)=f(x)+yT(Ax−b)
那么，其对偶函数为： g ( y ) = inf x L ( x , y ) g(y)=\inf _{x} L(x, y) g(y)=xinfL(x,y) 相应的对偶问题为： maximize g ( y ) (1) \text { maximize } g(y) \tag{1} maximize g(y)(1) 若强对偶性成立， 则最优解 x ⋆ x^\star x⋆由下式给出： x ⋆ = argmin x L ( x , y ⋆ ) , (2) x^{\star}=\underset{x}{\operatorname{argmin}} L\left(x, y^{\star}\right), \tag{2} x⋆=xargminL(x,y⋆),(2) 其中 y ⋆ y^\star y⋆为(1)的最优解。 接下来，我们考虑如何求解单变量对偶问题(1)， 因为有了(1)的解我们就可以由(2)得到原问题的最优解。
而对偶上升法的算法流程如下：
x k + 1 : = argmin x L ( x , y k ) y k + 1 : = y k + α k ( A x k + 1 − b ) , \begin{aligned} &x^{k+1}:=\underset{x}{\operatorname{argmin}} L\left(x, y^{k}\right) \\ &y^{k+1}:=y^{k}+\alpha^{k}\left(A x^{k+1}-b\right), \end{aligned} xk+1:=xargminL(x,yk)yk+1:=yk+αk(Axk+1−b),
流程很简单， 也就是说，我们可以通过一种梯度法的方式迭代求解 y y y。 但是，为什么可以这样呢？
对偶上升法的原理其实对偶上升法的思路就如一开始所说， 寻找一个 y y y最大化 g ( y ) g(y) g(y)， 那么给定初始点 y 0 y_0 y0时， 一种常见的做法就是梯度下降法（这里对应的是梯度上升法），即求取 ∇ g ( y 0 ) \nabla g(y_0) ∇g(y0), 将 y 1 y_1 y1更新为 y 0 + α ∇ g ( y 0 ) y_0 + \alpha\nabla g(y_0) y0+α∇g(y0)。
就着这个思路，我们事实上就是要求取 ∇ g ( y ) \nabla g(y) ∇g(y)。 注意到，无论 f ( x ) f(x) f(x)是否凸， 对偶函数 g ( y ) g(y) g(y)一定是凹函数 （一族仿射函数的逐点下确界）。 因此， 根据凹函数的一阶条件，我们有： g ( z ) ≤ g ( y ) + ∇ g ( y ) T ( z − y ) ∀ z (3) g(z) \leq g(y)+ \nabla g(y)^T(z-y) \quad \forall z \tag{3} g(z)≤g(y)+∇g(y)T(z−y)∀z(3)
注意到， 根据 g g g的定义， g ( z ) g(z) g(z)可写为： g ( z ) = inf x ( f ( x ) + z T ( A x − b ) ) = inf x ( f ( x ) + y T ( A x − b ) + ( z − y ) T ( A x − b ) ) g(z) =\inf_x(f(x)+z^{T}(A x-b)) =\inf_x(f(x)+y^{T}(A x-b)+(z-y)^{T}(A x-b)) g(z)=xinf(f(x)+zT(Ax−b))=xinf(f(x)+yT(Ax−b)+(z−y)T(Ax−b)) 令 x + ∈ argmin L ( x , y ) x^{+} \in \operatorname{argmin} L(x, y) x+∈argminL(x,y), 我们有： g ( z ) = inf x ( f ( x ) + y T ( A x − b ) + ( z − y ) T ( A x − b ) ) ≤ ( f ( x + ) + y T ( A x + − b ) + ( z − y ) T ( A x + − b ) ) = g ( y ) + ( A x + − b ) T ( z − y ) (4) g(z) = \inf_x(f(x)+y^{T}(A x-b)+(z-y)^{T}(A x-b)) \le (f(x^+)+y^{T}(A x^+-b)+(z-y)^{T}(A x^+-b))\\=g(y) + (A x^+-b)^T(z-y) \tag{4} g(z)=xinf(f(x)+yT(Ax−b)+(z−y)T(Ax−b))≤(f(x+)+yT(Ax+−b)+(z−y)T(Ax+−b))=g(y)+(Ax+−b)T(z−y)(4)
第一个不等式是下确界的性质， 第二个等式是 g g g的定义。 这时我们注意到， 对比(3)和(4)， 我们发现 ∇ g ( y ) = A x + − b \nabla g(y) = A x^+-b ∇g(y)=Ax+−b.
现在，回过头来看对偶上升法的流程， 第一步在求 x + x^+ x+， 第二步就是根据 ∇ g ( y ) \nabla g(y) ∇g(y) 更新 y y y。 因此，对偶上升法的收敛性是明确的， 因为这本质是就是一种梯度上升法。
可以一提的是， 如果 arg min x L ( x , y ) \arg\min_x L(x,y) argminxL(x,y) 在给定 y y y的情况下， 可以很容易得到 x x x的闭式解 x = ϕ ( y ) x=\phi(y) x=ϕ(y)的话， 也可以通过把 ϕ ( y ) \phi(y) ϕ(y)代入 g ( y ) g(y) g(y)中， 这样就无需对偶上升，只需对 y y y一次性迭代求解即可。
次梯度我们刚忽略了一种情况， 那就是如果 f ( x ) f(x) f(x)并不是严格凸的时候， 会存在 g ( y ) g(y) g(y)不可导的情况，即 ∇ g ( y ) \nabla g(y) ∇g(y)不存在。 此时，则需要引出次梯度的概念， 使得对偶上升法仍可以工作。
