第章高等数学规划预备知识.docx

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

1、第1章 预备学问1.1 根本概念及术语 数学规划问题举例例1 食谱配食问题l 假设市场上有n种不同的食物，第j种食物每个单位的销售价为。l 人体在正常生命活动过程中须要m种根本的养分成分。为了保证人体的安康，一个人每天至少须要摄入第i种养分成分个单位。l 第j种食物的每个单位包含第i种养分成分个单位。食谱配食问题就是要求在满意人体根本养分需求的前提下，找寻最经济的配食方案食谱。建立食谱的数学模型引入决策变量 ：食谱中第i种食物的单位数量s.t. 例2 选址及运输问题l 假设某大型建筑公司有m.l 第i个工地对某种建筑材料的日用量是的比方水泥的日用量单位：t为l 该公司打算分别在和两个地点建立临

2、时料场，并且保证临时料场对材料的日储量单位：t分别为和如何为该公司确定临时料场的位置，并且制订每天的材料供应方案，使建筑材料的总体运输负担最小？建立选址及运输问题的数学模型引入决策变量：位置变量,从临时料场向各工地运送的材料数量.s.t. 例3 消费方案问题l 某企业向客户供应一种机器，第1季度末须要交货台，第2季度末须要交货台，第3季度末须要交货台l 该企业最大消费实力是每季度消费b 台.l 假设用x表示该企业在某季度消费的机器台数，那么消费费用单位：元可以用函数来描绘.l 企业需为每台机器在每个季度多支付p元的存储费l 假设在第一个季度开始时无存货，不允许缺货.如何制订消费方案，确定在每个

3、季度应当消费多少台机器，才能既履行交货合同，又使企业总体费用最少？建立消费方案的数学模型决策变量：用表示企业在第i个季度消费的机器数量合同规定的总数量：每个季度消费数量要求：每个季度消费数量不大于最大消费实力b ，不少于该季度末的交货量及该季度初的库存量之差.第j个季度初库存量： =0变量隐含要求：，并且取整数企业总费用：全部季度消费及存储费用之和s.t. (Z表示全部整数的集合) 数学规划问题的模型及分类l 形成一个最优化问题的数学模型n 首先须要辨识目的，确定优化标准，即待探讨系统的性能定量描绘，如本钱、数量、利润、时间、能量等；n 其次用相宜的决策变量描绘系统的特征量，并将目的表示成决策

4、变量的函数目的函数，objective function )；n 此外需确定变量所受的范围限制，由假设干个函数的等式或者不等式来定义约束函数，constraint functions)l 最优化问题指在决策变量所受限制范围内，对相关的目的函数进展微小化或者极大化.s.t. 满意约束条件的点称为可行点feasible point ) ，全部可行点的集合称为可行域feasible region) ，记为S.- 当，无约束优化问题;否那么,约束优化问题- 和都是线性函数，为线性规划linear programming，LP);否那么为非线性规划nonlinear programming, NLP.-

5、 全部变量取整数，称为整数规划integer programming);允许一部分变量取整数，另一部分变量取实数，为混合整数规划mixed integer programming, MIP.- 从一个连通无限集合可行域中找寻最优解, 称为连续优化(continuous optimization)问题；从一个有限的集合或者离散的集合中找寻最优解，称为组合优化combinatorial optimization)，或者离散优化discrete optimization- 存在多个目的，即目的函数取一个向量值函数，称多目的规划multi-objective programming)，或多目的优化-

6、最优化问题中出现的参数是完全确定的，称为确定型优化deterministic optimization问题;否那么称为非确定型优化uncertain optimization) 问题，包括了随机规划stochastic programming、模糊规划fuzzy programming ) 等特别情形 最优解的概念定义: 设为目的函数，为可行域，假设对每个，成立，那么称为在上的全局微小点。定义: 设为目的函数，为可行域，假设存在的邻域，使得对每个成立，那么称为在上的部分微小点。l 全局微小点也是部分微小点，而部分微小点不肯定是全局微小点.l 大多数的优化算法通常只是找寻部分最优解.l 对于某些

7、特别情形，如凸规划，部分微小点也是全局微小点.1.2 多元函数分析 梯度及Hesse矩阵函数在x处的梯度为n维列向量：函数在x处的Hesse矩阵为矩阵：二次函数A是n阶对称矩阵，b是n维列向量，c是常数梯度：Hesse矩阵: 对向量值函数,每个重量为n元实值函数.h在点x的Jacobi矩阵为该矩阵称为h在x的导数,记作或, 其中例 向量值函数在任一点的Jacobi矩阵,即导数为 多元函数的Taylor展式假设在开集S上连续可微,给定点，那么f在点的一阶Taylor绽开式为当时,关于是高阶无穷小量假设在开集S上二次连续可微,那么f在点的二阶Taylor绽开式为当时,关于是高阶无穷小量 方向导及最

