假设$f \left( x \right), c_{i} \left( x \right), h_{j} \left( x \right)$是定义在$R^{n}$上的连续可微函数。
称约束最优化问题
\begin{align*} \\& \min_{x \in R^{n}} \quad f \left( x \right)
\\ & s.t. \quad c_{i} \left( x \right) \leq 0, \quad i = 1,2, \cdots, k
\\ & \quad \quad h_{j} \left( x \right) = 0, \quad j=1,2, \cdots, l\end{align*}
为原始最优化问题或原始问题。
引入拉格朗日函数
\begin{align*} \\& L \left( x, \alpha, \beta \right) = f \left( x \right) + \sum_{i=1}^{k} \alpha_{i} c_{i} \left( x \right) + \sum_{j=1}^{l} \beta_{j} h_{j}\left( x \right) \end{align*}
其中,$x=\left(x^{\left( 1 \right)}, x^{\left( 2 \right)}, \cdots, x^{\left( n \right) } \right)^{T} \in R^{n}, \alpha_{i}, \beta_{j}$是拉格朗日乘子,$\alpha_{i} \geq 0$。
构建关于$x$的函数
\begin{align*} \\& \theta_{P} \left( x \right) = \max_{\alpha, \beta; \alpha_{i} \geq 0} L \left( x, \alpha, \beta \right) \end{align*}
假设给定某个违反原始问题约束条件的$x$,即存在某个$i$使得$c_{i} \left( x \right) > 0$或$h_{j} \left( x \right) \neq 0$。若$c_{i} \left( x \right) > 0$,可令$\alpha_{i} \to +\infty$,使得$\theta_{P} \left( x \right)=+\infty$;若$h_{j} \left( x \right) \neq 0$,可令$\beta_{j}$使$ \beta_{j} h_{j} \left( x \right) \to +\infty$,使得$\theta_{P} \left( x \right)=+\infty$。将其余$\alpha_{i}, \beta_{j}$均取值为0。
即
\begin{align*} \\& \theta_{P} \left( x \right) = \max_{\alpha, \beta; \alpha_{i} \geq 0} \left[ f \left( x \right) + \sum_{i=1}^{k} \alpha_{i} c_{i} \left( x \right) + \sum_{j=1}^{l} \beta_{j} h_{j}\left( x \right)\right] = +\infty \end{align*}
假设给定某个符合原始问题约束条件的$x$,即$c_{i} \left( x \right) \leq 0$且$h_{j} \left( x \right) = 0$,
则
\begin{align*} \\& \theta_{P} \left( x \right) =\max_{\alpha, \beta; \alpha_{i} \geq 0} \left[ f \left( x \right) + \sum_{i=1}^{k} \alpha_{i} c_{i} \left( x \right) + \sum_{j=1}^{l} \beta_{j} h_{j}\left( x \right)\right]= f \left( x \right) \end{align*}
由以上,得
\begin{align*} \theta_{P} \left( x \right) = \left\{
\begin{aligned}
\ & f \left( x \right), x满足原始问题约束
\\ & +\infty, 否则
\end{aligned}
\right.\end{align*}
则极小化问题
\begin{align*} \\& \min_{x} \theta_{P} \left( x \right) = \min_{x} \max_{\alpha, \beta; \alpha_{i} \geq 0} L \left( x, \alpha, \beta \right)\end{align*}
与原始最优化问题等价,即有相同的解。
称为广义拉格朗日函数的极小极大问题。
定义原始问题的最优值 \begin{align*} \\& p^{*} = \min_{x} \theta_{P} \left( x \right) \end{align*} 称为原始问题的值。
构建关于$\alpha, \beta$的函数
\begin{align*} \\& \theta_{D} \left( \alpha, \beta \right) = \min_{x} L \left( x, \alpha, \beta \right)\end{align*}
则极大化问题
\begin{align*} \\& \max_{\alpha,\beta;\alpha_{i} \geq 0} \theta_{D} \left( \alpha, \beta \right) = \max_{\alpha,\beta;\alpha_{i} \geq 0} \min_{x} L \left( x, \alpha, \beta \right) \end{align*}
称为广义拉格朗日函数的极大极小问题。
将广义拉格朗日函数的极大极小问题表示为约束最优化问题
\begin{align*} \\& \max_{\alpha,\beta;\alpha_{i} \geq 0} \theta_{D} \left( \alpha, \beta \right) = \max_{\alpha,\beta;\alpha_{i} \geq 0} \min_{x} L \left( x, \alpha, \beta \right)
\\ & \quad s.t. \quad \alpha_{i} \geq 0, \quad i =1,2, \cdots, k \end{align*}
称为原始问题的对偶问题。
定义对偶问题的最优值 \begin{align*} \\& d^{*} = \max_{\alpha, \beta;\alpha_{i} \geq 0} \theta_{D} \left( \alpha, \beta \right) \end{align*} 称为对偶问题的值。
若原始问题与对偶问题都有最优解,则 \begin{align*} \\& d^{*} = \max_{\alpha,\beta;\alpha_{i} \geq 0} \min_{x} L \left( x, \alpha, \beta \right) \leq \min_{x} \max_{\alpha, \beta; \alpha_{i} \geq 0} L \left( x, \alpha, \beta \right) = p^{*}\end{align*}
对于原始问题及其对偶问题,假设函数$f \left( x \right)$和$c_{i} \left( x \right)$是凸函数,$h_{j} \left( x \right)$是仿射函数,且不等式约束$c_{i} \left( x \right)$是严格可行的,即存在$x$,对所有$i$有$c_{i} \left( x \right) < 0$,则存在$x^{*}, \alpha^{*}, \beta^{*}$,使$x^{*}$是原始问题的解,$\alpha^{*}, \beta^{*}$是对偶问题的解,并且 \begin{align*} \\& p^{*}=d^{*} = L \left( x^{*}, \alpha^{*}, \beta^{*} \right) \end{align*}
对于原始问题及其对偶问题,假设函数$f \left( x \right)$和$c_{i} \left( x \right)$是凸函数,$h_{j} \left( x \right)$是仿射函数,且不等式约束$c_{i} \left( x \right)$是严格可行的,即存在$x$,对所有$i$有$c_{i} \left( x \right) < 0$,则存在$x^{*}, \alpha^{*}, \beta^{*}$,使$x^{*}$是原始问题的解,$\alpha^{*}, \beta^{*}$是对偶问题的解的充分必要条件是$x^{*}, \alpha^{*}, \beta^{*} $满足下面的Karush-Kuhn-Tucker(KKT)条件: \begin{align*} \\& \nabla _{x} L \left( x^{*}, \alpha^{*}, \beta^{*} \right) = 0 \\ & \nabla _{\alpha} L \left( x^{*}, \alpha^{*}, \beta^{*} \right) = 0 \\ & \nabla _{\beta} L \left( x^{*}, \alpha^{*}, \beta^{*} \right) = 0 \\ & \alpha_{i}^{*} c_{i} \left( x^{*} \right) = 0,\quad i= 1, 2, \cdots, k \\ & c_{i} \left( x^{*} \right) \leq 0, \quad i=1,2, \cdots, k \\ & \alpha_{i}^{*} \geq 0, \quad i=1,2, \cdots, k \\ & h_{j} \left( x^{*} \right) = 0, \quad j=1,2, \cdots, l\end{align*}