《最优化方法第一章－孙文瑜》由会员分享，可在线阅读，更多相关《最优化方法第一章－孙文瑜（118页珍藏版）》请在金锄头文库上搜索。
1、1,最优化方法,2,前言什么是最优化最优化是一门应用性相当广泛的学科, 它讨论决策问题的最佳选择之特性, 寻找最佳的计算方法, 研究这些计算方法的理论性质及其实际计算表现,研究内容: 在有限种或无限种可行方案中挑选最优方案, 构造寻求最优解的计算方法研究目的: 主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题. 应用领域：科学工程、国防、交通、管理、经济、金融、计算机等,3,学习本课程所需的数学知识,向量、向量的模(范数)、向量的运算、 线性相关与无关、基. 矩阵的运算及性质、矩阵的秩、特征值、正定性. 向量函数、连续性、可微性、梯度、海森矩阵、向量函数(多元函数)的Tay
2、lor定理,4,主要参考书目：理论方面：(1)袁亚湘、孙文瑜著,最优化理论与方法, 科学出版社, 2005(2) 何坚勇, 最优化方法, 清华大学出版社, 2007计算方面：(3) 曹卫华, 郭正, 最优化技术方法及MATLAB的实现, 化学工业出版社，2005(4) 朱德通, 最优化模型与实验, 同济大学出版社, 2003,5,其它参考书：(5)卢名高、刘庆吉编著, 最优化应用技术, 石油工业出版社,2002(6)唐焕文, 秦学志,实用最优化方法, 大连理工大学出版社, 2004(7)钱颂迪, 运筹学, 清华大学出版社, 1990 (8)解可新、韩健, 最优化方法, 天津大学出版社, 200
3、4,6,目录,第1章 基本概念第2章 线性规划第3章 线性搜索与信赖域方法第4章 无约束最优化方法第5章 线性与非线性最小二乘问题第6章 二次规划第7章 约束最优化的理论与方法,7,第一章基本概念,8,1.1 最优化问题简介,9,第1章 基本概念,1.1 最优化问题简介1.2 凸集和凸函数1.3 最优性条件1.4 最优化方法概述,10,举 例,例：对边长为a的正方形铁板, 在四个角处剪去相等的正方形以制成方形无盖水槽, 问如何剪法使水槽的容积最大？,解 设剪去的正方形边长为x, 由题意易知, 与此相应的水槽容积为要使其最大, 则,令,得两个驻点：,因此, 每个角剪去边长为,的正方形可使所制成的
4、水槽容积最大,11,例:某制药厂生产甲、乙两种药品, 生产这两种药品要消耗某种维生素. 生产每吨药品所需要的维生素量, 所占用的设备时间, 以及该厂每周可提供的资源总量如下表所示:,已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元.但根据市场需求调查的结果, 甲药品每周的产量不应超过4吨. 问该厂应如何安排两种药品的产量才能使每周获得的利润最大？,12,定义: x1为生产甲种药品的计划产量数, x2为生产乙种药品的计划产量数. 目标：要使总利润最大化 max z=5x1+2x2约束：每周资源总量的限制, 30x1+20x2160 5x1+ x2 15甲种药品每周产量不应超过4吨的限制 x1
5、4计划生产数不可能是负数, x10 x20,13,数学模型为,这是一个如何合理的使用有限的资源, 使生产经营的效益达到最大的数学规划问题.在满足一组约束条件的限制下, 寻求决策变量x1, x2的决策值, 使目标函数达到最大值.,14,例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品. 已知甲、乙两种原料都含有A、B、C三种化学成分, 两种原料分别所含三种化学成分的百分比含量, 以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元, 厂方希望总成本达到最小, 问如何配置该产品？,化学成分,15,定义 x1，x2分别
6、为每公斤产品中甲, 乙两种原料的数量, 目标：使总成本最小化 min z=3x1+2x2约束：配料平衡条件, x1+x2=1产品中A、B、C三种化学成分的最低含量 12x1+3x24 2x1+3x22 3x1+15x25非负性条件 x10, x20,化学成分,16,数学模型：,化学成分,这是一个原料配制问题, 是在生产任务确定的条件下, 合理的组织生产, 使所消耗的资源数最少的数学规划问题.满足一组约束条件的同时, 寻求变量x1和x2的值使目标函数取得最小值.,17,例:某铁器加工厂要制作100套钢架, 每套要用长为2.9米, 2.1米和1.5米的圆钢各一根. 已知原料长为7.4米, 问应如何
7、下料, 可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢, 可以归纳出8种不同的下料方案：,问题归纳为如何混合使用这8种不同的下料方案, 来制造100套钢架, 且要使剩余的余料总长为最短.,18,设 表示用第j 种下料方案下料的原料根数, j=1,2,8,目标: 使余料总长度最小化min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8约束：三种规格圆钢根数 x1+2x2+ x4+ x6 100 2x3+2x4+x5+ x6+3x7 100 3x1+x2+2x3+3x5+x6+4x8 100非负取整条件 xj0 (j=1,28)且取整数
8、,19,数学模型 s.t. 这是一个下料问题, 是在生产任务确定的条件下, 合理的组织生产， 使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时, 寻求变量x1至x8的值,使目标函数取得最 小值.,且为整数,20,最优化的数学模型的一般形式: (1.1.1)其中为连续函数, 通常还要求连续可微,21,目标函数 f(x)决策变量 x 约束函数 ci(x)等式约束 ci(x)=0 (i=1, 2, .,m)不等式约束 ci(x)0 (i=m+1, m+2, .,p)min 极小化s.t. 受约束,22,根据实际问题的不同要求, 最优化模型有不同的形式, 但经过适当的变换都可以转换成上述一
9、般的形式例如, 对于求目标函数f(x)极大的问题 max f ( x) 可转换成求- f ( x) 极小的问题 其中,23,又如对于形如ci(x)0的不等式约束, 可同样转换成上述形式的不等式约束 hi (x)0 , 其中hi(x) =-ci(x) 还有像a(x)b(x)+c的不等式约束, 可通过令 h(x)=b(x)-a(x)+c 转换成h(x)0的不等式约束形式,24,问题(1.1.1)是最优化问题的一般数学表现形式. 只要在问题中存在任何约束条件, 就称为约束最优化问题. 只有等式约束 称为等式约束最优化问题,25,只有不等式约束 称为不等式约束最优化问题. 如果既有等式约束, 又有不等
10、式约束, 则称为混合约束问题.,26,如果问题中无任何约束条件, 则称为无约束最优化问题. 无约束最优化问题的数学模型为 min f(x) , xRn , (1.1.2) 一般简记为 min f (x),27,无约束最优化问题是最优化的基础一则很多实际的最优化问题本身就是无约束最优化问题二则许多约束最优化方法都是通过变换把约束最优化问题转换成无约束最优化问题后, 用适当的无约束优化方法求解.,28,根据模型(1.1.1)中函数的具体性质和复杂程度, 最优化问题又有许多不同的类型. 根据决策变量的取值是离散的还是连续的分为离散最优化和连续最优化 离散最优化通常又称组合最优化, 如整数规划、资源配
11、置、邮路问题、生产安排等问题都是离散最优化问题的典型例子 离散最优化问题的求解较之连续最优化问题的求解难度更大, 本书只介绍连续最优化的理论与方法.,29,根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光滑最优化 如果模型(1.1.1)中的所有函数都连续可微, 则称为光滑最优化 只要有一个函数非光滑, 则相应的优化问题就是非光滑优化问题. 本书只研究光滑最优化问题的求解方法,30,如果所有函数都是变量x=(x1, x2, , xn)T的线性函数, 则称(1.1.1) 为线性规划问题.线性规划问题的一般形式为,31,上述线性规划模型的矩阵向量表示为 其中c= (c1, c2, , cn)
12、T , b1=(b1, b2, , bm)T , b2=(bm+1, , bp)T,32,当模型(1.1.1)中的目标函数f (x)是变量x 的二次函数, 而所有约束都是x 的线性函数时称为二次规划问题.二次规划问题的一般形式为 其中A1, A2的表示同线性规划模型类似, c=(c1, c2, , cn)T , d 为纯量, G为nn阶对称矩阵,33,只要模型(1.1.1)的函数中有一个关于x是非线性的, 就称为非线性最优化问题.非线性最优化问题是最一般的最优化问题, 而线性规划和二次规划问题却是相当重要的特殊的最优化问题,34,如果点xRn 满足最优化模型(1.1.1)中的所有约束条件, 就
13、称其为可行点(feasible point)所有可行点的全体称为可行域 (feasible region)F表示可行域, 即F= x | ci(x)=0, i= 1, 2 , , m, ci(x)0, i= m+1, , p,35,对于一个可行点 , 考虑不等式约束ci(x)0如果有ci(x)=0, 就称约束ci(x)0在点 是有效约束或起作用约束(active constraint) , 并称可行点 位于约束ci(x)0的边界.如果有ci(x)0, 就称不等式约束ci(x)0 在点 是无效约束或不起作用约束(inactive constraint), 并称 是约束ci(x)0 的内点在任意可行点, 所有的等式约束都被认为是有效约束,36,在一个可行点, 所有有效约束的全体被称为该可行点的有效集, 并记为 对于一可行点 ,如果没有一个不等式约束是有效的, 就称 是可行域的内点,
