【知识总结】凸优化问题

优化问题

标准形式（默认是极小化问题）
相关术语
- 优化变量
- 目标函数（费用函数）
  - 如果是极大化问题，目标函数称为效用或满意度，而不是费用
- 不等式约束
- 不等式约束函数
- 等式约束
- 等式约束函数
- 无约束问题
- 优化问题的定义域
- 可行点
  - 定义域中满足约束条件的点
- 可行问题
  - 至少存在一个可行点的问题
- 可行集（约束集）
  - 所有可行点的集合
- 最优值
- 不可行问题
- 无下界问题
  - 存在可行解的数列满足，此时
- 最优点（最优解）
  - 满足的
- 最优集
  - 所有最优解的集合
- 可解问题
  - 存在最优解的问题，此时称最优值可得、可达
- -次优解
  - 满足的可行解
- -次优集
  - 所有-次优解的集合
- 局部最优解
  - 称是局部最优解，若存在，使得下面条件成立（两个条件是一个意思）
  - 是关于的优化问题的解
- 起作用约束
  - 若可行且，则称在处起作用
  - 若可行且，则称在处不起作用
- 冗余约束
  - 去掉该约束不改变可行集
- 可行性问题
  - 目标函数设置为常数（一般是设置成零）
  - 当可行集非空，最优解是零，否则是
  - 写作
等价问题
- 非正式定义
  - 若得到一个问题的解，能快速得到另一个问题的解，反之亦然，则两个问题等价
- 等价变换（这里不细展开，在凸优化等价问题中再讨论）
  - 变量代换
  - 目标函数变换
  - 约束变换变换
  - 松弛变量引入
  - 上境图问题形式

凸优化问题

标准形式（默认是极小化问题）
- 注
  - 是凸函数
  - 等式约束是仿射的，可以写成矩阵形式
拟凸优化问题
- 若是拟凸的而非凸的，其他条件不变，则问题是拟凸优化问题
凸优化问题相关性质
- 凸优化问题的定义域是凸集
- 凸优化问题的可行集是凸集
  - 所以凸优化问题是在凸集上优化凸函数
- 凸优化问题的任意局部最优解是全局最优解
可微函数的最优性条件
- 一般凸优化问题（目标函数可微）
  - 此时对于所有有，
  - 可行集
  - 是最优解，当且仅当，且
- 无约束凸优化问题
  - 是最优解，当且仅当
- 只含等式约束凸优化问题
  - 等式约束设为
  - 是最优解，当且仅当，且存在，使得
  - 上面条件也可以理解为或，具体来说，考虑到任意两个可行解满足，故要求和垂直
- 非负象限的凸优化问题
  - 设约束为，即
  - 是最优解，当且仅当
等价的凸问题
- 消除等式约束
  - 求解的特解，和的零空间矩阵
  - 通过换元得到如下关于的不包含等式的等价凸优化问题
- 引入等式约束
  - 当目标函数或约束函数有形式，通过换元得到等价的凸优化问题，此时引入了等式约束
- 松弛变量
  - 当约束函数有仿射形式，引入松弛变量，得到等式，并引入不等式
- 上境图形式
- 优化部分变量
  - 考虑到（其中），故下面两个优化问题等价
  - 注：设

线性规划问题

线性规划问题（LP）
- 目标函数和约束函数都是仿射的
- 形式为
  - 其中
  - 一般省略

二次优化问题

二次优化问题（QP）
- 目标函数是凸二次型，约束函数是仿射的
- 形式为
  - 其中
二次约束二次规划（QCQP）
- 目标函数和约束函数都是凸二次型
- 形式为
  - 其中
- 线性规划是二次规划的特例，二次规划是二次约束二次规划的特例
二阶锥规划（SOCP）
- 形式为
  - 其中
  - 不等式约束是二阶锥约束
  - 二次约束二次规划是二阶锥规划的特例（令后SOCP退化为QCQP）

几何规划

单项式函数
- 简称单项式
正项式函数
- 简称正项式
几何规划（GP）
- 正项式形式为
  - 其中是正项式，是单项式，问题定义域是
  - 是隐式的
- 通常使用变量代换
  - 单项式函数转换为以仿射函数为指数的函数
  - 多项式函数转换为以仿射函数为指数的函数的和
  - 正项式形式的几何规划转化为凸形式的几何规划
- 几何规划是线性规划的一种推广

广义不等式约束

本节介绍广义不等式的优化问题，核心是用定义在锥上的偏序推广约束关系中的不等号

基本形式
- - 其中为正常锥，为-凸的。
- 可行集，任意下水平集，最优集都是凸的
- 任意局部最优解是全局最优的
- 可微函数的最优性条件与上文介绍的相同
锥形式问题
- SOCP问题表示为锥形式问题
  - 其中（即中的二阶锥）
半定规划（SDP）问题
- - 其中
- 线性规划问题表示为SDP问题

向量优化

本节介绍向量优化问题，核心是用定义在锥上的偏序推广目标函数的最小化过程

向量优化问题基本形式
- - 是优化变量，是正常锥，是目标函数，是不等式约束函数，是等式约束函数
凸向量优化问题
- 目标函数是-凸的，不等式约束函数是凸的，等式约束函数是仿射的
- 等式约束也可以表示为
最优点和Pareto最优点
- 设可行点的目标值的集合
  - 可达值目标集合
- 最优点
  - 对应目标函数值是锥的最小元
- Pareto最优点
  - 对应目标函数值是锥的极小元