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

1、1第 1 章预备知识 1.1 基本概念与术语1.1.1 数学规划问题举例例 1 食谱（配食）问题假设市场上有 n 种不同的食物，第 j 种食物每个单位的销售价为q（j=1,2,，n）。人体在正常生命活动过程中需要m 种基本的营养成分。为了保证人体的健康，一个人每天至少需要摄入第 i 种营养成分b（i=1,2,，m）个单位。第 j 种食物的每个单位包含第 i 种营养成分aij个单位。食谱（配食）问题就是要求在满足人体基本营养需求的前提下，寻找最经济的配食方案 （食谱）。建立食谱的数学模型引入决策变量 为：食谱中第 i 种食物的单位数量nmin exi生ns.t. aijXj:-bi,i = 1,

2、2, , mj吕Xj0,j =1,2, ,n例 2 选址与运输问题假设某大型建筑公司有 m 个项目在不同的地点同时开工建设.记工地的位置分别为p-（ai,bi）, i=1,2, m.第 i 个工地对某种建筑材料的日用量是已知的（比如水泥的日用量 （单位：t ）为Di）.该公司准备分别在T=（为，yj和T2=（X2, y2）两个地点建造临时料场，并且保证临时料场对材料的日储量（单位：t）分别为M1和M2.如何为该公司确定临时料场的位置，并且制订每天的材料供应计划，使建筑材料的总体 运输负担最小？建立选址与运输问题的数学模型引入决策变量：位置变量（Xk, yk）,从临时料场向各工地运送的材料数量Z

3、ki(k =1,2; i =1,2,m).2 m- Zki,.(Xk-ajk F ms.t.二Zki三Mk, k =1,2i2o(yk-bi)min2Zki=Di, i =1,2, ,mk丄2Zki 0,(Xk,yk) R , k=1,2,i =1,2, ,m例 3 生产计划问题某企业向客户提供一种机器，第 1 季度末需要交货 G 台，第 2 季度末需要交货C2台，第 3 季度末需要交货c3台.该企业最大生产能力是每季度生产 b 台.若用 x 表示该企业在某季度生产的机器台数，则生产费用(单位：元)可以用函数f (x) fx - a2x来描述.企业需为每台机器在每个季度多支付p 元的存储费.假

4、设在第一个季度开始时无存货，不允许缺货如何制订生产计划，确定在每个季度应该生产多少台机器，才能既履行交货合同，又使企业总体费用最少？建立生产计划的数学模型决策变量：用(i =1,2,3)表示企业在第 i 个季度生产的机器数量.合同规定的总数量：x1x2X3 =C| C2C3每个季度生产数量要求：每个季度生产数量Xj不大于最大生产能力 b，不少于该季度末的交货量Cj与该季度初的库存量Ij之差第 j 个季度初库存量：Ij=v(xi- ci), j =1,2,3(I1=0)变量隐含要求：Xj_0(j =1,2,3)，并且取整数.企业总费用：所有季度生产与存储费用之和33F(x)f (x)xpIii=

5、1i=23_min F (x)=佝(3 i) p)Xia2X) p(2& C2)iM33S.t. 二Xj八Cjj T j mX1-C1x1x2- G c20Xj-b,Xj Z, j =1,2,3(Z 表示所有整数的集合)1.1.2 数学规划问题的模型与分类形成一个最优化问题的数学模型3首先需要辨识目标，确定优化标准，即待研究系统的性能定量描述，如成本、数量、利润、时间、能量等；其次用合适的决策变量描述系统的特征量，并将目标表示成决策变量的函数(目标函数，objective function)；此外需确定变量所受的范围限制，由若干个函数的等式或者不等式来定义(约束函数，constraint fu

6、nctions ).最优化问题指在决策变量所受限制范围内，对相关的目标函数进行极小化或者极大化minf(x)xWRns.t.gi(x) _0, i Ihj(x) =0, j E满足约束条件的点称为可行点(feasible poi nt)，所有可行点的集合称为可行域(feasible region)，记为 S.-当S = Rn，无约束优化问题；否则，约束优化问题.-f ,gi和hi都是线性函数，为线性规划(linear programming , LP);否则为非线性规划(nonlinear programming, NLP ).-所有变量取整数，称为整数规划(integer programmi

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

8、确定型优化(deterministic optimization )问题；否则称为非确定型优化(uncertain optimization)问题，包括了随机规划(stochasticprogramming )、模糊规戈V (fuzzy programming ) 等特殊情形.1.1.3 最优解的概念定义：设f(x)为目标函数，S为可行域，x S,若对每个S，成立f(x)_f(l), 则称x为f (x)在S上的全局极小点。定义：设f (x)为目标函数，S为可行域，若存在S的；0邻域N& =x|xI，使得对每个Sc N(x)成立f (x)兰f &),则称x为f (x)在S上的局部极小点。全局极小

