凸优化和非凸优化

凸优化和非凸优化

引用

CSDN

1.

https://blog.csdn.net/kebu12345678/article/details/54926287

凸优化和非凸优化是数学优化领域中的两个重要概念，它们在机器学习、数据科学和工程领域有着广泛的应用。本文将深入探讨凸优化和非凸优化的定义、重要性以及它们在实际中的应用。

凸优化和非凸优化

数学中最优化问题的一般表述是求取 (x)，使 (f(x)) 最小，其中 (x) 是 (n) 维向量，(f(x)) 是 (x) 的可行域，(f(x)) 是 (x) 上的实值函数。

凸优化问题是指 (f(x)) 是闭合的凸集且 (f(x)) 是 (x) 上的凸函数的最优化问题，这两个条件任一不满足则该问题即为非凸的最优化问题。

其中，凸集是指对集合中的任意两点 (x_1) 和 (x_2)，有 (ax_1 + (1-a)x_2) 也在集合内，即任意两点的连线段都在集合内，直观上就是集合不会像下图那样有“凹下去”的部分。至于闭合的凸集，则涉及到闭集的定义，而闭集的定义又基于开集，比较抽象，这里可以简单地认为闭合的凸集是指包含有所有边界点的凸集。

为什么要求是凸函数呢？因为如果是下图这样的函数，则无法获得全局最优解。

为什么要求是凸集呢？因为如果可行域不是凸集，也会导致局部最优。

实际建模中判断一个最优化问题是不是凸优化问题一般看以下几点：

• 目标函数 (f(x))：如果不是凸函数，则不是凸优化问题
• 决策变量 (x)：中包含离散变量（0-1变量或整数变量），则不是凸优化问题
• 约束条件写成 (g(x) \leq 0) 时，(g(x)) 如果不是凸函数，则不是凸优化问题

之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解，这个特性使凸优化问题在一定意义上更易于解决，而一般的非凸最优化问题相比之下更难解决。

非凸优化问题如何转化为凸优化问题的方法：

1. 修改目标函数，使之转化为凸函数
2. 抛弃一些约束条件，使新的可行域为凸集并且包含原可行域

关于凸优化的一些简单概念

凸集的定义

凸集的定义为：如果集合 (C) 中任意 2 个元素连线上的点也在集合 (C) 中，则 (C) 为凸集。其示意图如下所示：

常见的凸集有：

• (n) 维实数空间
• 一些范数约束形式的集合
• 仿射子空间
• 凸集的交集
• (n) 维半正定矩阵集
• 这些都可以通过凸集的定义去证明。

凸函数的定义

凸函数的定义为：函数任意两点连线上的值大于对应自变量处的函数值，示意图如下：

凸函数的一阶充要条件为：
[f(y) \geq f(x) + \nabla f(x)^T (y-x)]
其中要求 (f) 一阶可微。

二阶充要条件为：
[\nabla^2 f(x) \succeq 0]
其中要求 (f) 二阶可微，表示二阶导数需大于 0 才是凸函数。

按照上面的两个定义，如果 (f(x)=x^2) 肯定是凸函数，而 (g(x) = -x^2) 是非凸函数。也就是说开口向下的函数是非凸函数，但是对于这种情况可以通过添加负号变成凸函数，从而求解。

常见的凸函数有：

• 指数函数族
• 非负对数函数
• 仿射函数
• 二次函数
• 常见的范数函数
• 凸函数非负加权的和等
  这些可以采用上面 2 个充要条件或者定义去证明。

凸优化问题的定义

凸优化问题（OPT）的定义为：
要求目标函数是凸函数，变量所属集合是凸集合的优化问题。或者目标函数是凸函数，变量的约束函数是凸函数（不等式约束时），或者是仿射函数（等式约束时）。

对于凸优化问题来说，局部最优解就是全局最优解。

常见的凸优化问题包括：

• 线性规划（LP）：该问题是优化下面的式子：
• 二次规划（QP）：该问题是优化下面的式子：
• 二次约束的二次规划（QCQP）：该问题是优化下面的式子：
• 半正定规划（SDP）：该问题是优化下面的式子：

按照文章说 SDP 在机器学习领域应用很广，最近很流行，不过我好像没太接触到过。

为什么凸优化这么重要？

凸优化之所以重要，应当有下面几个原因：

1. 凸优化问题有很好的性质
   众所周知，凸问题的局部最优解就是全局最优解（许多答主已经提到了）。不过，凸优化理论中最重要的工具是 Lagrange 对偶，这个为凸优化算法的最优性与有效性提供了保证。近些年来关于凸问题的研究非常透彻，以至于只要把某一问题抽象为凸问题，就可以近似认为这个问题已经解决了。

2. 凸优化扩展性强
   前面提到，许多问题的关键是在于将问题抽象为凸问题。因此许多非凸问题通过一定的手段，要么等价地化归为凸问题，要么用凸问题去近似、逼近。典型的如几何规划、整数规划，它们本身是非凸的，但是可以借助凸优化手段去解，这就极大地扩张了凸优化的应用范围。

3. 凸优化的应用十分广泛
   现实生活中确实有大量的非凸问题，但是并不妨碍凸优化在许多问题上都可以大展身手。往细了说，比如线性回归、范数逼近、插值拟合、参数估计，以及许多的几何问题；往大了说，在通信、机器学习、统计、金融等涉及优化、决策的研究领域，凸优化都是非常有效的手段。

4. 针对其他非凸问题的研究还不充分
   凸优化的重要性，在工程领域应该说是无可撼动的了。

凸优化的重要性，在工程领域应该说是无可撼动的了。