跳至内容
张叶安的小站
用户工具
登录
站点工具
搜索
工具
显示页面
过去修订
反向链接
最近更改
媒体管理器
网站地图
登录
>
最近更改
媒体管理器
网站地图
您的足迹:
最优化方法:第七章_等式约束优化
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
====== 第七章 等式约束优化 ====== ===== 本章导读 ===== 等式约束优化问题是最基本的约束优化问题形式。本章介绍求解等式约束问题的经典方法——拉格朗日乘子法,推导一阶必要条件(KKT条件的特例),并讨论二阶充分条件。 ===== 7.1 等式约束问题的一般形式 ===== **定义 7.1**(等式约束优化问题) 等式约束优化问题的标准形式为: $$\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & h_j(\mathbf{x}) = 0, \quad j = 1, 2, \ldots, l \end{aligned}$$ 其中 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是目标函数,$h_j: \mathbb{R}^n \rightarrow \mathbb{R}$ 是约束函数。 记约束向量 $\mathbf{h}(\mathbf{x}) = (h_1(\mathbf{x}), h_2(\mathbf{x}), \ldots, h_l(\mathbf{x}))^T$。 **可行域**:$\mathcal{F} = \{\mathbf{x} \in \mathbb{R}^n \mid h_j(\mathbf{x}) = 0, j = 1, \ldots, l\}$ ===== 7.2 拉格朗日乘子法 ===== ==== 7.2.1 拉格朗日函数 ==== **定义 7.2**(拉格朗日函数) 引入拉格朗日乘子 $\lambda_j \in \mathbb{R}$,定义拉格朗日函数: $$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^l \lambda_j h_j(\mathbf{x}) = f(\mathbf{x}) + \boldsymbol{\lambda}^T \mathbf{h}(\mathbf{x})$$ 其中 $\boldsymbol{\lambda} = (\lambda_1, \ldots, \lambda_l)^T$。 ==== 7.2.2 一阶必要条件 ===== **定理 7.1**(拉格朗日乘子定理/一阶必要条件) 设: 1. $f$ 和 $h_j$ 在 $\mathbf{x}^*$ 的邻域内连续可微 2. $\mathbf{x}^*$ 是局部最优解 3. 约束梯度 $\nabla h_1(\mathbf{x}^*), \ldots, \nabla h_l(\mathbf{x}^*)$ 线性无关(LICQ条件) 则存在拉格朗日乘子 $\boldsymbol{\lambda}^* \in \mathbb{R}^l$ 使得: $$\nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) = \nabla f(\mathbf{x}^*) + \sum_{j=1}^l \lambda_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}$$ 即: $$\nabla f(\mathbf{x}^*) + \nabla \mathbf{h}(\mathbf{x}^*) \boldsymbol{\lambda}^* = \mathbf{0}$$ 同时满足约束条件: $$h_j(\mathbf{x}^*) = 0, \quad j = 1, \ldots, l$$ ==== 7.2.3 几何解释 ==== 在最优解 $\mathbf{x}^*$ 处,目标函数的梯度可以表示为约束函数梯度的线性组合: $$\nabla f(\mathbf{x}^*) = -\sum_{j=1}^l \lambda_j^* \nabla h_j(\mathbf{x}^*)$$ 这意味着 $\nabla f(\mathbf{x}^*)$ 位于约束函数梯度张成的空间中,等价于 $\nabla f(\mathbf{x}^*)$ 与可行域在 $\mathbf{x}^*$ 处的切空间正交。 ===== 7.3 二阶条件 ===== ==== 7.3.1 切空间 ==== **定义 7.3**(切空间) 在可行点 $\mathbf{x}$ 处的切空间定义为: $$\mathcal{T}(\mathbf{x}) = \{\mathbf{d} \in \mathbb{R}^n \mid \nabla h_j(\mathbf{x})^T \mathbf{d} = 0, j = 1, \ldots, l\}$$ 即与所有约束梯度正交的方向集合。 ==== 7.3.2 二阶必要条件 ==== **定理 7.2**(二阶必要条件) 设: 1. $f$ 和 $h_j$ 在 $\mathbf{x}^*$ 处二阶连续可微 2. $\mathbf{x}^*$ 是局部最优解 3. LICQ条件成立 则对满足一阶条件的 $(\mathbf{x}^*, \boldsymbol{\lambda}^*)$,有: $$\mathbf{d}^T \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) \mathbf{d} \geq 0, \quad \forall \mathbf{d} \in \mathcal{T}(\mathbf{x}^*)$$ 即拉格朗日函数的Hesse矩阵在切空间上半正定。 ==== 7.3.3 二阶充分条件 ==== **定理 7.3**(二阶充分条件) 设: 1. $f$ 和 $h_j$ 在 $\mathbf{x}^*$ 处二阶连续可微 2. $(\mathbf{x}^*, \boldsymbol{\lambda}^*)$ 满足一阶必要条件 3. $$\mathbf{d}^T \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) \mathbf{d} > 0, \quad \forall \mathbf{d} \in \mathcal{T}(\mathbf{x}^*) \setminus \{\mathbf{0}\}$$ 则 $\mathbf{x}^*$ 是严格局部最优解。 ===== 7.4 求解方法 ===== ==== 7.4.1 直接求解KKT方程组 ==== 求解非线性方程组: $$\begin{cases} \nabla f(\mathbf{x}) + \nabla \mathbf{h}(\mathbf{x}) \boldsymbol{\lambda} = \mathbf{0} \\ \mathbf{h}(\mathbf{x}) = \mathbf{0} \end{cases}$$ 可用Newton法求解: $$\begin{bmatrix} \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L} & \nabla \mathbf{h} \\ \nabla \mathbf{h}^T & \mathbf{0} \end{bmatrix} \begin{bmatrix} \Delta \mathbf{x} \\ \Delta \boldsymbol{\lambda} \end{bmatrix} = -\begin{bmatrix} \nabla_{\mathbf{x}} \mathcal{L} \\ \mathbf{h} \end{bmatrix}$$ ==== 7.4.2 消元法(降维法) ==== 若约束函数简单,可从中解出某些变量,代入目标函数,转化为无约束问题。 ===== 7.5 例题详解 ===== **例 7.1** 求解: $$\begin{aligned} \min \quad & f(x, y) = x^2 + y^2 \\ \text{s.t.} \quad & x + y - 1 = 0 \end{aligned}$$ **解**: 拉格朗日函数:$\mathcal{L}(x, y, \lambda) = x^2 + y^2 + \lambda(x + y - 1)$ KKT条件: $$\begin{cases} 2x + \lambda = 0 \\ 2y + \lambda = 0 \\ x + y = 1 \end{cases}$$ 由前两式:$x = y = -\frac{\lambda}{2}$ 代入第三式:$-\lambda = 1$,即 $\lambda = -1$ 解得:$x^* = y^* = \frac{1}{2}$,$f^* = \frac{1}{2}$ 验证二阶条件:$\nabla^2 \mathcal{L} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}$,切空间 $\mathbf{d} = (1, -1)^T$,$\mathbf{d}^T \nabla^2 \mathcal{L} \mathbf{d} = 4 > 0$。严格最优。 **例 7.2** 求解: $$\begin{aligned} \min \quad & f(x, y, z) = x^2 + 2y^2 + z^2 \\ \text{s.t.} \quad & x + y + z = 3 \\ & x - y = 0 \end{aligned}$$ **解**: 拉格朗日函数:$\mathcal{L} = x^2 + 2y^2 + z^2 + \lambda_1(x+y+z-3) + \lambda_2(x-y)$ KKT条件: $$\begin{cases} 2x + \lambda_1 + \lambda_2 = 0 \\ 4y + \lambda_1 - \lambda_2 = 0 \\ 2z + \lambda_1 = 0 \\ x + y + z = 3 \\ x - y = 0 \end{cases}$$ 由 $x = y$,解得:$x = y = 1, z = 1, \lambda_1 = -2, \lambda_2 = 0$ ===== 7.6 习题 ===== **理论题** 1. 证明拉格朗日乘子定理的一阶必要条件。 2. 解释LICQ条件的几何意义。 3. 推导等式约束优化问题的KKT方程组的Newton迭代格式。 **计算题** 4. 用拉格朗日乘子法求解: $$\min x^2 + 2y^2 \quad \text{s.t.} \quad x + 2y = 2$$ 5. 求解: $$\min (x-1)^2 + (y-2)^2 + (z-3)^2 \quad \text{s.t.} \quad x + y + z = 1, \quad 2x - y = 0$$ **应用题** 6. 用消元法求解例7.1,验证与拉格朗日乘子法结果一致。 --- *本章完*
最优化方法/第七章_等式约束优化.txt
· 最后更改:
2026/02/03 19:45
由
127.0.0.1
页面工具
显示页面
过去修订
反向链接
回到顶部