北工大第一次最优化方法

1、最优化理论与算法 （54课时） -绪论,李改弟 应用数理学院 ligd,最优化研究什么？,有选择的地方就有优化：田忌赛马 讨论在众多的方案中什么样的方案最优以及怎样找出最优方案 城建规划：如何安排工厂、机关、学校、商店、医院、住户和其他单位的布局，方能方便群众，利于城市的房展 食谱问题：保证营养要求条件下最经济,课本与教辅材料： 陈宝林，最优化理论与算法(第二版)，清华大学出版社 刘红英，数学规划基础，北京航空航天大学出版社，2012,优化的数学描述与例子,目 标：系统性能的一种“量的度量”(利润、时间、势能)任何数量或某些量的组合数 变 量：目标所依赖的系统的“某些可控的特征” 约束条件：经

2、常变量以某种方式受限制(分子中电子密度的量、贷款利率的量，不能是负的)-,优化问题的一般模型数学规划问题,优化建模(modeling)：识别出给定问题的目标、变量和约束的过程。,建立恰当模型：第一步、最重要的一步(太简单不能给实际问题提供有用的信息；太复杂不易求解) 选择特定算法：很重要-决定求解速度及质量(无通用优化算法，有求解特定类型优化问题的算法),优化实例：运输问题(transportation problem),背 景：化学制品公司考虑某种产品的产销问题.,数 据：,问 题：确定从每个工厂运送到每个销地的产品 数量，使其满足需求，同时极小化费用,变 量： 的产品数量,目标函数：,产量

3、约束：,销量约束：,非负约束：,问题中目标和约束函数都是线性函数, 称此类型的问题为线性规划问题.,优化实例2：选址问题(facility location problem),已知：,目标：确定货栈的位置，使各货栈到各市场的运输量 与路程乘积之和最小。,变量：,货栈的容量,市场的需要量,目标函数和约束函数至少有一个是非线性函数， 此为非线性规划！,1.2 最优化问题的分类与特征,某些或全部变量取整数值才有意义-整数规划 (IP). (上述运输问题中，工厂生产拖拉机而非化学产品). 分为整数线性规划和整数非线性规划；整数规划和混合整数规划；一般整数规划和0-1整数规划 简单松弛策略. 忽略整数要

4、求，当成实变量来求解问题，然后将所有分量舍入到最近的整数-可给出问题的界.Lagrange松弛策略. 整数规划属NP难问题. 常用算法：分支定界法、或其他启发式算法(求解一系列连续优化问题),连续与离散,约束与无约束,无约束优化肯定是非线性的、约束优化又分线性规划 和非线性规划,局部与全局,单目标与多目标,随机与确定,有的问题进行优化建模时，模型与一些不能提前确定的参数有关(运输问题中，零售市场的需求在实际中不能够精确确定. 许多经济和金融规划模型也具有该特征, 哪里经常与未来的利息率和经济的未来趋向有关).,多目标规划最重要的是Perato解/有效解的概念；一般 可用标量化方法求Perato

5、解,优化问题的简单分类与求解难度,问题的求解难度依次增加！,1.3 优化算法和优化软件,迭代法 从最优解的某个初始猜测出发，生成一个提高的估计序列，直到达到一个解. 大部分利用目标函数和约束，可能还有这些函数的一阶和二阶导数. 通常收敛到 (无约束问题)驻点或者 (约束问题)KKT点(极大点、极小点或鞍点). 如果问题是凸规划，则可确保算法收敛到全局极小点., 优化算法,AMPL: A Modeling Language for Mathema-tical Programming Lindo/Lingo软件(verb Matlab优化工具箱(见姜启源等编的数学实验,高教出版社) Cplex 其

6、它(Mathematica, Minos, Excel等的优化功能)., 优化软件,课程主题,介绍线性与非线性规划的 基本理论、实用算法和部分应用 具体的主题包括： 线性规划 基本性质、单纯形法、对偶理论 非线性规划 最优性条件、凸性、Lagrange对偶 无约束优化的算法：线搜索法和信赖域法、直接法 约束优化的算法：可行方向法、罚函数法,先修课程：线性代数，高等数学，最好会某种高级语言,Chap 1 预备知识,一、最优化问题的一般形式：,决策变量，目标函数， 约束函数（等式，不等式）。,二、可行点与可行域,三、（严格）局部极小点与（严格）全局极小点,称满足约束条件的点为可行点,称可行点全体组

7、成的集合为可行域, 记为D,若存在 ，使得 均有,则称 是 在可行域上的全局极小点。,则称 是 在可行域上的局部极小点。,四、向量范数、矩阵范数,1、向量范数定义三条件：,2、常见向量范数：,范数的等价性：,3.诱导矩阵范数,矩阵范数性质(4),常用的矩阵范数,4、向量序列的极限,极限、聚点、Cauchy序列,定理：,开集、闭集、紧集,五、线性空间、欧式空间,六、梯度、Hesse阵,例 求下列函数的梯度与Hesse阵,在线性空间中，定义内积和2范数为度量，这样的 空间为欧式空间。,七. 凸集与凸函数,1.凸集,（1）凸组合：已知 ，,任取k个点 ，,如果存在常数,，,使得,，则称,为,的凸组合

8、。,（2）凸集：设集合,，如果,中任意两点的凸组合,仍然属于,，则称,为凸集。,(3) 凸集的顶点：不能表示成另外两个点的严格凸组合。,（4）凸集的方向、极方向,凸锥,定理(表示定理),2. 凸集分离定理,定理1,证明：,唯一性由反正法得到.,证明:,定理3,证明:,定理4（凸集分离定理）,证明：,3. 凸集分离定理的应用,Farkas定理,必要性反正法，充分性凸集分离定理,2.凸函数,设,，任取,，如果,，,有,，则称,为X上的（严格）,凸函数。,例子：,凹函数？,水平集：,是凸函数。,性质：凸函数的水平集一定是凸集。,3. 凸函数的性质,定理5. 凸函数的局部极小点就是全局极小点。,证明:,4. 凸函数的判断条件,定理6.,则它是凸集X上的凸函数的充要条件是,.,证明：,定理7.设,在开凸集X上有二阶连续偏导