凸优化问题举例

线性规划（Linear Regression）

线性规划问题指的是目标函数为线性函数，约束条件也为线性函数的数学规划问题。而数学规划问题指的是在给定约束条件下，在某一意义下目标取得最优的问题称为数学规划问题。

给定线性规划问题形式如下：

根据“最优化理论基础：判定凸函数”一节的结论可知，约束条件中的半空间​\pmb{Ax} \leq \pmb{b}和​\pmb{x} \geq \pmb{0}均是凸集，而凸集之间的交集运算仍然为保凸运算，故可行域为凸集；此外，由于目标函数​\pmb{c}^{\top}\pmb{x}是可微函数，则根据凸函数的而阶判定条件可知：

故目标函数为凸函数。

鲁棒回归（Robust Regression）

鲁棒回归的目的在于克服离群点/异常点（outliers）所带来的影响，鲁棒回归的形式如下所示：

其中​y_{i} \in \mathbb{R}, \pmb{x}_{i} \in \mathbb{R}^{d}, \pmb{w} \in \mathbb{R}^{d}。

证明：绝对值函数​f(x) = |x|是凸函数

采用直接法进行证明。​\forall x_{1}, {x}_{2} \in \mathbb{R}, \forall t \in (0, 1)，有：

根据凸函数定义，命题得证。此外，根据“线性规划”一节中的证明可知，线性函数是凸函数。因此，根据“最优化理论基础：判定凸函数”一节中的保凸运算结论，仿射变换与凸函数的复合，其结果仍然为凸函数可知，上述鲁棒回归的目标函数为凸函数。

由于上述形式的鲁棒优化问题为无约束优化，其可行域为​\mathbb{R}^{d}是凸集，故该优化问题是凸优化问题。

最小二乘问题（Least Squares Problem）

最小二乘法问题的形式如下：

最小二乘法问题为无约束优化问题，其可行域为​\mathbb{R}^{d}，为凸集；现验证其该优化问题的目标函数是否为凸函数。证明该目标函数为凸函数的方法有很多，例如保凸运算来证明。本文采用凸函数的二阶条件来进行证明。

进而有：

进一步，有：

因此，问题的目标函数为凸函数，故该优化问题凸优化问题。对于这种目标函数含有二次项数学规划称为二次规划。

p范数损失（General Lp-Norm Loss）

对于目标函数为p-范数损失（p-norm loss），其问题形式如下：

下面不加证明的给出以下结论：

• 当​p = 1时，该问题为线性规划问题，为凸问题。
• 当​p = 2时，该问题为二次规划问题，为凸问题。
• 当​p > 2时，该问题为凸问题
• 当​p < 1时，不是范数，为NP-HARD问题。

线性SVM的目标函数（Objective of Linear SVM）

线性SVM（linear SVM）的目标函数形式如下：

其中​\lambda > 0。根据保凸运算性质易证该目标函数为凸函数。将该问题放在这里的原因是阐明如何去掉目标函数中的​\mathrm{max}运算且变化后的目标函数与原问题等价。

令​\gamma_{i} = \mathrm{max}\{0, 1- y_{i}\pmb{w}^{\top}\pmb{x}_{i}\}，则上式可以转换为：

为保证原式与变换后的问题等价，需引入约束条件：

其中​i = 1, 2, \cdots,n。转化后问题与原问题等价，该问题称为带有线性约束条件的二次规划（Quadratic Programming with Linear Constraints）。由于该问题的可行域为凸集，目标函数为凸函数。因此，该问题为凸二次规划问题（Convex QP）。

非凸优化问题举例

集合覆盖问题（Set Cover Problem）

给定全集​U（Universal Set），以及​m个子集合​S_{1}, {S}_{2}, \cdots, S_{m}且这​m个子集合的并集为全集​U。集合覆盖问题要找到最少个数的子集合，使得它们的并集等于全集​U。

例如​U = \{1, 2, 3, 4, 5\}, S = \{\{1, 2, 3\}, \{2, 3\}, \{3, 4\}, \{4, 5\}\}，最少的集合为​\{\{1, 2, 3\}, \{4, 5\}\}，个数为2。

设决策变量​x_{i} \in \{0, 1\}, i = 1, 2, \cdots, m，则集合覆盖问题的数学形式描述如下：

虽然目标函数是线性函数，为凸函数。但是它的可行域为离散的，是非凸集合，故该优化问题为非凸优化问题。进一步的，当决策变量都要求取值为整数时，这样的优化问题被称为整数规划。