泛函)及约束有明显的解析表达式的情况。求解方法是先求出最优 的必要条件,得到一组方程或不等式,再来求解这组方程或不等 式。一般是用求导数的方法或变分方法求出必要条件,通过必要条 件将问题简化,因此称为间接法。 2.直接法一—当目标函数较复杂或不能用变量显函数表示 时,无法用解析法求必要条件。我们要用直接搜素的方法经过若干 次迭代搜索到最优点。这种方法常常是根据经验或试验得到的。对 于一维搜素问题(单变量极值问题)主要是应用区间消去法或多项 式插值法。对于多维搜索问题(多变量极值向题)主要应用爬山法。 3.以解析法为基础的数值计算法 这类方法也是一种直接法,但是,是以梯度法为基础,因此是 种解析与数值计算相结合的方法。 网络最优化方法 这种方法是以图作为数学模型,称为图模型。然后用图论方法 进行搜索最优路径。 所有这些最优化方法实际上都离不开计算机。因此最优化方法 既是一种数学方法,又是一种计算机算法。 下表列出最优化问题求解的各种方法。实际上,一个最优化问 题常常是几种方法的结合,例如要用到一维搜索、无条件极值方法 无约束的梯度法)以及罚函数法等。而且,所求得的最优解,从 全局来看不一定是最优,而从邻近的小范围看,却是最优,称为局 部最优解。 最优化方法分类。 古典微分注 无约束 1.解析法(间接法 古典变分 有约束一极大值原理、库恩-图克定理
斐波那西法 区间消去法 (一维搜索)黄金分割法(0.618法) 插值法 2.数值计算法 坐标轮换法 直接法) 爬山法;步长加速法 (多维搜索)方向加速法 单纯形法及随机搜索法 最速下降法 无约束拟牛顿法 梯度法共轭梯度法 3.以梯度法为 变尺度法 基础的数值 计算方法 有约束∫可行方向法 梯度法 梯度投影法 SUMT法 化有约束问题 SWIFT法 为无约束问题 复形法 4.冈络最优化方法 习 题 1.列出下述最优化问题的数学模型: 用金属薄片欲成圆筒,设金属片面积一定,求圆筒的尺 寸,使圆筒体积为最大。 b.有三个电阻R1、R2、R8并联再和电阻R4串联组成
个电路。设电阻R1上电流为l;,i=I,2,3,4。已知Vmn≤ R;f;≤ Vi max。V;为R;上的压降。求R,使电路中消耗的总功 率为最小 c.n维空间内移动的物体,设位移向量为S=(s;,s2, sn),一单位作用力向量X=[x1,x2,…xn]求力的分量x; 使作用于物体的功为最大。i=1,2,…,n 2.作图画出下迟约束下的可行解城 设 a.x12+(x2-1)2-1≤0,(x1-1)2+x2-1≤0。 C.x:2+x2-1≤0,x1+x2、d+2-1≤0 b,x12+(x2-1)2-1≤0,x12+ ≤0。 3.求无盖矩形水箱的长、高和宽,使水箱容积为最大,而表 面积为A(A=侧面积+底面积)。试列出该问题的数学模型。 4.一个交流电路,负载阻抗为R2+j2,电源电压相量为 E/o°,电源内阻抗为R1+jY1,设R1,R2,X1,E均为给定, 求最优的R2使负载有功功率P为最大。试列出该问题的数学模 型 5.已知某试验结果为 x12345 q(x)|35421 现用一个二次多项式p(x)=ax2+bx+c去逼近g(x),求a、b 及c使x=2,3,4,5各点误差平方和为最小,已知x=1时 p(1)=g(1)。 试列出该问题的数学模型。 ·24·
第二章经典最优化方法 经典最优化方法包括无约束极值问题和等式约束下的条件极值 问题的各种求解方法。 设目标函数为f(X)=f(x1,x2…,x)无约束极值问题是没 有任何约束的情况下求f(X)的最优值。最优点X=x*,X为 n维列向量: X=[x1,x2,…,x],V为转置符号。 即X∈E,E为n维实欧几里得空间。 ∫x*)表示函数f(X)的最优值,即极大值或极小值,极大 值问题可以转化成极小值问题,因此,除特别注明的以外,本书中 关于最优值就指极小值而言 由极值理论我们J知道:为了求得f(X)的极值,变量X必须 满足某些必要条件,如果不满足这些条件,就不是最优解。因此最 优化的必要条件是在否定意义下使用的。为了验证X是否最优, 以及判明这时∫(K)是极大还是极小,应进一步确定充分条件数 学上经典的极值理论一即求可徽函数极值的必要和充分条件,已 有几百年的历史了。 如果最优化问题中规定了某些等式或不等式约束条件,则求函 数极值问题是有约束的最优化问题。经典的极值理论包括等式约束 的最优化问题。不等式约束可以化成等式约束。 例如:ax≤b,加松弛变量U,得ax+υ=b,变成等式约束, U也是待定的一个变量。 最优控制(或动态最优化)问题是求目标泛函的条件极值问 题,但是这类问题的求解方法也是以经典极值理论为基础的
最近30年对不等式约束最优化问题的研究得到了一些重要的 结果,可认为是极值问题的现代理论,经典理论可以看作是最优化 问题现代理论的特殊情况,经典理论比较简单,明确,因此我们先 介绍经典理论的结果。 §2-1无约束极值 我们先研究没有约束条件时,函数在定义城内存在极值的必要 和充分条件。对于最简单的情况即一元函数的极值条件只作简要的 复习,以便过渡到多元函数的极值注]。 图2-1表示定义在区间[a,b]的一元函数f(x),x*是 该区间内f(x)的极小点,则∫(x*)可以看作是f(x)在区间 [a,b内的全局最优值(极小值),因为图2-1所示的单变量函 数是一个单峰函数。 fx f(x> 在区间[a,b]内的单变量函数 单变量多峰函数 图2-1 图2-2 般情况下,f(x)可能是多峰函数,如图2-2所示,在定 义域[a,b]区间内,有三个极小点1,4,6,其中点6是全局极 注]一元函数即单变量函数,记作f(x)。多元函数即多变量函数,记 作、f(X)或∫(,郡2,…,)