第一章最优化理论基础

阳光穿透心脏的1/2处 2022-10-07 15:43 219阅读 0赞

> 内容来自马昌凤编著的《最优化方法及其Matlab程序设计》，文章仅为个人的学习笔记，感兴趣的朋友详见原书

# 1 最优化问题的数学模型 #

简单来说，最优化问题就是求一个多元函数在某个给定集合上的极值，其**一般表达**为：  
 m i n f ( x ) min f(x) minf(x)  
 s . t . x ∈ K s.t. x∈K s.t.x∈K  
其中， K K K为可行域， x x x为决策变量，s.t.是subject to（受限于）的缩写。

**非线性规划**：  
 m i n f ( x ) min f(x) minf(x)  
 s . t . h i ( x ) = 0 , i = 1 , . . . , l s.t. h\_\{i\}(x)=0, i=1,...,l s.t.hi(x)=0,i=1,...,l  
 g i ( x ) > = 0 , i = 1 , . . . , m g\_\{i\}(x)>=0, i=1,...,m gi(x)>=0,i=1,...,m  
其中， f ( x ) f(x) f(x)、 h i ( x ) h\_\{i\}(x) hi(x)、 g i ( x ) g\_\{i\}(x) gi(x)都是定义在 R n R^n Rn上连续可微的多元实值函数，并且至少有一个是非线性的。

记 E = i ∣ h i ( x ) = 0 E=\{i|h\_\{i\}(x)=0\} E=i∣hi(x)=0  I = i ∣ g i ( x ) > = 0 I=\{i|g\_\{i\}(x)>=0\} I=i∣gi(x)>=0  
**若两指标集的并集为∅**，则称之为**无约束优化问题**；否则为有约束优化问题。特别的，把 E E E≠∅且 I I I=∅的优化问题称为等式优化问题；而把 I I I≠∅且 E E E=∅的优化问题称为不等式优化问题。 f ( x ) f(x) f(x)称为目标函数， h i ( x ) h\_\{i\}(x) hi(x)， g j ( x ) g\_\{j\}(x) gj(x)称为约束函数。

**二次规划**：目标函数为二次函数，而约束函数都为线性函数的优化问题。（而目标函数和约束函数都为线性函数的优化问题称为线性规划）

# 2 函数的可微性与展开 #

## **梯度与Hess矩阵**： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70_pic_center]

## **泰勒展开：** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70_pic_center 1]

# 3 凸集与凸函数 #

## 凸集的定义&性质 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70]

## 凸函数的定义与判断 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 1]

# 4 无约束问题的最优性条件 #

全局极小点——最值  
局部极小点——极值

一阶必要条件：设 f ( x ) f(x) f(x)在开集 D D D上一阶连续可微，若 x ∗ ∈ D x^\*∈D x∗∈D是一个局部极小点，则必有 g ( x ∗ ) = 0 g(x^\*)=0 g(x∗)=0。

二阶必要条件：设 f ( x ) f(x) f(x)在开集 D D D上二阶连续可微，若 x ∗ ∈ D x^\*∈D x∗∈D是一个局部极小点，则必有 g ( x ∗ ) = 0 g(x^\*)=0 g(x∗)=0且 G ( x ∗ ) G(x^\*) G(x∗)是半正定矩阵。

**二阶充分条件**：设 f ( x ) f(x) f(x)在开集 D D D上二阶连续可微。若 x ∗ ∈ D x^\*∈D x∗∈D满足条件 g ( x ∗ ) = 0 g(x^\*)=0 g(x∗)=0及 G ( x ∗ ) G(x^\*) G(x∗)是**正定矩阵**，则 x ∗ x^\* x∗是一个局部极小点。

设 f ( x ) f(x) f(x)在 R n R^n Rn上是**凸函数**，并且是**一阶连续可微**的，则 x ∗ ∈ x^\*∈ x∗∈  R n R^n Rn是**全局**极小点的充要条件是 g ( x ∗ ) = 0 g(x^\*)=0 g(x∗)=0

# 5 无约束优化问题的算法框架 #

## 无约束问题的一般算法框架 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 2]

## 局部收敛与&全局收敛 ##

*  **局部收敛**：只有当初始点 x 0 x\_0 x0充分接近极小点 x ∗ x^\* x∗时，由算法产生的点列 x k \{x\_k\} xk才收敛于 x ∗ x^\* x∗,则称该算法具有局部收敛性。
 *  **全局收敛性**：若对任意的初始点 x 0 x\_0 x0，由算法产生的点列 x k \{x\_k\} xk都收敛于 x ∗ x^\* x∗,则称该算法具有全局收敛性。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/b6c2e5b669d44e6cb96fc24f59d574dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/073bc0b566404c85b6bdf6bfd4ff6486.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70]: /images/20221005/9ba954a2a8684c349a8ee66c5c871467.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 1]: /images/20221005/c690e4391fd947f6b35cb0471739b7d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 2]: /images/20221005/b92b96bdecb348da8053a03975826fee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDYwNjc0_size_16_color_FFFFFF_t_70 3]: /images/20221005/09e388fa0c5143618437314645b9f529.png