凸优化笔记 10：凸优化问题

前面讲了那么多关于凸集、凸函数的知识，然而都是铺垫，现在我们才来到了这门课的重头戏部分——凸优化问题！

1. 一般优化问题

一般优化问题的形式为 $$\begin{array}{rl}\text{ minimize }& f_0(x)\\ \text{ subject to }& f_i(x)\le 0,i=1,\dots ,m\\ & h_i(x)=0,i=1,\dots ,p\end{array}$$ 其中 $f_0(x)$ 为目标函数，$f_i(x)$ 为不等式约束函数， $h_i$ 为等式约束函数。优化问题的最优解为 $$p^{\star }=inf\{f_0(x)|f_i(x)\le 0,i=1,\dots ,m,h_i(x)=0,i=1,\dots ,p\}$$ 如果 $p^{\star }=\mathrm{\infty }$，则问题不可行；如果 $p^{\star }=-\mathrm{\infty }$ 则该问题没有下界。

最优解则有 $f_0(x)=p^{\star }$，局部最优解(local optimal)有 $$\begin{array}{rl}\text{minimize}(\text{over }z)& f_0(z)\\ \text{subject to}& f_i(z)\le 0,i=1,\dots ,m,h_i(z)=0,i=1,\dots ,p\\ & \Vert z-x{\Vert }_2\le R\end{array}$$ 也即只在一个小的邻域内考虑优化问题。

注意：

• 有的优化问题有最小值，但是没有可行解，比如 $f_0(x)=1/x$；
• 有的问题根本就没有最小值，比如 $$
• 有的问题只有局部最小值，比如 $$

上面提到的优化问题中有等式和不等式约束，这些我们都称为显式约束(explicit constraints)，同时由于 $$ 应属于各个函数的定义域内，因此还有隐式约束(implicit constraint)，即 $$ 没有显式约束的优化问题被称为无约束优化问题(unconstrained)。比如 $$ 是一个无约束优化问题，包含了隐式约束 $$。

其实有约束优化问题也可以转化为无约束优化问题，只需要加一个指示函数，一开始提到的一般优化问题就可以利用 $$ 转化为下面的无约束优化问题，不过这种转化可能并没有太大的意义 $$ 除了优化问题，还有一种可行解问题(Feasibility problem)，也就是给定一系列约束来寻找是否有可行解 $$ 这实际上也可以转化为一般优化问题 $$

2. 凸优化问题

2.1 凸优化问题定义

凸优化问题(Convex optimization problem)要求目标函数为凸函数，而且定义域为凸集，这样可以利用凸函数和凸集的优良性质简化问题，因此凸优化问题的一般形式为 $$ 其中要求目标函数和约束函数 $$ 均为凸函数。

Remarks：需要注意这里还要求等式约束均为仿射函数，这是因为我们希望定义域是凸集，假设等式约束 $$ 不是线性的，即使 $$ 是凸函数，$$ 也不一定是凸集。比如二次等式约束 $$，得到的定义域就是一个球面，显然不是一个凸集，这对优化不利。

有时候我们直接拿到的优化问题并不符合上面的形式，但是可以经过化简得到等价问题，就是凸的了，比如 $$ 经过简单化简就有 $$

2.2 凸优化问题的最优解

对于凸优化问题有一个极其重要的性质，就是

凸优化问题的局部最优解就是全局最优解

证明也很简单，若 $$ 为局部最优解，只需要假设另外一个全局最优解 $$，那么利用凸函数的性质，就可以在 $$ 的邻域内导出矛盾，如下图图示。

optimal

凸优化问题的最优解还有一个很好的判据

$$ 为最优解，当且仅当 $$

证明过程只需要应用凸函数的一阶等价定义即可，即 $$。

这个怎么直观理解呢？还记得我们之前在拟凸函数那里提到的“支撑超平面”吗？实际上 $$ 定义了一个等高线，由于 $$ 是一个凸函数，因此这个等高线实际上围成了一个凸集，这个凸集也就是一个下水平集。而这里的 $$ 就是这个下水平集的一个支撑超平面，正如下图所示。同时注意，$$ 也代表着函数指上升的方向，如果说对任意定义域内的 $$，都有 $$ 成立，那么说明我们从 $$ 走到 $$ 总会使 $$ 增大，也就是说 $$ 就是最优解，对应最小值。

