$$ \min f(x)\\ s.t. \ x\in\Omega $$

• 最优性条件 ：变分刻画约束优化问题

  • 【约束优化问题】

    • 一阶充分

      $$ d^T\nabla f(x^*)>0,\forall d\in T_\Omega(x) $$

      ⇒$x^*$是严格极小点。

    • 二阶必要条件

      极小点⇒海塞矩阵对可行方向的二次型大于等于零

    • 二阶充分条件

      一阶欧拉式为零，海塞对可行方向的二次型（范数）大于零。

      ⇒$x^*$是严格极小点

  	一元可微函数	无约束优化	约束优化	拉格朗日条件(等式约束)	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，条件为等价条件
  • 极值点的数量与约束集大小无正相关（约束集边界构成局部极值点）
  • Weierstrass 定理 Weierstrass 定理：极小值点集合是非空紧集的条件

• 可行方向：

  可行解集$\Omega$一定可以刻画为一些等式方程组和不等式方程组的解集。

  • 内点int(\Omega) 边界点bd(\Omega)

  • 线性化可行方向（近似的可行方向）

    $$ x\in bd(\Omega) \to \\ 0\ne d=\lim_{x\to x^\prime}T(x) $$

凸优化

<aside> 👘

Convex Optimization 唯一可求解的问题

• $h_i$是仿射函数
• $f,g_j$是凸函数 </aside>

等式约束

<aside> 📢

无动画Chapter20.pdf

</aside>

$$ \Omega=\{x\in\mathbb F^n:h_i(x)=0,i=2\cdots m\} $$

• Weierstrass 定理：极小值点集合是非空紧集的条件

约束可微。$\mathbf h(\mathbf x)=0$

超平面的交集构成可行域（约束集），可以用曲线是曲面的交想象之（注意区分这里想象的曲线和之后真正使用的参数化的曲线，后者只有一个变量）。

正则点

• mm

【regularity】正则→没有多余的等式约束，即每个约束至少提供了一个梯度信息。$rank \ Dh(x^)=m$等价于$x^$为正则点

【雅可比矩阵】

• 正则点：满足等式约束的点，其等式约束的梯度向量是线形无关的。

• 曲面维数与正则点

  

  曲面：$S=\{x\in F^n:h_{1\cdots m}(x)=0\}$，如果$S$曲面上所有点都是正则点，那么曲面的维数确定为$n-m$

• 切空间与法空间

  • 【线形化可行方向全体】

    切空间，等式约束的导数(梯度)做系数矩阵的齐次线形方程组的解

    $$ T_{x^}M=T(x^)=\{\vec d\mid \left(D h_i(x^*)\right) \vec d=0\}\\=\mathcal N(Dh_i) $$

  • 【切平面】切平面$\mathrm{TP}(x)$-移动到原点→切空间$\mathrm T_x\mathrm M$

    

    $h(x)$→一阶泰勒展开

    →$h(x^)+h^\prime(x^)(x-x^)$or$h(x^)+[\nabla h(x^)]^T(x-x^)$→移动到原点

    →$T(x)=\{d\in F^n:[\nabla h(x^*)]^Td=0\}$得到切空间。

    更一般地，$n$个等式约束

    $$ T_\Omega(x)=\{d\in F^n:\begin{pmatrix} \nabla h_1(x)^T\\ \nabla h_2(x) ^T\\ \cdots \\ \nabla h_n(x)^T \end{pmatrix}d=0\}=\mathcal N(Jh(x^*)). $$

    $$ TP(x^)=T(x^)+x^* $$

  • 一阶展开的思想可以具体化为一个定理：

    • 【存在匹配对$\in (V^*,V)$】
      • 如果$x^\in S$是正则点，那么$y\in T(x^)$的充要条件是曲面$S$中存在过$x^$的可微曲线，其在$x^$处的导数为$y$

  • 【法空间】等式约束的导数做矩阵变换的像，系数矩阵的行向量(梯度)张成的子空间

    • 法空间是切空间的正交补空间。

      $$ N(x^)=\mathcal R(Dh(x^)^T) $$

    $$ N(x^)=\{x\mid x=Dh(x^)^T z,z\in \mathbb F^m\}=\mathcal L\left(\nabla h_i(x^*)\right) $$

• 齐次线性方程组$\mathbf A\mathbf x=0,\mathbf A\in \mathbb F^{m\times n}$基础解系$\text{span}(\xi_1,\xi_2,\cdots,\xi_{n-\text{rank}\mathbf A})=\mathcal N(\mathbf A)=\{x\in \mathbb F^n:Ax=0\}=\ker(\mathbf A)$核空间， 非齐次线性方程组$x^*=\eta+...=\eta +\mathcal N(\mathbf A)$齐次解构成的子空间的平移。 像空间$\mathcal R(A)=\{Ax\in \mathbb F^m:\forall x\in \mathbb F^n\}$ 值域空间与核空间垂直，互为正交补空间$\mathcal V^\perp=\{x:v^Tx=0,\forall v\in \mathcal V\}$。

  • 【定理】$\mathcal R(A)^\perp=\mathcal N(A^T),\mathcal N(A)^\perp=\mathcal R(A^T)$

• ??

lagrange条件极值$\lambda_i$。

拉格朗日条件