凸优化（1）——引入，优化实例分析，凸集举例与相关性质

学弱猹

发布于 2021-08-09 17:01:37

1.3K0

发布于 2021-08-09 17:01:37

大家好！

这是一个全新的系列，我们会给大家介绍凸优化（Convex Optimization）相关的内容。

凸优化在机器学习，深度学习等人工智能与大数据相关的方向都有举足轻重的作用。虽然现在很多实际的深度学习项目和课题中，多半不会直接利用上凸优化的知识，但学习凸优化有助于从一个更高的角度来思考相关的问题（当然了，这也是数学学科的一大优势了）。而且事实上，在当今的算法工程师面试中，很多企业都会加入对面试者凸优化知识的考查。相信很多相关专业的本科生和研究生，也修过学校的《凸优化》这一门课。

对于凸优化，我们最容易产生的疑惑就是它与最优化（数值优化）有什么区别？虽然它们俩本质上都是优化，但是凸优化的研究范围更窄，可以看出对“凸”的要求更高。所以在这个领域下，就会涌现出很多有趣而独特的理论与算法。因此如果要保留凸优化的本真，其实更多像是一门分析的课程（很多老师会把这门课起名叫“凸分析”），但我们这个系列不会这么做，而是尽量与数值优化相同，虽不可避免的要介绍一些理论，但还是努力以算法为导向，理论为辅助。

因为厦大没有开设《凸优化》的课程，因此这一门课的参考资料会从两个地方选取。一是卡内基梅隆大学（CMU）Ryan Tibshirani 的Convex Optimization（10-725 / 36-725），二是中科大（USTC）凌青教授的《最优化理论》，它们俩共同的参考书则是Stephen Boyd的Convex Optimization。虽然我在写作之前还没有看完这两个系列，但也算能看出一点二者对课程设计的差别。简单来说，中科大的课程更加理论，而CMU的课程则更偏向于当前优化界，与机器学习和统计相关的算法（插一个小知识：CMU的课程的开头10表示这个是它们Machine Learning Department的课，36则表示是Statistics Department，725的7开头，表示是PhD level）。所以这一个系列还是会主要以CMU的课程为主，用中科大的课程来辅助一些理论的知识。

因为凸优化与数值优化的交集甚多，故很多凸优化所需要的知识，其实我们在数值优化中很有可能已经介绍过。因此在这个系列中，会有大量对《数值优化》这个系列的引用。也正是因为这个原因，很有可能出现一节的内容量很大的情况（毕竟有很多东西引用了，就不怎么占地方了，就会不由自主的为了凑字数多写一点2333……）。当然了，如果你事先没有看过《数值优化》，那么这个系列我也自然会推荐你去点开看一下

数值优化（C）——二次规划（下）：内点法；现代优化：罚项法，ALM，ADMM；习题课

但如果没有看，跟上《凸优化》也没有问题，因为需要引用的时候，我会把引用范围说的比较清楚。

好的，废话说的够多了，我们开始吧。

Source

CMU 10-725: Convex Optimization
USTC: 最优化原理
Boyd, Vandenberghe, Convex Optimization
Fan (1949), On a theorem of Weyl conerning eigenvalues of linear transformations

引入：优化的历史

什么是优化，在数值优化（1）——引入，线搜索：步长选取条件的开头引入中已经说的很清楚。这里只强调一下，我们比较关心的是如何求解

\min_{x \in D} f(x)

在《数值优化》中，我们根据问题是否有约束条件，会把问题拆分成无约束优化问题和带约束优化问题。同时在数值优化中，我们的重点放在了数值上，我们介绍了很多实际的算法，然后需要通过编程来实际解决问题。但是其实优化本身的思想，和它发展的源头，事实上远比我们想象的要早，尽管主要的潮流认为，优化学科在二战得以兴起。我们也算是发了一笔战争财吧。

事实上优化是从17世纪开始就有发展，一开始是Newton和Rapson在求解非线性方程的时候，将问题做了如下的修改

f(x) = 0 \Rightarrow \min f^2(x)

然后通过优化方法来找

。类似的方法也被Gauss-Seidel和Jacobi所利用（对，就是数值分析里面的那两种求解线性方程组的迭代法），它们是为了求解这样的一个问题。

\begin{cases}f_1(x) = 0 \\ \vdots \\ f_n(x) = 0\end{cases} \Rightarrow \min \sum_{i = 1}^n f_i^2(x)