gradient

利用上面这两个性质，我们可以对很多类型的凸优化问题的最优解有一个认识。

无约束优化问题：对无约束优化问题，$$ 为最优解，当且仅当 $$ 等式约束优化问题：$$，则有 $$ 为最优解，当且仅当存在 $$ $$ 证明：因为 $$ 实际上定义了一个超平面，如果 $$ 为最优解，那么 $$ 一定没有这个平面内的分量，也就是说 $$。

这个实际上就等价于 Lagrange 乘子法，我们来看拉格朗日函数的定义 $$ 非负象限内的优化：$$，$$ 为最优解，当且仅当 $$ 证明：首先由于定义域为非负象限，意味着 $$ 可以取到正无穷，因此可以推导出 $$，故 $$。另一方面，对于凸优化问题的最优解，有 $$，取 $$，因此有 $$，故 $$。

实际上这里被称为互补性条件(complementary condition)，也就是 KKT 条件的一部分。

2.3 等价问题化简

有时原始优化问题比较难，可以通过等价转换进行简化。

消去等式约束：比如对一般的凸优化问题，等式约束实际上定义了一个超平面，这可以表示为特解 + 一组基的形式 $$ 原始凸优化问题就可转化为 $$ 添加等式约束：实际上就是上面的一个逆过程，这个过程中取药添加一个等式约束 $$，由于添加了变量 $$，会使问题变量数增加，同时优化变量也需要加上 $$。

引入松弛变量：比如对于线性不等式约束的优化问题 $$ 可以引入松弛因子 $$，得到 $$ 例子：下面两个优化问题是等价的吗？其中 $$ $$ 不一定等价。由于 $$，若 $$ 为方针，则二者等价，否则说明 $$，也即 $$ 为一个瘦高型的矩阵，如果我们取 $$，那么很显然 $$ 与 $$ 并不等价，因为 $$ 列不满秩。

epigraph 形式：任意标准形式的凸优化问题都可以转化为下面的形式 $$ 这种变化很重要，可以将优化目标转化为约束函数，对于后面一些典型凸优化问题的转化很有用。

对某些变量最小化：实际上就是对于存在多个优化变量时，提前通过计算消去一些变量 $$ 其中 $$。

3. 拟凸优化问题

拟凸函数跟凸函数有一些相似的性质，尤其是拟凸函数的任意下水平集都是凸集，因此很多时候对于拟凸问题，也可以用凸优化的一些方法有效解决。

拟凸优化问题(Quasi convex optimization) 的一般定义为与凸优化基本相同，只不过目标函数 $$ 可以是拟凸函数，但约束函数 $$ 仍需要是凸函数。

Remarks：我个人觉得这里其实约束函数也可以是拟凸函数？因为即使是拟凸函数，$$ 也可以得到凸的定义域？

但是此时拟凸优化问题就没有凸优化那么好的性质了，比如局部最优解不一定是全局最优解

quasicvx

尽管如此，由于拟凸函数任意下水平集 $$ 都是凸集，我们可以利用这个性质将其转化为凸函数 $$ 来表示，由此就可以用凸优化来求解。

例子

最简单的例子，拟凸函数 $$ 的下水平集可以表示为 $$，我们可以用函数 $$ 来等价表示 $$ 不过这种表示方法意义不大， 这个函数不连续不可微。我们还有其他的表示方法比如 $$ 另外，如果拟凸函数 $$ 有一些特定的性质，比如 $$，其中 $$ 为凸函数，而 $$ 为凹函数（容易证明此时 $$ 为拟凸函数），那么我们还可以取 $$ 为 $$ 拟凸优化问题的求解

假如当前拟凸优化问题的最优解为 $$，那么对于寻找可行解问题 $$ 如果 $$，则该问题有可行解，如果 $$，则没有可行解。因此对于原始凸优化问题，可以利用二分法迭代求解

quasicvx-solve

4. 典型凸优化问题

4.1 线性规划(LP)

