利用拉格朗日对偶性求解带约束条件的最优化问题

创作时间:

作者:

@小白创作中心

利用拉格朗日对偶性求解带约束条件的最优化问题

引用

CSDN

https://m.blog.csdn.net/qq_44665283/article/details/136620754

拉格朗日对偶性是解决带约束条件最优化问题的重要工具，在机器学习、深度学习等领域有着广泛的应用。本文将详细介绍如何利用拉格朗日对偶性求解这类问题，包括原始问题的定义、对偶问题的构建以及KKT条件的应用。

1 原始问题

设 (f(x), c_i(x), h_j(x)) 是定义在 (\mathbb{R}^n) 的连续可微函数，求解在下面约束条件时，(f(x)) 的极小值：

[
\min_{x \in \mathbb{R}^n} {f(x)} \
s.t. \quad c_i(x) \leq 0, \quad i = 1, 2, \ldots, k \
\quad \quad \quad h_j(x) = 0, \quad j = 1, 2, \ldots, l
]

这就是带有约束条件的原始问题。

需要用到拉格朗日乘子法，将不等式换成等式，那么我们就可以引进广义拉格朗日函数：

[
L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)
]

对于每个约束条件前面都来加一个拉格朗日乘子，对应的 (\alpha_i) 有 (k) 维，对应的 (\beta_j) 有 (l) 维，而原始的 (f(x)) 有 (n) 维。

我们对广义拉格朗日函数先最大化、后最小化。我们令：

[
\theta_P(x) = \max_{\alpha, \beta; \alpha_i \geq 0} L(x, \alpha, \beta)
]

因此，

[
\min_x [\theta_P(x)] = \min_x [ \max_{\alpha, \beta; \alpha_i \geq 0} L(x, \alpha, \beta) ]
= \min_x { f(x) + \max_{\alpha, \beta; \alpha_i \geq 0} [\sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)] }
]

其中，(P) 是 ([Primal])，即原始的含义。

拉格朗日函数为什么要先最大化呢？在满足KKT条件的情况下，公式(一)和公式(三)是等价的。暂且抛开KKT条件的具体细节。很明显，如果 (\alpha，\beta) 是非零常数，那么这两个式子是不可能相等的。现在把这两组乘子看成自变量，然后调节之使 (L(x, \alpha, \beta)) 最大化。

对于公式(三)，我们将 (x) 分成两部分分析：

可行解区域内，此时公式(一)中的约束条件都得到满足。因为 (h_j(x) = 0)，所以不管 (\beta) 如何变化，必然有 (\beta_j h_j(x) = 0)。(c_i(x) \leq 0)，且限定了 (\alpha_i \geq 0)，则 (\alpha_i c_i(x)) 最大值为0。综上，在可行解区域内 (\theta_P(x) = f(x))。
可行解区域外，此时公式(一)的约束条件未满足。如果 (\alpha_i) 和 (\beta_j) 取无穷大，那么 (\theta_P(x) = +\infty)。

因此，综合上面两个论域，(f(x)) 在可行解区域内最小化，等于 (\max_{\alpha, \beta; \alpha_i \geq 0} L(x, \alpha, \beta)) 的最小化，而在可行解区域外，(\max_{\alpha, \beta; \alpha_i \geq 0} L(x, \alpha, \beta)) 无极值。这样当我们尝试最小化 (\max_{\alpha, \beta; \alpha_i \geq 0} L(x, \alpha, \beta)) 时也就相当于求解公式(一)了。即通过构造拉格朗日函数，我们将有约束的优化问题转化成了无约束的优化问题。

这个原始问题的最优值就可以写成：

[
p^* = \min_x \theta_P(x) = \min_x \max_{\alpha, \beta; \alpha_i \geq 0} L(x, \alpha, \beta)
]

这样就转为了极小极大值的问题，记为 (p^*)。