所以一个重要的思想就是：求解方程的根和优化函数的极小值，二者很多时候可以等价。这个思想在《数值优化》中也被多次提及过。

随着时间的发展，到了二战的前后，其实出现了很多有趣的发展。很多发现其实体现在与优化紧密联系的运筹学中。比方说1940年，Bellman发展了动态规划算法 (Dynamic Programming，DP)。这个算法的关键在于，状态转移不再是从前往后，而是从后往前。这样的话可以避免很多重复计算。当然了这个算法就我自己看来算是很困难的，也是算法工程师面试必考的代码算法之一。

说到凸优化，我们一般还会提一下单纯形法（Simplex Method），这个方法是1947年由Dantzig完善。说到数值优化，都会提一下内点法（Interior Point Method）。内点法是1984年由Karmarkar完善。而之后的很多优化的发展，都关注在了内点法的很多细节上。

好的，关于优化的历史，我们就说这么多。大家就当看小说就好了。

引入：优化实例

关于优化的实例我们之前说的不算多，这里给大家补几个例子来丰富这一节的内容。这里的每一个例子都有一些高阶的设计思想在，有些理解的话需要对高等代数有比较深刻的认识。不过即使没有理解也没有关系，用来看看优化可以做什么的，也足够了。

Example 1: Linear Quadratic Regulator (Source: USTC) 考虑一个控制器

x_k = A x_{k - 1} + B u_k

，那么线性二次调节器要解决的优化问题为

\min_{\{u_k\}} \sum_{k = 1}^n (x_k^T Q x_k + u_k^T R u_k)

。

这是一个自动化的问题。抽象来说

\{x_k\}

就是状态集合，而

u_k

就是我们在每一步的状态输入，且状态一步一步都会有转移，用转移矩阵

表示。这个目标函数可以拆分为两个部分理解。

x_K^T Qx_k

可以理解为状态的方差，

u_k^T R u_k

可以理解为输入的方差，或者说是物理上的能量的概念。所以我们的目标就是控制每一步的输入能量尽可能的小。虽然不是学这个方向的，但是我相信这句话如果翻译成“节能减排”，那么大家就都能够理解这个优化问题有什么实际的作用了。

Example 2: Shortest-Path Problem (Source: USTC) 考虑最短路问题，严格来说可以把它写成一个优化问题，即

\min \sum_{i, j \in E}w_{ij}x_{ij}

s.t. x_{ij} = \{0, 1\}, \sum_{j}x_{ij} - \sum_{j}x_{ij} = \begin{cases}1 & i \in S \\ -1 & i \in D &\\ 0 & others\end{cases}

这里

表示是起点（Source），

表示是终点（Destination）。这个优化问题直接来看是很抽象的，我们画张图解释一下。

这里的

x_{ij}

就表示是否选取从

到

的路径。所以对于一条路径而言，如果是起始点，那么因为它的出度比入度要大1，如果是终点，它的入度比出度一定大1（也就是出度一定比入度大-1），中间的经过的点则出度与入度相同，这个即使不懂图论，看蓝色的一条路径也很容易看出这一点。

当然了这个优化问题并不是一个非常容易的问题。因为它的约束是离散的点，离散的点当然不可能是凸的。因此很多时候，会考虑使用凸松弛的技巧。也即

x_{ij} = {0, 1} \Rightarrow x_{ij} \ge 0

当然了凸松弛之后，与原始问题是否等价就是一个大的问题

接下来给出几个统计机器学习的例子。

Example 3: 2d-fused LASSO (Source: CMU) 考虑问题

\min_\theta \frac 12 \sum_{i = 1}^n (y_i - \theta_i)^2 + \lambda \sum_{i = 1}^{n -1}|\theta_i - \theta_{i + 1}|

，其中

y_i

是数据点。

如果去掉后面的罚项部分，那么就是一个最小二乘回归问题。而这个罚项可以看出，它是针对相邻点的差距来进行惩罚的。换句话说，如果你的值变化的频繁，变化的幅度大，对应的罚项就大，这样的话就一定程度上使得曲线变成了分段的直线。因此事实上

\lambda

越大，曲线就越来越不可能有值的变化，这也就是下面的图所展现的趋势。

接下来这个例子是一个比较一般的优化形式。

Example 4: Eliminating Equality Constraints (Source: CMU) 考虑问题

\min_x f(x)

s.t. g_i(x) \le 0, i = 1, \ldots, m

Ax = b

，问是否可以消去等式约束？

