凸优化笔记(1) 引言

凸优化笔记(1) 引言

1. 引言

1.1 数学优化

优化问题可以写成如下形式

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

一般的，如果目标函数和约束函数是线性函数的话，则是线性规划问题，即

凸优化即讨论约束函数和目标函数是凸函数的优化问题，即

可以将凸优化看成是线性规划的扩展

1.1.1 应用

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

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

1.1.2 求解优化问题

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

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

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

1.2 最小二乘和线性规划

1.2.1 最小二乘问题

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

求解最小二乘问题 上述式子的求解可以简化为求解一组线性方程，由

可以推出

可得解析解

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

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

加权最小二乘 形式如下

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

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

1.2.2 线性规划

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

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

使用线性规划

比如Chebyshev逼近问题

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

1.3 凸优化

凸优化问题具有以下形式化

其中需要满足

且

1.3.1 求解凸优化问题

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

1.3.2 使用凸优化

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

1.4 非线性优化

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

1.4.1 局部优化

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

1.4.2 全局优化

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

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

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