8、速下降方向在点处沿方向d的改变率用方向导数表示.在处沿方向d的方向导数定义为极限:对于可微函数,方向导数等于梯度及方向的内积,即在点处下降最快的方向,称为最速下降方向,它是在点处的负梯度方向:1.3 凸分析初步 凸集的定义、举例(常见凸集)及性质定义：设S为n维欧氏空间中一个集合假设对S中随意两点，联结它们的线段仍属于S；换言之，对S中随意两点,及每个实数，都有那么称S为凸集常见凸集： 集合为凸集p为n维列向量，为实数集合H称为中的超平面，故超平面为凸集 集合为凸集集合称为半空间，故半空间为凸集 集合为凸集d是给定的非零向量，是定点集合称为射线,故射线为凸集.证明：对随意两点及每一个，必有 以

9、及由于，因此有凸集的性质:设和为中的两个凸集, 是实数,那么(1) 为凸集;(2) 为凸集;(3) 为凸集;(4) 为凸集.凸锥和多面集定义: 设有集合，假设对C中每一点x，当取任何非负数时，都有,那么称C为锥.又假设C为凸集，那么称C为凸锥例 向量集的全部非负线性组合构成的集合为凸锥定义 有限个半空间的交称为多面集例: 集合为多面集假设b=0，那么多面集也是凸锥，称为多面锥极点和极方向定义: 设S为非空凸集，假设x不能表示成S中两个不同点的凸组合；换言之，假设假设, 必推得，那么称x是凸集S的极点定义: 设S为非空凸集，d为非零向量，假如对S中的每一个x，都有射线,那么称向量d为S的方向又设

10、和是S的两个方向，假设对任何正数，有, 那么称和是两个不同的方向假设S的方向d不能表示成该集合的两个不同方向的正的线性组合，那么称d为S的极方向留意:有界集不存在方向，因此也不存在极方向对于无界集才有方向的概念多面集的一个重要性质表示定理：设为非空多面集，那么有：(l)极点集非空，且存在有限个极点.(2)极方向集合为空集的充要条件是S有界假设S无界，那么存在有限个极方向.(3) 的充要条件是: ，. 凸集别离定理及其应用(择肯定理)凸集的另一个重要性质别离定理集合的别离：指对于两个集合和，存在一个超平面H，使在H的一边，在H的另一边假如超平面的方程为，那么对位于H某一边的点x，必有，而对位于H

11、另一边的点x，必有.S1S2H定义:设和是两个非空集合，为超平面如对每个,有，对每个，有(或情形恰好相反，那么称H别离集合和.定理(凸集别离定理)：设和是两个非空凸集，那么存在超平面H，使得，.凸集别离定理的另一种表述方法：设和是两个非空凸集，那么存在非零向量p，使凸集别离定理在最优化理论中很有用。闻名的应用是所谓的择肯定理。择肯定理(the theorem of the alternative)指对于两个相关的线性系统等式或不等式组I和II来说，或者系统I有解，或者系统II有解，但两者不行能同时有解.择肯定理有多种不同的形式: Farkas定理,Gordan定理,Motzkin定理等.定理(

12、Farkas定理):设A为矩阵,c为n维向量,那么线性系统(I) , 有解,当且仅当(II) , 无解.定理(Gordan定理):设A为矩阵,那么的充要条件是不存在非零向量,使. 凸函数的定义、性质及判别方法定义: 设S为非空凸集，f是定义在S上的实函数假如对随意的,及每个数,都有那么称f为S上的凸函数假如对随意互不一样,及每一个数，都有,那么称f为S上的严格凸函数 假如-f 为S上的凸函数，那么称f为S上的凹函数凸函数的几何说明：连接函数曲线上随意两点的弦不在曲线的下方凸函数的一些性质： f是定义在凸集S上的凸函数，实数，那么也是定义在S上的凸函数 和是定义在凸集S上的凸函数，那么也是定义在

13、S上的凸函数 是定义在凸集S上的凸函数，实数，那么也是定义在S上的凸函数. S是非空凸集，f是定义在S上的凸函数，是一个实数，那么程度集是凸集 S是非空凸集，f是定义在S上的凸函数，那么f在S上部分微小点是全局微小点，且微小点的集合为凸集 证明: 设是f在S上的部分微小点，即存在的的邻域，使得对每一点，成立.假设不是全局微小点，那么存在，使由于S 是凸集，因此对每一个数,有由于及是不同的两点，可取,又由于f 是S 上的凸函数,因此有当获得充分小时，可使这及为部分微小点冲突故是f在S上的全局微小点 由以上证明可知，f在S上的微小值也是它在S上的最小值设微小值为，那么微小点的集合可以写作依据性质,

14、 为凸集凸函数判别的一阶条件定理: 设S 是非空开凸集，是定义在S上的可微函数，那么为凸函数的充要条件是对随意两点，都有而为严格凸函数的充要条件是对随意的互不一样的，成立推论: 设S是中的凸集, ,是定义在上的凸函数，且在点可微,那么对随意的,有凸函数判别的二阶条件定理: 设S 是中非空开凸集，是定义在S上的二次可微函数，那么为凸函数的充要条件是在每一点处Hesse矩阵半正定 Hesse矩阵半正定, 即对于随意的和, 有定理: 设S 是中非空开凸集，是定义在S上的二次可微函数，假如在每一点,Hesse矩阵正定,那么为严格凸函数留意: 逆定理并不成立假设是定义在S上的严格凸函数，那么在每一点处，

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