这一部分其实就是想解决这个问题。消除等式约束的做法比较像线性方程组求解中，先找到一个特解，然后就可以得到无数多个通解的情况。简单来说，就是设

x = My + x_0

，其中

Ax_0 = b, \operatorname{col}(M) = \operatorname{null}(A)

（这是为了保证

AM y = 0

，

\operatorname{col}(A)

表示

的列空间）。那么这个时候，问题就会变为

\min_y f(My + x_0)

s.t. \quad g_i(My + x_0) \le 0, i = 1, \ldots, m

这是因为对于

来说并没有任何其它的限制了。

但这里要注意的是这样的做法在有些时候是不推荐的。如果说

是一个稀疏矩阵，那么一般来说

就会是一个稠密矩阵，因为

低秩的可能性比较大，所以

的零空间的秩就不会小。这样的话原始矩阵

的性质就被破坏了，因此在数值上就不一定是一个值得提倡的方法了。

Example 5: Principal Components Analysis (Source: CMU) 考虑下面这个优化问题

\min_{R} \|X - R\|_F^2 \quad s.t. \quad r(R) = k

。其中

X \in \mathbb{R}^{n \times p}

。

这个问题就是机器学习中的主成分分析，形式上可能不同地方写的不一样，这里给大家放一个我录的视频作为辅助理解。

https://www.bilibili.com/video/BV1ZK4y1b7Xt/

学过这个的人会知道它是有一个基于奇异值分解的闭合解的。也即

R = U_k D_k V_k^T

，这里的

U_k, D_k ,V_k^T

就是对应的矩阵的前

列，行或前

个对角元素等（因为这个不是重点，我们不说太多）。但是我们要说明的是，它的约束

r(R) = k

是一个非凸集，因此这本质上是一个非凸优化问题。

为什么秩的限制集合是非凸的问题呢，事实上举一个例子就好了。

\frac 12 \begin{bmatrix}1 &0 \\ 0 & 0\end{bmatrix} + \frac 12 \begin{bmatrix}0 &0 \\ 0 & 1\end{bmatrix} = \frac 12 \begin{bmatrix}1 &0 \\ 0 & 1\end{bmatrix}

可以看出两个秩1矩阵加在一起不一定是秩1矩阵。

当然了，科学家有办法解决这个问题，把它转变成了一个凸优化的问题，而且可以获得一致的最优解。具体的可以看Source中的Fan (1949)。

引入：凸优化的问题形式与基本性质

对于凸优化，我们的问题形式如下

\min_{x \in D} f(x)

s.t. \quad g_i(x) \le 0, i = 1, \ldots, m \\ h_j(x) = 0, j = 1 ,\ldots, r

这里的话

就是目标和约束函数所有的限制的交集。也就是《数值优化》中已经提到的可行域的概念。如果要问题是一个凸优化问题，那么要求

f, g_i, i = 1, \ldots, m

是凸的，并且要求

h_j, j = 1, \ldots, p

具有仿射性。也就是说我们要求

h_j(x) = a_j^T x + b_j, j = 1, \ldots, p

。

将问题归结为这个形式，一个最重要的原因就是下面这个性质。

Proposition 1: 凸优化问题局部最优解即为全局最优解

我们证明一下这个结论。考虑反证法，假如说

点处是局部极小值，但存在一个

z \in D

，使得

f(z) < f(x)

，那么设

y = tx + (1 - t)z

，那么这个时候，因为

g_i(y) \le 0

仍然成立（这是因为函数的凸性），

h_i(y) = 0

仍然成立（这是因为线性性），所以

依然是一个可行解。但是这个时候，注意到目标函数也是凸的，所以

f(y) \le t f(x) + (1 -t )f(z) < f(x)

这里的关键是在于说明，如果局部极小值不是全局极小值，那么我们可以通过修改

，使得

靠近

，成为与

竞争“局部极小值”的一份子，进而得出矛盾。这个条件是好满足的，因为我们会发现，由于

\|y - x \|_2 = (1 - t) \|z - x\|_2

这就说明了我们可以选择合适的

，使得

\|y - x \|_2 \to 0

，换句话说，即使

在

的邻域内，都有

f(y) < f(x)

，这就违背局部极小值的定义了。

所以到此为止，我们也算是介绍完了凸优化的一些基本场景和设定。和最优化不同的是，我们不会立刻长驱直入进入到介绍算法的环节，而是会先用大量的理论和展示来介绍与凸性有关的一些内容。

