最优化参考讲义（上海交大参考讲义）

【实例简介】
详细介绍了最优化方法，是学习最优化的比较好的参考讲义
第一章引言 第一章引言 §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+ 所受到的约束为每年的使用数额既不能为负数又不能超过当年资金拥有数,即 第一年0<x1<400 第二年0≤x2≤(400-m1)×1.(第一年未使用资金存入银行一年后本利和) 第三年0≤x3≤[(400-x1)×11-x2]×1.1 第四年0≤x4={[(400-m1)×11-x2]×11-3}×1.1 资金使用问题的数学模型为 =√m1+ s.x1≤400 (1.1.4) 111+2≤400 1.21:1+1.12+x3≤48 1331x1+1.212+1.1x3+x4=532.4 x1,T2,C3,x4>0 其中max是 maxmize的简写,读作“极人化”。 、最优化有关概念 线性规划问题:日标函数和约束函数都是线性的最优化问题; 非线性规划问题:日标函数或约束函数含有非线性函数的最优化问题 叮行点:满足约束条件的点; 可行域:全体可行点组成的集合; 无约束优化问题:可行集是整个空间最优化问题。 卜面给出最优化问题的最优解概念。 定义1.1.1设∫(x)为目标函数,S为可行域,亚∈S,若对每一个x∈S,成立∫(x)≥(),则 称正为极小化冋题min∫(x),∈S的最优解(全局最优解) 定义1.1.2设f(m)为目标函数,S为可行域,若存在的领域 N(x)-{c|x-到‖<e,e>0 使得对每个∈S∩N(),成立∫(r)≥∫(),则称正为极小代冋题nin∫(x),x∈S的局部最优解 图例 注:(1)对于极大化问题,可类似定义全局最优解和局部最优解。 (2)全局最优解也是局部最优解,反之木必。但对某些特殊情腦,如凸规划,局部最优解 也是全局最优解。 1.2数学基础 81.2数学基础 梯度、Hese矩阵、 Taylor展式 定义12.连续画数f:R→R称为在x∈R"连续可微,如果/O b))在且连续,=1 f在x处的梯度定义为 af O 如果∫在开集D<F中的每一点连续可徵,则称∫在D中连续可微,记作∈C"() 定义12.2连续可徼函数f:→H称为在x二次连续可微,如果 (x)存在且连续,1≤i, Oxi aaj n.f在汇处的Hese矩阵定义为n×n矩阵,其第i,j元素为 Vf(a)lij 02f(x) 如果∫在开集D中的毎一点二次连续可微,则称∫在D中二次连续可微,记作∫∈C2(D) 例.f(x1,x2)=x2+2x1x2-32+2x1-2x2+6 f(x)=aT AT+62+c, Vf(r)=Ax +b, v2f(r)=A 定义12.3设∫:Rn一}R在开集D上连续可微,对于x∈R,d∈R",f在x点关于方向d的方向导 数定义为 D(f; d) f( c+ 8d)-f(a) 上述定义的方向导数等于Vf(x)d,其中Vf(x)表示f在x的梯度 对任何x,+d∈D,或x,y∈D,若f:R"→R在开凸集D上连续可微.则有 f(a+d)-f(x)+Vf(r+td (12.1) 囚而也有 f(x+d)=f(x)+Ⅴf()d,s∈(x,m+d) 或 (y)=/(x)+V/(x+l(y-x)(y-x),t∈(0,1), 或 f(u)=f(a)+vf(e)(y-x)+o(lly-a) 上式称为f在点x处的一阶 Taylor展式 设f:Rn→F在开集D二次连续可微,对于仟何x,x+d∈D,存在∈(x,+d),使得 f(a+d)=f(a)+vf()d+od vf(s)d, 第一章引言 或 f(a+d)=f(a)+vf(ad+ed vf(a d+o(d) 上式称为f在点x处的二阶 Taylor展式。 Jacob矩阵、链式法则、隐函数存在定理 定义.2.4设h:R"→Fm,h(x)=(h1(x),…hmn(),对任意,,偏导数Oh2(m) O2,存在。h在 点x的 Jacob矩阵(或导数)为 Ohi(a)ahi(c) 0 O 亦可记为Vh(x),其中Vh(x)=(Vh1(x),Vh2(x),…,Vhn(x) 例 设有复合函数h(x)-f(g(x),其中x∈,g:Pn→lm,f:Pm→P.由复合函数求导的链 式法则,有 h(a)=f (g())g(a), (1.22) 其中∈Bxm,y∈Rmn,h∈R×,记Vf=(Vf,Vf2,…,Vf) 9m), 由b′=V12,f=V Vg1,可将(1.2.2)改写为 Vh(a)-vg(a)vf(g(a) (1.2.3) 式中Vh∈Px,第列Vh;(x)为h;(x)的梯度 f() 1n u 例.求h(a)=f((x)的导数,其中f() f2(u) 考虑m个方程的n元方程组 ha(x)=0,i=1. (1.2.4) 能否确定其中m个变量1,…,m为另外n-m个变量rm+1,…,xn的隐函数,即是否存在满足方 程组(12.4)的函数x1=(a =1 定理1.2.1设x(0)∈P"满足下列条件 (1)h2(x0)-0(-1 n (2)在x0的某个邻域内h;∈C1(i=1 1.2数学基础 6 (3)方程组关于1,…,m的 Jacobi矩阵行列式 ahi(r()ah1(z(0)) ah1(a: (D) 0h2( 0 (0) D ≠0 ahm(a())ahm((o (0) O axm 则存在0)=(x20+1,…,m)∈Bm=m的一个域,使得对邻域中的点=(xm+1,…,xn)存在画 数()(i=1,…,m)满足 (1)a∈C1(=1 (2)x0)=a(i() n (3)h2(1(x),…,qm(),)=0 、向量和矩阵的范数 为研究近似解(向量序列)的收敛性,我们对向量和矩阵引入范数(人小) 定义1.2.5设V为R上的一个线性空间。如果V上的实函数‖·‖满足性质: 1.正定性:对x∈V,‖l20,且|x‖-04x=0; 2.齐次性:对v∈V,a∈R,|la= cxl ll; 3.三角不等式:对x,y∈V,|+l≤‖l+y, 则称V是一个赋范线性空间,称‖c‖为V中x的向量范数。 几种常用的向量范数(x∈fn) 1.向量的∞范数(最大范数):|ll Imax 1<t<n 2.向量的1范数:|p1=∑z, 向量的2范数(FNd数):1l=(∑>P 4.向量的p范数:‖lb x 可以证明当γ趋向∞时,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=、∑aP 2.A的行范数:‖Ax-max∑向a 3.A的列范数:‖4|1=max 4.A的2范数(谱范数):‖A4|2-√入ma2(A47A),其中max(4A)表示A7A的最大特征 值 定义1.2.6(矩阵算子范数)x∈R",A∈Rxn,给定一个向量范数川ll(如=1,2,∞,相应的定 义矩阵范数 ALv= ma IA 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)-洲<e,称序列{x(k}以x为极限.记为limx(6)=.即k充分大时,x(b)和x靠得充 分的近 可以证明这样的极限必定唯一,且任意子序刎也以x为极限 定义1,2.8若存在序列{x(k}的一个子序列{x(},使得imx()=x,称x为序列{x(k)}的聚点 0→∞ 1.3凸集和凸函数 8 定理12.3若序列{x()}有界即存在M>0,使得对于任意的k有|)川<M,则该序列必定有 聚 定义1.2.9设{x(b)}为R的序列,若对于任意的>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<e}CS,称S为开集.有界的闭集称为 紧集 注:不包含边界的球是开集,廾集的补集是闭集. 813凸集和凸函数 凸性在最优化理论和方法研究中起着重要作用.本节扼要介绍凸集和凸函数的基本概念和基 本结果. 凸集 定义13.1设集合S<R",如果对任意x1,x2∈S,有 ax1+(1-a)2∈S,va∈0,1], (13.1) 则称S是凸集. 定义表明,如果x1,x2∈S,则迕接x1和x2的线段属于S 图例 (1.3.)的x=a1+(1-a)2称为r1和2的凸组合 例1.3.1超平面H={xp=a}是凸集,其中p∈F"是非零向量,称为超平面的法向量,c为实 数 事实卜,对仟意x1,x2∈H和每一个∈,1],有 pex1+(1-0)x2 故em+(|-)x2∈H 例1.3.2半空间H={x|p2≤从和H+={x|p2x≥}为凸集 【实例截图】
【核心代码】