对于一个函数f:Rn→R（不要求是凸函数），我们可以定义它的共轭函数f:Rn→R为：
f(y)=supx∈domf(yTxf(x))
按照上面的定义，这个函数值是有可能取到∞的，这并不是我们希望的结果。因此我们规定，使函数值有界的y的取值范围就是共轭函数的定义域。
下面是一些常用函数的对偶函数：
这个函数的几何意义可以通过下图解释：
的距离。这个距离显然在图中的黑点处取到最大值，也就是最小上界。共轭函数就是描述这个最小上界随着
y
的变化所变化的情况。
很容易看出不管原函数的凹凸性如何，共轭函数一定是凸函数（可以由凸函数性质看出，这里不细说）。
对于一个标准形式的优化问题：
minimizesubjecttof0(x)fi(x)≤0,i=1,…,mhi(x)=0,i=1,…,p
这里我们并没有假定这个问题是凸的。
拉格朗日函数就是将目标函数和约束进行有权重的求和：
L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x)
这个函数不仅仅是x的函数，还是拉格朗日乘子向量λ和ν的函数。其中λi被称为对应于不等约束fi(x)≤0的拉格朗日乘子；νi被称为对应于相等约束hi(x)=0的拉格朗日乘子。
拉格朗日对偶函数，或者直接叫对偶函数，被定义为拉格朗日函数在x自由变化时所取到的最小值：
g(λ,ν)=infx∈D(f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x))
很显然，这是一个关于拉格朗日乘子向量λ,ν的函数。可以通过凸函数的性质发现无论原优化问题的凹凸性，这个对偶函数始终是凹的。
假设原始问题目标函数最优值是p。如果令λ≥0，则对于任何一个原问题的可行解x~，都有fi(x~)≤0,hi(x~)=0。我们很容易发现：
∑i=1mλifi(x~)+∑i=1pνihi(x~)≤0
因此，很容易得到下面的不等式：
g(λ,ν)=infx∈DL(x,λ,ν)≤L(x~,λ,ν)≤f0(x~)
所以，我们可以得到：
g(λ,ν)≤p
但是需要注意的是，由于g(λ,ν)可能取到∞，此时这个下界没有任何意义。所以我们下面研究的问题都是在g函数不会取到无穷这样的定义域内进行的。
线性约束的问题的拉格朗日对偶函数可以通过对共轭函数来表达出来。考虑如下线性约束问题：
minimizesubjecttof0(x)Ax≤bCx=d
他的拉格朗日对偶函数为：
g(λ,ν)=infx(f0(x)+λT(Axb)+νT(Cxd))=bTλdTν+infx(f0(x)+(ATλ+CTν)Tx)=bTλdTνf0(ATλCTν)
对偶函数的定义域由共轭函数f的定义域所确定：
domg={(λ,ν)∣ATλCTν∈domf0}
由于我们知道g(λ,ν)是一定不会大于原问题的最优解的，我们可以通过构造一个如下的最优化问题来寻找原始优化问题的最优下界：
maximizesubjecttog(λ,ν)λ≥0
我们用(λ,ν)来代表这个问题找到最优时候的对应的拉格朗日乘子的值。
由于我们知道拉格朗日对偶函数g(λ,ν)一定是凹的（不论原始优化问题凹凸性如何），因此我们知道这个拉格朗日对偶问题一定是个凸优化问题。
上面形式的拉格朗日对偶问题很难在实际中求解。通常情况下为了求解，我们需要一些更明确的条件来把拉格朗日对偶问题表述出来。一般我们如下几种方法。
由定义消去下确界
如果拉格朗日函数能够简单的求得下确界。我们就可以直接消去原始问题的变量，得到明确的对偶问题。
例如对于：
minimizesubjecttoxTxAx=b
拉格朗日函数为L(x,ν)=xTx+νT(Axb)。这显然是个凸函数，我们可以直接求极值，令其导数为0：
xL(x,ν)=2x+ATν=0
可得x=(1/2)ATν，带入拉格朗日函数：
g(ν)=L((1/2)ATν,ν)=(1/4)νTAATνbTν
可以看到，这个问题的对偶问题变成了一个无约束的优化问题：
maximize(1/4)νTAATνbTν
隐式求解约束
有时候拉格朗日对偶函数可以取到无穷。为了得到有意义的解，我们可以求出对偶可行域，即让g(λ,ν)=infx∈DL(x,λ,ν)>∞成立所需要的约束。然后可得对偶问题。
例如对于标准线性规划问题：
minimizesubjecttocTxAx=bx0
拉格朗日函数为：
L(x,ν)=cTx∑i=1mλixi+νT(Axb)=bTν+(ATν+cλ)Tx
应用下确界运算，可以得到：
g(λ,ν)={bTν∞ATν+cλ=0otherwise.
则可以得到对偶问题为：
maximizesubjecttobTνATν+cλ=0λ0
也可以把这个问题写成这样的形式;
maximizesubjecttobTνATν+c0
共轭函数法
由于线性约束的问题和共轭函数有密切的关系，很多时候我们可以利用共轭函数来求解对偶问题的约束。
例如最大化熵问题：
minimizesubjecttof0(x)=∑i=1nxilogxiAx≤b1Tx=1
我们知道，负熵函数f(x)=xlogx的共轭函数是f(y)=ey1，定义域是R。可以看出上面f0的共轭函数是：
f0(y)=∑i=1neyi1
定义域是Rn。
由线性约束问题的对偶函数与共轭函数的关系可得：
g(λ,ν=bTλν∑i=1neaTiλν1=bTλνeν1∑i=1neaTiλ
这里ai是A矩阵的第i列。
所以，这个问题也转化为了一个无约束的优化问题：
maximizebTλνeν1∑i=1neaTiλ
如果我们把拉格朗日对偶问题的最优值记为d。相对于原始问题的最优值p，我们有如下关系：
d≤p
这个关系就被称为弱对偶关系。
弱对偶关系即使在d或p为无穷的时候也是成立的。如果原始问题是无界的，即p=∞,则d=∞,即拉格朗日对偶问题是不可行的。相应的，如果对偶问题无界，即d=∞，则p=∞，即原始问题是不可行的。
我们把原始问题和对偶问题最优值之间的差值pd称为最有对偶间隙（optimaldualitygap）。显然，这个值总是正的。
如果原始问题和对偶问题的最优值相等，即：
d=p
我们就称这种关系为强对偶关系。在这种情况下，我们仅仅从对偶问题中就可以知道原始问题的最优解。
通常情况下强对偶关系并不成立。但是如果原始问题是凸的，即对于这样的形式：
minimizesubjecttof0(x)fi(x)≤0,i=1,…,mAx=b
有f0,…,fm都是凸的，那么我们通常能够得到强对偶关系。但是这种情况下也存在两个问题都无可行解的情况，此时强对偶关系不成立。为了确保我们一定能得到强对偶关系，除了原始问题是凸的之外，我们还需要更多的限制条件。
一种经常被用到的条件是
可以证明，如果原问题是凸的，并且Slator条件成立的情况下，强对偶条件一定成立。
如果有一些不等约束是仿射的，Slator条件还可以被弱化。假设前k个不等约束是仿射的，则Slator条件可以被转化为：
即仿射的不等约束不必取严格小于。
此外，满足Slater’s条件（或RefinedSlater’s条件）不仅意味着（凸优化问题）强对偶性的成立，而且也表示当d>∞时，存在一组对偶变量(λ,ν)满足g(λ,ν)=d=p，即此时对偶最优值是可取到的。
现在假设我们现在已经知道了原始问题和对偶问题的最优值相等（强对偶）。x是原始问题的最优解，(λ,ν)是对偶问题的最优解。我们可以写出如下的式子：
f0(x)==≤≤g(λ,ν)infx(f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x))f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x)f0(x)
强对偶存在的情况下，上面的不等号都要取到等号。
这里有两个不等号，第三行取到等号的必要条件是：
f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x)=0
这个条件会出现在下面的KKT条件中。
而第四行取到等号的条件是：
∑i=1mλifi(x)=0
这个条件可以得到下面的互补松弛（Complementaryslackness）条件。
上面得到：
由于这个求和的每一项都小于等于0，所以我们可以得到：
λifi(x)=0,i=1,…,m
这就是著名的互补松弛条件。由这个条件我们可以得到如下结论：
互补松弛条件通常代表着一定物理意义。其中的乘子常常是一个明确的状态指示器。代表着约束的有效与否。
一般问题的KKT条件
将上面讨论的条件结合起来，我们就得到了著名的KKT条件：
fi(x)≤hi(x)=λi≥λifi(x)=f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x)=0,i=1,…,m0,i=1,…,p0,i=1,…,m0,i=1,…,m0
这里前两行条件是原始问题的约束，第三行是拉格朗日函数的要求，第四行是互补松弛条件，最后一行是对拉格朗日函数取极值时候带来的一个必要条件。
容易看出，由于最后一个条件的限制，对于任意优化问题，只要x和(λ,ν)是原始问题和对偶问题的最优解，则其一定满足KKT条件。即KKT条件是一组解成为最优解的必要条件。
凸问题的KKT条件
如果原始问题是凸的，则KKT条件也是充分的。这是因为KKT的最后一个条件在对拉格朗日函数取下确界的时候成为了充要条件。这时候我们有如下结论：
KKT条件的用途
KKT条件在优化问题中有重要意义。它可以用于如下方面：
上面的论述都是拉格朗日乘子法的数学基础。但是上面的公式无法解释一个问题：为何要如此构造拉格朗日函数？其背后的意义是什么？这一部分就试图来回答这个问题。
考虑这个决策变量是二维平面内点(x,y)的优化问题：
minimizesubjecttof(x,y)g(x,y)=c
我们在二维平面内画出两个函数的图像。由于缺少第三维，我们使用等高线来表示目标函数f(x,y)的函数值。如下图：
，则其梯度如图中绿色箭头所示。很容易看出来，要想让目标函数
f(x,y)
的等高线和约束相切，则他们切点的梯度一定在一条直线上，即：
f(x,y)=νg(x,y)
其中ν可以是任何实数。
因此，我们通过观察可以得到优化取到最小值的条件：
g(x,y)f(x,y)νg(x,y)=c=0
最为对比，我们使用前一部分推导的KKT条件来直接写出这个问题的KKT条件：
g(x,y)cf(x,y)+νg(x,y)=0=0
可以看到这两个条件几乎完全一样，唯一的不同就是ν的符号。由于我们并没有对ν的符号有任何限制，所以是否取负号对于这个问题没有任何影响。
仍然需要提醒的是，这些条件对于一般问题只是取到最优的必要条件。但是对于大多数凸问题来说，这个条件也是充分条件。具体情况请看上面公式推导。
上面仅仅考虑了等式约束的情况。那么含有不等式的约束情况下，λ乘子又有什么意义呢？
我们还是考虑一个和上面问题类似的问题：
minimizesubjecttof(x,y)g1(x,y)≤c,g2(x,y)≥d
我们同样在平面内画下这个问题的图像：
和
g(x,y)=d
来决定。
大家立刻可以从图中发现，这个问题的最优解和之前的等式约束情况下没有任何区别。也就是依然满足条件：
g1(x,y)f(x,y)νg1(x,y)=c=0
我们来看看不等约束的KKT条件怎么说：
g1(x,y)cdg2(x,y)λ1λ2λ1(g1(x,y)c)λ2(dg2(x,y))f(x,y)+λ1g1(x,y)λ2g2(x,y)≤0≤0≥0≥0=0=0=0
这两个条件看起来一点也不像。。。。。。好吧，让我们来仔细分析一下这个KKT条件。
这里的核心问题是互补松弛条件。我们上面已经说过了由于互补松弛条件的存在，λ乘子是一个非常明确的状态指示器。如果不等约束能够取到等号，则λ乘子是个正数；如果不等约束只能取严格不等，则λ乘子必然为0。我们也很容易从图里看出来，要想取到最优，我们首先需要：
g1(x,y)c=0
这时候我们有：
λ1>0,λ2=0
把这样两个关系带入KKT条件，可以得到：
g1(x,y)cf(x,y)+λ1g1(x,y)=0=0
果然和我们之前的最优点条件一模一样了。
由上面的问题可以看出来，不等约束的拉格朗日乘子λ确实就是一个状态指示器，它起到了一个开关的作用。当不等约束能够取到等号的时候，开关打开（λ>0），λ乘子的作用就和前面等式约束乘子ν的作用一样，使目标函数的梯度和约束的梯度保持线性关系；而不等约束无法取到等号的时候，开关关闭(λ=0)，λ乘子就带着对应的约束从梯度运算中消失了，并不去影响目标函数的梯度。