优化问题基本分类 优化方法基本分类 教材以及考核方式
优化问题基本分类 优化方法基本分类 教材以及考核方式
例、和优化联系非常密切的一类问题 （回归、辨识、估计、训练、学习、拟合、逼近…） 前提：标量 y 的取值由向量 X x1 , x2 ,, xn T 的取值决定 条件：有一组一一对应的样本数据
t 1 i 1 i 1 N m p m
s.t. i 0,1 , 1 i m
其中 w 是设定的正的权值
前面的例子包含了优化问题最基本的类型 线性（凸优化） 与 无约束 连续变量 与 与 一般非线性 有约束 离散变量
后者相对于前者在难度上均有质的改变 具有不确定性和动态特性的问题
课程名：最优化算法理论与应用 教师：王书宁 swang@ 电话 62783371 助教：王晶 wang-jing08@ 电话 62785047 时间：2012年10月9日开始每周二下午 2:30-3:20；3:25-4:15；4:20-5:10 地点：自动化所自动化大厦十三层第二会议室


E p 最终要解决的是优化问题 min
这是连续变量无约束优化问题
对于采用 l 范数形成的优化问题
ˆ X (t ), min max y(t ) f

1t N
为克服目标函数不可导的困难，可以等价转换成下面的 连 变 连续变量约束优化问题 束
min ˆ X (t ), , 1 t N s.t. y(t ) f
教材：运筹学（第三版），刁在筠等编，高教出版社 自第2章到第6章按教材顺序讲课，内容有增减
考核：课程结束时的（开卷）考试成绩50％，平时成 绩占50％，后者为平时作业加课堂测验成绩
转换成上述问题
优化问题基本分类 优化方法基本分类 教材以及考核方式
例
max f ( x)
a x b
f ( x)
x
a c
x1 x1
d
b
基本方法：从 a, b 之间的任一点出发，朝着能够改进目 标函数的方向搜索前进，直至目标函数不能改进 肯定能够收敛到一个局部最优解，不能保证全局最优
y(t ), X (t ) x1 (t ), x2 (t ),, xn (t ) , t 1, 2,, N
T
目的 确定 个函数 f ( X ) ，能够在包含所有样本数据 目的：确定一个函数 能够在包含所有样本数据 的某个集合 里用 f ( X ) 近似描述 y 和 X 之间的 对应关系，即，满足
f ( x)
x a c
ˆ x ˆ x ˆ x
d
b
为了使算法收敛，只能引入不确定性，让算法在任何一 为了使算法收敛，只能引入不确定性，让算法在任何 点以一定的概率前进到邻近的某点，移动概率和相应点 的目标函数值正相关，所以
ˆ|x ˆ px ˆ| x ˆ px
由此产生的算法是结果不确定的算法
y f X , y, X
基本方法：选择含有待定参数的函数 fˆ ( X , ) ，通过极小 化某种样本误差确定待定参数得到所需函数 常用 l1 , l2 , l 范数的样本误差
N ˆ X (t ), y ( t ) f t 1 2 N ˆ X (t ), E p y(t ) f ) t 1 max y(t ) f ˆ X (t ), ) 1t N p 1 p2 p
f ( x)
x a c
ˆ x ˆ x ˆ x
d
b
跳出局部陷阱的唯一途经是在搜索过程中允许前进到目 跳 局部陷 是在搜索 程中允许前 到 标函数值变差的点，如在 c, d 之间容许目标函数下降才 有可能找到全局最优解 由此产生新问题 无法保证算法收敛 由此产生新问题，无法保证算法收敛
特别是，当 fˆ ( X , ) 是 的线性函数时，即
ˆ ( X , ) ( X ) f ii
i 1 m
上面的优化问题是线性规划问题
一般情况下，选择足够多的基函数 i ( X ) 可使优化问题
min y(t ) ii X (t )

t 1 i 1 N m p
的目标函数任意小，这样得到的模型在样本集以外通常 会产生 大 会产生很大的预报误差，即出现过度拟合或过度训练 差 过度 过度 练 解决该问题的根本途经是同时极小化基函数的个数 理 解决该问题的根本途经是同时极小化基函数的个数，理 论上要解决连续和离散变量混合的优化问题
min y(t ) i ii X (t ) w i
前面的例子包含了优化方法最基本的类型 确定型搜索 与 不确定型搜索
前者是经典的优化教材介绍的主要内容，后者 包括模拟退火、禁忌搜索、遗传算法、免疫算 法 蚂蚁算法 …等方法， 法、蚂蚁算法、 等方法 一般称为智能算法 般称为智能算法 本课程主要讨论基于确定性搜索的优化方法

优化问题基本分类 优化方法基本分类 教材以及考核方式