$$ \begin{array}{rl}\text{minimize}&f(\boldsymbol{x})\\\text{subject to}&\boldsymbol{x}\in\Omega\end{array} $$

• 目标函数objective function |价值函数$f\colon\mathbb{R}^{n}\to\mathbb{R}$

• 决策变量decision variable $\boldsymbol x\in\mathbb R^n$

• 约束集|可行集constraint/ feasible set $\Omega$

  无约束优化问题unconstrained optimization ：$\Omega\in\mathbb R^n$

  约束优化问题：$\Omega\subsetneqq\mathbb R^n$

  • 约束条件：不等式约束、等式约束 $\Omega=\{\boldsymbol{x}:\boldsymbol{h}(\boldsymbol{x})=\boldsymbol{0},\boldsymbol{g}(\boldsymbol{x})\leqslant\boldsymbol{0}\}$

最优性条件

<aside> 💡 无约束优化问题：一元、多元函数； 约束优化问题：可行方向锥。

无动画Chapter6.pdf

</aside>

• 极小点： 【局部部local minimum】在邻域$\mathcal N(x^)$中最小$f(x)\geqslant f(x^{})$。 【全局】在定义域$\Omega=\text{dom} (f)$中最小

  

  • $\text{dom} (f)$表示定义域
  • 严格（全局/局部）极小点$f(x)>f(x^{*})$
  • 全局极小点$f({\boldsymbol{x}}^{})=\mathrm{min}_{x\in\Omega}f({\boldsymbol{x}})$ 或 $x^{}=\arg\min_{x\in\Omega}f(x)$ argument minimum
  • 边界上的极值点

    • 可行方向feasible direction $x\in \Omega,d\in \mathbb F^n$→$\exist\alpha_0, x+\alpha d \in \Omega,\alpha\in[0,\alpha_0]$，则称方向d是可行的，称可行方向。

      

      • 内点 $x\in \text{int}(\Omega)$，可行方向全体为$\mathbb F^n$

      • 边界点

        【切锥】【可行锥】【可行方向锥】 $x\in\text{bd}(\Omega)$，（光滑可微）切平面下方构成可行方向全体(也是可行方向锥)；（拐点）可行方向全体$T_\Omega(x)$构成可行方向锥-可行锥 - 切锥

        • 【切集】【线性化可行方向全体】 所有线性化（获得引入了泰勒一阶展开）可行方向全体定义为$0\ne d=\lim (x-x^\prime)$ 用 $T_\Omega(x)$或 $T(x)$表示，称 切集（本质上是极值函数，随点变化）

      ---

      • 如，$\Omega=\{x\in \mathbb R^n|h_i(x)=0,i=1,2,\cdots,m\}$以等式约束
      • 以一元可微函数(无约束优化问题)为例，寻找极小值。

      $f^\prime$ ↔ $\nabla$,$f^{\prime\prime}$↔$\nabla^2$黑塞矩阵，$>$正定$\ge$半正定

      对于约束优化问题【最优性条件】

      $\bm x$是（局部、严格、全局）极小值的条件是：

      （充分条件S⇒极小）（必要条件N←极小）

      	一元可微函数	无约束优化	约束优化	拉格朗日条件(等式约束)	KKT 条件(不等式约束)
      一阶必要条件
      FONC	$f^\prime(x^*)=0$	$\nabla f(x^*)=0$	$\bm d^T\nabla f (\bm x^)\ge 0,\ \forall d\in T_\Omega (x^)$

      • 欧拉公式|变分不等式 - 方向导数
      • 梯度方向与任意可行方向为锐角。泰勒展开证之。
      • $f\in\mathcal C^1(\Omega)$ 特别的，$\Omega=\mathbb R^n$or $x^\in \text{int}(\Omega)$,退化至$\nabla f(x^)=0$，约束进而等价于无约束。 $(x-x^)\cdot \nabla f(x^)$, $\delta x\cdot \nabla f$ | - 正则点$\text{rank} Dh(x^*)=m$ Jacobian矩阵行满秩
      • $\mathcal L$无约束FONC | | | 一阶充分条件 FOSC | | | $d^T\nabla f(x^\prime)>0,\forall d\in T_{\Omega}(x^\prime)$ ⇒$x^\prime$是严格极小点
      • $f\in\mathcal C^1(\Omega)$ | | | | 二阶必要条件 SONC | $f^{\prime\prime}\ge0,f^\prime=0$ | $\left\{\begin{matrix} \nabla f (x^)= 0, &\\ F f (x^)\ge 0 \end{matrix}\right.$ | $\left\{\begin{matrix} d^T\cdot\nabla f (x^)= 0, &\\ d^T\cdot F f (x^)d\ge 0,&\forall d\in T_\Omega (x^*). \end{matrix}\right.$
      • 满足FONC，同时关于$\bm x$的海塞矩阵可行锥内半正定$F\succeq0,\bm d\in T_{\Omega}(x^*)$
      • 如果极小点还是内点，结论同无约束优化
      • $f\in\mathcal C^2(\Omega)$ | - 正则点
      • $\mathcal L$无约束SONC(FONC+关于$x$的海塞矩阵半正定) | | | 二阶充分条件SOSC | $f^{\prime\prime}\ge0,f^\prime=0$ | $\left\{\begin{matrix} \nabla f (x^)= 0, &\\ F f (x^)> 0 \end{matrix}\right.$⇒严格局部极小点 | $\left\{\begin{matrix} d^T\cdot\nabla f (x^\prime)= 0, &\\ d^T\cdot F f (x^\prime)d> 0,&\forall d\in T_\Omega (x^\prime). \end{matrix}\right.$ ⇒严格局部极小点
      • 满足FONC，同时海塞矩阵可行锥内正定$F\succ 0,\bm d\in T_{\Omega}(\bm x)$
      • $f\in\mathcal C^2(\Omega)$ | | |
      • 若$f$是凸函数且$\Omega$，则FONC变为FONS，条件为等价条件

      ---

    • 积极约束

    • 方向导数

一元单值函数

$$ \begin{array}{rl}\text{minimize}&f(\boldsymbol{x}):\mathbb R\to \mathbb R\\\text{subject to}&\boldsymbol{x}\in\Omega\end{array} $$

迭代算法$x^{(0)}\to x^{(1)}\to x^{(2)}\to \cdots$

一维优化问题 :

黄金分割法：三段法

二分法 bisection

牛顿方法

插值类方法

划界法|技术

如何确定有解区间（搜索区间）

• 解析法
• 试误法

多元函数 - 无约束优化

• 最优性条件：

  $$ \nabla f(x)=0. $$

• line search 线搜索

  $$ \boldsymbol x_{k+1}=\boldsymbol x_k+\alpha _k\boldsymbol p_k. $$

共轭方法

共轭类方法