最优化学习笔记

视频1：什么是最优化？

在这一个视频中主要是介绍最优化问题的一些基础概念，什么是最优化问题？什么叫做最优化问题的解？最优化问题的表现形式？有哪些分类？

最优化问题是什么，就涉及最优化的基本含义，简单来说就是在一定的约束下求得一个函数或者一个函数组的最优值，最优化的基本数学模型可以写为：

其中，$x$称之为决策变量，$f(x)$称之为优化目标（目标函数），$C_i(x)$ 称之为约束函数，包括等式约束与不等式约束，$I,E$称之为约束指标集，包括等式指标集与不等式指标集。

其中一个小细节：其中$f(x)$既可以是实值函数也可以是向量函数，但是$C_i(x)$只可以是实值函数。

从此便可以看出一个优化问题必须含有3个要素，决策变量、目标函数、约束函数。

接下来考虑，面对一个最优化问题，决策变量可以从哪些集合中寻找，这就涉及可行域与可行集的概念，对于一个集合当其同时满足等式约束与不等式约束时，称之为可行集，写法如下：

如果$F$为空集，那么就能够称该最优化问题为空集，连满足约束的点都没有了，何谈最优的点，最优化问题也就是不可行的，需要注意的是，可行并不意味着最优解的存在，只是满足约束条件而已。

最后再来考虑最后结果的形式，也就是解的定义，对于一个$x$来说，在可行域内，如果其目标函数计算出来最小，并且不存在任何其他的$x$的目标函数与其相等，则称其为严格全局最优解，如果有可能相等的值，那么就称为全局最优解。如果只是在某一个邻域内满足最小的条件，那么就是局部最优解或者严格局部最优解。在这里练习一下数学表达式的严谨性。

• 全局最优解：$\forall x \in F \quad f(x^*) \leq f(x)$
• 严格全局最优解：$\forall x \in F \backslash \lbrace x^* \rbrace \quad f(x^*) \leq f(x)$
• 局部最优解：$\forall x \in F \bigcap N_{\epsilon}(x^*) \quad f(x^*) \leq f(x)$
• 严格局部最优解：$\forall x \in F \bigcap N_{\epsilon}(x^*) \backslash \lbrace x^* \rbrace \quad f(x^*) \leq f(x)$

全局最优解的结合也就构成了最优解集的定义，通常写作$S$，那么一个最优问题无最优解就可能是以下三种情况：

1. 最优解集为空集
2. 可行域为空集
3. 最优问题的目标函数在可行域上无下界。

需要注意的是，最优问题在实际过程中，目标函数可能取最大值，也有可能取最小值，但在最优化的学习中，只针对最小值学习即可，最大值转化一下符号就行）

此外，对于最优化问题的描述方法还有很多，大同小异：

例如：

还可以直接将可行集写在决策变量处（角标）

最优化问题有很多，对于每一种优化问题会有其最适合的寻优方法，这就涉及到了优化问题的分类，常见的最优化问题分类如下：

1. 无约束优化（可行域为全空间）/约束优化
2. 线性规划（目标函数与约束函数均为线性）/非线性优化
3. 单目标优化（目标函数为实值函数）/多目标优化（目标函数为向量值函数）
4. 光滑优化（目标函数与约束函数均是连续可微的）/非光滑优化
5. 凸规划（目标函数是凸函数，可行域是凸集）/非凸规划
6. 连续优化/离散优化（可行域中有限的点）

等等等等

需要注意的时候，部分优化问题是可以转化优化问题的分类，例如整型的离散优化，可以将其转化为连续型

视频2：基础知识

在这一讲中主要叙述了：

1. 向量范数与矩阵范数
2. 梯度、海森阵、雅可比阵
3. 中值定理、泰勒公式

首先是范数，范数的提出的主要作用就是衡量距离远近，比如在迭代优化求解过程中，最优点为$(10,5)$，在第 $k$ 步中，迭代到了$(8,7)$，在第$k+1$步时，迭代到了 $(9,6)$ ，那么如何去判断距离最优点的距离呢？之前我们通常使用两点之间距离直接判断 $((10-8)^2+(5-7)^2)$， 这是一种方法，那么范数就是这种意思，它将向量或者矩阵映射到实数域上，使得其更容易比较两点接近程度。

先来说，向量范数其实就是向量的映射，将一个向量映射到实数域，让其可以直接对比，但是范数并不是一种唯一确定的计算方法，满足下面3个特性的向量映射方法均能称为范数：

1、满足非负性，向量的范数是非负的，并且，当范数为0时，向量必定也是0向量

2、满足正齐次性，一个实数与向量的乘积的范数等于实数与向量范数的乘积，就是$\parallel ax \parallel=\mid a \mid \parallel x\parallel$

3、满足三角不等式，两个向量和的范数不超过两个向量的范数和，就是：$\parallel x+y \parallel \leq \parallel x \parallel+\parallel y \parallel$

常用的范数：

1范数：所有项的和，写法：$\parallel x \parallel_1:=\sum_{i=1}^n \mid x\mid$

2范数：平方和再开方，$\parallel x \parallel_2=\sqrt{x^Tx}=\sqrt{\sum_{i=1}^nx_i^2}$

无穷范数：就是向量中元素最大的项，$\parallel x\parallel_\infty=max\lbrace \mid x_i\mid:i\in \lbrace1,2,\cdots,n \rbrace \rbrace$

通用的范数计算公式，上面的范数其实都符合同一个计算结果，P范数：

此外，椭球范数有时候也会用上：

其中 $A$ 必须为正定矩阵。

范数还有一个等价性命题，其实就是说用$p$范数与用$a$范数其实是一样的，是等价的，公式如下，可以利用距离的概念来理解范数的意义（无论是使用公里还是米，都可以作为距离的衡量）。

然后是矩阵的范数的概念，与向量一样，不过是将矩阵$(n \times n)$ 映射到实数域，也需要满足3个性质，非负性、正齐次性、三角不等式关系，这里不再叙述。

矩阵的范数其实还有一点不同，矩阵范数的计算方法是需要借助一个诱导向量来实现：

常用的矩阵范数有

1. 列范数（由1范数诱导得到）：其实就是矩阵先按照列求出每一列的和，然后找到最大的列。
2. 行范数（由无穷范数诱导得到）：其实就是矩阵先按照行求出每一行的和，然后找到最大的行
3. 谱范数（有2范数诱导得到），具体公式先不赘述。

相比于向量范数，矩阵范数的性质多了一个相容性，及两个矩阵乘积的范数小于等于两个矩阵范数的乘积。

以上是用于衡量距离的范数的定义。

在最优化方法中还会涉及到方向问题，那就会涉及