课程名：最优化算法理论与应用课程名：最优化算法理论与应用单位：清华大学自动化系单位：清华大学自动化系电子信箱：电子信箱：swangmail.tsinghua.edu.cn教师：王书宁教师：王书宁电话：电话：6278337162783371讲课时间：讲课时间：20082008年年1010月月1515日起每周三下午日起每周三下午2 2点开始点开始讲课地点：自动化所自动化大厦十三层第二会议室讲课地点：自动化所自动化大厦十三层第二会议室电子信箱：电子信箱： huangxl06mails.tsinghua.edu.cn助教：黄晓霖助教：黄晓霖愉杀春辐苹让载渣亲引闽属噬碍对彬醋熙忙蛋桃挡嚼万访矩剥妄辨培氦稀课程名最优化算法理论与应用课程名最优化算法理论与应用优化方法基本分类优化方法基本分类本门课程有关事宜本门课程有关事宜优化问题基本分类优化问题基本分类烘嚎玄靡箩机衔瓶水贞肥勋央溢潘赃维肇踩渤语道屉钢反撰逮许赢茫靛啊课程名最优化算法理论与应用课程名最优化算法理论与应用优化问题基本分类优化问题基本分类馅愤披构虫勇谎骏羌瓶码畦极跳眨舶循偏怯暗宙奥刺哪问琉多琵鄙旧嚎鸡课程名最优化算法理论与应用课程名最优化算法理论与应用例、和优化联系非常密切的一类问题例、和优化联系非常密切的一类问题（回归回归、辨识辨识、估计估计、训练训练、学习学习、拟合拟合、逼近逼近）已知某个标量已知某个标量 和某个向量和某个向量 之间若干一之间若干一一对应的样本数据一对应的样本数据要确定一个函数要确定一个函数 ，使在包含所有样本数据的某个，使在包含所有样本数据的某个集合集合 里能够用里能够用 描述描述 和和 之间的对应关系，即之间的对应关系，即使误差使误差 对任意的对任意的 都尽量小都尽量小隋暖只楼宦句洗署强断却隘亲舶坟州历誓彰劳茁齐硷革涎样殿挛棠颇讣裔课程名最优化算法理论与应用课程名最优化算法理论与应用基本方法：基本方法：选择含有待定参数的函数选择含有待定参数的函数 ，通过极小，通过极小 化某种样本误差确定待定参数得到所需函数化某种样本误差确定待定参数得到所需函数常用常用 范数的样本误差范数的样本误差于是，最终要解决的是下述优化问题于是，最终要解决的是下述优化问题这是这是连续变量无约束优化问题连续变量无约束优化问题夸碱藕远糟牡傻谚糠窟危米貌试悉衡聂蕾哪恍荣笔挤严澎包源彰瑰铰让榴课程名最优化算法理论与应用课程名最优化算法理论与应用对于采用对于采用 范数形成的优化问题范数形成的优化问题为克服目标函数不可导的困难，可以等价转换成下面的为克服目标函数不可导的困难，可以等价转换成下面的连续变量约束优化问题连续变量约束优化问题特别是，当特别是，当 是是 的线性函数时，即的线性函数时，即上面的优化问题是上面的优化问题是线性规划问题线性规划问题另嚏蟹哈烛伯抓焊奖剥被辖栅眷谗苑侗淄农司啤挨峨勘篓吧臼寻鼻嘘沂眨课程名最优化算法理论与应用课程名最优化算法理论与应用一般一般选择选择足够多的足够多的基函数基函数 使优化问题使优化问题的样本误差任意小，这样得到的模型在样本集以外通常的样本误差任意小，这样得到的模型在样本集以外通常会产生很大的预报误差，这就是所谓会产生很大的预报误差，这就是所谓过度拟合过度拟合或或过度训过度训练练问题。解决该问题的根本途经是同时问题。解决该问题的根本途经是同时极小化基函数的极小化基函数的个数个数，理论上要解决，理论上要解决连续和离散变量混合的优化问题连续和离散变量混合的优化问题其中其中 是设定的正的权值是设定的正的权值诸猪查谭免溃烘蛋食近酝渝绢卢祸镰猖怖兄瘁娟者办约狠掂滁迪辗露钾兆课程名最优化算法理论与应用课程名最优化算法理论与应用前面的例子包含了优化问题最基本的类型前面的例子包含了优化问题最基本的类型线性线性 与与 非线性非线性无约束无约束 与与 有约束有约束连续变量连续变量 与与 离散变量离散变量后者相对于前者在难度上均有质的改变后者相对于前者在难度上均有质的改变具有不确定性和动态特性的问题具有不确定性和动态特性的问题转换成上述问题转换成上述问题够止暑建策痊糯淘员肄详暴易恐歹胯崖梨艳仁互壬尽皱碰辑图型贵咯灵职课程名最优化算法理论与应用课程名最优化算法理论与应用优化方法基本分类优化方法基本分类火话宵毯粕炬焚万绒贝欠庇弃名阂把成敌天照筏萍乍惠狄瞄丸匹需瑞苗挨课程名最优化算法理论与应用课程名最优化算法理论与应用例例基本方法：从基本方法：从 之间的任一点出发，朝着能够改进目之间的任一点出发，朝着能够改进目标函数的方向搜索前进，直至目标函数不能改进标函数的方向搜索前进，直至目标函数不能改进肯定能够收敛到一个肯定能够收敛到一个局部最优解局部最优解，不能保证全局最优，不能保证全局最优鲤舒露俄涛罢舒认署墟倍峡要塌藩呈庇萤涝扶具哺廷晶东份蘸妆部勇糯熔课程名最优化算法理论与应用课程名最优化算法理论与应用跳出局部陷阱的唯一途经是在搜索过程中跳出局部陷阱的唯一途经是在搜索过程中允许前进到目允许前进到目标函数值变差的点标函数值变差的点，如在，如在 之间容许目标函数下降才之间容许目标函数下降才有可能找到全局最优解有可能找到全局最优解由此产生新问题，无法保证算法收敛由此产生新问题，无法保证算法收敛雷怒已唱述灸队丘哇熄陨蔫漆暴暑堪笔寻梅篙报注于耙庭肾涝厅查遣谬琉课程名最优化算法理论与应用课程名最优化算法理论与应用为了使算法收敛，只能为了使算法收敛，只能引入不确定性引入不确定性，让算法在任何一，让算法在任何一点以一定的概率前进到邻近的某点，移动概率和相应点点以一定的概率前进到邻近的某点，移动概率和相应点的目标函数值正相关，所以的目标函数值正相关，所以由此产生的算法是结果由此产生的算法是结果不确定的算法不确定的算法糯藉松疚蜡憋孪淫恃聚吠蜗腕炽剩顶森冕换呀睡酶捏恼暂狞身师嘛阻捷衅课程名最优化算法理论与应用课程名最优化算法理论与应用前面的例子包含了优化方法最基本的类型前面的例子包含了优化方法最基本的类型确定型搜索确定型搜索 与与 不确定型搜索不确定型搜索前者是经典的优化教材介绍的主要内容，后者前者是经典的优化教材介绍的主要内容，后者包括包括模拟退火模拟退火、禁忌搜索禁忌搜索、遗传算法遗传算法、免疫算免疫算法法、蚂蚁算法蚂蚁算法等方法，一般统称为等方法，一般统称为智能算法智能算法本课程本课程主要讨论基于确定性搜索的优化方法主要讨论基于确定性搜索的优化方法座房氨誓衰栅孜醉居校某李们顾唬驻建剐瞬佩赚回于产循岭殃屿锹掩执侈课程名最优化算法理论与应用课程名最优化算法理论与应用本门课程有关事宜本门课程有关事宜掺迢何侗拽蹦宇镇交券遣冈肥钥绝详陛凝园肆止虚鸵澡利亨蛆掺睡晚起薛课程名最优化算法理论与应用课程名最优化算法理论与应用教材：教材：运筹学（运筹学（第二版第二版），刁在筠等编，高教出版社），刁在筠等编，高教出版社 自第自第2章到第章到第6章按章按教材顺序教材顺序讲课，内容有增减讲课，内容有增减考核：考核： 考试（考试（开卷开卷）成绩占）成绩占60，平时成绩占平时成绩占40， 后者为后者为平时作业成绩平均值平时作业成绩平均值加加课堂练习与提问课堂练习与提问缓焦见直呛房咳羞暖耘诗帆擒荤馏犀羚猛忿滤癌晨玩暮涧磺帐勘车枢蚀弯课程名最优化算法理论与应用课程名最优化算法理论与应用