凸优化笔记(1) 引言

1. 引言

1.1 数学优化

优化问题可以写成如下形式
$minimize\ \ \ f_0(x) \\ subject \ to\ \ f_i(x)\leq b_i\ \ \ i=0,...,m$

向量 $x$ 称之为优化向量， $f_0$ 是目标函数， $f_i$ 是约束函数，问题在于满足约束条件下寻找最优解

一般的，如果目标函数和约束函数是线性函数的话，则是线性规划问题，即
$f_i(\alpha x+\beta y) = \alpha f_i(x)+\beta f_i(y)$
凸优化即讨论约束函数和目标函数是凸函数的优化问题，即
$f_i(\alpha x+\beta y)\leq \alpha f_i(x)+\beta f_i(y)$
可以将凸优化看成是线性规划的扩展

1.1.1 应用

比如投资组合优化等问题，再寻求效益最大化且风险最小化的时候就是应用

大量涉及决策的问题大多数可以转化为数学优化的问题

1.1.2 求解优化问题

优化问题的求解并不简单，但有些特殊的优化问题可以有效地求解
有两类优化问题广为人知：

最小二乘问题
线性规划问题

凸优化问题也是可以被有效求解的

1.2 最小二乘和线性规划

1.2.1 最小二乘问题

最小二乘问题没有约束条件，形式如下

image.png

求解最小二乘问题
上述式子的求解可以简化为求解一组线性方程，由 $Ax-b=0$ 可以推出

image.png

可得解析解
$x=(A^TA)^{-1}A^Tb$

此外如果系数矩阵A是稀疏的话可以更快的进行求解

使用最小二乘
判别一个优化问题是否是最小二乘十分简单，只需要检验目标函数是否是二次函数，然后检验是否是半正定的。

加权最小二乘
形式如下

image.png

可以很方便转化成最小二乘进行求解

正则化
正则化是解决最小二乘问题的另一个技术，一个最简单的形式如下：

image.png

1.2.2 线性规划

线性规划问题如下述形式表示

求解线性规划
存在许多非常有效求解线性规划问题的方法，比如Dantzig的单纯形法，最近发展起来的内点法

使用线性规划

比如Chebyshev逼近问题

image.png

等价于求解如下线性规划问题

image.png

1.3 凸优化

凸优化问题具有以下形式化
$minimize\ \ \ f_0(x) \\ subject \ to\ \ f_i(x)\leq b_i\ \ \ i=0,...,m$
其中需要满足
$f_i(\alpha x+\beta y)\leq \alpha f_i(x)+\beta f_i(y)$
且 $\alpha+\beta=1,\alpha\geq0,\beta\geq0$

1.3.1 求解凸优化问题

凸优化问题没有一个确定的解析解，但是和线性规划类似，存在许多算法求解凸优化问题，实际意义中内点法就比较有效

1.3.2 使用凸优化

同线性规划和最小二乘类似，我们可以将某个问题转化为凸优化问题进而将其求解，不过，判断哪些问题是否属于凸优化问题是比较有挑战性的工作

1.4 非线性优化

即目标函数和约束函数是非线性函数的优化问题

1.4.1 局部优化

寻找局部最优解，不保证是全局最优

1.4.2 全局优化

在全局优化中，人们致力于搜索问题的全局最优解，付出的代价是效率

1.4.3 非凸问题中凸优化的应用

局部优化中利用凸优化进行初始值的选取
非凸优化中的凸启发式算法
- 随机化算法
- 搜索带约束条件的稀疏向量
全局优化的界
- 松弛算法中，每个非凸的约束都用一个松弛的凸约束来替代