第一章 最优化问题与数学预备知识

第一部分最优化方法基础知识•最优化问题与数学预备知识•凸性•最优性条件第一章最优化问题与数学预备知识•实例与模型•数学预备知识•最优化的基本术语•最优化的计算软件第一章最优化问题与数学预备知识最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为最优方案，搜索最优方案的方法，称为最优化方法。这种方法的数学理论，称为最优化理论。第一章最优化问题与数学预备知识最优化方法已广泛应用于空间技术、军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、经济管理等等领域。最优化方法包括的内容很广泛，如线性规划、非线性规划、整数规划、动态规划、多目标规划、组合优化等等。本课程重点介绍非线性规划。实例与模型实例1—配棉问题棉纺厂的主要原料是棉花，一般要占总成本的70%左右.棉花的品种、等级不同，价格也不同.因此，若采用品种好、等级高、价格贵的棉花来纺成一种质量要求一般的棉纱，势必提高成本.所谓配棉问题就是要根据棉纱的质量指标，采用各种价格不同的棉花，按一定比例配制成纱，使其达到质量指标，又使总成本最低.实例1—配棉问题一个年纺纱能力15000锭的小厂在采用最优化方法配棉前，某一种产品32D纯棉纱的棉花配比、质量指标及单价如下：有关部门对32D纯棉纱规定的质量指标为棉结不多于70粒，品质指标不少于2900.试制定出该厂的最佳配棉方案以使总成本最低.原料品名单价(元/t)混合比棉结粒品质指标混棉单价(元/t)国棉1318400256038002100国棉2297500356535002625国棉3276700408025002680平均合计1007031757405实例与模型实例与模型实例1—配棉问题分析：首先建立数学模型，然后采用相应的最优化方法求解.321,,xxx令分别为国棉131，229，327的棉花配比，则该问题的数学模型为.0,,1290025003500380070806560..670075008400min321321321321321xxxxxxxxxxxxtsxxxz实例与模型实例2—资金使用问题设有400万元资金，要求4年内使用完，若在一年内使资金x万元，则可得到效益x1/2万元(效益不能再使用)，当年不用的资金可存入银行，年利率为10%.试制订出资金的使用规划，以使4年内效益之总和最大.分析：令xi(i=1,2,3,4)分别表示第i年所使用的资金数.目标函数：4321maxxxxxz约束条件：所受到的约束即为每年的使用额既不能为负数又不能超过当年资金拥有数，即实例与模型实例2—资金使用问题40001x第一年：1.1)400(012xx第二年：1.1]1.1)400[(0213xxx第三年：1.1}1.1]1.1)400{[(03214xxxx第四年：实例与模型实例2—资金使用问题则数学模型为.0,,,4.5321.121.1.33114841.1.211440.11400..max432143213212114321xxxxxxxxxxxxxxtsxxxxz实例与模型实例3—二曲线之间距离问题已知二曲线C1:y1=2sin(x)与C2:y2=x2+2无交点，试求C1与C2之间的最短距离d.分析：令(x1,y1)为C1上的点,(x2,y2)为C2上的点.目标函数：221221)()(minyyxxD约束条件：2)sin(222211xyxy令y1=x3,y2=x4,则数学模型为实例与模型实例3—二曲线之间距离问题令y1=x3,y2=x4,则数学模型为.020)sin(2..)()(min42231221221xxxxtsyyxxD实例与模型实例4—数据拟合问题在生产实践和科技活动中，人们常常从实验或测量中得到数据：xi=x1,x2,…,xm;yi=y1,y2,…,ym称为原始数据，而由原始数据所确定的点列P(xi,yi),i=1,2,…,m,称为原始点列.人们希望将这些数据或点列所蕴含的客观规律用一个函数y=f(x)近似地表示出来.在一般情况下通常将f(x)取为代数多项式的形式，即取y=f(x)=a0+a1x1+a2x2+…+anxn.分析：如果测量数据不很准确(即含有较大的测量误差)，但测得数据或点列较多(mn).在此条件下，人们往往采用拟合的办法，即是去求一组系数(a0,a1,a2,…,an)使得下式取值最小2010)(),,,(miiinxfyaaaS实例与模型实例4—数据拟合问题20210)(min),...,,,(minmiiianaxfyaaaaSjj则数学模型为实例与模型实例5—结构设计问题结构设计师的传统工作在于力图提出这样的设计，该设计能够安全地承受作设计的载荷，最有性的概念仅仅隐含在设计的标准规范和设计师的经验之中.但是现在有了计算机的帮助，复杂的结构设计如航空空间结构的设计，对最优性的要求更明显了.以两杆对称桁架的极小重量设计为例.考虑下图所示的平面桁架，它由两根钢管构成，顶点为两杆的共同端点，两杆的另两个支点固定.已知桁架的跨度为2L,承受负荷为2P,钢管的厚度T,材料比重为ρ，纵向弹性模数为E,容许力为σ.要确定钢管的平均直径d和桁架高度h,使桁架重量最小.实例与模型实例5—结构设计问题d(b)钢管剖面图2L(a)桁架示意图实例与模型.222hLTdW分析：这里决策变量为d和h,目标函数为实例5—结构设计问题;22TdhhLP(1)钢管内压应力不超过容许极限，即约束条件包括：(2)为保证在负荷2P的作用下钢管不发生弯曲，要求压应力不超过临界应力σl，由材料力学知dhThLPhLTdEl2222222)(8)(实例与模型实例5—结构设计问题(3)设计变量d和h有界..,,0)(8)(,0..2minminmaxminmax22222222222hhhddddhThLPhLTdEdhThLPtshLdT则数学模型为实例与模型实例6—政治区划问题假设m个基本人口单元(如县、社团等)按某种政治需要可以得到n个政区组合.设cj为选取政区j的费用或不可接受性的度量.问怎样把这m个人口单元分成K个政区,使总的费用(或不可接受性)最小?,n...,21j,0j,1，，否则选取政区jx分析：令,n...,21j1,2,...m,i,0ji,1，，否则划到政区人口单元ija实例与模型.,...,2,1,,...,2,11010,,...,21,1..min111njmixaKxmixatsxcjijnjjnjjijnjjj，或，或，，实例6—政治区划问题则数学模型为最优化问题的数学模型一般形式为：1.1.1minxf2.1.1,,2,1,0..mixctsi（目标函数）（等式约束）（不等式约束）3.1.1,,,1,0pmixci其中nTnRxxxx,,21实例与模型决策变量约束条件xfnRxmin实例与模型无约束最优化问题UnconstrainedOptimizationProblem根据数学模型中有无约束函数分为无约束的最优化问题和有约束的最优化问题。xfmin.,2,1,0..mixctsi等式约束最优化问题OptimizationProblemwithEqualityConstraints实例与模型xfmin.,,1,0s.t.pmixci实例与模型不等式约束最优化问题OptimizationProblemwithInequalityConstraints实例与模型线性规划：LP当目标函数和约束函数均为变量x的线性函数时，模型(1.1)-(1.3)称为线性规划问题.非线性规划：NLP当目标函数和约束函数中至少有一个为变量x的线性函数时，模型(1.1)-(1.3)称为非线性规划问题.根据决策变量、目标函数和约束条件的不同，最优化还可分为二次规划、整数规划、动态规划、网络优化、非光滑优化、随机规划、几何规划、目标规划、模糊规划、全局最优化等若干分支.定义范数：在n维向量空间nR中，定义实函数,x使其满足以下三个条件：在（１）对任意nRx有,0x当且仅当0x时0x；0x（２）对任意nRx及实数有；xx（３）对任意x有yxyx则称函数nRyx,为nR上的向量范数。数学预备知识---向量的范数(Norm)两类比较常见的范数：P-范数：pxxpnipip1/11其中最常用的是2-范数，即：(1.2.1)2/1122niixx范数：inixx1maxEuclid范数数学预备知识---向量的范数(Norm)性质(向量范数的等价性)：设||.||A和||.||B是定义于Rn中的两种向量范数，则总存在正数c1和c2，使对一切x∈Rn,有(1.2.2).21ABAxcxxc数学预备知识---向量的范数(Norm)范数的两个重要不等式：(1)三角不等式：;yxyx(2)Cauchy不等式：;yxyxT其中等式成立当且仅当).(y为实数x数学预备知识---向量的范数(Norm)矩阵的谱半径.AAA,RATnm的奇异值为的特征值的正平方根称方阵设.A||...,||||Ann21的谱半径中的最大者为，，的各特征值的绝对值阶方阵称数学预备知识---矩阵的条件数(ConditionNumber)矩阵的奇异值矩阵的条件数,)()()(1AAAt称A的最大奇异值与最小非零奇异值之商为A的条件数,记为κ(A),即rank(A)).t(AtA)(...)(...)()(nt21即的秩为所有奇异值，且的为其中AAAA性质1.)A()A((A))n,...,2,1i)(A()A(A)A(...)A()A(0)A(...)A()A(nAn1iin21n21，于是的特征值和奇异值，则分别为和阶正定矩阵，为设数学预备知识---矩阵的条件数(ConditionNumber)即正定矩阵的条件数等于它的最大特征值与最小特征值之商.性质2.)A()A((A)0)A(...)A()A(AnAn1n21，从而的所有奇异值阶满秩矩阵，则为设数学预备知识---矩阵的条件数(ConditionNumber)即满秩矩阵的条件数等于它的最大奇异值与最小奇异值之商.病态：数学预备知识---矩阵的条件数(ConditionNumber)如果一个n阶满秩矩阵A的n个列向量之间存在着近似线性关系，则称A为病态的.此时A的最小奇异值就会很小，相应的条件数就会很大.因此，条件数可以用来度量矩阵的病态程度.例.1011A，.11)A(1,1(A),1(A)21时，当相应地，A趋于奇异矩阵，也就是说，A的病态程度愈来愈来严重.可微、微分：数学预备知识---多元函数的梯度(Gradient)、Hesse矩阵及Taylor公式.x(1.2.4)d,x(1.2.3)0limxn,pn.Rx,:0n处的微分在点为并称处可微在点则称使得维非零向量对任意的维向量如果存在设f(x)Δxpf(x)f(x)ΔxΔxp)xf(Δx)xf(RRf(x)TTΔxn(1.2.5)).()()(xxpxfxxfT式(1.2.3)可以写成下述等价形式梯度：数学预备知识---多元函数的梯度(Gradient)、Hesse矩阵及Taylor公式.x)x(fx)x(f...,x)x(fx)x(f)x(fx)x(fn,...,2,1i,x)x(fxx.Rx,:Tn21in