第1章 预备知识§1.1 基本概念与术语1.1.1 数学规划问题举例例1 食谱（配食）问题● 假设市场上有n 种不同的食物，第j 种食物每个单位的销售价为),,2,1(n j c j 。

● 人体在正常生命活动过程中需要m 种基本的营养成分。

为了保证人体的健康，一个人每天至少需要摄入第i 种营养成分),,2,1(m i b i 个单位。

● 第j 种食物的每个单位包含第i 种营养成分ij a 个单位。

食谱（配食）问题就是要求在满足人体基本营养需求的前提下，寻找最经济的配食方案（食谱）。

建立食谱的数学模型引入决策变量i x ：食谱中第i 种食物的单位数量i ni i x c 1mins.t.m i b x a i j nj ij ,,2,1,1n j x j ,,2,1 ,0例2 选址与运输问题● 假设某大型建筑公司有m 个项目在不同的地点同时开工建设.记工地的位置分别为m i b a P i i i ,,2,1 ),,( .● 第i 个工地对某种建筑材料的日用量是已知的（比如水泥的日用量（单位：t ）为i D ）． ● 该公司准备分别在),(111y x T 和),(222y x T 两个地点建造临时料场，并且保证临时料场对材料的日储量（单位：t ）分别为1M 和2M ．如何为该公司确定临时料场的位置，并且制订每天的材料供应计划，使建筑材料的总体运输负担最小？建立选址与运输问题的数学模型引入决策变量：位置变量),(k k y x ,从临时料场向各工地运送的材料数量),,2,1 ;2,1(m i k z ki .21122)()(min k mi i k i k ki b y a x zs.t.2,1 ,1k M z k mi kim i D z i k ki ,,2,1 ,21m i k y x z k k ki ,,2,1,2,1 , R ),( ,02例3 生产计划问题● 某企业向客户提供一种机器，第1季度末需要交货1c 台，第2季度末需要交货2c 台，第3季度末需要交货3c 台．● 该企业最大生产能力是每季度生产b 台.● 若用x 表示该企业在某季度生产的机器台数，则生产费用（单位：元）可以用函数x a x a x f 21)( 来描述.● 企业需为每台机器在每个季度多支付p 元的存储费． ● 假设在第一个季度开始时无存货，不允许缺货.如何制订生产计划，确定在每个季度应该生产多少台机器，才能既履行交货合同，又使企业总体费用最少？建立生产计划的数学模型决策变量：用)3,2,1( i x i 表示企业在第i 个季度生产的机器数量． 合同规定的总数量：321321c c c x x x每个季度生产数量要求：每个季度生产数量j x 不大于最大生产能力b ，不少于该季度末的交货量j c 与该季度初的库存量j I 之差.第j 个季度初库存量：3,2,1 ,)( j c x I ji i i j （1I =0）变量隐含要求：)3,2,1(0 j x j ，并且取整数． 企业总费用：所有季度生产与存储费用之和3231)()(i i i i pI x f x F)2()))3(()(min 213121c c p x a x p i a x F i i is.t. 3131j j j j c x11c x2121c c x x3,2,1,,0 j Z x b x j j (Z 表示所有整数的集合)1.1.2 数学规划问题的模型与分类● 形成一个最优化问题的数学模型⏹ 首先需要辨识目标，确定优化标准，即待研究系统的性能定量描述，如成本、数量、利润、时间、能量等；⏹ 其次用合适的决策变量描述系统的特征量，并将目标表示成决策变量的函数（目标函数，objective function )；⏹ 此外需确定变量所受的范围限制，由若干个函数的等式或者不等式来定义（约束函数，constraint functions )．● 最优化问题指在决策变量所受限制范围内，对相关的目标函数进行极小化或者极大化.)(min nRx f x s.t. I i x g i ,0)(E j x h j ,0)(满足约束条件的点称为可行点（feasible point ) ，所有可行点的集合称为可行域（feasible region ) ，记为S .当nS R ，无约束优化问题;否则,约束优化问题．i g f ,和i h 都是线性函数，为线性规划（linear programming ，LP );否则为非线性规划（nonlinear programming, NLP ）.所有变量取整数，称为整数规划（integer programming );允许一部分变量取整数，另一部分变量取实数，为混合整数规划（mixed integer programming, MIP ）.从一个连通无限集合（可行域）中寻找最优解, 称为连续优化(continuous optimization )问题；从一个有限的集合或者离散的集合中寻找最优解，称为组合优化（combinatorial optimization)，或者离散优化（discrete optimization ）．存在多个目标，即目标函数)(x f 取一个向量值函数，称多目标规划（multi-objective programming)，或多目标优化．最优化问题中出现的参数是完全确定的，称为确定型优化（deterministic optimization ）问题;否则称为非确定型优化（uncertain optimization) 问题，包括了随机规划（stochastic programming ）、模糊规划（fuzzy programming ) 等特殊情形．1.1.3 最优解的概念定义: 设)(x f 为目标函数，S 为可行域，S x ，若对每个S x ，成立)()(x f x f ，则称x 为)(x f 在S 上的全局极小点。

定义: 设)(x f 为目标函数，S 为可行域，若存在S x 的0 邻域}|{),( x x x x N ，使得对每个),( x N S x 成立)()(x f x f ，则称x 为)(x f 在S 上的局部极小点。

● 全局极小点也是局部极小点，而局部极小点不一定是全局极小点. ● 大多数的优化算法通常只是寻找局部最优解.● 对于某些特殊情形，如凸规划，局部极小点也是全局极小点.§1.2 多元函数分析1.2.1 梯度及Hesse 矩阵函数)(x f 在x 处的梯度为n 维列向量：Tn x x f x x f x x f x f)(,,)(,)()(21函数)(x f 在x 处的Hesse 矩阵为n n 矩阵)(2x f ：n n j i n n n n n x x x f x x x f x x x f x x x f x x x f x x x f x x x f x x x f x x x f x x x f x f)()()()()()()()()()()(222212222222122122121122二次函数c x b Ax x x f T T21)( A 是n 阶对称矩阵，b 是n 维列向量，c 是常数．梯度：b Ax x f )( Hesse 矩阵:A x f )(2对向量值函数 Tm x h x h x h x h )(,),(),()(21 ,每个分量)(x h i 为n 元实值函数.h 在点x的Jacobi 矩阵为n m j i n m m m n n x x h x x h x x h x x h x x h x x h x x h x x h x x h xx h)()()()()()()()()()(212221212111该矩阵称为h 在x 的导数,记作)('x h 或Tx h )( , 其中)(,),(),()(21x h x h x h x h m例 向量值函数2121221212cos sin ),()(21x x x e x x x x f x f x x )(x f 在任一点),(21x x 的Jacobi 矩阵,即导数为1212221'42sin cos )()(2121x x x e e x x x f x f x x x x T 1.2.2 多元函数的Taylor 展式假设)(x f 在开集S 上连续可微,给定点S x ，则f 在点x 的一阶Taylor 展开式为)()()()()(x x o x x x f x f x f T)(x x o 当0 x x 时,关于x x 是高阶无穷小量．假设)(x f 在开集S 上二次连续可微,则f 在点S x 的二阶Taylor 展开式为)())(()(21)()()()(22x x o x x x f x x x x x f x f x f T T)(2x x o 当02 x x 时,关于2x x 是高阶无穷小量．1.2.3 方向导与最速下降方向)(x f 在点x 处沿方向d 的变化率用方向导数表示. )(x f 在x 处沿方向d 的方向导数);(d x Df 定义为极限:)()(lim);(0x f d x f d x Df对于可微函数,方向导数等于梯度与方向的内积,即d x f d x Df T )();()(x f 在点x 处下降最快的方向,称为最速下降方向,它是)(x f 在点x 处的负梯度方向:)()(x f x f d§1.3 凸分析初步1.3.1 凸集的定义、举例(常见凸集)及性质定义：设S 为n 维欧氏空间nR 中一个集合．若对S 中任意两点，联结它们的线段仍属于S ；换言之，对S 中任意两点)1(x ,)2(x及每个实数]1,0[ ，都有S x x )2()1()1(则称S 为凸集．常见凸集：① 集合}|{ x p x H T为凸集．（p 为n 维列向量， 为实数） 集合H 称为n R 中的超平面，故超平面为凸集． ② 集合}|{x p x H T 为凸集． 集合H 称为半空间，故半空间为凸集． ③ 集合}0,|{)0( d x x x L 为凸集．（d 是给定的非零向量，)0(x 是定点）集合L 称为射线,故射线为凸集.证明：对任意两点L xx )2()1(,及每一个]1,0[ ，必有d x x 1)0()1( d x x 2)0()2(以及dxd x d x x x ])1([ ))(1()()1(21)0(2)0(1)0()2()1(由于0)1(21 ，因此有L x x )2()1()1(凸集的性质:设1S 和2S 为nR 中的两个凸集, 是实数,则 (1)}|{11S x x S 为凸集; (2)21S S 为凸集; (3)},|{2)2(1)1()2()1(21S x S x x x S S 为凸集; (4)},|{2)2(1)1()2()1(21S x S x x x S S 为凸集.凸锥和多面集定义: 设有集合nR C ，若对C 中每一点x ，当 取任何非负数时，都有C x ,则称C 为锥.又若C 为凸集，则称C 为凸锥．例 向量集)()2()1(,,k的所有非负线性组合构成的集合k i i ki i i ,,2,1,0|1)( 为凸锥．定义 有限个半空间的交}|{b Ax x 称为多面集．例: 集合}0,0,1,42|{212121 x x x x x x x S 为多面集．若b =0，则多面集}0|{ Ax x 也是凸锥，称为多面锥． 极点和极方向定义: 设S 为非空凸集，S x ，若x 不能表示成S 中两个不同点的凸组合；换言之，若假设)2()1()1(x x x , S x x )2()1(,必推得)2()1(x xx ，则称x 是凸集S 的极点．定义: 设S 为非空凸集，d 为非零向量，如果对S 中的每一个x ，都有射线S d x }0|{ ,则称向量d 为S 的方向．又设)1(d和)2(d是S 的两个方向，若对任何正数 ，有)2()1(d d, 则称)1(d 和)2(d 是两个不同的方向．若S 的方向d 不能表示成该集合的两个不同方向的正的线性组合，则称d 为S 的极方向．注意:有界集不存在方向，因而也不存在极方向．对于无界集才有方向的概念．多面集的一个重要性质——表示定理： 设}0,|{ x b Ax x S 为非空多面集，则有： (l)极点集非空，且存在有限个极点)()1(,,k xx .(2)极方向集合为空集的充要条件是S 有界．若S 无界，则存在有限个极方向)()1(,,l d d .(3)S x 的充要条件是: l j j j kj j j d xx 1)(1)( ， kj j 11 ，k j j ,,2,1,0 ，l j j ,,2,1,0 .1.3.2 凸集分离定理及其应用(择一定理)凸集的另一个重要性质——分离定理．集合的分离：指对于两个集合1S 和2S ，存在一个超平面H ，使1S 在H 的一边，2S 在H 的另一边．如果超平面的方程为 x p T ，那么对位于H 某一边的点x ，必有 x p T，而对位于H 另一边的点x ，必有 x p T.定义:设1S 和2S 是两个非空集合，}|{ x p x H T为超平面．如对每个1S x ,有x p T ，对每个2S x ，有 x p T (或情形恰好相反），则称H 分离集合1S 和2S .定理(凸集分离定理)：设1S 和2S 是两个非空凸集， 21S S ，则存在超平面H ，使得}|{1x p x H S T，}|{2x p x H S T.凸集分离定理的另一种表述方法：设1S 和2S 是两个非空凸集， 21S S ，则存在非零向量p ，使}|sup{}|inf{21S x x p S x x p T T凸集分离定理在最优化理论中很有用。