凸优化（一）——Introduction

Introduction

一、最优化问题的数学表达

在最优问题中，其数学表达往往能化成标准形式，如下：

$$\begin{aligned} &minimize \quad f_0(x)\\ &subject \ to \quad f_i(x) \leq b_i,\quad i = 1,...,m \end{aligned}$$ 上面的数学形式被称之为最优化问题的标准形式。 $x$是一个向量，$x=(x_i,x_2,...,x_n)$。 $subject \ to$有时候也写成 $s.t.$
上式中的 $minimize\quad f_0(x)$被称之为“目标函数”，即我的优化问题的目标是使目标函数的值达到最小。 $subject \ to \quad f_i(x) \leq b_i,\quad i = 1,...,m$被称之为约束条件，即对变量x的约束。

实际上在实际问题中，往往会有很多不同的形式，但是都是可以通过一定的方法化成这种标准形式的。这里给出一个例子：
假如我有一个优化问题，如下形式：

$$\begin{aligned} &minimize \quad f_0(x)\\ &subject \ to \quad f_i(x) = b_i,\quad i = 1,...,m \end{aligned}$$ 那么怎么样才能转换为标准形式呢？
即如何找到小于等于的不等式，使其等价于这个等式。实际上，在数学中，a=b的充要条件是a既大于等于b,而且a小于等于b。故上面的最优化问题可以化成如下形式：
$$\begin{aligned} &minimize \quad f_0(x)\\ &subject \ to \quad f_i(x)\leq b_i,\quad i = 1,...,m\\ &subject \ to \quad f_i(x)\geq b_i,\quad i = 1,...,m\\ \end{aligned}$$ 上式中含有大于等于，仍旧不是标准形式，则在大于等号的两边同乘一负号，即可化为标准形式。
$$\begin{aligned} &minimize \quad f_0(x)\\ &subject \ to \quad f_i(x)\leq b_i,\quad i = 1,...,m\\ &subject \ to \quad -f_i(x)\leq -b_i,\quad i = 1,...,m\\ \end{aligned}$$ 同样的，如果优化问题不是求最小值，而是求最大值，那只要在目标函数前面加一个负号，即可转换为求最小值的问题。总而言之，不管是求最大、最小，不管约束是等式还是不等式，都是可以转化为标准形式的。

二、线性规划、非线性规划、凸优化概念

如果最优化问题中的目标函数和约束条件都是线性的，即满足：

$$f_i(\alpha x +\beta y)=\alpha f_i(x)+\beta f_i(y),\quad i=0,1,...,m$$ 则称此最优化问题为线性规划。反之，若 $f_i$含有非线项，则称之为非线性规划。

在非线性规划中，有一类比较特殊的规划问题————凸优化。即其目标函数和约束条件满足如下形式：

$$f_i(\alpha x +\beta y)\leq \alpha f_i(x)+\beta f_i(y),\quad i=0,1,...,m\\ \alpha \geq0 ,\beta \geq0,\alpha +\beta =1$$ 比较线性规划和凸优化的表达形式，会发现凸优化比线性规划的表达更具有一般性。前面已经给出了如何将一个等式等价的转换为两个小于等于的不等式。实际上，线性规划可以看成是一种比较特殊的凸优化。（关于为何满足这种形式的就是凸优化，会在后面详细的描述，这里只是为了了解这个概念）。

在概念上来说，凸优化问题与最小二乘法和线性规划是非常相似的。如果我们能够将一个最优化问题转换为一个凸优化问题，那么我们一定能够高效的解决这个问题（有一点点夸大）。虽然解凸优化比较容易，但是如何把一个问题转化为凸优化问题是非常难的。

三、非线性规划方法

在非线性规划中，如果我们不知道目标函数和约束条件是否是凸的，那么很难找到一个有效的方法来解决这种一般的非线性规划问题。即使你的变量只有很少的几个，求解也是非常麻烦的，更不用说变量有成千上万个的情况。现有的对于一般非线性规划的方法都只能处理一些较为特殊的情况。

1、局部最优化

在局部最优化方法中，我们放弃了寻找全局最优解，转而寻找局部最优解。

局部最优化方法非常的快速，能够解决变量比较多得情况，也有较好的普适性，因为它只要求目标函数和约束可导即可。在很多工程设计中，我们有时候全局最优解和局部最优解的差异不是很大，那实际上我只要找到一个比较好的局部最优解即可。

局部最优化也有很多缺点，比如不能发现正确的全局最优解。另外，这种方法对初始点的要求比较高，选择了不同的初始点，那么结果可能也是千差万别的。局部最优算法也对参数变量比较敏感。运用局部最优算法相对于最小二乘法、线性规划、凸优化也较复杂。他需要选择算法、需要调整算法参数、需要找到好的初始点等。

2、全局最优化

在全局最优化中，我们要找到真实的全局最优解，随之而来的是对算法效率的牺牲。全局最优算法的运算量会随着参数个数n和约束条件个数m的增加而呈指数增加。这也说明，一旦参数增加或者约束条件增加，会使算法的运算量变得非常大。所以一般全局最优算法都用在变量较少的情况。

3、凸优化在非凸问题中的应用

（1）用于初始化局部最优化法的初始值
这是一种将凸优化与局部最优化方法的结合。对于一个非凸最优化问题，我们首先找到一个与其很相似的凸函数，先解出这个凸优化问题的最优解（对于凸优化问题，我们不需要找到特定的初始值，因为不管初始化值是什么，凸优化都能找到问题的最优解），然后以此最优点作为初始点来运行局部最优算法。
（2）用于限定全局最优化法的最优值范围
具体有两种方法，一种是一般松弛法，即用松弛的、凸的约束条件替代原来的非凸约束。另一种是拉格朗日松弛法（拉格朗日对偶问题），这种方法能够在全局最优解周围一个比较窄的限定范围。

Preference：
1、Convex Optimization—Stephen Boyd and Lieven Vandenberghe
2、Convex Optimization Lecture slides —Stephen Boyd