最优化方法学习笔记01——基本概念

发布时间：2024-11-24 13:17

采用故事化学习法记忆复杂概念 #生活技巧# #学习技巧# #跨学科学习技巧#

最优化方法学习笔记01——基本概念

肝！

最优化方法最优化方法学习笔记01——基本概念前言一、最优化方法的定义与分类1. 一般形式2. 简单分类二、最优化的条件和一些基本概念1. 凸集2. 超平面3. 支撑面4. 凸函数5. 方向导数6. 可微函数的凸性的三定理7. 局部最优点与全局最优点8. 极值的求解9. 鞍点与极值判别定理总结参考

前言

传统优化算法一般是针对结构化的问题，有较为明确的问题和条件描述，如线性规划，二次规划，整数规划，混合规划，带约束和不带约束条件等，即有清晰的结构信息；而智能优化算法一般针对的是较为普适的问题描述，普遍比较缺乏结构信息。

传统优化算法不少都属于凸优化范畴，有唯一明确的全局最优点；而智能优化算法针对的绝大多数是多极值问题，如何防止陷入局部最优而尽可能找到全局最优是采纳智能优化算法的根本原因：对于单极值问题，传统算法大部分时候已足够好，而智能算法没有任何优势；对多极值问题，智能优化算法通过其有效设计可以在跳出局部最优和收敛到一个点之间有个较好的平衡，从而实现找到全局最优点，但有的时候局部最优也是可接受的，所以传统算法也有很大应用空间和针对特殊结构的改进可能。

传统优化算法一般是确定性算法，有固定的结构和参数，计算复杂度和收敛性可做理论分析；智能优化算法大多属于启发性算法，能定性分析却难定量证明，且大多数算法基于随机特性，其收敛性一般是概率意义上的，实际性能不可控，往往收敛速度也比较慢，计算复杂度较高。

在这里插入图片描述

一、最优化方法的定义与分类

1. 一般形式

公式定义
在这里插入图片描述
其中，对于上式中的字母，含义如下：

· f ( x ) f(x) f(x)：代价函数(目标函数)
· x x x：决策向量（单值或者是向量）
· X X X：约束集合，约束集合一定是从属于n维实数空间( R n R^n Rn)中的某个子空间

2. 简单分类

最优化问题主要分为以下几类：

基础：线性规划（Linear Programming）

其他优化：
（1）整数规划(Interger Programming)
也称离散优化(Discrete Optimization)，要求问题定义与求解中的所有决策变量或向量都是离散的整数类型。

（2）混合整数规划(Mixed Integer Programming)
决策变量有些是整型，有些是连续型的。

（3）动态规划/最优控制(Dynamic Optimization)
需要考虑系统的动态性，往往会考虑时间的影响。

（4）随机优化(Stochastic Optimization)
需要考虑问题中的不确定性因素，比如涉及到的部分变量是随机变量，而非确定性的。
e.g. 前台接待系统中某一时段的客流量就是随机、不确定的。

（5）多目标最优化(Multi-Objective Optimization)
在进行优化时，有多个目标函数需要同时达到最优。
e.g. 比如建造房子的时候，需要同时考虑“工期短”、“质量优”、“成本低”等目标

在这里插入图片描述

二、最优化的条件和一些基本概念

1. 凸集

在凸几何中，凸集(convex set)是在凸组合下闭合的仿射空间的子集。更具体地说，在欧氏空间中，凸集是对于集合内的每一对点，连接该对点的直线段上的每个点也在该集合内。例如，立方体是凸集，但是任何中空的或具有凹痕的例如月牙形都不是凸集。

2. 超平面

超平面是n维欧氏空间中余维度等于一的线性子空间，也就是必须是(n-1)维度。
这是平面中的直线、空间中的平面之推广（n大于3才被称为“超”平面），是纯粹的数学概念，不是现实的物理概念。因为是子空间，所以超平面一定经过原点。

3. 支撑面

支撑面 (supporting plane)是凸集几何的一个概念，它是支撑线的推广，也是支撑超平面的特例，设给定凸体Q和平面a，若平面a同F.Q有公共点，但同Q没有公共点，则称a是Q的支撑面.也可把支撑面定义为与Q有非空交集，且Q位于它的一侧的一个平面。

4. 凸函数

在这里插入图片描述

5. 方向导数

方向导数的本质是一个数值，简单来说其定义为：一个函数沿指定方向的变化率。

6. 可微函数的凸性的三定理

（1）定理一

如果f(x)是定义在凸集X上的一个可微函数，则f(x)是凸函数的充要条件是
f ( x 2 ) − f ( x 1 ) ≥ ▽ f ( x 1 ) T ⋅ ( x 2 − x 1 ) f(x_2)-f(x_1)≥▽f(x_1)^T·(x_2-x_1) f(x2)−f(x1)≥▽f(x1)T⋅(x2−x1)

（2）定理二

如果 f ( x ) f(x) f(x)是定义在凸的开集 X X X上的一个二阶可微的函数，则 f ( x ) f(x) f(x)是凸函数的充要条件为
f ( x ) f(x) f(x)对应的Hessian矩阵 H ( x ) H(x) H(x)，对于任意一个 x x x都是半正定的。

【背景知识补充】
开集：对于集合中的任意一点，都能找到该点的一个邻域，且该邻域一定在集合内部。可以近似地认为所谓开集就是“没有边界的集合”,e.g.
x ∣ 满足 ∣ ∣ x ∣ ∣ 2 ＜ 5 {x|满足||x||2＜5} x∣满足∣∣x∣∣2＜5就是开集，如果“<”改成“≤”，则不再是开集。
半正定矩阵：如果一个矩阵是对称阵，且对于任意一个非零的向量x，都有 x T A x ≥ 0 x^TAx≥0 xTAx≥0，就称矩阵A是半正定矩阵。 p.s.
在矩阵论系列博文中《【矩阵论】Hermite二次型(2)》中也对矩阵的正定性定义及定理进行了探讨。

【证明】
在这里插入图片描述
梳理了以上证明过程，即可明白，定理2是基于定理1的。