一般最佳化條件 (General condition)

Optimization problem

• 雙變數$\mathbf{x} = (x_1, x_2)$最佳化函數(數學規劃, mathematical programming)如下
  • $\begin{array}{rl} \max & f(\mathbf{x}) \\ s.t. & g_i(\mathbf{x}) = 0, \\ & i=1,2,\cdots, K. \end{array}$
• $f(x)$ 稱為目標函數(ojbective function)，$g_i(x) \ i=1,2,\cdots,K$ 為限制式函數(constraint function)。
• 滿足上面限制式的集合$\mathcal{X} = \left\{ \mathbf{x} \in \mathbb{R}^M \vert g_i(\mathbf{x})=0, \ i=1,2,\cdots,K \right\}$.稱為可行集(合)或可行域(feasible set, feasible region)。

• 所有的不等式限制式，都可以用鬆弛變數(slack variables)與剩餘變數(surplus variable)化為等式限制式。

  • e.g. $c_1 x_1 + c_2 x_2 \geq 0 \Leftrightarrow c_1 x_1 + c_2 x_2 - e_1 = 0, \ e_1 \geq 0$.
  • e.g. $c_1 x_1 + c_2 x_2 \leq 0 \Leftrightarrow c_1 x_1 + c_2 x_2 + s_1 = 0, \ s_1 \geq 0$.

• 如果$f(\mathbf{x})$ 為convex function，且可行集$\mathcal{X}$為convex set時，稱為convex programming‧

• 在不考慮限制式$g(x_1, x_2)=0$的情形下，若一階微分存在，則$f(x_1, x_2)$的極值(最大值或最小值)發生在梯度向量(gradient vector) $\nabla f(x_1, x_2) = (\frac{\partial{f}}{\partial{x_1}}, \frac{\partial{f}}{\partial{x_2}})=(0, 0)$ 之處。

  • 因為一階微分代表斜率，而最大值與最小值以及平面的微分值都等於0。
• 若二階微分存在，令 Hessian matrix $H(x_1,x_2)= \left( \begin{array}{cc} \frac{\partial^2{f}}{\partial{x_1^2}} & \frac{\partial^2{f}}{\partial{x_1 x_2}} \\ \frac{\partial^2{f}}{\partial{x_2 x_1}} & \frac{\partial^2{f}}{\partial{x_2^2}} \end{array} \right)$，則行列式之值$|H(x_1, x_2)| =\frac{\partial^2{f}}{\partial{x_1^2}} \frac{\partial^2{f}}{\partial{x_2^2}} - \frac{\partial^2{f}}{\partial{x_1x_2}} \frac{\partial^2{f}}{\partial{x_1 x_2}}$.
  • 二階微分斂代表曲率，所以平面或是鞍點(saddle point)[斜率由正變負或由負變正的點]的曲率均為0，即$|H(x_1, x_2)|=0$.
    • 若$\mathbf{x}$的梯度為0，且$|H(\mathbf{x})| > 0$ (開口向上)，則$f(\mathbf{x})$為最小值。
    • 若$\mathbf{x}$的梯度為0，且$|H(\mathbf{x})| < 0$ (開口向下)，則$f(\mathbf{x})$為最大值。
    • 若$\mathbf{x}$的梯度為0，且$|H(\mathbf{x})| = 0$ ，則$f(\mathbf{x})$為鞍點。