9、点也是局部极小点，而局部极小点不一定是全局极小点 大多数的优化算法通常只是寻找局部最优解4对于某些特殊情形，如凸规划，局部极小点也是全局极小点5 1.2 多元函数分析1.2.1 梯度及 Hesse 矩阵函数f(x)在 x 处的梯度为 n 维列向量:W(x)=迪，葩,拼(XX1；x2f (x)在 x 处的 Hesse 矩阵为n n矩阵2f (x):-：xn-f(x)Ff(x)Ff(x)1cX1cX2cxxnd f (X)2f(x)d f(x)v2f (x)=做&JaCX2CX2I-Ff (X)Ff(x)Ff(x)IcXsX1CXnCX?FXnXn _二次函数fgxUX +cn 阶对称矩阵，b 是

10、n 维列向量，c 是常数.梯度：帝f(x)=Ax+bHesse 矩阵：2V f(x)=A对向量值函数h(x)= (h1(x),h2(x)；i，hm(X)T，函数Pa2f(x/l-X；：Xj的 Jacobi 矩阵为A 是每个分量h (x)为 n 元实值函数nx：n昂i(x)旳(x)(x)cx2欣n昂2(X)引2(x)chz(x)acx2欣na引m(x)Chm(x)Chm(x)Xicx2CXn_ 旨(x)该矩阵称为 h 在 x 的导数，记作h(x)或 Ih(x)T,其中 h(x) =、hi(x),i h2(x),hm(x)sin XiCOSX2例向量值函数f (x) = f(X|, x2)=XiC

11、OSX22XX2e22为+xjx2f (x)在任一点(X4,X2)的 Jacobi 矩阵,即导数为mxn6cosx1-sin x2|f(x) =Nf (x)T =2e2e2E4xi+x2Xi1.2.2 多元函数的 Taylor 展式假设f (x)在开集 S 上连续可微，给定点XS,贝yf 在点 X 的一阶 Taylor 展开式为f (x)二f (x)、f(X)T(XX)0( XX )o(|xx|)当|XX|T0时,关于|x -X是高阶无穷小量.假设f (X)在开集 S 上二次连续可微，则 f 在点X S的二阶 Taylor 展开式为f(x)= f(x)if(X)T(xX)*(xX)Ti2f(X

12、)(xX)0(xx2)1.2.3 方向导与最速下降方向f (X)在点X处沿方向 d 的变化率用方向导数表示.f (X)在x处沿方向 d 的方向导数Df(x;d)定义为极限Df(x;d)=limf(x d)f(x)0 对于可微函数，方向导数等于梯度与方向的内积，即Df (x;d)f (x)Tdf (x)在点X处下降最快的方向，称为最速下降方向，它是f(X)在点X处的负梯度方向f(x) 1.3 凸分析初步1.3.1 凸集的定义、举例( (常见凸集) )及性质定义：设 S 为 n 维欧氏空间Rn中一个集合若对 S 中任意两点，联结它们的线段仍属 于 S;换言之，对 S 中任意两点x，x及每个实数0,

13、1，都有X(1 - )x(2)S则称 S 为凸集.0( X_X )当X _x0时,关于X-x是高阶无穷小量.7常见凸集：1集合H二x | pTx为凸集.(p 为 n 维列向量，:-为实数) 集合 H 称为Rn中的超平面，故超平面为凸集.2集合H -=x | pTx乞:为凸集.集合H一称为半空间，故半空间为凸集.3集合L二x|x =x() d, -0为凸集.(d 是给定的非零向量 ,x)是定点)集合L称为射线，故射线为凸集.证明：对任意两点x，x(2)L及每一个0,1，必有x(1)=x(0)+X,dx(2)=x(0)+入2d以及X(1 -)X(2)= (x(0)d) (1 - )(x(0)2d)

14、=x(0)W(1 - ；)2d由于匚対* (1 -2_ 0，因此有血+(1丸)x亡L凸集的性质：设s和5为Rn中的两个凸集，一：是实数，则(1)昨=Px|xS为凸集；(2)35 为凸集；(3)S!S2=x(1)- X|x s，x(2)S2为凸集;(4)3 S2=x(1)_x(2)| X亡S，x叫SJ为凸集.凸锥和多面集定义：设有集合C Rn，若对 C 中每一点 X,当取任何非负数时，都有XC,则 称 C 为锥.又若C 为凸集，则称 C 为凸锥.例向量集:(1), :(2),(k)的所有非负线性组合构成的集合(h)8|入3 0,i=1,2，,k为凸锥.定义 有限个半空间的交x I Ax乞b称为多

15、面集.9例：集合S=x|xi 2x2乞4, Xi- X2乞1,Xi_ 0 必_ 0为多面集若 b=0,则多面集x| Ax乞0也是凸锥，称为多面锥.极点和极方向定义：设 S 为非空凸集，S，若 x 不能表示成 S 中两个不同点的凸组合；换言之, 若假设a丄a、(2)(1)(2)_ gX = X (1 -)x,x ,x S必推得x = x=x(2)，则称x是凸集S的极点.(b)定义：设 S 为非空凸集，d 为非零向量，如果对 S 中的每一个 x,都有射线x d | _0 S,则称向量 d 为 S 的方向.又设d和d(2)是 S 的两个方向，若对任何正数，有d(1)- d，则称d和d是 两个不同的方

16、向.若 S 的方向 d 不能表示成该集合的两个不同方向的正的线性组合，则称 d 为 S 的极方向.(a)10注意:有界集不存在方向，因而也不存在极方向.对于无界集才有方向的概念.11多面集的一个重要性质一一表示定理：设S =x| Ax =b,x _0为非空多面集，则有:d,d(l).I(3)xwS的充要条件是：x= EkjX(j)+4jd，乞打=1，丸j启0, j=1,2,，k,j 4j 4j 4Jj-0,j =1,2, ,l.1.3.2 凸集分离定理及其应用（择一定理）凸集的另一个重要性质一一分离定理.集合的分离：指对于两个集合S和S2，存在一个超平面 H，使 S 在 H 的一边，S2在 H

17、 的另一边.如果超平面的方程为pTX=，那么对位于 H 某一边的点 X,必有pTX工二，而对位 于 H 另一边的点 X,必有pTX _ :-.定义：设s和S是两个非空集合，H =x| pTx=a为超平面如对每个xE s,有pTX ：-：，对每个X S，有pTX _ （或情形恰好相反），则称H 分离集合 S|和S2.定理（凸集分离定理）：设S和S2是两个非空凸集，S, S,-一，则存在超平面 H,使得S H”叫x|pTx_：,S2H）x|pTx.凸集分离定理的另一种表述方法：设3 和是两个非空凸集，S,，则存在非零向量 p，使inf pTx| x SJ _ suppTx I x S2凸集分离定理

18、在最优化理论中很有用。著名的应用是所谓的择一定理。择一定理（the theorem of the alternative）指对于两个相关的线性系统（等式或不等式组）I 和 II 来说，或者系统 I 有解，或者系统 II 有解，但两者不可能同时有解择一定理有多种不同的形式：Farkas 定理，Gordan 定理，Motzkin 定理等.定理（Farkas 定理）:设 A 为m n矩阵，c 为 n 维向量，则线性系统（I）Ax _ 0,cTx 0（I） 极点集非空， 且存在有限个极点(k),x()（2）极方向集合为空集的充要条件是S 有界若 S 无界，则存在有限个极方向12有解，当且仅当(II)A

19、Ty=c,y_0无解定理(Gordan 定理):设 A 为m n矩阵,那么Ax 0的充要条件是不存在非零向量y - 0,使ATy= 01.3.3 凸函数的定义、性质及判别方法定义：设 S 为非空凸集，f 是定义在 S 上的实函数如果对任意的X，x.S及每个数(0,1),都有f(x(1一)x上f(x)(1一)f(x)则称 f 为 S 上的凸函数.如果对任意互不相同X,x(2)S及每一个数(0,1),都有f(X(1 -)x):：f (x)(1 -)f(x(2),则称 f 为 S 上的严格凸函数.如果-f 为 S 上的凸函数，则称 f 为 S 上的凹函数.凸函数的几何解释：连接函数曲线上任意两点的弦

20、不在曲线的下方.凸函数的一些性质：1f 是定义在凸集 S 上的凸函数，实数_0,则，f 也是定义在 S 上的凸函数.2f1和f2是定义在凸集 S 上的凸函数，贝y f f2也是定义在 S 上的凸函数.k3f1, f2/, fk是定义在凸集 S 上的凸函数，实数 鼻鼻,，-。，则Vifi也是定im义在 S 上的凸函数.4S 是非空凸集，f 是定义在 S 上的凸函数，是一个实数，则水平集S广x|x S, f (x)岂:是凸集.5S 是非空凸集，f 是定义在 S 上的凸函数，贝 y f 在 S 上局部极小点是全局极小点，且 极小点的集合为凸集.证明：设X是 f 在 S 上的局部极小点，即存在x的；.

21、0的邻域N (x)，使得对每一点/I./W(b)13x S N(x)， 成立f (x) f (x).假设x不是全局极小点，则存在? S，使f(x):：f (x)由于 S 是凸集，因此对每一 个数0,1,有(1 -S由于x与:?是不同的两点，可取(0,1),又由于 f 是S 上的凸函数，因此有f(?(1- 鼻)f (x)(1 -，)f &):f(x) ( ) f(x)= f(x)当取得充分小时，可使?(1一S N (x)这与x为局部极小点矛盾.故x是 f 在 S 上的全局极小点.由以上证明可知，f 在 S 上的极小值也是它在 S 上的最小值设极小值为，则极小点的集合可以写作丨.二x|x S, f

22、(x)乞:根据性质，为凸集.凸函数判别的一阶条件定理：设 S 是非空开凸集，f (x)是定义在 S 上的可微函数，则f (x)为凸函数的充要 条件是对任意两点x,x S，都有f(X)_f(X)(X)T(xX(1)而f (x)为严格凸函数的充要条件是对任意的互不相同的X,x(2厂S，成立f(X)f(X)lf(X)T(X(2)-X)推论：设 S 是Rn中的凸集，S,f(x)是定义在Rn上的凸函数，且在点x可微，则 对任意的x S,有f(x)_ f(X)i f(X)T(x-X)凸函数判别的二阶条件定理：设 S 是Rn中非空开凸集，f(x)是定义在 S 上的二次可微函数，则f(x)为凸函 数的充要条件是在每一点X- S处 Hesse 矩阵半正定.Hesse 矩阵半正定，即对于任意的x，S和x，Rn,有14xVf (X)x_O定理：设 S 是Rn中非空开凸集，f (x)是定义在 S 上的二次可微函数，如