这是一篇介绍数学优化中凸优化的概念以及对偶理论的文章。
0 引言
区分数学优化问题的关键在于一个问题是凸优化抑或是非凸优化，而非在于线性与非线性。
1 凸优化
2 对偶理论
2.x 鞍点定理
鞍点定理：博弈存在均衡解(x^*,y^*)的充要条件为K(x,y)存在鞍点。（此时强对偶性成立）
鞍点条件：$K(x^,y) \leq K(x*,y) \leq K(x,y^*) \quad \text{for} \ \forall x \in X, \forall y \in Y $
鞍点定理的证明：
- 前提：函数$\eta(x)= \sup \lbrace K(x,y)|y \in Y \rbrace 是关于x的K(x,y)$的上界函数
- 前提：函数$\zeta(y)= \inf \lbrace K(x,y)|x \in X \rbrace 是关于y的K(x,y)$的下界函数
必要性证明（博弈存在均衡解(x^*,y^*) \Rightarrow K(x,y)存在鞍点）：
充分性证明（K(x,y)存在鞍点\Rightarrow博弈存在均衡解(x^*,y^*)）：
存在K(x^*,y^*)满足:K(x^*,y) \leq K(x^*,y^*) \leq K(x,y^*) \quad \text{for} \ \forall x \in X, \forall y \in Y \hspace{50em} \\ \Rightarrow \sup \lbrace K(x^*, y)|y \in Y \rbrace \leq K(x^*,y^*) \leq \inf \lbrace K(x,y^*) | x \in X \rbrace \hspace{50em} \\ \Rightarrow \eta(x^*) \leq K(x^*, y^*) \leq \zeta(y^*) \hspace{50em} \\ \Rightarrow \inf \lbrace \eta(x)|x \in X \rbrace \leq K(x^*, y^*) \leq \sup \lbrace \zeta(y)|y \in Y \rbrace \hspace{50em}
同时，由于博弈满足弱对偶性