那么先进一段广告吧。

广告结束，我们继续

凸集举例与相关结论

凸集的定义我们在数值优化（1）——引入，线搜索：步长选取条件中已经给出，简单来说，就是

x, y \in C \Rightarrow tx + (1- t)y \in C, \forall t \in [0, 1]

比方说直线肯定是凸集。但是一个关键的地方在于空集，单点集也是凸集。这有点反直觉，但是走定义的话不难说明。比方说对于空集，因为

\emptyset

是集合的元素，而空集的线性组合自然也是空集，所以这是符合凸集的定义的。所以看似你在讨论一个“不存在”的概念，但这个“不存在”其实是“存在”于任何一个集合中的。很有哲学的意味了。

说到凸集必然要提到凸组合和凸包的概念。

Definition 1: Convex Combination, Convex Hull 定义

x_1, \ldots, x_k \in \mathbb{R}^n

的凸组合为

\sum_{i = 1}^k \theta_i x_i

，其中

\theta_i \ge 0, \sum_{i = 1}^k \theta_i = 1

。定义凸包为集合

的凸组合的所有可能，记为

\operatorname{conv}(C)

。

接下来我们给出一些其它的定义

Definition 2: Norm ball, Hyperplane, Halfspace, Affine Space 定义球（虽然严格来说叫范数球，但我真的不喜欢这个名字……）为

\{x: \|x \| \le r\}

，其中

\|\cdot \|, r

给定。定义半平面为

\{x: a^T x = b\}

，其中

a, b

给定。定义半空间为

\{x: a^T x \le b\}

，定义仿射空间为

\{x: Ax = b\}

，其中

A, b

给定。

这些都比较好理解，部分的图可以在数值优化（A）——线性规划中的单纯形法与内点法中找到，在线性规划中这些都是必备的几何具象。

相对来说比较陌生的是下面的这几个

Definition 3: Polyhedron, Simplex 定义多面体为

\{x: Ax \le b\}

，定义单纯形为

\operatorname{conv}\{x_0, \ldots, x_k\}

。其中这些点是仿射独立的（简单来说，三个点不在一条直线上）。

这一张图解释了什么是多面体。

而对于单纯形而言，可以认为是这个五边形的五个顶点的凸包。可能有的人会问为什么我只画了一张图，就能解释这两个概念。这个原因我们在之后会说。

这里有一个细节，就是

\{x: Ax \le b, Cx = d\}

在很多地方也是多面体的定义。这个的原因在于，我们可以把它写成

\{x: Ax \le b, Cx \le d, -Cx \le -d\}

然后把约束拼起来，写成

\begin{bmatrix}A \\ C \\ -C\end{bmatrix} x \le \begin{bmatrix}b \\ d\\ -d\end{bmatrix}

就可以了。所以严格来说，多面体内可以有不等式约束，也可以有等式约束。

接下来我们给出锥和凸锥的概念。

Definition 4: Cone, Convex Cone, Conic Combination, Conic Hull 设

C \in \mathbb {R}^n

，那么锥满足

x \in C \Rightarrow tx \in C, \forall t \ge 0

。凸锥满足

x_1, x_2 \in C \Rightarrow t_1 x_1 + t_2 x_2 \in C, \forall t_1, t_2 \ge 0

。定义

x_1, \cdots, x_k

的凸锥组合为

\sum_{i= 1}^k \theta_i x_i, \theta_i \ge 0, i = 1, \ldots, k

。定义凸锥包为凸锥组合的所有可能的集合。

虽然锥我们在《数值优化》里给出了定义，但是对于锥究竟是什么，我们这里还是需要多画一些图来做一些解释。

可以看出，左边的是一条过原点的直线，可以证明它其实也是一个锥。而对于右边，我们如果构造所有红点对应的凸锥包，那么蓝色的两条线对应的内部的区域就是结果，大家可以自己想一想为什么是这样。

好的，我们来给几个例题，温习一下这些概念。注意，我们不会直接堆砌所有的凸优化的性质啊定理啊来丰富我们的文章，而是希望通过几个小例题，介绍一些证明的思想工具，做到“四两拨千斤”的效果。

Problem 1: 证明

\mathbb{S}_+^n = \{X \in \mathbb{S}^n: X \succeq 0\}

是一个锥。

其中

X \succeq 0

表示它的所有的特征值都非负，也就是半正定的含义。

要证明这个非常简单，现在假如说

是某一个

