凸优化笔记(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 非凸问题中凸优化的应用
  • 局部优化中利用凸优化进行初始值的选取
  • 非凸优化中的凸启发式算法
    • 随机化算法
    • 搜索带约束条件的稀疏向量
  • 全局优化的界
    • 松弛算法中,每个非凸的约束都用一个松弛的凸约束来替代

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券