第1章--高等数学规划预备知识(共12页).doc

《第1章--高等数学规划预备知识(共12页).doc》由会员分享，可在线阅读，更多相关《第1章--高等数学规划预备知识(共12页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第1章 预备知识1.1 基本概念与术语1.1.1 数学规划问题举例例1 食谱（配食）问题l 假设市场上有n种不同的食物，第j种食物每个单位的销售价为。l 人体在正常生命活动过程中需要m种基本的营养成分。为了保证人体的健康，一个人每天至少需要摄入第i种营养成分个单位。l 第j种食物的每个单位包含第i种营养成分个单位。食谱（配食）问题就是要求在满足人体基本营养需求的前提下，寻找最经济的配食方案（食谱）。建立食谱的数学模型引入决策变量 ：食谱中第i种食物的单位数量s.t. 例2 选址与运输问题l 假设某大型建筑公司有m个项目在不同的地点同时开工建设.记工地的位置分别为.l

2、第i个工地对某种建筑材料的日用量是已知的（比如水泥的日用量（单位：t）为）l 该公司准备分别在和两个地点建造临时料场，并且保证临时料场对材料的日储量（单位：t）分别为和如何为该公司确定临时料场的位置，并且制订每天的材料供应计划，使建筑材料的总体运输负担最小？建立选址与运输问题的数学模型引入决策变量：位置变量,从临时料场向各工地运送的材料数量.s.t. 例3 生产计划问题l 某企业向客户提供一种机器，第1季度末需要交货台，第2季度末需要交货台，第3季度末需要交货台l 该企业最大生产能力是每季度生产b 台.l 若用x表示该企业在某季度生产的机器台数，则生产费用（单位：元）可以用函数来描述.l 企业

3、需为每台机器在每个季度多支付p元的存储费l 假设在第一个季度开始时无存货，不允许缺货.如何制订生产计划，确定在每个季度应该生产多少台机器，才能既履行交货合同，又使企业总体费用最少？建立生产计划的数学模型决策变量：用表示企业在第i个季度生产的机器数量合同规定的总数量：每个季度生产数量要求：每个季度生产数量不大于最大生产能力b ，不少于该季度末的交货量与该季度初的库存量之差.第j个季度初库存量： （=0）变量隐含要求：，并且取整数企业总费用：所有季度生产与存储费用之和s.t. (Z表示所有整数的集合)1.1.2 数学规划问题的模型与分类l 形成一个最优化问题的数学模型n 首先需要辨识目标，确定优化

4、标准，即待研究系统的性能定量描述，如成本、数量、利润、时间、能量等；n 其次用合适的决策变量描述系统的特征量，并将目标表示成决策变量的函数（目标函数，objective function )；n 此外需确定变量所受的范围限制，由若干个函数的等式或者不等式来定义（约束函数，constraint functions)l 最优化问题指在决策变量所受限制范围内，对相关的目标函数进行极小化或者极大化.s.t. 满足约束条件的点称为可行点（feasible point ) ，所有可行点的集合称为可行域（feasible region) ，记为S.- 当，无约束优化问题;否则,约束优化问题- 和都是线性函数

5、，为线性规划（linear programming，LP);否则为非线性规划（nonlinear programming, NLP）.- 所有变量取整数，称为整数规划（integer programming);允许一部分变量取整数，另一部分变量取实数，为混合整数规划（mixed integer programming, MIP）.- 从一个连通无限集合（可行域）中寻找最优解, 称为连续优化(continuous optimization)问题；从一个有限的集合或者离散的集合中寻找最优解，称为组合优化（combinatorial optimization)，或者离散优化（discrete opt

6、imization）- 存在多个目标，即目标函数取一个向量值函数，称多目标规划（multi-objective programming)，或多目标优化- 最优化问题中出现的参数是完全确定的，称为确定型优化（deterministic optimization）问题;否则称为非确定型优化（uncertain optimization) 问题，包括了随机规划（stochastic programming）、模糊规划（fuzzy programming ) 等特殊情形1.1.3 最优解的概念定义: 设为目标函数，为可行域，若对每个，成立，则称为在上的全局极小点。定义: 设为目标函数，为可行域，若存在

