Lagrange与KKT的简易解释

2023-11-20 16:10

文章标签 解释 lagrange 简易 kkt

本文主要是介绍Lagrange与KKT的简易解释，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文将以梯度下降法的方式来解释Lagrange和KKT。

关键词：梯度下降法、等高线

基础定义

Lagrange

求解等式约束下的最优化问题

$\min_x f(x), s.t. h_k(x)=0, k=1,2,...,m$

Lagrange函数： $L(\lambda_{1,2,...,m} ,x) = f(x) + \sum_{i=1}^m\lambda_i\cdot h_i(x)=f(x)+\lambda\cdot h(x)$ (1)

方程组 $\{\frac{\partial L}{\partial x}=0, \frac{\partial L}{\partial \lambda_1}=0 , \frac{\partial L}{\partial \lambda_2}=0, ... , \frac{\partial L}{\partial \lambda_m}=0\}$ 的解是原问题的可能的最优解

KKT

求解不等式约束下的最优化问题

$\min_x f(x) \\ s.t. h_k(x)=0, k=1,2,...,m \\ g_t(x)=0, t=1,2,...,n$

Lagrange函数： $L(\lambda, \mu ,x) = f(x) + \sum_{i=1}^m\lambda_i\cdot h_i(x) + \sum_{j=1}^n\mu_j\cdot g_j(x) \\=f(x)+\lambda\cdot h(x)+\mu\cdot g(x), \; \mu_j\geq0$ (2)

方程组 $\{h_i(x)=0, g_j(x)\leq 0, \mu_j\geq0, \frac{\partial L}{\partial x}=0, \mu_j\cdot g_j=0\}$ ，即KKT条件，的解是原问题的可能的最优解

解释

梯度的定义

$\lim_{\Delta x}\frac{f(x+\Delta x)-f(x)}{\Delta x}=\nabla f$ ， ${f(x+\delta x)-f(x)}= {\delta x} \cdot \nabla f$

等式约束

因为在最小化f(x)的同时必须要满足等式约束h(x)=0，即x的更新 $\delta x$ 要满足 ${h(x+\delta x)-h(x)}=0= {\delta x} \cdot \nabla h$ ，即 $\delta x$ 必须要正交与h的梯度 $\nabla h$ ，而要想f(x)的取得最小则更新 $\delta x$ 必须无法再减小f(x)的值，即要满足 ${f(x+\delta x)-f(x)}=0= {\delta x} \cdot \nabla f$ ，即 $\delta x$ 必须要正交与f的梯度 $\nabla f$ ，所以最小点处有 $\nabla h$ 、 $\nabla f$ 平行，即 $\nabla f + \lambda \cdot \nabla h = 0 = \partial_x L$ ，当然还要满足约束h(x)=0。

不等式约束

不等式约束的情况比等式约束复杂些，分以下两种情况讨论：

最小点处于约束空间之内

此时，不等约束相当于没有约束，此时最小化f(x)，则有 $\nabla f + \lambda \cdot \nabla h = 0$ ；当然，由于最小点可能有多个，仍需不等约束进行过滤，即最小点需满足 $\{\nabla f + \lambda \cdot \nabla h = 0=\nabla f+\lambda \cdot \nabla h+\mu \cdot \nabla g= \partial_x L, \mu = 0; \;\; h(x)= 0, g(x)\leq 0 \}$

最小点不在约束空间之内

由于约束g(x)是个有上界的函数，约束下的最小点必然是在约束的上界处即g(x)=0处（由于此时f与g的梯度方向相反，所以有要求 $\mu\geq0$ ），即不等约束退化为等式约束，同等式约束的分析，即此时有 $\{\nabla f + \lambda \cdot \nabla h + \mu \cdot \nabla g = 0= \partial_x L, \; \mu \geq 0, \; g(x) = 0, \; h(x)= 0 \}$

综合

综合上述两种情况，即有 $\{\nabla f + \lambda \cdot \nabla h + \mu \cdot \nabla g = 0= \partial_x L, \; \mu \cdot g(x) = 0, \; \mu \geq 0, \; g(x) \leq 0, \; h(x)= 0 \}$ ，即KKT条件。