【最优化方法】随笔 - 基本概念简单整理

前言

随笔 - 基本概念

1.背景知识

最优化是一种数学方法，在一定约束条件下，找到某个目标函数的最大值或最小值。简单来说，最优化就是“找到最佳解决方案”的过程。（从所有可能的方案中选择最合理的一种方案）

寻找最优方案的方法即最优化方法

两个概念：

• 目标函数：需要优化的函数，可以是求最大值或最小值。
• 约束条件：限制目标函数的一系列条件或规则。

2.最优化问题

2.1应用

商业决策、工程设计、资源分配、算法设计等

2.2 最优化问题的数学形式

极小化目标函数、可行区域和可行解是优化问题中的三个核心概念。

极小化目标函数

极小化目标函数是指在优化问题中，希望找到的解使得目标函数的值尽可能小。

可行区域

可行区域是指所有可能的解中，满足所有约束条件的解的集合。

可行解

可行解是指在可行区域内的任何一个解。这些解满足所有的约束条件，因此可以被认为是问题的有效候选解。

求解此类问题称为programming问题

2.3 举例说明

数学模型为

2.4 最优化问题不同的类型

1. 离散最优化：决策变量取值是离散的，也就是说，它们只能取有限个或可数无限个值。这类问题通常涉及整数或组合优化，例如旅行商问题（TSP）和0-1背包问题。

2. 连续最优化：决策变量取值是连续的，可以是任意实数值。这意味着决策变量可以在某个区间内取任意值，例如在生产计划中确定产品的最优产量。

3. 光滑最优化：所有函数（包括目标函数和约束函数）都是连续可微的。这意味着这些函数在定义域内具有连续的导数，可以使用微分法来寻找最优解。

4. 非光滑最优化：至少有一个函数（目标函数或约束函数）是非光滑的，也就是说，它可能在某点不可导或不连续。这类问题可能需要特殊的优化算法来解决，因为传统的基于梯度的方法可能不适用。

5. 线性规划：目标函数和所有约束函数都是变量的线性函数，即它们可以表示为变量的一次幂的线性组合。线性规划问题通常可以通过单纯形算法等方法解决。（我们开始学用）

6. 二次规划：目标函数是变量的二次函数，即可以表示为变量的平方项和变量乘积的线性组合，而约束函数是线性函数。二次规划问题比线性规划问题复杂，但仍然可以通过一些特定的算法（如内点法或二次规划算法）来解决。

2.5 一些概念

3.凸集和凸函数

3.1 范数

概述：范数是一个在向量空间中定义的函数，它赋予每个向量一个非负长度或大小。范数通常用来衡量向量的大小或距离，它具有以下性质：

1. 非负性：对于任意向量 𝑥，范数 ‖𝑥‖ 总是非负的，即 ‖𝑥‖ ≥ 0。当且仅当向量 𝑥 是零向量时，范数等于0。

2. 齐次性（绝对齐次性）：对于任意向量 𝑥 和任意非负实数 α，有 ‖α𝑥‖ = |α|‖𝑥‖。

3. 三角不等式：对于任意向量 𝑥 和 𝑦，有 ‖𝑥 + 𝑦‖ ≤ ‖𝑥‖ + ‖𝑦‖。

最常见的几种范数包括：

• 欧几里得范数（L2范数）：这是最常用的范数，定义为向量的各分量平方和的平方根，即 ‖𝑥‖₂ = √(∑︀_{𝑖=1}^{𝑛} |𝑥𝑖|²)。

• 曼哈顿范数（L1范数）：也称为1-范数，是向量的各分量绝对值之和，即 ‖𝑥‖₁ = ∑︀_{𝑖=1}^{𝑛} |𝑥𝑖|。

• 无穷范数（L∞范数）：是向量中所有分量绝对值的最大值，即 ‖𝑥‖₊ = max(|𝑥₁|, |𝑥₂|, ..., |𝑥𝑛|)。

• p-范数：是L1范数和L2范数的一般化，定义为 ‖𝑥‖ₚ = (∑︀_{𝑖=1}^{𝑛} |𝑥𝑖|^𝑝)^(1/𝑝)，其中 𝑝 ≥ 1 且 𝑝 ≠ ∞。

在函数空间中，范数可以用来衡量函数的“大小”或“能量”。

3.2 矩阵范数（扩展）

3.3 凸集与凸函数

凸集

定义：一个集合 C 在向量空间中称为凸集，如果对于集合中的任意两个点 x 和 y，以及任意的 λ 满足 0 ≤ λ ≤ 1，点 λx + (1 - λ)y 也在集合 C 中。

几何解释：直观上，如果一个集合中的任意两点之间的线段都完全包含在这个集合内，那么这个集合就是凸的。

性质：

• 任意两个点的凸组合（即线性组合，系数之和为1）也在凸集内。
• 凸集是封闭的，即如果一个序列的点都在凸集内，并且收敛到某一点，那么这个极限点也在凸集内。

凸函数

定义：一个函数 f: C → ℝ 定义在凸集 C 上，如果对于任意的 x, y ∈ C 和任意的 λ 满足 0 ≤ λ ≤ 1，都有：

f(λx + (1 - λ)y) ≤ λf(x) + (1 - λ)f(y)

几何解释：如果一个函数的图像位于任意两点连线的下方，那么这个函数是凸的。

性质：

• 凸函数的局部最小值也是全局最小值。
• 凸函数的一阶导数（如果存在）是单调递增的，二阶导数（如果存在）是非负的。

凸集的证明见：【最优化方法】期末考试题型讲解部分 - 凸集的证明

写在最后

欢迎技术类的问题到这里提出，我会逐个解答

END