我們定義Lagrange對(duì)偶函數(shù)：

[g:mathbb{R}^{m} imesmathbb{R}^{p}longrightarrow mathbb{R},
]

egin{equation}g(lambda,
u)=inf_{xin D}L(x,lambda,
u)end{equation}

值得注意的是，無(wú)論 (f_{i}), (h_{i})是否為凸函數(shù)，Lagrange 對(duì)偶函數(shù)(g)都將是凹函數(shù)。另外，對(duì)于任意的(xinmathbb{R}^{n})滿足(1)中的約束條件以及((lambda,
u)inmathbb{R}^{m} imesmathbb{R}^{p}),(lambdasucceq 0)
egin{split}g(lambda,
u)leq L(x,lambda,
u)&=f_{0}(x)+sum_{i=1}^{{m}lambda_{i}f_{i}(x)+sum_{i=1}}{p}
u_{i}h_{i}(x)
ewline &leq f_{0}(x),end{split}
上式兩邊同時(shí)取下確界"(inf_{C})"我們得到：

egin{equation}
g(lambda,
u)leq p^{ast}
end{equation}

現(xiàn)在我們考慮如下的優(yōu)化問(wèn)題：
egin{equation}egin{split}maxquad & g(lambda,
u)
ewline ext{subject to:}quad & lambdasucceq 0 end{split}end{equation}
則我們稱該問(wèn)題是原始問(wèn)題(1)的"Lagrange對(duì)偶問(wèn)題",簡(jiǎn)稱"對(duì)偶問(wèn)題"。

這時(shí)我們?cè)O(shè)(q^{ast})為上述問(wèn)題的最優(yōu)值，即(q^{ast}=sup_{lbracelambdasucceq 0brace}g(lambda,
u)), 則由（4）可知(q^{ast}leq p^{ast})。我們?cè)倭?d^{ast}=p^{ast}-q^{ast}), 稱(d^{ast})為原問(wèn)題和對(duì)偶問(wèn)題之間的差距(gap). 進(jìn)一步，如果(d^{ast}=0),我們稱原問(wèn)題和對(duì)偶問(wèn)題是強(qiáng)對(duì)偶的。

egin{equation}mathcal{G} riangleqlbrace (f_{1}(x),...,f_{m}(x),h_{1}(x),...,h_{p}(x),f_{0}(x))in mathbb{R}^{{m} imesmathbb{R}}{p} imesmathbb{R}mid xin D braceend{equation}

這時(shí)候很容易知道：

egin{equation}p^{ast}=inflbrace tmid (u,v,t)in mathcal{G}, upreceq 0, v=0braceend{equation}

對(duì)于任意的(lambdainmathbb{R}^{m}), (
uinmathbb{R}^{p}), (xin D), 過(guò)點(diǎn)(p riangleq (f_{1}(x),...,f_{m}(x),h_{1}(x),...,h_{p}(x),f_{0}(x)))與向量((lambda,
u,1))垂直的超平面為：

[lambdacdot u+
ucdot v+t-L(x,lambda,
u)=0
]

該超平面在(t)軸上的截距正好就是Lagrange函數(shù)在((x,lambda,
u))處的取值！！！

由以上觀察我們?nèi)菀椎贸?g(lambda,
u))的幾何意義：

(g(lambda,
u))是與((lambda,
u,1))垂直且與集合(mathcal{G})相交的超平面的t-截距的最小值!!!!,

（注意，“最小值”是不嚴(yán)謹(jǐn)?shù)恼f(shuō)法，其實(shí)應(yīng)該是下確界，但是為了方便理解而這么將錯(cuò)就錯(cuò)，畢竟這里我們是形象描述！！！）

如上圖所示，在這里我們畫出了一個(gè)無(wú)等式約束條件，二維情形下對(duì)應(yīng)的示意圖。如圖所示，(g(lambda)) 是以(-t)為斜率的一條直線在t軸上的截距。可以觀察到該直線要是繼續(xù)向下平移的話將不再和(mathcal{G})相交。同時(shí)我們注意到，當(dāng)(lambdageq 0)時(shí)，(g(lambda)<p^{ast})，這時(shí)(gap)嚴(yán)格大于零， 這似乎時(shí)是因?yàn)橛捎?mathcal{G})的非凸性并且(mathcal{G})的右半部分，也就是(ugeq 0)部分的最低點(diǎn)比左半部分更低造成的。