7、的邻域，使得对每个成立，则称为在上的局部极小点。l 全局极小点也是局部极小点，而局部极小点不一定是全局极小点.l 大多数的优化算法通常只是寻找局部最优解.l 对于某些特殊情形，如凸规划，局部极小点也是全局极小点.1.2 多元函数分析1.2.1 梯度及Hesse矩阵函数在x处的梯度为n维列向量：函数在x处的Hesse矩阵为矩阵：二次函数A是n阶对称矩阵，b是n维列向量，c是常数梯度：Hesse矩阵: 对向量值函数,每个分量为n元实值函数.h在点x的Jacobi矩阵为该矩阵称为h在x的导数,记作或, 其中例 向量值函数在任一点的Jacobi矩阵,即导数为1.2.2 多元函数的Taylor展式假设在

8、开集S上连续可微,给定点，则f在点的一阶Taylor展开式为当时,关于是高阶无穷小量假设在开集S上二次连续可微,则f在点的二阶Taylor展开式为当时,关于是高阶无穷小量1.2.3 方向导与最速下降方向在点处沿方向d的变化率用方向导数表示.在处沿方向d的方向导数定义为极限:对于可微函数,方向导数等于梯度与方向的内积,即在点处下降最快的方向,称为最速下降方向,它是在点处的负梯度方向:1.3 凸分析初步1.3.1 凸集的定义、举例(常见凸集)及性质定义：设S为n维欧氏空间中一个集合若对S中任意两点，联结它们的线段仍属于S；换言之，对S中任意两点,及每个实数，都有则称S为凸集常见凸集： 集合为凸集（

9、p为n维列向量，为实数）集合H称为中的超平面，故超平面为凸集 集合为凸集集合称为半空间，故半空间为凸集 集合为凸集（d是给定的非零向量，是定点）集合称为射线,故射线为凸集.证明：对任意两点及每一个，必有 以及由于，因此有凸集的性质:设和为中的两个凸集, 是实数,则(1) 为凸集;(2) 为凸集;(3) 为凸集;(4) 为凸集.凸锥和多面集定义: 设有集合，若对C中每一点x，当取任何非负数时，都有,则称C为锥.又若C为凸集，则称C为凸锥例 向量集的所有非负线性组合构成的集合为凸锥定义 有限个半空间的交称为多面集例: 集合为多面集若b=0，则多面集也是凸锥，称为多面锥极点和极方向定义: 设S为非空

10、凸集，若x不能表示成S中两个不同点的凸组合；换言之，若假设, 必推得，则称x是凸集S的极点定义: 设S为非空凸集，d为非零向量，如果对S中的每一个x，都有射线,则称向量d为S的方向又设和是S的两个方向，若对任何正数，有, 则称和是两个不同的方向若S的方向d不能表示成该集合的两个不同方向的正的线性组合，则称d为S的极方向注意:有界集不存在方向，因而也不存在极方向对于无界集才有方向的概念多面集的一个重要性质表示定理：设为非空多面集，则有：(l)极点集非空，且存在有限个极点.(2)极方向集合为空集的充要条件是S有界若S无界，则存在有限个极方向.(3) 的充要条件是: ，.1.3.2 凸集分离定理及其

