全球网站流量排名100,网页制作专业选择,微信开发小程序工具,智能化网站建设文章目录 统计学习方法 拉格朗日对偶性原始问题对偶问题原始问题和对偶问题的关系 统计学习方法 拉格朗日对偶性
读李航的《统计学习方法》时#xff0c;关于拉格朗日对偶性的笔记。
在许多统计学习的约束最优化问题中#xff0c;例如最大熵模型和支持向量机#xff0c;常… 文章目录 统计学习方法 拉格朗日对偶性原始问题对偶问题原始问题和对偶问题的关系 统计学习方法 拉格朗日对偶性
读李航的《统计学习方法》时关于拉格朗日对偶性的笔记。
在许多统计学习的约束最优化问题中例如最大熵模型和支持向量机常常使用拉格朗日对偶性Lagrange duality将原始问题转换为对偶问题通过求解对偶问题而得到原始问题的解。
原始问题
假设 f ( x ) f(x) f(x) c i ( x ) c_i(x) ci(x) 和 h j ( x ) h_j(x) hj(x) 是定义在 R n \R^n Rn 上的连续可微函数考虑约束最优化问题记为 P P P min x ∈ R n f ( x ) s.t. c i ( x ) ≤ 0 , i 1 , 2 , ⋯ , k h j ( x ) 0 , j 1 , 2 , ⋯ , l \begin{aligned} \min_{x\in\R^n}\, f(x) \\ \text{s.t.}\,\, c_i(x)\leq 0,\quad i1,2,\cdots,k \\ \,\, h_j(x)0, \quad j1,2,\cdots,l \end{aligned} x∈Rnmins.t.f(x)ci(x)≤0,i1,2,⋯,khj(x)0,j1,2,⋯,l 它的 Lagrangian 为 L ( x , α , β ) f ( x ) ∑ i 1 k α i c i ( x ) ∑ j 1 l β j h j ( x ) L(x,\alpha,\beta)f(x)\sum_{i1}^{k}\alpha_ic_i(x)\sum\limits_{j1}^l \beta_jh_j(x) L(x,α,β)f(x)i1∑kαici(x)j1∑lβjhj(x) 其中 α i ≥ 0 \alpha_i \geq 0 αi≥0 以下是一个关于 x x x 的函数下标 P P P 代表原始问题 θ P ( x ) max α , β ; α i ≥ 0 L ( x , α , β ) \theta_P(x)\max\limits_{\alpha,\beta;\,\alpha_i\geq0}L(x,\alpha,\beta) θP(x)α,β;αi≥0maxL(x,α,β) 可以得到该函数的性质 θ P ( x ) { f ( x ) , x 满足原始问题的约束 ∞ , else \theta_P(x)\left\{ \begin{array}{ll} f(x), x\text{ 满足原始问题的约束} \\ \infty, \text{else} \end{array} \right. θP(x){f(x),∞,x 满足原始问题的约束else
如果 x x x 不满足原始问题的约束即存在某个 i i i 使得 c i ( x ) 0 c_i(x)\gt 0 ci(x)0 或者存在某个 j j j 使得 h j ( x ) ̸ 0 h_j(x)\not0 hj(x)0 那么就有 若存在某个 i i i 使得 c i ( x ) 0 c_i(x)\gt 0 ci(x)0 我们令 α i → ∞ \alpha_i\to\infty αi→∞ 则 θ P ( θ ) → ∞ \theta_P(\theta)\to\infty θP(θ)→∞ 若存在某个 j j j 使得 h j ( x ) ̸ 0 h_j(x)\not0 hj(x)0 我们令 β j \beta_j βj 取和 h j ( x ) h_j(x) hj(x) 相同的符号并且令 ∣ β j ∣ → ∞ |\beta_j|\to\infty ∣βj∣→∞ 即 β j h j ( x ) → ∞ \beta_jh_j(x)\to\infty βjhj(x)→∞ 则 θ P ( θ ) → ∞ \theta_P(\theta)\to\infty θP(θ)→∞ θ P ( x ) max α , β ; α i ≥ 0 [ f ( x ) ∑ i 1 k α i c i ( x ) ∑ j 1 l β j h j ( x ) ] ∞ \theta_P(x)\max\limits_{\alpha,\beta;\,\alpha_i\geq0}\left[f(x)\sum_{i1}^{k}\alpha_ic_i(x)\sum\limits_{j1}^l \beta_jh_j(x)\right]\infty θP(x)α,β;αi≥0max[f(x)i1∑kαici(x)j1∑lβjhj(x)]∞
若 x x x 满足原始问题的约束则 ∑ i 1 k α i c i ( x ) ≤ 0 \sum\limits_{i1}^{k}\alpha_ic_i(x)\leq 0 i1∑kαici(x)≤0 ∑ j 1 l β j h j ( x ) 0 \sum\limits_{j1}^l \beta_jh_j(x)0 j1∑lβjhj(x)0 因此 θ P ( x ) f ( x ) \theta_P(x)f(x) θP(x)f(x)
基于 θ P ( x ) \theta_P(x) θP(x) 的性质我们考虑其极小化问题 min x θ P ( x ) min x max α , β ; α i ≥ 0 L ( x , α , β ) \min_{x}\theta_P(x)\min_{x}\max\limits_{\alpha,\beta;\,\alpha_i\geq0}L(x,\alpha,\beta) xminθP(x)xminα,β;αi≥0maxL(x,α,β) 它与原始问题 P P P 是等价的因为 x x x 满足约束条件时 θ P ( x ) \theta_P(x) θP(x) 和 f ( x ) f(x) f(x) 是等价的。以上这个问题称为广义拉格朗日函数的极小极大问题。我们定义原始问题的最优值 p ∗ min x θ P ( x ) p^\ast\min_x\theta_P(x) p∗xminθP(x) 称为原始问题的值。
对偶问题
以下是一个关于 α \alpha α 和 β \beta β 的函数下标 D D D 代表对偶问题 θ D ( α , β ) min x L ( x , α , β ) \theta_D(\alpha,\beta)\min_xL(x,\alpha,\beta) θD(α,β)xminL(x,α,β) 再考虑 θ D ( α , β ) \theta_D(\alpha,\beta) θD(α,β) 的极大化问题 max α , β ; α i ≥ 0 θ D ( α , β ) max α , β ; α i ≥ 0 min x L ( x , α , β ) \max\limits_{\alpha,\beta;\,\alpha_i\geq0}\theta_D(\alpha,\beta)\max\limits_{\alpha,\beta;\,\alpha_i\geq0}\min_xL(x,\alpha,\beta) α,β;αi≥0maxθD(α,β)α,β;αi≥0maxxminL(x,α,β) 该问题称为广义拉格朗日函数的极大极小问题其还可以表示为约束最优化问题 max α , β ; α i ≥ 0 θ D ( α , β ) max α , β ; α i ≥ 0 min x L ( x , α , β ) s.t. α i ≥ 0 , i 1 , 2 , ⋯ , k \begin{aligned} \max\limits_{\alpha,\beta;\,\alpha_i\geq0}\, \theta_D(\alpha,\beta)\max\limits_{\alpha,\beta;\,\alpha_i\geq0}\min_xL(x,\alpha,\beta) \\ \text{s.t.}\,\, \alpha_i\geq 0, \quad i1,2,\cdots,k \end{aligned} α,β;αi≥0maxs.t.θD(α,β)α,β;αi≥0maxxminL(x,α,β)αi≥0,i1,2,⋯,k 极大极小问题称为原始问题的对偶问题定义对偶问题的最优值为 d ∗ max α , β ; α i ≥ 0 θ D ( α , β ) d^\ast\max\limits_{\alpha,\beta;\,\alpha_i\geq0}\theta_D(\alpha,\beta) d∗α,β;αi≥0maxθD(α,β) 称为对偶问题的值。
原始问题和对偶问题的关系
Th C.1若原始问题和对偶问题都有最优值则对偶问题的最优值小于等于原始问题的最优值 d ∗ ≤ p ∗ d^\ast \leq p^\ast d∗≤p∗ 证明由前面的定义得对于任意的 α \alpha α β \beta β x x x 有 θ D ( α , β ) min x L ( x , α , β ) ≤ L ( x , α , β ) ≤ max α , β ; α i ≥ 0 L ( x , α , β ) θ P ( x ) \theta_D(\alpha,\beta)\min_xL(x,\alpha,\beta)\leq L(x,\alpha,\beta)\leq\max\limits_{\alpha,\beta;\,\alpha_i\geq0}L(x,\alpha,\beta)\theta_P(x) θD(α,β)xminL(x,α,β)≤L(x,α,β)≤α,β;αi≥0maxL(x,α,β)θP(x) 即 θ D ( α , β ) ≤ θ P ( x ) \theta_D(\alpha,\beta)\leq\theta_P(x) θD(α,β)≤θP(x) 即 d ∗ max α , β ; α i ≥ 0 θ D ( α , β ) ≤ min x θ P ( x ) p ∗ d^\ast\max\limits_{\alpha,\beta;\,\alpha_i\geq0}\theta_D(\alpha,\beta)\leq\min_x\theta_P(x)p^\ast d∗α,β;αi≥0maxθD(α,β)≤xminθP(x)p∗ 推论 C.1设 x ∗ x^\ast x∗ 和 α ∗ \alpha^\ast α∗ β ∗ \beta^\ast β∗ 分别是原始问题和最优问题的可行解即满足约束条件且 d ∗ p ∗ d^\astp^\ast d∗p∗ 则 x ∗ x^\ast x∗ 和 α ∗ \alpha^\ast α∗ β ∗ \beta^\ast β∗ 分别是原始问题和最优问题的最优解。
Th C.2对于原始问题和对偶问题假设
函数 f ( x ) f(x) f(x) 和 c i ( x ) c_i(x) ci(x) 是凸函数 h j ( x ) h_j(x) hj(x) 是仿射函数存在 x x x 对于任意 i i i 满足 c i ( x ) 0 c_i(x)\lt 0 ci(x)0 即不等式约束 c i ( x ) c_i(x) ci(x) 严格可行
则存在 x ∗ x^\ast x∗ α ∗ \alpha^\ast α∗ β ∗ \beta^\ast β∗ 使得 x ∗ x^\ast x∗ 是原始问题的解 α ∗ \alpha^\ast α∗ β ∗ \beta^\ast β∗ 是对偶问题的解并且 p ∗ d ∗ L ( x ∗ , α ∗ , β ∗ ) p^\astd^\astL(x^\ast,\alpha^\ast,\beta^\ast) p∗d∗L(x∗,α∗,β∗) Th C.3跟 Th C.2 一样的假设下 x ∗ x^\ast x∗ 和 α ∗ \alpha^\ast α∗ β ∗ \beta^\ast β∗ 分别是原始问题和最优问题的可行解的充分必要条件是 x ∗ x^\ast x∗ α ∗ \alpha^\ast α∗ β ∗ \beta^\ast β∗ 满足 KKT 条件 ∇ x L ( x ∗ , α ∗ , β ∗ ) 0 α i ∗ c i ( x ∗ ) 0 , i 1 , 2 , ⋯ , k c i ( x ∗ ) ≤ 0 , i 1 , 2 , ⋯ , k α i ∗ ≥ 0 , i 1 , 2 , ⋯ , k h j ( x ∗ ) 0 , j 1 , 2 , ⋯ , k \begin{array}{c} \nabla_x L(x^\ast,\alpha^\ast,\beta^\ast)0 \\ \alpha_i^\ast c_i(x^\ast)0, \quad i1,2,\cdots,k \\ c_i(x^\ast)\leq 0, \quad i1,2,\cdots,k \\ \alpha_i^\ast \geq 0, \quad i1,2,\cdots,k \\ h_j(x^\ast)0, \quad j1,2,\cdots,k \\ \end{array} ∇xL(x∗,α∗,β∗)0αi∗ci(x∗)0,i1,2,⋯,kci(x∗)≤0,i1,2,⋯,kαi∗≥0,i1,2,⋯,khj(x∗)0,j1,2,⋯,k 其中 α i ∗ c i ( x ∗ ) 0 , i 1 , 2 , ⋯ , k \alpha_i^\ast c_i(x^\ast)0, \quad i1,2,\cdots,k αi∗ci(x∗)0,i1,2,⋯,k 称为 KKT 的对偶互补条件。由此可知若 α i 0 \alpha_i \gt 0 αi0 则 c i ( x ∗ ) 0 c_i(x^\ast)0 ci(x∗)0