為了研究方便，我們引入“上鏡圖”（Epigrah）的概念。我們定義集合：

egin{equation}mathcal{A}=lbrace p+ (u,0,t)in mathbb{R}^{{m} imesmathbb{R}}{p} imesmathbb{R}mid pin mathcal{G}, uin mathbb{R}^{m},usucceq 0, tin mathbb{R}, tgeq 0braceend{equation}
并稱之為最優(yōu)化問(wèn)題(1)的上鏡圖（Epigrah)。容易看出，上鏡圖是由(mathcal{G})的一系列正向平移所構(gòu)成。

如圖所示，我們這里畫出了和上圖情形之下的上鏡圖(mathcal{A})的示意圖。我們?nèi)菀昨?yàn)證如下的性質(zhì)：

定理：如果原問(wèn)題(1)是一個(gè)凸優(yōu)化問(wèn)題，存在( ilde{x}in ext{relint} D) 使得：(f_{i}( ilde{x})<0), 對(duì)任意的(i=1,...,m), 則原問(wèn)題和對(duì)偶問(wèn)題是強(qiáng)對(duì)偶的。

證明：
我們不妨假設(shè)仿射函數(shù)：
(h_{i}(x)=sum_{j=1}^{n}a_{ij}x_{j}+b_{i}), 且矩陣(A=(a_{ij}))滿足(rank(A)=p),否則我們可以進(jìn)一步減少等式約束條件的數(shù)量，得到等價(jià)的凸優(yōu)化問(wèn)題，而(d^{ast})保持不變。

我們令集合：

[mathcal{B}=lbrace (u,0,t)in mathbb{R}^{m} imesmathbb{R}^{p} imesmathbb{R}mid upreceq 0,t<p^{ast} brace$$,
此時(shí)$mathcal{B}$與上鏡集$mathcal{A}$交集為空，它們均為凸集。于是由凸集分離定理，存在超平面分離兩集合，也就是存在著$(lambda_{0},
u_{0},t_{0})
eq 0inmathbb{R}^{m} imesmathbb{R}^{p} imesmathbb{R}$以及$binmathbb{R}$使得：
對(duì)任意的$xin D$, $xi in mathbb{R}_{+}^{m}$和$tinmathbb{R}_{+}$：
egin{equation}sum_{i=1}^{m}lambda_{0,i}(f_{i}(x)+xi_{i})+sum_{i=1}^{p}v_{0,i}h_{i}(x)+t_{0}(f_{0}(x)+t)geq bend{equation}
且對(duì)任意的$uin mathbb{R}^{m}$,$upreceq 0$, $t<p^{ast}$:
egin{equation}lambda_{0}cdot u+t_{0}tleq bend{equation}
由（9）中的任意性我們立即可以知道$lambda_{0}succeq 0$,$t_{0}geq 0$, 這時(shí)我們令(10)中$uightarrow 0$,$tightarrow p^{ast}$，可以知：$t_{0}p^{ast}leq b$，于是我們?cè)俳Y(jié)合（9）可知對(duì)任意$xin D$：
egin{equation}sum_{i=1}^{m}lambda_{0,i}f_{i}(x)+sum_{i=1}^{p}v_{0,i}h_{i}(x)+t_{0}f_{0}(x)geq t_{0}p^{ast}.end{equation}
我們注意到，如果這時(shí)候$t_{0}>0$則上式兩邊同時(shí)除以$t_{0}$我們立即得到對(duì)任意的$xin D$：
$$L(x,lambda_{0}/t_{0},
u_{0}/t_{0})geq p^{ast},]

這時(shí)我們立即得到：
(g(lambda_{0}/t_{0},
u_{0}/t_{0})geq p^{ast}), 于是強(qiáng)對(duì)偶成立。