放牧代码和思想
专注自然语言处理、机器学习算法

拉格朗日对偶性

目录

在看《统计学习方法》支持向量机一章的时候,看到“应用拉格朗日对偶性(参阅附录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

《统计学习方法》

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 拉格朗日对偶性

分享到:更多 ()

评论 4

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    [good]

    张子豪博客2年前 (2015-11-09)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机