type
Post
status
Revise
password
date
Apr 12, 2023
slug
summary
category
人工智能
URL
tags
数学
icon
在求解最优化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。
拉格朗日函数
拉格朗日乘数法的思想是，通过引入拉格朗日乘子 、 将原来的约束优化问题转化为无约束的方程组问题。
计算示例
等式约束条件
对上式进行计算可得
通过求解上式可得，；当 时，或者 ，而当 时，无解。所以原问题的解为 或者 。
推导
等式约束条件
求函数 在满足 下的条件极值，可转化为函数 的无条件极值问题。我们可以画图来辅助思考。
绿线标出的是约束 的点的轨迹。蓝线是 的等高线。箭头表示斜率，和等高线的法线平行。从图上可以直观地看到在最优解处， 和 的斜率平行且相反的。
一旦求出 的值，将其带入下式，可以通过 求得 在无约束极值和极值所对应的点。
不等式约束条件
求函数 在满足 下的条件极值，可转化为函数 的无条件极值问题。我们可以画图来辅助思考，如下图所示， 有5个函数，即5个约束条件。
橙线标出的是约束 的点的轨迹。蓝线是 的等高线。箭头表示斜率，和等高线的法线平行。从图上可以直观地看到在最优解处， 和 的斜率平行且相反的。具体到上图示例，在最优值 的地方。
一旦求出 的值，将其带入下式，可以通过 求得 在无约束极值和极值所对应的点。
拉格朗日朗日求出的极值不一定是最优质，那么面对于非凸优化的话，我们可以用拉格朗日对偶函数来解决。拉格朗日对偶函数一定是凸优化。但是拉格朗日函数和对偶函数不是等价的。
原始问题
证明
对偶函数
对偶函数一定是凸优化问题
对偶函数是：
- 首先 一定是凸函数，假设当 的时候使得 。那么 ，公式中的 、、都是常数，所以一条直线也就是一个凸函数。
- 其次 是一个凸集
原问题与对偶问题的关系
原问题与对偶问题的等价条件
等价形式即强对偶关系
设和分别是原始问题和对偶问题的可行解，并且
则和分别是原始问题和对偶问题的最优解。
等价条件
- 原问题是一个凸优化问题。是凸函数，约束条件是凸集。
- slater条件（充分条件）
至少存在一个点可以让所有的
只有满足slater条件的凸函数才是强对偶关系。但是强对偶关系的问题不一定满足slater条件。
kkt条件
只要是强对偶关系的问题一定满足kkt条件，但是满足kkt条件的问题，不一定是强对偶关系。但是一般使用是认为只要满足kkt条件就是强对偶问题