在看《统计学习方法》支持向量机一章的时候,看到“应用拉格朗日对偶性(参阅附录C),通过求解对偶问题得到原始问题的最优解”一句,于是往下递归学习了一下附录C的拉格朗日对偶性。名曰学习,实则是摘抄,加入了少量个人理解与背景补充。毕竟定理和推论看懂就行,也不可能写出花来。甚至原著也没有给出部分推论的证明,只是知道有这回事,下次要用记得过来扫一眼就行。以下是摘抄的正文:
在约束最优化问题中,常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题,通过解对偶问题而得到原始问题的解。该方法应用在许多统计学习方法中,例如,最大熵模型与支持向量机。这里简要叙述拉格朗日对偶性的主要概念和结果。
1. 原始问题
假设是定义在Rn上的连续可微函数。考虑约束最优化问题
称此约束最优化问题为原始最优化问题或原始问题。
首先,引进广义拉格朗日函数(generalized Lagrange function)
这里,是拉格朗日乘子,。考虑x的函数:
这里,下标P表示原始问题。
假设给定某个x,如果x违反原始问题的约束条件,即存在某个i使得或者存在某个j使得,那么就有
因为若某个i使约束,则可令,若某个j使,则可令使,而将其余各均取为0。
相反地,如果x满足约束条件式(C.2)和式(C.3),则由式(C.5)和式(C.4)可知,(少的两项一个是非正的,一个是0,要取最大值的话当然得令两者都为0)。因此,
所以如果考虑极小化问题
它是与原始最优化问题(C.1)〜(C.3)等价的,即它们有相同的解。问题称为广义拉格朗日函数的极小极大问题。这样一来,就把原始最优化问题表示为广义拉格朗日函数的极小极大问题。为了方便,定义原始问题的最优值
称为原始问题的值。
2. 对偶问题
定义
再考虑极大化,即
问题称为广义拉格朗日函数的极大极小问题。
可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题:
称为原始问题的对偶问题。定义对偶问题的最优值
称为对偶问题的值。
3. 原始问题和对偶问题的关系
下面讨论原始问题和对偶问题的关系。
定理C.1
若原始问题和对偶问题都有最优值,则
证明
由式(C.12)和式(C.5),对任意的α,β和x,有
即
由于原始问题和对偶问题均有最优值,所以,
即
这似乎很好理解,同一个函数的最小值的上界小于它的最大值的下界。
推论C.1
设分别是原始问题(C.1)〜(C.3)和对偶问题(C.12)〜(C.13)的可行解,并且则分别是原始问题和对偶问题的最优解。
在某些条件下,原始问题和对偶问题的最优值相等,。这时可以用解对偶问题替代解原始问题。下面以定理的形式叙述有关的重要结论而不予证明。
定理C.2
考虑原始问题(C.1)〜(C.3)和对偶问题(C.12)〜(C.13)。假设函数和是凸函数,是仿射函数;
豆知识 仿射函数
仿射函数是特殊的凸函数.既是凸函数,又是凹函数的函数称为仿射函数.它必定是线性函数与常数之和.在有限维空间上,仿射函数就是一次函数.仿射函数的重要性在于局部凸空间(包括赋范线性空间、有限维空间)上的下半连续凸函数一定是连续仿射函数族的上包络.
——《数学辞海 第三卷》(很遗憾,中文学术书籍我一般看不懂,只能看懂红色这一句。)
Affine functions represent vector-valued functions of the form
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有,则存在使是原始问题的解,是对偶问题的解,并且
定理C.3
对原始问题(C.1)〜(C.3)和对偶问题(C.12)〜(C.13),假设函数和是凸函数,是仿射函数,并且不等式约束是严格可行的,则和分别是原始问题和对偶问题的解的充分必要条件是;满足下面的Karush-Kuhn-Tucker(KKT)条件:
特别指出,式(C.24)称为KKT的对偶互补条件。由此条件可知:若,则。
Reference
《统计学习方法》
[good]