最近总是忘记一些基础知识, 有些还能问问ChatGPT, 大部分情况还是需要自己找课堂笔记, 索性就整理出来好了. 如有错误, 欢迎大家指正.

Convex Set

定义 集合 是一个 convex set 如果对于任意 ，都有

如下图所示，左边的是convex set，而右边的则不是。

命题

• (a) 如果 和 是convex sets, 那么 也是convex set, 而 不是.
• (b) 令 为convex set 的点, . 那么 .证明   数学归纳法, 假设 的时候成立, 现在证 . 假设有 和 . 至少存在一个 , 设 . 令 . 令 , 由 的假设可知 . 现在令, 因为 , 所以 , 证毕.

定义 集合 的 convex hull 是 中所有包含 的convex sets的交集. 换句话说, 是 中最小的包含 的 convex set.

定义 点 属于 convex set , 令 , 如果对于任意 和 , 都有 , 那么称 为 的 extreme point. 换句话说, 不能表示成集合 中任何两个不同的点的组合.

定义 一个polytope是 中一个有限点集的convex hull.

定义 一个polyhedral set是 中一个有限族的closed halfspace的交集. 例如:

为了方便, 我们使用 表示 "if and only if", "当且仅当", .

命题 一个 中的集合是一个 polytope 它是一个有界的 polyhedral set.

定义 对于任意 和 , 映射 满足 , 那么称 为一个 affine transformation. 例如, .

命题 设 是一个 affine transformation, 是一个 convex set , 那么 是 中的一个 convex set.

证明   如果 , 那么 . 因为 是一个 convex set, 那么对于任意 都有 . 那么

所以 是 中的一个 convex set.

Convex Function

定义 如果函数 满足

那么称函数 是convex的.

定义 称 是 concave 的如果 是 convex 的.

例子:

• , convex
• , concave
• , convex 和 concave
• , 时 concave, 时 convex

命题 设 是一个 convex function, 以及 满足 . 那么

证明  

因为 是 convex 的, 有

类似的:

推论 设 是一个 convex function, . 那么 随 单调增.

证明   分情况讨论即可, 要证 , 考虑三种情况:

命题 函数 可微, 那么 是 convex 是单调增的.

证明   假如函数 是 convex 的, 令 , 我们需要证明 , 利用上面一个推论:

现在证另一个方向, 假设 是单调增的, 对于任意 , 有 . 由中值定理可得:

因为 , 那么:

因此, 是一个 convex function.

推论 如果 二次可微, 那么 是 convex . 例如:

定义 , 的 epigraph 定义为:

命题 令 . 是一个 convex set, 那么 是 convex 它的 epigraph 是 上的一个 convex set.

证明   假设 是一个convex function, 令 , 那么

由 的convex属性可知:

因此

现在证另一个方向, 假设 是 convex的, 那么

因此, 是一个 convex function.

命题 设 是一族定义在 上的 convex functions. 对于每一个 , 假设集合 是上有界的, 那么

是convex的.

证明  

因为 是一个 convex set, 所以 是 convex 的, 因此 是一个 convex function.

命题 (a) 设 为 convex functions, 那么对于任意 , 也是一个 convex function.

证明  

命题 (b) 设 为 上的一个 convex function, 在 上单调递增, 那么复合函数 也是一个 convex function.

证明  

其中, 第一个不等式是因为 是 convex 以及 是单调增的. 第二个不等式是因为 是 convex的.

