optimization is the core of machine learning

AI问题 = 模型 + 优化
任何一个优化问题，都可以写成如下形式：
$Minimize f_0(x)$Minimizef0​(x)
$s.t. f_i(x)<=0,i={1,2...,K}$s.t.fi​(x)<=0,i=1,2...,K
$g_j(x)=0,j={1,2,...L}$gj​(x)=0,j=1,2,...L

1.优化问题的分类

·smooth Vs Non-smooth
·convex Vs Non-convex
·constrained Vs Non-constrained
·continous Vs distributed

2.凸函数和非凸函数

凸函数具有全局最优解，非凸函数具有局部最优解

3.怎么判断凸函数?

·通过定义：定义域为凸集，函数本身为凸函数
·通过一阶充要条件：$f(y) >= f(x) + f'(x)(y-x)$f(y)>=f(x)+f′(x)(y−x)
·通过二阶充要条件：$f''(x)>=0$f′′(x)>=0
·通过operation，凸+凸 = 凸

4.优化目标函数的种类

·least squar problem 最小二乘
·linear programing problem 线性
·qudratic programing problem 二次
·integer programing problem 整型
·geometic programing 图

5.非凸函数的处理

整数线性规划的分治方法。

举例说明优化问题的重要性

set cover problem

假设我们有个全集U(Universal Set),以及$m$m个子集合$S_1,S_2,...,S_m$S1​,S2​,...,Sm​,目标是找最少的集合，使得集合的Union等于U。

令U={1,2,3,4,5},S:$S_1$S1​={1,2,3},$S_2$S2​={2,4},$S_3$S3​={1,3},$S_4$S4​={4},$S_5$S5​={3,4},$S_5$S5​={3,4},$S_6$S6​={4,5},最少的集合为$S_1$S1​={1,2,3}，$S_6$S6​={4,5}。

approach1: Exhausive search

iteration1:选择一个集合 S1,S2,S3,S4,S5,S6 == U?
iteration2:选择两个集合 S1US2,S1US3… S1US6 一定得到全局最优解

approach2:贪心算法

iteration1: S1,S2,S3,S4,S5,S6中删除一个，删除S1,保证剩下能并到U
iteration2:S2,S3,S4,S5,S6再删除一个S4,保证剩下能并到U
iteration3:S2,S3,S5,S6再删除一个S5,保证剩下能并到U
iteration4:S2,S3,S6 达到终止条件，无法删除，最终得到局部最优{S2,S3,S6}

approach3:Optimization

objection function: $\sum_i^m x_i$∑im​xi​
$s.t. x_i\in0,1$s.t.xi​∈0,1 ，$i=1,2,...,m$i=1,2,...,m
$\sum_{i:e\in S_i} \quad x_i>=1$∑i:e∈Si​​xi​>=1 对于$U$U中的元素$e$e,在$S_i$Si​中被取次数大于等于1
$question1: is\quad it \quad convex$question1:isitconvex
定义域为Convex Set？No 目标函数为Convex function? yes

#进行松弛操作
objection function: $\sum_i^m x_i$∑im​xi​
$s.t. x_i\in[0,1]$s.t.xi​∈[0,1] ，$i=1,2,...,m$i=1,2,...,m
$\sum_{i:e\in S_i} \quad x_i>=1$∑i:e∈Si​​xi​>=1 对于$U$U中的元素$e$e,在$S_i$Si​中被取次数大于等于1
通过线性规划的算法解出松弛解，
$if\quad x_i<0.5,\quad x_i=0,\quad else\quad x_i=1$ifxi​<0.5,xi​=0,elsexi​=1