#!/usr/bin/env python
# coding: utf-8

# 假设$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*} \\&  \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*}

# In[ ]: