标准形式：

定义： 是可行解当且仅当 。

定义：可行解 是（全局）最优解如果 对于所有的可行解 成立。

定义：可行解 是局部最优解，如果存在 ， 对于所有满足 的可行解成立。

凸优化问题：如果(1)中 和 是凸函数， 是仿射函数，那么我们称该优化问题是凸优化问题。

命题：凸优化问题的可行解集一定是凸集。

定理：凸优化问题的局部最优解一定是全局最优解。

证明：

设(P)的可行解集是 ， 是局部最优解，那么存在 ，使得 。

， ， ，因为 是凸集，所以 ，进而有：

所以： 成立。

定理： 是凸优化问题的最优解当且仅当 是可行的，并且 对于所有的可行解 成立。

推论：

凸优化问题如果存在可行解 并且 ，那么 一定是最优解。

无约束问题的最优解：

凸问题：最优解 等价于 梯度为零

非凸问题：

• 如果 是局部最优解，那么 ；
• 如果 ，那么 是局部最优解。

我们说两个优化问题（P1），（P2）是等价的：如果可以通过（P1）的最优解得到（P2）的最优解，反之亦然。

产生等价问题的变换：

1. 变量替换
2. 目标函数和约束的变换

比如在最小二乘法中下面两个问题是等价的：

2. 松弛变量（Slack variable）

注意到 当且仅当 ，所以优化问题（P）等价于：

注意到（P3）的变量是 ，一共有 个变量，新变量 叫做松弛变量。显然（P1）和（P3）等价，这是因为如果 是（P1）的最优解，那么 是（P3）的最优解；反之 是（P3）的最优解，那么 是（P1）的最优解。

3. 函数上图优化问题（epigraph problem form）

优化问题（P）等价于：

是（P）的最优解当且仅当 是（P4）的最优解。

LP（线性规划问题）：

（P5）是线性规划问题的标准形式，更广泛的线性规划问题是：

而（P6）和（P5）事实上是等价的：也就是说广泛线性规划问题可以转化为线性规划的标准格式。方法是引入松弛变量 和将 分为正部和负部，那么（P6）可以转化为：

QP（二次规划问题）：

这里要求 。可以看到 LP 是 QP 在 时的特殊形式

QCQP（二次约束二次规划问题）

SOC（二阶锥优化问题）

当 时，SOC 退化为一个 QOQP 问题；当 时，SOC 退化为一个 LP 问题。因此SOC 是比 QCQP 更加泛化的问题。

例子：

最优线性分类问题：

假设我们有两类点： ，我们希望找到一个超平面能够使得A、B中的点在超平面两边，并且使得距离超平面最近点到超平面的距离是最大的。

那么优化问题是：

这个优化问题不是一个凸优化问题，但是可以转化为一个凸优化问题：

这是因为对于（P2）的一个可行解 ，那么它也是（P1）的可行解，并且 ，因此存在 使得：

也就是说：

对于（P1）的一个可行解 ，令 ，那么 是（P2）的一个可行解，并且有：

因此存在 使得：

因此：

因此：

把下述优化问题：

转化为 SDP（半定规划）问题。