集合约束和无约束优化问题的基础知识
# 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 则𝒙^∗^是函数𝑓的一个严格局部极小点。