class: center, middle, inverse, title-slide # 约束极值问题 ### 吴燕丰 ### School of Finance, JXUFE ### 2022/04/18 --- ### 约束极值问题 `\begin{align} \text{min}\quad & f(\mathbf{x})\quad \mathbf{x} \in \mathcal{R}^n\\ \text{s.t.}\quad & g_i(\mathbf{x}) \ge 0, i = 1,\cdots,m,\\ & h_j(\mathbf{x}) = 0, j = 1,\cdots,l, \end{align}` 可行集: $$ S = \\{ \mathbf{x} | g_i(\mathbf{x}) \ge 0, i=1,\cdots,m;h_j(\mathbf{x}) = 0, j = 1,\cdots,l.\\} $$ --- ### 等式约束优化问题 `\begin{align} \text{min}\quad & f(\mathbf{x})\quad \mathbf{x} \in \mathcal{R}^n\\ & h_j(\mathbf{x}) = 0, j = 1,\cdots,l, \end{align}` Lagrange方法 `\begin{align} \mathcal{L}(\mathbf{x},\lambda) \triangleq f(\mathbf{x}) + \lambda^T (h(\mathbf{x})-\mathbf{0}) \end{align}` Solution `\begin{align} \frac{\partial \mathcal{L}}{\partial x_i} &= 0, i=1,\cdots,n\\ \frac{\partial \mathcal{L}}{\partial \lambda_j} &=0,j=1,\cdots,l \end{align}` --- ### 不等式约束问题 `\begin{align} \text{min}\quad & f(\mathbf{x})\quad \mathbf{x} \in \mathcal{R}^n\\ \text{s.t.}\quad & g_i(\mathbf{x}) \ge 0, i = 1,\cdots,m, \end{align}` 对于某 `\(\mathbf{x}\)`,起作用约束小标集 $$ I \triangleq \\{i|g_i(\mathbf{x}) = 0\\} $$ 起作用约束 $$ g_i(\mathbf{x}) = 0 , i\in I $$ 不起作用约束 $$ g_i(\mathbf{x}) > 0, i\notin I $$ --- ### 下降方向与可行方向 - **下降方向** `\(f(\mathbf{x})\)` 在 `\(\mathbf{x}\)` 处的下降方向 `\(\mathbf{d}\)` : $$ F_0 = \\{ \mathbf{d}|\nabla f(\mathbf{x})^T \mathbf{d} < 0\\} $$ -- - **可行方向** $$ G_0 = \\{\mathbf{d}|\nabla g_i(\mathbf{x})^T\mathbf{d} > 0, i\in I \\} $$ 其中 `\(I\)` 为起作用约束下标集,即 $$ I = \\{i|g_i(\mathbf{x})=0\\}. $$ -- 局部最优解条件 $$ F_0 \cap G_o = \emptyset $$ --- ### 局部最优条件 下面不等式约束组无解, `\(\mathbf{x}\)` 已知, `\(\mathbf{d}\)` 未知 `\begin{cases} \nabla f(\mathbf{x})^T\mathbf{d} &< 0\\ \nabla g_i(\mathbf{x})^T\mathbf{d} &> 0, i\in I \end{cases}` 变换 `\begin{cases} \nabla f(\mathbf{x})^T\mathbf{d} &< 0\\ -\nabla g_i(\mathbf{x})^T\mathbf{d} &< 0, i\in I \end{cases}` -- 定义 `\(A\)` 矩阵为 `\begin{bmatrix} \nabla f(x_1) & \nabla f(x_2) & \cdots & \nabla f(x_n)\\ -\nabla g_1(x_1) & -\nabla g_1(x_2) & \cdots & -\nabla g_1(x_n)\\ \vdots & \vdots & \cdots & \vdots\\ -\nabla g_{|I|}(x_1) & -\nabla g_{|I|}(x_2) & \cdots & -\nabla g_{|I|}(x_n) \end{bmatrix}` --- ### 变换 下面不等式组无解 $$ A\mathbf{d} < \mathbf{0} $$ Fritz John条件、Gordan定理 存在非零向量 $$ \mathbf{w} = (w_0,w_i, i\in I) \ge 0 $$ 使得 `$$w_0 \nabla f(\mathbf{x}) - \sum_{i\in I} w_i \nabla g_i(\mathbf{x}) = \mathbf{0}$$` --- ### 开集合、闭集合 $$ [0,1) $$ --- ### Farkas定理 设 `\(\mathbf{A}\)` 为 `\(m\times n\)` 矩阵, `\(\mathbf{c}\)` 为 `\(n\)` 维向量,则 $$ \mathbf{Ax} \le \mathbf{0}, \mathbf{c}^T\mathbf{x} > 0 $$ 有解的充要条件是 $$ \mathbf{A^Ty} = \mathbf{c}, \mathbf{y} \ge \mathbf{0} $$ 无解 ### Gordan定理 设 `\(\mathbf{A}\)` 为 `\(m\times n\)` 矩阵,那么, $$ \mathbf{Ax} < 0 $$ 有解的充要条件是不存在非零向量 `\(\mathbf{y}\ge \mathbf{0}\)`,使得 $$ \mathbf{A}^T\mathbf{y} = \mathbf{0} $$ --- ### K-T条件 Kuhn-Tucker条件 设 `\(\bar{x}\in S\)`, `\(f\)`, `\(g_i(i\in I)\)` 在 `\(\bar{x}\)` 处可微, `\(g_i(i\notin I)\)` 在点 `\(\bar{x}\)` 连续,{ `\(\nabla g_i(\bar{x})|i\in I\)` }线性无关。若 `\(\bar{x}\)` 是局部最优解,则存在非负数 `\(w_i,i\in I\)` ,使得 $$ \nabla f(\bar{x}) - \sum_{i\in I} w_i \nabla g_i(\bar{x}) = \mathbf{0}. $$ 若 `\(g_i(i\notin I)\)` 在 `\(\bar{x}\)` 可微,则K-T条件可写成等价形式: `\begin{align} \nabla f(\bar{x}) - \sum_{i=1}^m w_i \nabla g_i(\bar{x}) = \mathbf{0},\\ w_i g_i(\bar{x}) = 0, i=1,\cdots,m,\\ w_i \ge 0, i = 1,\cdots,m. \end{align}` --- class: center, middle ### 留白 --- ### Zoutendijk 可行方向法 考虑非线性规划问题 `\begin{align} \text{min} \quad &f(\mathbf{x})\\ \text{s.t.} \quad &\mathbf{A}\mathbf{x} \ge b,\\ & \mathbf{Ex} = \mathbf{e} \end{align}` 设 `\(\hat{\mathbf{x}}\)` 是一个可行解,在点 `\(\hat{\mathbf{x}}\)` 处有 `\(\mathbf{A}_1\mathbf{\hat{x}} = \mathbf{b}_1, \mathbf{A}_1\mathbf{\hat{x}} > \mathbf{b}_2\)` ,其中 $$ \mathbf{A} = \begin{bmatrix}\mathbf{A}_1\\\\ \mathbf{A}_2 \end{bmatrix},\quad \mathbf{b} = \begin{bmatrix} \mathbf{b}_1 \\\\ \mathbf{b}_2 \end{bmatrix} $$ 则非零向量 `\(\mathbf{d}\)` 为 `\(\mathbf{\hat{x}}\)` 处的可行方向的充要条件是 `\begin{align} \mathbf{A}_1 \mathbf{d} \ge \mathbf{0},\\ \mathbf{E}\mathbf{d} = \mathbf{0}. \end{align}` --- ### 续 如果非零向量 `\(\mathbf{d}\)` 同时满足 `\(\nabla f(\mathbf{\hat{x}})^T \mathbf{d} < 0, \mathbf{A}_1\mathbf{d}\ge \mathbf{0}, \mathbf{Ed} = \mathbf{0}\)` ,则 `\(\mathbf{d}\)` 是 `\(\mathbf{\hat{x}}\)` 处的下降可行方向。 `\begin{align} \text{min} \quad &\nabla f(\mathbf{x})^T \mathbf{d}\\ \text{s.t.} \quad & \mathbf{A}_1\mathbf{d} \ge \mathbf{0},\\ & \mathbf{Ed} = \mathbf{0},\\ & |d_j| \le 1, j=1,\cdots,n. \end{align}` ``` if 目标函数最优值 < 0: 获得可行下降方向 d else: x 即是K-T点 ``` --- ### 一维搜索确定步长 `\begin{align} \text{min} \quad &f(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)})\\ \text{s.t.} \quad & \mathbf{A}(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)}) \ge \mathbf{b},\\ & \mathbf{E}(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)}) = \mathbf{e},\\ & \lambda \ge 0. \end{align}` 由于 `\(\mathbf{d}^{(k)}\)` 是可行方向,必有 $$ \mathbf{Ed}^{(k)} = \mathbf{0}, \mathbf{Ex}^{(k)} = \mathbf{e} $$ 化简为 `\begin{align} \text{min} \quad &f(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)})\\ \text{s.t.} \quad & \mathbf{A}(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)}) \ge \mathbf{b},\\ & \lambda \ge 0. \end{align}` --- ### 起作用约束和不起作用约束 `\begin{align} \mathbf{A}_1 \mathbf{x}^{(k)} &= \mathbf{b}_1,\\ \mathbf{A}_2 \mathbf{x}^{(k)} &> \mathbf{b}_2. \end{align}` 即 `\begin{align} \mathbf{A} = \begin{bmatrix} \mathbf{A}_1 \\ \mathbf{A}_2 \end{bmatrix}, \mathbf{b} = \begin{bmatrix} \mathbf{b}_1 \\ \mathbf{b}_2 \end{bmatrix}. \end{align}` $$ `\begin{bmatrix} \mathbf{A}_1 \mathbf{x}^{(k)} + \lambda \mathbf{A}_1 \mathbf{d}^{(k)} \\\\ \mathbf{A}_2 \mathbf{x}^{(k)} + \lambda \mathbf{A}_2 \mathbf{d}^{(k)} \end{bmatrix}` \ge `\begin{bmatrix} \mathbf{b}_1 \\\\ \mathbf{b}_2 \end{bmatrix}` $$ 由于 `\(\mathbf{d}^{(k)}\)` 为可行方向, `\(\mathbf{A}_1\mathbf{d}^{(k)} \ge \mathbf{0},\lambda \ge 0\)` 以及 `\(\mathbf{A}_1 \mathbf{x}^{(k)} = \mathbf{b}_1\)`,因此式中第一个不等式自然成立。剩下的约束为 $$ \mathbf{A}_2 \mathbf{x}^{(k)} + \lambda \mathbf{A}_2 \mathbf{d}^{(k)} \ge \mathbf{b}_2 $$ --- ### 一维搜索简化 `\begin{align} \text{min} \quad &f(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)})\\ \text{s.t.} \quad & \mathbf{A}_2\mathbf{x}^{(k)} + \lambda \mathbf{A}_2\mathbf{d}^{(k)} \ge \mathbf{b}_2,\\ & \lambda \ge 0. \end{align}` define $$ \hat{\mathbf{b}}\triangleq \mathbf{b}_2 - \mathbf{A}_2\mathbf{x}^{(k)}, \quad \hat{\mathbf{d}} \triangleq \mathbf{A}_2\mathbf{d}^{(k)}. $$ Then `\begin{align} \text{min} \quad &f(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)})\\ \text{s.t.} \quad &\lambda\hat{\mathbf{d}} \ge \hat{\mathbf{b}}, \\ & \lambda \ge 0. \end{align}` --- ### `\(\lambda\)` 的上限 $$ \lambda_{\text{max}} = `\begin{cases} \text{min} \left\{ \frac{\hat{b}_i}{\hat{d}_i} | \hat{d}_i < 0\right\}, & \hat{\mathbf{d}} \ngeqslant \mathbf{0},\\ \infty, & \hat{\mathbf{d}} \geqslant \mathbf{0}. \end{cases}` $$ 简化版一维搜索 `\begin{align} \text{min} \quad f(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)})\\ \text{s.t.}\quad 0\leqslant \lambda \leqslant \lambda_{\text{max}} \end{align}` --- ### 初始可行解 `\begin{align} \text{min} \quad & \sum_{i=1}^m\xi_i + \sum_{i=1}^l\eta_i \\ \text{s.t.} \quad & \mathbf{Ax} + \mathbf{\xi} \geqslant \mathbf{b},\\ & \mathbf{Ex} + \mathbf{\eta} = \mathbf{e},\\ & \mathbf{\xi} \geqslant \mathbf{0}, \quad \mathbf{\eta} \geqslant \mathbf{0}. \end{align}` 如果 $$ (\bar{\mathbf{x}},\bar{\mathbf{\xi}},\bar{\mathbf{\eta}}) = (\bar{\mathbf{x}},\mathbf{0},\mathbf{0}), $$ 那么 `\(\bar{\mathbf{x}}\)` 即是原问题的一个可行解。 --- ### 例子 用Zoutendijk可行方向法解下列问题: `\begin{align} \text{min} \quad &x_1^2 + x_2^2 - 2x_1 - 4x_2 + 6\\ \text{s.t.} \quad & -2x_1 + x_2 + 1 \geqslant 0,\\ & -x_1 - x_2 + 2 \geqslant 0,\\ & x_1,x_2 \geqslant 0. \end{align}` --- class: middle, center, reverse ### 留白 --- ### 非线性约束优化 `\begin{align} \text{min} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_i(x) \geqslant 0, i = 1,\cdots,m. \end{align}` 求**可行下降方向**,也就是求解满足下列不等式组的解 `\(\mathbf{d}\)` : `\begin{align} &\nabla f(\mathbf{x})^T\mathbf{d} < 0,& \text{下降方向}\\ &\nabla g_i(\mathbf{x})^T\mathbf{d} > 0, i \in I. & \text{可行方向} \end{align}` -- 可归结为求解线性规划问题 `\begin{align} \text{min}\quad & z\\ \text{s.t.}\quad & \nabla f(\mathbf{x})^T\mathbf{d} - z \leqslant 0,\\ & \nabla g_i(\mathbf{x})^T\mathbf{d} + z \geqslant 0, i\in I,\\ & |d_j| \leqslant 1, j=1,\cdots,n. \quad \text{(等价于}~~-1 \leqslant d_j \leqslant 1) \end{align}` -- 设最优解为 `\((\bar{z},\bar{\mathbf{d}})\)` , - 如果 `\(\bar{z} <0\)` ,则 `\(\bar{d}\)` 是在 `\(\mathbf{x}\)` 处的下降可行方向; - 如果 `\(\bar{z} =0\)` ,则 `\(\mathbf{x}\)` Fritz John 点。 --- ### 确定步长 `\(\lambda_k\)` 一维搜索 `\begin{align} \text{min}\quad &f(\mathbf{x}^{(k)} +\lambda \mathbf{d}^{(k)})\\ \text{s.t}\quad & 0 \leqslant \lambda \leqslant \lambda_{\text{max}}, \end{align}` 其中 $$ \lambda_{\text{max}} = sup\\{\lambda | g_i(\mathbf{x}^{(k)} + \lambda \mathbf{d}^{(k)}) \geqslant 0, i = 1,\cdots,m \\}. $$ .footnote[ 参加教材:《最优化理论—理论与算法》(第2版), 陈宝林编著,清华大学出版社,2005年 ]