资 源 简 介
详细介绍了最优化方法，是学习最优化的比较好的参考讲义第一章引言第一章引言§1.1最优化问题概述学科简述最优化理论与方法:研究某些数学上定义的问题的最优解,即对于给出的实际问题,从众多的方案中选出最优方案。最优化是一门应用性很强的年轻学科。比如:●工程设计中怎样选择参数,使得设计既满足要求又能降低成本;资源分配中,怎样的分配方案既能满足各方面的基本要求,又能获得好的经济效益:生产计划安排中,选择怎样的计划方案才能提高产值和利润;·原料配比冋题中,怎样确定各种成分的比例才能提高质量、降低成本,最优化问题分类最优化问题分类表分类标志变量个数变量性质约束情况极值个数日标个数函数关系问题性质时间单变量连续无约朿单峰单目标线性确定性静态类型离散随机性多变量函数约束多峰多日标非线性模糊性动态比如:线性规划,非线性规划,随机规划,非光滑规划,多目标规划,整数规划,工作步骤:用最优化方法解决实际问题,一般经过下列步骤1.提出最优化问题,收集有关数据和资料2.建ν最优化问题的数学模型确定变量,列出目标函数和约束条件;3.分析模型,选择合适的最优化方法4.求解,一般通过编制程序,用计算机求最优解5.最优解的检验和实施上述5个步骤常常相互支持、相互制约,在实践中反复交叉进行。模型的三要素:1.变量:最优化问题中待确定的某些量;2.约束条件:求最优解时对变量的某些限制,包括技术上的约束、资源上的约束和时间上的约束等,用等式、不等式、或可行集表示;1.1最优化闩题概述3.目标函数:最优化评价标准的数学描述,一般用最大或最小表示。最优化方法:解析法,直接法,数值解法,二、线性与非线性规划问题例1.1.1[食谱问题设市场上可以买到n种不同的食品,每种食品含有m种营养成分.每单位的笫j种食品售价为c;,且含有第种营养成分为a;设每人每天对第种营养成分的需求量不少于b;,试确定在保证营养的要求下的最经济食谱建立数学模型(1)根据问题的需要设置变量:设每人每天需要各种食品的数量分别为x1,…,xn(2)用所设置的变量把所追求的目标和听受的约束,用数学语言表述出来,得该问题的数学模型:(1.1.3)这里a11表示购买了x;个第种食品所包含的第种营养量,其中min是 minimize的简写,读作“极小化”,s.t.是 subject tol的简写,读作“受限制于”或“约束条件是”。(1.1.1)称为日标函数,(1.1.2)-(1.1.3)称为约束条件例1.1.2[资金使用问题]设有400万元资金,要求4年内使用完,若在一年使用资金x万元,则可得到效益√万元(效益不能再使用),当年不用的资金可存入银行,年利率为10%。试制订出资金的使用规划,以使4年效益总和为最大。显然,不同的使用方案取得的效益总和是不同的。如(1)第一年就把400万元全部用完,则效益总和为√400=20.0(万元)(2)若前三年均不用而存入银行,则第四年把本息和:400×(1.1)3=532.4(万元)全部用完,则效益总和为√52.4-23.07(万元),比第一方案效益大3万元多;(3)若运用最优化方法,可得如下最优方案第年第二年第三年第四年现有资金400342265.1152.8使用金额86.2104.2126.2152.8第一章引言效益总和为√86.2+√104.2+√126.2+√152.8=43.1(万元),是第方案效益总和的两倍多。建立数学模型:设变量x(i-1,2,3,4)分别表示第所使用的资佥数。所追求的目标-4年的效益总和最大,表为+√3+所受到的约束为每年的使用数额既不能为负数又不能超过当年资金拥有数,即第一年00其中max是 maxmize的简写,读作“极人化”。、最优化有关概念线性规划问题:日标函数和约束函数都是线性的最优化问题;非线性规划问题:日标函数或约束函数含有非线性函数的最优化问题叮行点:满足约束条件的点;可行域:全体可行点组成的集合;无约束优化问题:可行集是整个空间最优化问题。卜面给出最优化问题的最优解概念。定义1.1.1设∫(x)为目标函数,S为可行域,亚∈S,若对每一个x∈S,成立∫(x)≥(),则称正为极小化冋题min∫(x),∈S的最优解(全局最优解)定义1.1.2设f(m)为目标函数,S为可行域,若存在的领域N(x)-{c|x-到‖0使得对每个∈S∩N(),成立∫(r)≥∫(),则称正为极小代冋题nin∫(x),x∈S的局部最优解图例注:(1)对于极大化问题,可类似定义全局最优解和局部最优解。(2)全局最优解也是局部最优解,反之木必。但对某些特殊情腦,如凸规划,局部最优解也是全局最优解。1.2数学基础81.2数学基础梯度、Hese矩阵、 Taylor展式定义12.连续画数f:R→R称为在x∈R"连续可微,如果/Ob))在且连续,=1f在x处的梯度定义为afO如果∫在开集DP4.向量的p范数:‖lbx可以证明当γ趋向∞时,p-范数趋向∞范数例.7第一章引言定理1.2.2(向量范数的等价性)设llll是Rn上的任意两种范数,则存在常数1,C2>0,使得xlls≤ lac|t≤c2|rl,∈R”例如ls≤lll≤mlls,vx≤R"几种常用的矩阵范数(A∈R"nx").4的 Frobenius克数:‖4=、∑aP2.A的行范数:‖Ax-max∑向a3.A的列范数:‖4|1=max4.A的2范数(谱范数):‖A4|2-√入ma2(A47A),其中max(4A)表示A7A的最大特征值定义1.2.6(矩阵算子范数)x∈R",A∈Rxn,给定一个向量范数川ll(如=1,2,∞,相应的定义矩阵范数ALv= maIA cll称‖A|,为Rxm上的A的算子范数注:它满足(1)|Ax|≤‖A|,(2)|lA|-|alA,va∈(3)三角不等式A4+B≤‖A|+|B|,(4)‖AB≤‖AB|四、序列的极限定义1.27设{x()}为R的向量序列。若对于任意的ε>0,存在正整数K>0,使得当k>K时,有|(8)-洲0,使得对于任意的k有|)川0,存在正整数K>0,使得当k,l>K时,有|x()-xO川<,称序到{x()}为 Cauchy点列即k,充分大时,x(8)和x()靠得充分的近定理124 Cauchy点列必有极限从而 Cauchy点列的聚点就是极限点,它是唯一的定义1.2.10设S是Rη的子集。若S中每个收敛序列的极限都属于S,称S为闭集.若对于任意的∈S,存在一个x的一个邻域N(x,)={x:l|-l
