前言

最近在学习数据挖掘相关过程，之前已经学习了朴素贝叶斯和SVM，但没有及时记录下来，之后可能会补发相关的学习笔记，目前的学习系列是凸优化的学习内容，内容会比较详细，可能涉及公式推导之类的基础问题。

凸优化基础知识体系

在正式讲述什么是凸优化之前，我们需要大致了解一些凸优化的相关概念，进而引入凸优化，以下是几个重要相关概念的笔记：

一个简单的定理证明

定理证明

在介绍凸优化相关概念之前，首先介绍一个简单的定理，这个定理的内容是：
For any x₁，x₂$\in\mathbb R$∈R, 且 x₁<x₂, 若x₀$\in\mathbb [x_1,x_2]$∈[x1​,x2​]，则
$x_0= x_1\theta+x_2(1-\theta)$x0​=x1​θ+x2​(1−θ)
$(其中0\leq\theta\leq1)$(其中0≤θ≤1)
这个定理是很容易证明的，具体如下：

如图，该直线上有三个点：x₀，x₁和x₂，其中x₀位于x₁和x₂之间，引入一个参数 t:$t=\frac{x_0-x_1}{x_2-x_1}$t=x2​−x1​x0​−x1​​
t的范围即为[0，1]
$则x_0=(x_2-x_1)t+x_1$则x0​=(x2​−x1​)t+x1​
$整理可得 x_0=(1-t)x_1+tx_2$整理可得x0​=(1−t)x1​+tx2​
从而得证。

从一维推导至多维

上述结论可以由一维推广到多维，具体来说：
For any X，Y$\in\mathbb R^d$∈Rd, 其中 X = (x₁, x₂, …, x_d), Y = (y₁, y₂, …,y_d), 若任取一个Z 位于X, Y的连线上，则
$Z= X\theta+Y(1-\theta)$Z=Xθ+Y(1−θ)
$(其中0\leq\theta\leq1)$(其中0≤θ≤1)

凸集（convex sets）

凸集，定义目标函数和约束函数的定义域。
英文的准确表述为：
A set C is convex if the lines segment between any two points in C lines in C, i.e., if for any x₁, x₂$\in\mathbb C$∈C, and any $\theta$θ with 0<$\theta$θ<1, we have:
$\theta x_1+(1-\theta )x_2\in\mathbb C$θx1​+(1−θ)x2​∈C
举个例子来说：
(one convex, two nonconvex sets)

凸集（convex sets）与仿射集（Affine Set）区分

仿射集：如果通过集合 C 中任意两个不同点之间的直线仍在集合C中，那么称集合C是仿射的。

凸集：如果通过集合 C 中任意两个不同点之间的线段仍在集合C中，那么称集合C是凸的。

因为仿射集的条件比凸集的条件强，所以仿射集必然是凸集。

凸函数（convex function）

凸函数定义

函数f(x): Rⁿ$\rightarrow$→R 为凸函数，当且仅当满足如下条件：

1. x的定义域 D(f) 为凸；即for any x, y$\in$∈ D(f), $\theta x+(1- \theta )\in D(f)$θx+(1−θ)∈D(f) $( 0\leq\theta\leq1)$(0≤θ≤1)
2. 对上述x, y, $\theta$θ 满足 f($\theta$θx+(1-$\theta$θ)y)$\leq$≤ $\theta$θ f(x)+ (1-$\theta$θ) f(y)

凸函数举例

1. 一维上
   几何意义表示为函数任意两点连线上的值大于对应自变量处的函数值，示意图如下：
   
   由图可以看出，f(z) = f($\theta$θx+(1-$\theta$θ)y) < $\theta$θ f(x)+ (1-$\theta$θ) f(y)
   一维情况下，不严格的说，凸函数是弦在上的函数。

2. 二维上
   
   由图可以看出，f(x₀) = f($\theta$θx₁+(1-$\theta$θ)x₂) < $\theta$θ f(x₁)+ (1-$\theta$θ) f(x₂)

凸优化

凸优化是约束优化的特殊形式（即要求定义域和目标函数均为凸函数）
其具体定义为：
A convex optimization problem is one of the form
$minimize f_0(x)$minimizef0​(x)
$subject \ to \ f_i(x)\leq b_i, i = 1, \ldots, m$subject to fi​(x)≤bi​,i=1,…,m
where the function f₀, $\ldots$…,f_m: Rⁿ$\rightarrow$→R are convex, i.e., satisfy
$f_i(\alpha x+\beta y) \ \leq \alpha f_i(x)+\beta f_i(y)$fi​(αx+βy) ≤αfi​(x)+βfi​(y)
for all x, y $\in$∈ Rⁿ and all $\alpha$α, $\beta$β $\in$∈R with $\alpha + \beta$α+β = 1, $\alpha \geq 0$α≥0, $\beta \geq 0$β≥0.

参考资料

关于凸优化的一些简单概念
北京大学凸优化课程PPT