\mathbb{S}_+^n

的元素，那么只要说明，对任意的

t \ge 0

，都有

tX \in \mathbb S_+^n

就可以了。但是这个是很显然的，一方面可以通过特征值都乘了一个

倍，所以依然都非负来解释。另一方面也可以通过半正定的定义

\forall y \in \mathbb R^n, y^T X y \ge 0

来得到。而注意到

y^T tX y = t (y^T X y) \ge 0, \forall t \ge 0

，所以结论成立。

Problem 2: 设

A \in \mathbb{R}^{m \times n}

，证明如果

S \subset R^m

是一个凸集，那么

A^{-1}(S) = \{x \in \mathbb{R}^n : Ax \in S\}

也是一个凸集。

这个题也不是很困难。我们取

x, y \in S

，那么会有

Ax \in S, Ay \in S

。取

t \in [0, 1]

，那么会有

A[tx + (1-t)y] = tAx + (1 - t)Ay \in S

（因为

是凸的）。这就可以推出

tx +(1- t)y \in A^{-1}(S)

，也就证明完毕了。

这里补充一个知识：

A^{-1}(S)

一般称为原象集 (pre-image) 或核 (kernel)。这一个性质也说明了在线性映射下，凸集的性质可以被保留下来。因为相对称的，如果说

是一个凸集，那么

AS = \{Ax | x \in S\}

也是一个凸集，不过这里就不给大家写证明了，大家可以之后去思考这个事情。

事实上引出Problem 2也是出于特有的目的，也即下面这个例子。

Problem 3: Linear Matrix Inequality Solution Set (Source: USTC, CMU) 给定

A_1, \cdots, A_k, B \in \mathbb S_+^n

，那么所有满足不等式

\sum_{i = 1}^k x_i A_i \preceq B

的点构成的集合为凸集。

这个问题要想解释清楚，使用常规的凸集证明方式即可。但是有一种更加有趣的证明方法。设

f: \mathbb R^k \to \mathbb S_+^n, f(x) = B - \sum_{i = 1}^k x_i A_i

，那么这个时候我们会发现

f^{-1}(\mathbb S^n) = \{x: f(x) \in \mathbb S^n\} = \{x: B - \sum_{i = 1}^k x_i A_i \succeq 0 \}

而这个就是我们关注的那个集合。这个集合当然是凸集，因为它是一个凸集在线性映射下的原象集，也就是利用上了Problem 2的结论。

接下来我们给出一个凸集的加和性质，它的证明方法也是很巧妙的。

Problem 4: (Source: USTC) 如果集合

X_1, X_2

是凸集，那么

X_1 + X_2 = \{x + y \mid x \in X_1, y \in X_2\}

也是凸集。

我们证明一下这个结论。注意到

X_1 \times X_2 = \{(x,y) \mid x \in X_1, y \in X_2\}

是一个凸集（想想为什么？），所以我们设

f(x,y) = x + y

。那么这个时候，可以得到

f(X_1 \times X_2) = X_1 + X_2

但是

f(x, y)

显然是一个线性映射，所以保凸性，因此这就完成了证明。不得不说这个证明很巧妙，因为集合的“和”本身就是一个很难具象的东西，因此缺失几何图像，就会使得联想的证明产生难度。

接下来我们给出一个解析几何的例子

Problem 5: Ellipsoid (Source: USTC) 证明椭球是一个凸集。

可能大家不知道怎么描述椭球，这里补充几句。如果化归到二维平面上，就是

\frac {x^2} {a^2} + \frac {y^2}{b^2} = 1

这样的一个形式，也就是高中数学里学过的椭圆。但是事实上它有一个更加通用的写法。

\epsilon(x_c, P) = \{x \mid (x -x_c)^T P^{-1} (x - x_c) = 1\}, x_c \in \mathbb R^n, P \in \mathbb S_{++}^n

落实到我们这一个问题中，就是设

P = \begin{bmatrix}a^2 & 0 \\ 0 & b^2\end{bmatrix}

，

x_c = 0

，并且设

(x, y)

是点的坐标，那么就是

x^T P^{-1}x = \begin{bmatrix}x & y\end{bmatrix} \begin{bmatrix}\frac 1 {a^2} & 0 \\ 0 & \frac 1{b^2}\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} = \frac {x^2}{a^2} + \frac{y^2}{b^2} = 1

因此二者是一致的。

那么注意到球体本身是一个凸集，而我们只要考虑设新变量

