优化-1-背景知识

优化 Optimization

广义上的优化问题即要求解如下问题：

$\min_{x\in\mathbb{R}^d} f(x)\quad s.t.\quad x\in X\subseteq \mathbb{R}^d$

其中为候选解 (candidate solutions)，即被优化的参数；为目标函数 (objective function)。

一般我们假定函数是连续且可导的，否则问题将变得十分难以求解。

如果优化目标是已知的，我们往往可以使用求闭式解等方法来针对性的求解。但本文主要聚焦于一类更广泛的问题，即当优化目标具体形式未知时该如何求解。

如果将函数视为黑盒，我们可以引入 Oracle 来和函数进行交互。Oracle 可以被视为目标函数的一个代理，算法可以对 Oracle 进行查询操作，来获取函数的某个信息，如某处的函数值，某处的梯度，某个值是否在约束范围内等等。

其中我们一般称呼为 Zero Order Oracle, 为 First Order Oracle，以此类推。

由此可以将优化算法与优化目标具体形式解耦，同时提供了对于优化算法的评价指标，根据算法收敛对 Oracle 询问次数的需求，可以对算法的优劣进行评价。

评价一个算法的好坏最直观的就是看这个算法收敛所需调用 Oracle 的消耗,考虑一个简单的例子:

$\min_{x\geq 0} x$

我们设计如下优化算法

由此可以计算收敛率

$f(x_t) - (x^*) = f(x_t) - 0 = \frac{1}{2^t}f(x_0) \leq \epsilon$

则

$T \sim \mathcal{O}(\log\frac{1}{ \epsilon})$

凸集 Convex set
- 定义：若一个集合是凸集，那么对于集合内任意两点的连线上的点仍在凸集内
- 性质：凸集的交仍是凸集
- 性质：凸集外一点到凸集上的投影是唯一的，且 $Proj_C(x):=\arg\min_{y\in C}||y-x||$
凸函数 Convex function
- 定义：若一个函数是凸的，则
  1. 定义域是凸集
  2. 对定义域内任意两点，两点间连线高于对应位置函数值，即 $f(\lambda x+(1-\lambda)y)\leq \lambda f(x) + (1-\lambda) f(y)$
- 推论：对定义域内任意两点和处的梯度，有 $f(y)\geq f(x)+ \langle \nabla f(x),y-x \rangle$
- 推论：对定义域内任意一点，其黑塞矩阵正半定，即 $\nabla^2f(x) \succeq 0$
凸优化 Convex Optimization
- 定义: 给定凸函数，凸集，凸优化即求解 $\min_{x\in\mathbb{R}^d} f(x)\quad s.t.\quad x\in C$
- 性质: 在凸函数上，局部最优解同时也是全局最优解，因此极小值 Local Minimum 和鞍点 Critical point 都是全局最小值 Global Minimum。

本系列 “优化” 笔记均整理自 Dr. Martin Takac 在 MBZUAI 2023 Spring 开设的 MTH702 Optimization 课程内容。