这个系列的最优化笔记以唐焕文老师的《实用最优化方法》为基础，主要分享我学习中认为重要的知识点，但不会全盘分享，我也没那个精力。

凸集与凸函数

1. 凸集

定义 ：设$\Omega$Ω$\subset$⊂$R^n$Rn,如果对于任意的点$x,y\in\Omega$x,y∈Ω,连接点$x,y$x,y的线段上的一切点都在$\Omega$Ω中，则称$\Omega$Ω是一个凸集。其具体数学判别式为：
对于 $\forall$∀$x,y\in\Omega$x,y∈Ω, $\forall$∀$\mu\in[0,1]$μ∈[0,1],恒有$\mu$μ$x+(1-\mu)y\in\Omega$x+(1−μ)y∈Ω,则$\Omega$Ω为一个凸集。
$e.g.$e.g. : 单点集，$R^n$Rn.

定理1(常考)：集合$\Omega$Ω$\subset$⊂$R^n$Rn为凸集的充要条件是：点$x^{(i)}\in\Omega(i=1,2,...,p)$x(i)∈Ω(i=1,2,...,p)的任意凸组合$^{[1]}$[1]仍包含在$\Omega$Ω中。
$[1]$[1]凸组合：设实数$a_i\geq0$ai​≥0 $(i=1,2,...,p),\sum_{i=1}^{p}a_i=1$(i=1,2,...,p),∑i=1p​ai​=1,$x^{(i)}\in R^n(i=1,2,...,p)$x(i)∈Rn(i=1,2,...,p),则称$x=\sum_{i=1}^{p}a_ix^{(i)}$x=∑i=1p​ai​x(i)为点$x^{(1)},x^{(2)},...,x^{(p)}$x(1),x(2),...,x(p)的一个凸组合。
充分性性显然。
必要性如下

定理2：任意一组凸集的交集仍为凸集。

2. 凸函数

定义：设$f(x)$f(x)是定义在非空凸集$\Omega$Ω$\subset$⊂$R^n$Rn上的函数，若对于$\forall$∀$x,y\in\Omega, \forall\lambda\in[0,1]$x,y∈Ω,∀λ∈[0,1]，不等式$f(\lambda x+(1-\lambda)y) \leq \lambda f(x)+(1-\lambda)f(y)$f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)恒成立，则称$f(x)$f(x)是$\Omega$Ω的凸函数。
从函数图像上看，则函数图象总是在切线(或切平面)的上方。
注：凸函数的非负线性组合仍未凸函数。(使用定义易证明)。

定理1(凸函数的充要条件1):定义在非空凸集$\Omega$Ω$\subset$⊂$R^n$Rn上的$f(x)$f(x)为凸函数的充要条件是：
对于$\forall$∀$x,y\in\Omega$x,y∈Ω，都有：$f(y)-f(x)\geq(\nabla f(x))^T(y-x)$f(y)−f(x)≥(∇f(x))T(y−x)

定理2(凸函数的充要条件2)：定义在非空凸集$\Omega$Ω$\subset$⊂$R^n$Rn上的$f(x)\in C^2$f(x)∈C2(即$f(x)$f(x)是二阶连续可微的)，$f(x)$f(x)为凸函数的充要条件是：
$f(x)$f(x)的海赛矩阵$F=\nabla^2f(x)$F=∇2f(x)在整个$\Omega$Ω上是半正定的。
(正定则为严格凸函数,逆定理一般不成立)。

3. 凸规划

定义：目标&约束函数在可行解R上为凸函数，则这样的优化问题称为凸规划问题(与线性规划问题没有关系)。

定理1：凸规划问题的可行集R为凸集。
定理2：对于凸规划问题，目标函数$f(x)$f(x)的任一局部极小点都是$f(x)$f(x)在非空可行集R上的全局极小点。
（证明常考，用反证法证明)。
（若凸规划的问题的目标函数$f(x)$f(x)在非空可行集R上是严格凸函数，则该优化问题的全局极小点是唯一的)。

第一节，完。