拉格朗日对偶性-码农场

1. 原始问题
2. 对偶问题
3. 原始问题和对偶问题的关系
定理C.1
推论C.1
定理C.2
豆知识仿射函数
定理C.3
Reference

Lagrange duality.jpg

在看《统计学习方法》支持向量机一章的时候，看到“应用拉格朗日对偶性（参阅附录C），通过求解对偶问题得到原始问题的最优解”一句，于是往下递归学习了一下附录C的拉格朗日对偶性。名曰学习，实则是摘抄，加入了少量个人理解与背景补充。毕竟定理和推论看懂就行，也不可能写出花来。甚至原著也没有给出部分推论的证明，只是知道有这回事，下次要用记得过来扫一眼就行。以下是摘抄的正文：

在约束最优化问题中，常常利用拉格朗日对偶性（Lagrange duality)将原始问题转换为对偶问题，通过解对偶问题而得到原始问题的解。该方法应用在许多统计学习方法中，例如，最大熵模型与支持向量机。这里简要叙述拉格朗日对偶性的主要概念和结果。

1. 原始问题

假设原始问题假设.png 是定义在Rⁿ上的连续可微函数。考虑约束最优化问题

考虑约束最优化问题.png

称此约束最优化问题为原始最优化问题或原始问题。

首先，引进广义拉格朗日函数（generalized Lagrange function)

广义拉格朗日函数.png

这里，是拉格朗日乘子.png 是拉格朗日乘子，。考虑x的函数：

考虑x的函数.png

这里，下标P表示原始问题。

假设给定某个x，如果x违反原始问题的约束条件，即存在某个i使得某个i使得.png 或者存在某个j使得某个j使得.png ,那么就有

那么就有.png

因为若某个i使约束某个i使得.png ，则可令则可令.png ，若某个j使某个j使得.png ,则可令使拉格朗日对偶性1.png ，而将其余各拉格朗日对偶性2.png 均取为0。

相反地，如果x满足约束条件式(C.2)和式(C.3)，则由式(C.5)和式(C.4)可知，拉格朗日对偶性3.png （少的两项一个是非正的，一个是0，要取最大值的话当然得令两者都为0）。因此，

拉格朗日对偶性4.png

所以如果考虑极小化问题

极小化问题.png

它是与原始最优化问题（C.1)〜（C.3)等价的，即它们有相同的解。问题拉格朗日对偶性6.png 称为广义拉格朗日函数的极小极大问题。这样一来，就把原始最优化问题表示为广义拉格朗日函数的极小极大问题。为了方便，定义原始问题的最优值

原始问题的最优值.png

称为原始问题的值。

2. 对偶问题

定义

拉格朗日对偶性对偶问题.png

再考虑极大化再考虑极大化.png ，即

拉格朗日对偶性7.png

问题广义拉格朗日函数的极大极小问题.png 称为广义拉格朗日函数的极大极小问题。

可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题：

极大极小问题表示为约束最优化问题.png

称为原始问题的对偶问题。定义对偶问题的最优值

对偶问题的最优值.png

称为对偶问题的值。

3. 原始问题和对偶问题的关系

下面讨论原始问题和对偶问题的关系。

定理C.1

若原始问题和对偶问题都有最优值，则

原始问题和对偶问题都有最优值.png

证明

由式(C.12)和式(C.5),对任意的α,β和x，有

拉格朗日对偶性8.png

即

拉格朗日对偶性9.png

由于原始问题和对偶问题均有最优值，所以，

拉格朗日对偶性10.png

即

拉格朗日对偶性11.png

这似乎很好理解，同一个函数的最小值的上界小于它的最大值的下界。

推论C.1

设拉格朗日对偶性12.png 分别是原始问题(C.1)〜(C.3)和对偶问题(C.12)〜(C.13)的可行解，并且拉格朗日对偶性13.png 则分别是原始问题和对偶问题的最优解。

在某些条件下，原始问题和对偶问题的最优值相等，拉格朗日对偶性13.png 。这时可以用解对偶问题替代解原始问题。下面以定理的形式叙述有关的重要结论而不予证明。

定理C.2

考虑原始问题(C.1)〜(C.3)和对偶问题(C.12)〜(C.13)。假设函数和是凸函数，是仿射函数；

豆知识仿射函数

仿射函数是特殊的凸函数.既是凸函数,又是凹函数的函数称为仿射函数.它必定是线性函数与常数之和.在有限维空间上,仿射函数就是一次函数.仿射函数的重要性在于局部凸空间(包括赋范线性空间、有限维空间)上的下半连续凸函数一定是连续仿射函数族的上包络.

——《数学辞海第三卷》（很遗憾，中文学术书籍我一般看不懂，只能看懂红色这一句。）

Affine functions represent vector-valued functions of the form

Affine Function.gif

The coefficients can be scalars or dense or sparse matrices. The constant term is a scalar or a column vector.

In geometry, an affine transformation or affine map (from the Latin, affinis, "connected with") between two vector spaces consists of a linear transformation followed by a translation. In a geometric setting, these are precisely the functions that map straight lines to straight lines.

——http://mathworld.wolfram.com/AffineFunction.html （英文真好懂，仿射函数就是一个线性函数，其输入是n维向量，参数A可以是常数，也可以是m*n的矩阵，b可以是常数，也可以是m维的列向量，输出是一个m维的列向量。在几何上，仿射函数是一个线性空间到另一个线性空间的变换。）

并且假设不等式约束是严格可行的，即存在x，对所有i有对所有有.png ,则存在拉格朗日对偶性15.png 使拉格朗日对偶性16.png 是原始问题的解，拉格朗日对偶性17.png 是对偶问题的解，并且