11、应用(择一定理)凸集的另一个重要性质分离定理集合的分离：指对于两个集合和，存在一个超平面H，使在H的一边，在H的另一边如果超平面的方程为，那么对位于H某一边的点x，必有，而对位于H另一边的点x，必有.S1S2H定义:设和是两个非空集合，为超平面如对每个,有，对每个，有(或情形恰好相反），则称H分离集合和.定理(凸集分离定理)：设和是两个非空凸集，则存在超平面H，使得，.凸集分离定理的另一种表述方法：设和是两个非空凸集，则存在非零向量p，使凸集分离定理在最优化理论中很有用。著名的应用是所谓的择一定理。择一定理(the theorem of the alternative)指对于两个相关的线性系统

12、（等式或不等式组）I和II来说，或者系统I有解，或者系统II有解，但两者不可能同时有解.择一定理有多种不同的形式: Farkas定理,Gordan定理,Motzkin定理等.定理(Farkas定理):设A为矩阵,c为n维向量,则线性系统(I) , 有解,当且仅当(II) , 无解.定理(Gordan定理):设A为矩阵,那么的充要条件是不存在非零向量,使.1.3.3 凸函数的定义、性质及判别方法定义: 设S为非空凸集，f是定义在S上的实函数如果对任意的,及每个数,都有则称f为S上的凸函数如果对任意互不相同,及每一个数，都有,则称f为S上的严格凸函数 如果-f 为S上的凸函数，则称f为S上的凹函数

13、凸函数的几何解释：连接函数曲线上任意两点的弦不在曲线的下方凸函数的一些性质： f是定义在凸集S上的凸函数，实数，则也是定义在S上的凸函数 和是定义在凸集S上的凸函数，则也是定义在S上的凸函数 是定义在凸集S上的凸函数，实数，则也是定义在S上的凸函数. S是非空凸集，f是定义在S上的凸函数，是一个实数，则水平集是凸集 S是非空凸集，f是定义在S上的凸函数，则f在S上局部极小点是全局极小点，且极小点的集合为凸集 证明: 设是f在S上的局部极小点，即存在的的邻域，使得对每一点，成立.假设不是全局极小点，则存在，使由于S 是凸集，因此对每一个数,有由于与是不同的两点，可取,又由于f 是S 上的凸函数,

14、因此有当取得充分小时，可使这与为局部极小点矛盾故是f在S上的全局极小点 由以上证明可知，f在S上的极小值也是它在S上的最小值设极小值为，则极小点的集合可以写作根据性质, 为凸集凸函数判别的一阶条件定理: 设S 是非空开凸集，是定义在S上的可微函数，则为凸函数的充要条件是对任意两点，都有而为严格凸函数的充要条件是对任意的互不相同的，成立推论: 设S是中的凸集, ,是定义在上的凸函数，且在点可微,则对任意的,有凸函数判别的二阶条件定理: 设S 是中非空开凸集，是定义在S上的二次可微函数，则为凸函数的充要条件是在每一点处Hesse矩阵半正定 Hesse矩阵半正定, 即对于任意的和, 有定理: 设S

15、是中非空开凸集，是定义在S上的二次可微函数，如果在每一点,Hesse矩阵正定,则为严格凸函数注意: 逆定理并不成立若是定义在S上的严格凸函数，则在每一点处，Hesse矩阵是半正定的(而不是正定的)例: 给定二次函数由于在每一点处,是正定的，因此是严格凸函数 1.3.4 凸规划及其性质考虑极小化问题：s.t. 设是凸函数，是凹函数，是线性函数问题的可行域由于是凹函数，因此满足,即满足的点的集合是凸集.根据凸函数和凹函数的定义，线性函数既是凸函数也是凹函数，因此满足的点的集合也是凸集S是m+l个凸集的交，因此也是凸集上述问题是求凸函数在凸集上的极小点这类问题称为凸规划 注意: 如果是非线性的凸函数，满足的点的集合不是凸集,问题就不属于凸规划 凸规划的重要性质 凸规划的局部极小点就是全局极小点，且极小点的集合是凸集 如果凸规划的目标函数是严格凸函数，又存在极小点，那么它的极小点是惟一的习题1考虑极小化问题：s.t. （1） 该规划问题是否为凸规划？为什么？（2） 用图解法找出该问题的最优解2 证明有可行解，其中专心-专注-专业