命题 (c) (Jensen's 不等式) 设 为 上的一个 convex function, 对于任意

证明   利用数学归纳法证明, 对于 时, 显然成立. 假设对于 时成立, 我们想证明当 时也成立. 当 时, , 那么在 中至少存在一个严格小于1的, 假定为 . 定义 , 那么

如果令 , 那么就可以得到著名的Jensen's 不等式

命题 如果 是定义在 上的一个 convex function, 其中 为 上的一个 open convex set, 那么 在 上是连续的.

证明   设 , 为包含于 的一个 polytope, 为 的一个内点, 为 的顶点. 选取 且 , 其中 . 对于任意 , 存在 , 使得 . 那么根据 Jensen不等式

其中 . 定义

易证 是一个关于 的 convex function 并且 . (注: 通过定义新函数 , 把 的函数转化为 上的函数) 那么有

其中, , 那么可得

因此, 当 , , 是一个连续函数.

命题 令 , 假设 有连续的二阶偏导数, 它的 hessian matrix 为

那么 是 convex 的当且仅当 是 positive semi-definite, 即, .

证明   定义

那么 . 如果 是 convex, 易证 也是一个 convex function.

反过来, 假设 是一个 convex function, 我们想证明 也是一个 convex function. 令 ,

因此, 是 convex 当且仅当 是 convex. 那么

, 令 , 那么 .

命题 如果函数 是可微的, 令 , 那么 是 convex 当且仅当

证明   定义 , 那么 是 convex 当且仅当 是 convex.

先证方向 , 如果 关于 convex, 那么

第二个等式中, .

现在我们来证方向 , 如果条件 成立, 我们想证 是 convex, 对于任意 . 由条件 可得

将 , 可得

那么可得

其中 .

命题 如果 是 上的一个连续可微函数, 那么 是 convex 当且仅当 是单调的, 即

证明   令 . 如果 是 convex, 那么

反之, 对于任意 , 由条件 可得

可得, 关于 单调增, 所以 是 convex.

Optimization Problems

令 为 上的一个开区间, 是 的一个 local minimizer 当且仅当存在 , 使得

命题 令 为 上的一个开区间, 是一个二次可微的连续函数. 如果 是 的一个 local minimizer, 那么 .

证明   因为 是 local minimizer, 存在 使得 . 因此, 对于 ,

对于 ,

那么

可得 .

根据泰勒展开, 使得

令 , 我们有 , 即

命题 是一个二次可微的连续函数, 对于 , 如果 , 那么 是 的一个 local minimizer.

注意上面的条件 , 是严格大于0, 而不是大于等于0. 为什么呢? 举个例子, 例如 , 但是 并不是一个 local minimizer.

证明   因为 是连续的并且 , 使得 , 由泰勒展开

其中 , 可得 .

推论 如果 , 在一些包含 的区间上有 , 那么 是一个 local minimizer.

命题 设 是一个开集, 是一个 local minimizer, 那么

以及

是 positive semi-definite.

证明   因为 是一个开集, , 使得

其中 , 第 个元素为1. 定义 . 对于 , 是一个良定义（well defined）的函数, 并且在 时有一个 local minimizer

定义 . 通过链式法则, 有

因为 是 的一个 local minimizer, 0 是 的一个 local minimizer, 那么有

可得 是 positive semi-definite.

命题 设 为定义在凸集 上的 convex function:

(i) 如果 在 处取得 local minimizer, 那么 也在 处取得 global minimizer. (ii) 如果 满足

即 是严格 convex, 那么它的 global minimizer 是唯一的. (iii) 如果 不是常数函数, 并且它在集合 上的一些点 获得 maximizer, 那么 必为 的一个边界点.

证明   (i) 因为 在 处获得 local minimizer, 使得对于所有 . 那么 , 我们需要证明 . 注意到区间 , 因此 , 我们有

定义 , 那么

(ii) 如果存在 使得 , 那么

与 " 是 global minimizer" 矛盾.

(iii) 如果 不是一个边界点, 那么 一定是一个内点. 因为 不是一个常数, . 注意到 , 因为 是一个内点, 存在 使得 对于一些 , 那么

这就导致了矛盾, 因此, 必为一个边界点.

命题 设 为定义在开凸集 上的可微 convex function. 那么, 是 的一个 global minimizer 当且仅当 .

证明   如果 . 因为 是 convex, 有

反之, 如果 是 global minimizer, 它必然是一个 local minimizer, 那么

现在设 , 有如下的优化问题:

如果存在一个 , 使得 以及 , 那么可以称这个优化问题是 strongly consistent 或者称其满足 slater condition.

命题 设 和 为可微的 convex function, 令 , 是 affine的. 如果上述的优化问题是 strongly consistent, 那么一个可行点 是最优解当且仅当存在 且 使得

命题 (KKT Condition) 设 为上述优化问题的最优解, 那么必然存在一个实数 , 向量 使得

拉格朗日对偶性 令 , , 其中 称为 primal problem. 定义

令 . 定义

称为 dual problem.

定理 (对偶性)

(i) 如果 , 那么对于任意 , 都有 .

(ii) 令 , 如果 在 上无界, 那么 .

(iii) 令 , 如果 在 上无界, 那么 .

(iv) 如果存在 使得 , 那么 . 也就是说, 是 primal problem 的一个最优解, 是 dual problem 的一个最优解.