在我们的实际生活中，优化问题通常包括三类：无约束优化问题，等式约束优化问题以及不等式约束优化问题。其中无约束问题求解最为简单，直接求导验证即可。而带有约束条件的问题则比较棘手，往往不能通过简单的消元法求解。这时，我们可以通过构造$Lagrange$函数，将约束问题的目标函数和约束条件加以结合。此时，问题简化为无约束问题，我们就能通过求解$Lagrange$函数的优化问题来得到原约束问题的近似解。

算法框架

构造对应的$Lagrange$函数
求解变量的偏导方程
将结果代入目标函数

下面我们对等式约束问题和不等式约束问题分别进行讨论。

等式约束问题的乘子法

考虑如下等式约束问题：
$$
\min f(x),\ \ \\\text{s.t. }h_i(x)=0, \ \ (i\in E={1,\cdots,m_1})
$$

定义如下函数$\tilde{L}_\mu{(x)}$

$$
\tilde{L}_\mu(x)=L(x,\lambda^*)+\frac{1}{2}\mu S(x)
$$
其中，
$$
L(x, \lambda)=f(x)-\sum_{i \in E} \lambda_{i} h_{i}(x)
$$
称为$Lagrange$函数，
$$
S(x)=\left|h_{E}(x)\right|^{2}=\sum_{i \in E} h_{i}(x)^{2}
$$
称为约束破坏度函数。

`数值算法流程`：等式约束问题的乘子法

取初始点$x^{(0)}\in R^n$，$初始乘子\lambda_i^{(0)}\in,(i\in E)$。给定参数序列${\mu_k}$，算法精度$\varepsilon>0$。令$k:=0$。
构造增广$Lagrange$函数：
$$
L_{\mu_{k}}\left(x, \lambda^{(k)}\right)=L\left(x, \lambda^{(k)}\right)+\frac{1}{2} \mu_{k} S(x)
$$
其中，
$$
L\left(x, \lambda^{(k)}\right)=f(x)-\sum_{i \in E} \lambda_{i}^{(k)} h_{i}(x), \quad S(x)=\left|h_{E}(x)\right|^{2}=\sum_{i \in E} h_{i}^{2}(x)
$$
以$ x^{(k-1)} $作为初始点，$(k=0$时，初始点任意$)$，求解无约束问题：
$$
\min L_{\mu_{k}}\left(x, \lambda^{(k)}\right), \quad\left(x \in \mathrm{R}^{n}\right)
$$
得解$x^{(k)}$。
若
$$
\left|h_{E}\left(x^{(k)}\right)\right|=S\left(x^{(k)}\right)^{1 / 2} \leqslant \varepsilon
$$
得解$x^{(k)}$。
乘子迭代：
$$
\lambda_{i}^{(k+1)}=\lambda_{i}^{(k)}-\mu_{k} h_{i}\left(x^{(k)}\right), \quad(i \in E)
$$
令$k:=k+1$。转1。

【例1】

设有如下等式约束问题：
$$
\begin{array}{l}
\min f(x)=x_{1}^{2}-3 x_{2}-x_{2}^{2} \\
\text { s.t. } h(x)=x_{2}=0
\end{array}
$$
取$\lambda_0 = -1$，$\mu_k=6$。该问题最优解为$x^{*}=(0,0)^\text{T}$，相应的$Lagrange$乘子为$\lambda^{*}=-3$。

解　　该问题的增广$Lagrange$函数为：
$$
L_{\mu}(x, \lambda)=x_{1}^{2}-3 x_{2}-x_{2}^{2}-\lambda x_{2}+\frac{1}{2} \mu x_{2}^{2}
$$
其无约束问题$\min L_{\mu_{k}}\left(x, \lambda_{k}\right)$的解为：
$$
x^{(k)}=\left(0, \frac{3+\lambda_{k}}{\mu_{k}-2}\right)^{\mathrm{T}}=\left(0, \frac{3+\lambda_{k}}{4}\right)^{\mathrm{T}}
$$
乘子迭代格式为：
$$
\begin{aligned}
\lambda_{k+1} &=\lambda_{k}-\mu_{k} x_{2}^{(k)}=-\frac{9}{2}-\frac{1}{2} \lambda_{k} \\
&=-\frac{9}{2}\left[1-\frac{1}{2}+\frac{1}{2^{2}}-\cdots+(-1)^{k} \frac{1}{2^{k}}\right]+(-1)^{k} \frac{1}{2^{k+1}} \lambda_{0} \\
&=-3\left[1-(-1)^{k+1} \frac{1}{2^{k+1}}\right]+(-1)^{k+1} \frac{1}{2^{k+1}} \\
&=-3+(-1)^{k+1} \frac{1}{2^{k}} \rightarrow-3=\lambda^{*}
\end{aligned}
$$
从而解得：
$$
x^{(k)}=\left(0,(-1)^{k} \frac{1}{2^{k+1}}\right)^{\mathrm{T}} \rightarrow(0,0)^{\mathrm{T}}=x^{*}
$$