线性规划(Linear program)问题的一般形式为 $$ 联系我们前面提到的凸优化问题最优解性质，有 $$，也即目标函数的等高线是一系列超平面

LP

例子 1：对于 piecewise-linear minimization 问题(无约束优化) $$ 可以转化为 $$ 例子 2：多面体的切比雪夫中心(Chebyshev center) $$ 可以用优化问题表示为 $$

chebyshev_center

4.2 线性分式规划

线性分式规划(Linear-fractional program) 的一般形式为 $$ 其中 $$。这个问题可以等价转化为线性规划。

4.3 二次规划(QP)

二次规划(Quadratic program)的一般形式为 $$ 其中 $$。

与线性规划不同的是，目标函数的等高线变成了椭球面

QP

例子：最小二乘就是最经典的二次规划的例子，$$

4.4 二次约束二次规划(QCQP)

二次约束二次规划(Quadratically constrained quadratic program)的一般形式为 $$ 其中 $$。

一般会限制 $$，也就是不能为 0 矩阵(有什么意义吗？不关键)

4.5 二次锥规划(SOCP)

二次锥规划(Second-order cone programming)的一般形式为 $$ 其实 SOCP 比前面几种问题都更广泛，他们都可以看作是 SOCP 的一种情况

SOCP

4.6 鲁棒线性规划

对于优化问题，有时候我们的参数比如 $$ 等都是不确定的，他们可能是在一定范围内属于某个集合，也可能是一个随机变量，这个时候就引入了鲁棒优化的概念。

对于线性规划问题来说，比如 $$ 一种是考虑确定性模型，也即 $$ 如果 $$ 是一个椭球，则该问题可以转化为一个 SOCP 问题 $$ 另一种是随机性模型，即 $$ 假如 $$ 服从高斯分布，则该问题同样可以转化为一个 SOCP 问题 $$

4.7 几何规划(GP)

首先定义单项式函数(monomial function) $$，其中 $$ 为任意实数；

正项式函数(posynomial function) $$

然后就可以定义几何规划(geometric program)了 $$ 其中 $$ 为正项式，$$ 为单项式。

首先说明，这个优化问题并不一定是凸的，因为 $$ 可以取任意实数，比如 $$ 就不是凸的。那么我们这里为什么要介绍这个问题呢？别急，一会稍微做一个变换我们就可以解决这个问题了。那还有一个问题，这种形式的函数有什么意义呢？为什么专门引入这样一种非凸优化问题呢？我们看这个单项式函数 $$，像不像体积或者面积的表达式？这也是他被称为“几何规划”的原因吧。

好，现在我们怎么把这个非凸的问题转化为凸优化问题呢？加个 $$ 就行啦！对单项式来说 $$ 对多项式来说 $$ 这么一来，取完对数后的问题就是凸的了，而且我们也知道 $$ 是一个单射函数，原始优化问题就变成了 $$

4.8 半正定规划(SDP)

前面所讲到的都是标量函数，约束条件也都是函数值与 0 比大小，而前面的章节中我们也提到了广义不等式，对于正常锥则可以定义不等号。所以我们可以定义一种凸优化问题，这种凸优化问题的约束条件不再是普通不等式，而是广义不等式 $$ 其中 $$ 为凸函数，$$ 为关于正常锥 $$ 的凸函数。

注意这种带有广义不等式约束的凸优化问题与普通凸优化问题有着相同的性质，比如可行集为凸的，局部最优解就是全局最优解等。

一种简单形式的凸优化问题就是向量形式的，也就是说目标函数与约束都是仿射函数 $$ 这种向量形式的广义不等式实际上就是对每个元素进行比较，因此实际上可以按照每一行拆分成多个不等式，如果取 $$ 就与普通的线性规划(LP)没什么区别了。

接下来要介绍的就是重头戏半正定规划(Semidefinite program)了，我们取 $$ $$ 其中 $$。

这里的不等式约束就是大名鼎鼎的线性矩阵不等式(linear matrix inequality, LMI)。

如果说我们现在有两个不等式约束怎么办呢？ $$ 合成一个更大的矩阵就可以了，实际上这种操作在后面也会经常见到 $$ 这是因为分块对角矩阵为正定矩阵等价于每一个子块都为正定矩阵。

