杂记

最优化方法第7章的内容比较多，稍微做了一下逻辑整理，里面各种定理只表达了下大意没有做严格阐述

对于一个优化问题$min f(x)$, 

一、原问题无约束

   1.目标函数为一般函数

   1).一阶条件：

     如果$\bar{x}$是局部极小点，则在该点梯度为0

   2).二阶条件：

     如果$\bar{x}$是局部极小点，则在该点Hessian矩阵半正定；如果梯度为0且Hessian矩阵在$\bar{x}$微分领域内半正定，则$\bar{x}$是局部极小点。

   2.目标函数为凸函数

   1).$\bar{x}$为全局极小点的充要条件是该点梯度为0

二、原问题只有不等式约束

    1.原问题为一般规划问题

    1).几何最优性条件：如果$\bar{x}$是问题的局部最优解，则在该点的下降方向集与局部约束方向锥交集为空

    2).代数最优性条件:

    (1).如果$\bar{x}$是局部极小点,则在该点一定满足Fritz John条件

    (2).由于Fritz John条件中$w_0$可能为0，这时无法提供任何关于目标函数的信息，因此对Fritz John条件加强一条：所有 起作用约束$g_i(\bar{x})$的梯度向量$\nabla g_i(\bar{x})$在该点线性无关,即有KKT条件

    则如果$\bar{x}$是局部极小点，该点一定满足KKT条件

    2.原问题为凸规划问题

    1).如果$\bar{x}$点KKT条件满足，则$\bar{x}$是全局极小点；如果$\bar{x}$是全局极小点，那么$\bar{x}$一定满足KKT 条件

三、原问题具有一般约束

    几个比较不太直观的地方

    *此时如果等式约束不是线性约束的话，仅用梯度无法描述在可行域的运动，因此需要引入一族曲线族，以点在曲线切线方向来定义运动方向。因此可以将原来的可行方向推广至序列化可行方向，也即$\textbf{切锥}$。

    * $\bar{S}$和$\bar{G}$定义看起来很奇怪，但是仔细看一下会发现如果一个局部极小点$\bar{x}$限定在$\bar{S}$中运动，那么在不改变原来的$\bar{w},\bar{v}$的情况下后面几个式子不会发生改变。而$\bar{G}$定义了一组方向，如果沿这组方向运动的话不会改变$\nabla_x L(x, w, v)$的后两项。或者简单来说，如果$\textbf{限定在S并只沿着G的方向运动}$，那么对于Lagrange乘子问题的变化只会反应到$f(x)$上，从而可以分析目标函数的变化,进而转化为考虑$\nabla^2_xL$在$\bar{G}$的半正定性

    1.原问题为一般规划问题

    1).几何最优性条件：如果$\bar{x}$是一个正则点，则在该点的 $\textbf{下降方向集}$, $\textbf{局部约束方向锥}$， $\textbf{切向量集}$三者无交集

    2).代数最优性条件:

    (1).如果$\bar{x}$是局部极小点，则该点一定满足Fritz John条件

    (2).如果$\bar{x}$是局部极小点且为正则点,则该点一定满足KKT条件(注意存在$\bar{x}$不是正则点且不符合KKT条件但是局部极小点的情况)

    (3).如果$(\bar{x}, \bar{w}, \bar{v})$是Lagrange乘子问题的一组解且$\nabla^2_xL$在$\bar{G}$正定，则$\bar{x}$是严格局部极小点；如果$\bar{x}$是局部极小点，$(\bar{x}, \bar{w}, \bar{v})$是Lagrange乘子问题的一组解且$\bar{G} = \bar{T}$成立，则$\nabla^2_xL$在$\bar{G}$半正定。其中$\bar{G} = \bar{T}$等价于$\bar{x}$为正则点。

    2.原问题为凸规划问题  

    1).如果$\bar{x}$点KKT条件满足，则$\bar{x}$是全局极小点；如果$\bar{x}$是全局极小点，那么$\bar{x}$一定满足KKT 条件