0x1.集合约束与无约束优化

集合约束优化问题：

如下形式的优化问题 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓(𝒙) subject to 𝒙∈Ω

其中𝑓: ℝ^𝑛^→ℝ成为目标函数或价值函数，是一个实值函数。𝒙是一个𝑛维向量，Ω是ℝ^𝑛^的一个子集，成为约束集或可行域。

0x2.极小点

∀𝑥∈𝛿(𝑥^∗^,𝜀)\{𝑥^∗^}，$𝑓(𝑥)≥𝑓(𝑥^∗)，𝑥^∗$称为==局部极小点==。

∀𝑥∈Ω\{𝑥^∗^}，𝑓(𝑥)≥𝑓(𝑥^∗^)，𝑥^∗^称为==全局极小点==。

如果将上述的≥替换为＞，则称为==严格局部极小点==和==严格全局极小点==。

0x3.局部极小点的条件

1.定义6.2：

对于向量𝒅∈ℝ^𝑛^， 𝒅≠𝟎和约束集中的某个点𝒙，如果存在一个实数𝑎~0~>0，使得所有的𝑎∈[0,𝑎~0~]，𝒙+𝑎𝒅仍然在约束集内，即𝒙+𝑎𝒅∈Ω，则称𝒅为𝒙处的==可行方向==。

2.方向导数𝒅^⊺^ 𝛻𝑓(𝒙)：

𝑑为𝑛元实值函数𝑓: ℝ^𝑛^→ℝ在𝒙∈ Ω处的可行方向，则函数𝑓在𝒙点沿𝑑方向的方向导数为:

导数>0，表示在该局部，函数单调递增。 导数<0，表示在该局部，函数单调递减。 导数=0，表示在该点，函数处于临界点。

由此可见，当d是一个单位向量（|| d || = 1）时，函数f的值在x处沿方向d的增长率可以用内积<▽f(x),d>表示。

3.定理6.1（一阶必要条件）

点不为内点时（如边界点）用这个判断是否满足局部极小点的一阶条件。

多元实值函数𝑓在约束集Ω一阶连续可微，即𝑓∈𝐶^1^，约束集Ω是ℝ^𝑛^的子集。如果𝒙^∗^是𝑓在约束集Ω上的局部极小点，则对于𝒙^∗^处的任意可行方向𝒅，都有 𝒅^⊺^ 𝛻𝑓(𝒙^∗^ )≥0 成立。

4.推论6.1（内点一阶必要条件）

点为内点时用这个判断是否满足局部极小点的一阶条件。

多元实值函数𝑓在约束集Ω一阶连续可微，即𝑓∈𝐶^1^，约束集Ω是ℝ^𝑛^的子集。如果𝒙^∗^是𝑓在约束集Ω上的局部极小点，且是Ω的内点，则有 𝛻𝑓(𝒙^∗^ )=0 成立。

5.定理6.2（二阶必要条件）

多元实值函数𝑓在约束集Ω二阶连续可微，即𝑓∈𝐶^2^，约束集Ω是ℝ^𝑛^的子集。如果𝒙^∗^是𝑓在约束集Ω上的局部极小点， 𝒅是𝒙^∗^点的可行方向，且𝒅^⊺^ 𝛻𝑓(𝒙^∗^ )=0，则有 𝒅^⊺^ 𝐹(𝑥^∗^ )𝒅≥0 其中𝐹为函数𝑓的==Hessian矩阵(黑塞矩阵)==。

6.推论6.2（内点二阶必要条件）

多元实值函数𝑓在约束集Ω二阶连续可微，即𝑓∈𝐶^2^，约束集Ω是ℝ^𝑛^的子集。如果𝒙^∗^是𝑓在约束集Ω上的局部极小点， 且是Ω的内点，则有 𝛻𝑓(𝒙^∗^ )=𝟎 且对于所有方向𝒅有， 𝒅^⊺^ 𝐹(𝒙^∗^ )𝒅≥0

7.定理6.3（内点二阶充分条件）

多元实值函数𝑓在约束集Ω二阶连续可微，即𝑓∈𝐶^2^，约束集Ω是ℝ^𝑛^的子集。如果𝒙^∗^是𝑓在约束集Ω的一个内点，且有 𝛻𝑓(𝒙^∗^ )=𝟎 且对于所有方向𝒅有， 𝒅^⊺^ 𝐹(𝒙^∗^ )𝒅>0 则𝒙^∗^是函数𝑓的一个严格局部极小点。