多变量有约束非线性优化问题

如何解决 Multi-Variable Constrained Optimization?

一种方法是把一个 Constrained Porblems 转化成 a sequence of Unconstrained Problems $\to$ Sequential Unconstrained Minimization Techniques (SUMT).

另一种方法是在迭代过程中直接将约束纳入考量，于是迭代结束时约束满足且为最小值点 $\to$ Primal Methods

Converting Methods: Exterior Penalty Function Method

我们在原 objective function $f$ 上加上 penalty function $P$ ，构造出新目标函数 $\phi$

\phi(\bold{x}, r_p)=f(\bold{x})+r_p P(\bold{x})

其中 $r_p$ 是 penalty 的系数用以控制 penalty 的强度。我们令 $P$ 采取下面这样的形式

P(\bold{x})=\sum_{j=1}^m \Bigg[ \max\bigg(0, g_j(\bold{x})\bigg) \Bigg]^2+\sum_{k=1}^l h_k^2(\bold{x})

为什么 $h_k^2(\bold{x})$ 是平方项？

因为我们想让 $h_k(\bold{x})$ 保持严格为 $0$ ，小于 $0$ 和大于 $0$ 在平方之后都会变成 $\gt 0$ 的值，这样就可以优化了。

为什么 $[\max(0,g_j(\bold{x}))]^2$ 要取 $\max$ ？为什么要取平方？

取 $\max$ 是因为 $g_j(\bold{x})\le 0$ 是不等式约束，只要在 $g_j(\bold{x})\gt 0$ 时才会产生 penalty，所以需要和 $0$ 取 $\max$ .

取平方是因为考虑 $\bold{x}=\bold{x}_0$ 使得 $g_j(\bold{x}_0)=0$ ，我们发现在这一个点 $\max(0, g_j(\bold{x}))$ 这个函数是不可导的，所以加上平方之后在该点处就可导了。

迭代策略

r_p

的选取

如果 $r_p$ 较小，很有可能 $\phi()$ 取到最小值的解不满足约束条件；但是如果 $r_p$ 太大，也会造成数值计算困难等问题

这个 Method 先从较小的 $r_p^{(0)}$ 初值开始，优化函数 $\phi(\bold{x}, r_p^{(0)})$ 在下一步迭代开始时， $r_p$ 会乘上一个倍率

r_p^{(t+1)}\gets \gamma r_p^{(t)}

然后去优化函数 $\phi(\bold{x}, r_p^{(t+1)})$ . 重复迭代直到相邻两次迭代得到的最小值小于误差，并且每一个约束是否被满足（需要小于给定误差）

\Big| f(\bold{x}^{(t+1)})-f(\bold{x}^{(t)}) \Big|\lt \epsilon_f \\ g_j(\bold{x}) \le \epsilon_g \\ |h_k(\bold{x})| \le \epsilon_h

Generalized Reduced Gradient (GRG) Method

使用 slack variable 将不等式约束转化为等式约束，于是约束可以表示成如下的形式

\begin{array}{ll} g_j(\bold{x})+s_j=0, &j\in [1, m]\\ h_k(\bold{x})=0, &k\in [1,l]\\ x_i^l\le x_i\le x_i^u, &i\in[1, n]\\ s_j\ge 0, &j\in[1, m] \end{array}

和 Lagrange 方法不同，我们添加的不是 $s_j^2$ 项而是 $s_j$ 项，而且额外添加 $s_j\ge 0$ 约束

更进一步地，我们把 $s_j$ 也看作是 $\bold x$ 的一部分， $s_j\ge 0$ 视作 $0\le s_j\le \infin$ ，那么 $g_j(\bold x)+s_j=0$ 也可以看作是 $h(\bold{x}')=0$ ，于是上面的约束可以写成

\begin{array}{ll} h_k(\bold {x})=0, &k\in[1, m+l]\\ x_i^l\le x_i\le x_i^u, &i\in[1, n+m] \end{array}

$m+l$ 个等式可以消除 $m+l$ 个变量，于是还剩下 $(n+m)-(m+l)=n-l$ 个独立变量 (non-basic variables)，我们令 non-basic 的为 $\bold y$ ，basic 的为 $\bold z$ ，故

\bold{x}=\begin{Bmatrix} \bold y\\ \bold z \end{Bmatrix}

所以这个问题对于 $\bold y$ 来说就变成了 unconstrained problem（只有定义域约束，可以在优化过程中直接检查解的合法性）。我们从 initial point 开始，保证每一步移动都在 feasible region 内即可。

梯度推导

每一步的移动既要满足在定义域内，又要满足保持 $h_k(\bold{x})=0$ . 而在曲线上移动一小段距离即为

\Delta h_k(\bold{x})=\nabla h_k(\bold{x})^T \Delta \bold{x}

代入 $\bold{x}=\begin{bmatrix}\bold y &\bold z\end{bmatrix}^T$ 并对两部分分别求偏导

\implies \nabla_y h_k(\bold{x})^T\Delta \bold y+ \nabla_z h_k(\bold{x})^T\Delta \bold z=0

所以一共有 $m+l$ 个这样的矩阵等式，可以合并为一个等式

\begin{array}{rrl} &\bold{A}\Delta\bold{y} + \bold{B}\Delta\bold{z}&=0\\ \implies&\Delta \bold{z}&=-\bold{B}^{-1}\bold{A}\Delta\bold{y} \end{array}

所以 $f(\bold{x})$ 的变化量为

\begin{aligned} f(\bold{x})&=\nabla f(\bold{x}) \Delta \bold{x}\\ &=\nabla_y f(\bold{x})^T\Delta \bold y + \nabla_z f(\bold{x})^T\Delta \bold z\\ &=\nabla_y f(\bold{x})^T\Delta \bold y - \nabla_z f(\bold{x})^T \bold{B}^{-1}\bold{A}\Delta\bold{y}\\ &=\Bigg(\nabla_y f(\bold{x})^T - \nabla_z f(\bold{x})^T \bold{B}^{-1}\bold{A}\Bigg) \Delta\bold{y}\\ &=\Bigg(\nabla_y f(\bold{x}) - \bigg(\bold{B}^{-1}\bold{A}\bigg)^T\nabla_z f(\bold{x})\Bigg)^T \Delta\bold{y}\\ &=\Big( \frac{d f(\bold{x})}{d \bold{y}} \Big)^T\Delta\bold{y} \end{aligned}

其中 $\frac{d f(\bold{x})}{d \bold{y}}$ 是一个记号，称为 Generalized reduced gradient.