例子 1：半正定规划之所以重要，是因为他的形式更广泛，前面说 SOCP 包含了 LP、QP、QCQP，而半正定规划则包含了 SOCP！比如下面的 SOCP 问题就可以转化为 SDP $$ 例子 2：最小化矩阵的最大特征值 $$，也可以通过半正定规划来描述 $$ 其中优化变量为 $$。这种等价转化是因为 $$。

例子 3：最小化矩阵范数 $$，也可以等价为SDP $$

4.9 向量优化

前面介绍的所有优化问题的目标函数都是标量（尽管约束可能会出现广义不等式），如果目标函数为向量怎么办呢？前面的章节中我们介绍了广义的凸函数，同样也是基于锥定义的（实际上高维空间中“比大小”我们一般都需要通过锥来定义）。

一般的向量优化问题可以表示为 $$ 凸的向量优化问题只需要将上面的等式约束换为仿射函数 $$，同时要求 $$ 为 $$convex 的，$$ 为凸的。

向量约束优化问题的最优解相当于在下面的集合中寻找最优解 $$ 前面在将广义不等式和凸集的时候，我们讲过最小元和极小元的概念，这两个概念是不是已经忘得差不多啦！反正我基本全忘了......让我们来复习一下。

复习：最小元与极小元

下面两幅图分别表示最小元和极小元

minimum and minimal

利用对偶锥，我们可以获得最小元的等价定义，即

$$ 是集合 $$ 关于 $$ 的最小元 $$ 对任意的 $$，$$ 为 $$ 在集合 $$ 上的唯一最小解

什么意思呢？也就是说任意的 $$，实际上都代表了一个法向量，也就是一个支撑超平面。如果 $$ 是最小元，则意味着对任意一个 ($$所定义的) 支撑超平面来说，$$ 都是支撑点，就像下面这条幅图一样

minimal

而极小元的定义是什么呢？

• 充分条件：若对于某些 $$，$$ minimizes $$ over $$，$$ $$ 为极小元
• 必要条件：$$ 为凸集 $$ 的极小元，$$ 存在非 0 的 $$ 使得 $$ minimizes $$ over $$

我们来看充分条件，只需要存在某一个 $$，使得 $$ 为对应支撑超平面的支撑点就可以了。比如下面这幅图，蓝色的点，我们可以找到这样一个蓝色的支撑超平面，使其为支撑点，所以它就是一个极小元；而对于红色的点来说，无论如何不可能找到一个支撑超平面，使其为支撑点，因此他就有可能不是极小元，因为这只是充分条件（对这个例子来说他就不是极小元）。

minimum

简单总结一下：

• 最小元：无论沿着锥 $$ 里边哪一个方向走，$$ 都是最小值点，那么他就是最小元；
• 极小元：如果沿着其中某一个方向走，$$ 是最小值点，那么他就是极小元。

复习完了最小元和极小元，不要忘了正事。我们要考虑向量约束优化问题中的最优解 $$ 这是一个集合，如果 $$ 是关于锥 $$ 的最小元，那么对应的 $$ 就被称为最优解(optimal)；如果 $$ 是关于锥 $$ 的极小元，那么对应的 $$ 则被称为 Pareto optimal。

optimal vs Pareto optimal

例子：假如我们取 $$，其中 $$ 相当于有 $$ 个不同的目标 $$，最好的情况当然是希望 $$ 都是最小的。

若 $$ 为最小元（存在）就说明任意其他可行解 $$ 都有 $$，正是我们希望的；

而如果只能得到极小元 $$，就有对任意可行解 $$，$$。这是什么意思呢？

1. 首先不可能存在另一个 $$ 使得每一个元素都有 $$，要不然 $$ 出现在这里的意义是什么？我们直接选择 $$ 作为极小元不就好了吗？如果存在那也顶多是 $$，这种情况下 $$ 跟 $$ 其实没什么区别了。
2. 第二点，有可能存在某些 $$，满足对一些 $$ 有 $$，而对另一些 $$ 则有 $$，这意味着 $$ 在某些方面表现得比 $$ 差，但在另一些方面则表现得更好，这实际上体现了我们在不同因素之间的一种权衡。