u= P^{-\frac 12} (x - x_c)

，就可以把集合内部的表达式化为

u^T u = 1

的形式，也就是一个球。又因为这个变换是一个仿射变换，所以保持了凸性（很容易证明球是一个凸集），因此我们就算证明完了这个结论。

下面就是一个球变成椭球的形象表示（在

\Sigma

的那个部分）。这里用了奇异值分解的图，是因为对于

P^{\frac 12}

来说，它的两个特征值就对应椭圆的长轴和短轴。

好的，关于凸集的例子，我们就说这么多。

再放个广告！

广告结束！如果太多了，可以发我消息，我下次少放点！

延伸：单纯形法的思路来源

最后，我们给出两个结论来说明单纯形法设计的思路。

Proposition 2: (Source: USTC) 证明单纯形是多面体

证明这个的目的是要利用到一个多面体的性质，而这个性质会与我们之后的单纯形法有密切的关联。

这个证明不是特别简单，我们一步步来看，假如说

x \in C \subset \mathbb R^n

且

是一个单纯形，那么就会有

x = \sum_{i = 0}^k \theta_i v_i

，并且有

\mathbf 1^T \theta = 1, \theta \ge 0

（注意这里的

\theta

是一个向量，表示

(\theta_0, \cdots, \theta_k)^T

。并且

v_1 - v_0, \cdots, v_k - v_0

线性无关（这就是它们仿射独立的含义）。

我们定义

[v_1 - v_0, \cdots, v_k - v_0] = B \in \mathbb{R}^{n \times k}

，那么这个时候，可以得到

x = \sum_{i = 0}^k \theta_i v_i = v_0 + \sum_{i = 1}^k \theta_i(v_i - v_0) = v_0 + B \theta

注意到根据条件，

是列满秩的，所以我们可以找到一个变换矩阵

A = \begin{bmatrix}A_1 \\ A_2\end{bmatrix} \in \mathbb{R}^{n \times n}

，使得

AB = \begin{bmatrix}I_k \\ 0\end{bmatrix}

。那么这个时候，会有

\begin{cases}A_1 x = A_1 v_0 + \theta \\ A_2 x = A_2 v_0\end{cases}

那么因为

是有一个范围的限制的。所以我们会有

\begin{cases} A_1 x \ge A_1 y_0 \\ \mathbf 1^T A_1 x \le \mathbf 1 + \mathbf 1^T A_1 v_0 \\ A_2 x = A_2 v_0\end{cases}

这个事实上就完成了证明，因为只需要把第一个不等式反号一下就可以了。

我们要证明这个，是为了用到下面这个凸多面体的性质。

Proposition 3: 证明在一个有界多面体作为可行域的情况下，凸函数的最大值在这个多面体的顶点上取到。

如果我们把这个有界多面体限制在

\mathbb R^1

上，那么就是一条线段。我们画一个图就能理解这个性质究竟是什么意思了。

你会发现，最大值要不就在

x_1

处取到，要不就在

x_2

处取到，它们俩都是边界上的点。

好的，我们证明一下这个结论。

注意到它是一个凸多面体，凸多面体是单纯形，所以可以写成它顶点的凸包。所以我们设

\{x_1, \cdots, x_n\}

是顶点的集合，那么这个时候所有的凸多面体的点就可以写成

y = \sum_{i = 1}^n \alpha_i x_i

，且

\sum_{i=1}^n \alpha_i = 1

。那么这个时候，根据凸性就可以得到

f(\sum_{i = 1}^n \alpha_i x_i) \le \sum_{i = 1}^n \alpha_i f(x_i) \le \max\{f(x_1), \cdots, f(x_n)\}

这就证明了结论。

如果你看了数值优化（A）——线性规划中的单纯形法与内点法中的单纯形法的话，你就会明白为什么线性规划中的单纯形法，是通过找集合的extreme point来寻找极值的了。当然了如果深究细节还是有些不同，但是通过凸优化的这个性质，可以初见端倪。

小结

这一节我们给了一些优化的实例，并从相对high-level的层次上对优化目标的设计思路做了简单的分析。当然了除此之外，我们还给出了很多凸优化的与”凸“有关的分析性质，因此风格和《数值优化》有些不同。了解这些证明多半是为了让喜欢这一方面的朋友们能够看得舒服，看得过瘾。当然如果对这一块不感兴趣，或者更加关注凸优化中与算法相结合的部分，那么理论的部分跳过就好～

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-08-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度