《优化问题的计算机求解》由会员分享，可在线阅读，更多相关《优化问题的计算机求解（18页珍藏版）》请在金锄头文库上搜索。
1、第七章最优化问题的计算机求解7.1 无约束最优化问题求解无约束最优化问题是最简单的一类最优化问题，其一般数学描述为min f (x)（ 7-1-1 ）x其中， x x1 , x2 , , xn T 称为优化变量，f ( ) 函数称为目标函数， 该数学表示的含义亦即求取一组x 向量，使得最优化目标函数f (x) 为最小，故这样的问题又称为最小化问题。其实，最小化是最优化问题的通用描述，它不失普遍性。如果要想解最大化问题，那么只需给目标函数 f ( x) 乘一个负号就能立即将最大化问题转换成最小化问题。所以本书中描述的全部问题都是最小化问题。7.1.1 解析解法和图解法无约束最优化问题的最优点x*
2、f ( x)对 x0处，目标函数各个分量的一阶导数为，从而可以列出下面的方程：f0,f0,f0（ 7-1-2 ）x1 x x*xn x x*x2 x x*求解这些方程构成的联立方程可以得出极值点。其实，解出的一阶导数均为0 的极值点不一定都是极小值的点，其中有的还可能是极大值点。极小值问题还应该有正的二阶导数。对于单变量的最优化问题可以考虑采用解析解的方法进行来解。然而多变量最优化问题因为需要将其转换成求解多元非线性方程，其难度也不低于直接采取最优化问题，所以没有必要采用解析解方法求解。一元函数最优化问题的图解法也是很直观的，应绘制出该函数的曲线， 在曲线上就能看出其最优值点。二元函数的最优化
3、也可以通过图解法求出。但三元或多元函数，由于用图形没有办法表示，所以不适合用图解法来解。【例 7-1】函数f()e3t sin( 42)4 0 .5t cos(2t)0.5 ，试用解析求解和图形求解的tte方法研究该函数的最优性。【求解】可以先表示该函数，并解析地求解该函数的一阶导教，用ezplot() 函数可以给制出t 0,4 区间内一阶导函数的曲线，如图7-1a 所示。 syms t; y=exp(-3*t)*sin(4*t+2)+4*exp(-0.5*t)*cos(2*t)-0.5;y1=diff(y,t);%求取一阶导数ezplot(y1,0,4)绘制出选定区间内一阶导函数的曲线其实求
4、解导数等于 0 的方程不比直接求解其最优值简单。用图解法可以看出， 在这个区域内有两点： A1 , A2 ，使得它们的一阶导数为0，但从其一阶导数走向看，A2 点对应负的二阶导数值， 所以该点对应于极大值点，而A1 点对应于正的二阶导数值，故为极小值点。A1 点的值可以由下面的语句直接解出。 t0=solve(y1),ezplot(y,0,4)% 求出一阶导数等于零的点t0 =1.4528424981725411893375778048840y2=diff(y1); b=subs(y2,t,t0)% 并验证二阶导数为正b =7.8553420253333601379464405534590这样
5、，就可以求出函数的最小值。还可以用图形绘制的方法进一步验证得出的结果如图7-1b 所示，可见，A1 为最小值点，A2 为最大值点。然而因为给定的函数是非线性函数 所以用解析法或类似的方法求解最小值问题一点都不比直接求解最优化问题简单。因此除演示之外，不建议用这样的方法求解该问题，而直接采用最优化问题求解程序得出问题的解。精选文库-.-8 exp(-1/2 t) sin(2 t)exp(-3 t) sin(4 t+2)+4 exp(-1/2 t) cos(2 t)-1/223A1A 220-21A 1-40A 2-1-6-2-800.511.522.533.5400.511.522.533.54
6、tt(a) 函数 的一 阶 导函 数 曲 线(b) 函数 曲 线图 7-1联立方程图解法示意图7.1.2 基于 MATLAB的数值解法MATLAB 语言中提供了求解无约束最优化的函数fminsearch() ，其最优化工具箱中还提供了函数 fminunc() ，二者的调用格式完全一致，为x=fminunc(Fun, x )最简求解语句0x， f， flag ，out=fminunc(Fun, x0,opt,p1,p2,)一般求解格式opt 为控制参数。该函数主要采用了单纯形算法。下面将通过例子来演示无约束最优化问题的数值解法。【例 7-2】已知二元函数 zf ( x, y)( x22 x)e
7、x 2y2 xy ，试用 MATLAB 提供的求解函数求出其最小值并用图形方法表示其求解过程。【求解】因为函数中给出的自变量是x, y ，而最优化函数需要求取的是自变量向量x 。故在求解前应该先进行变量替换，如令x1x , x2y ，这样就可以用下面的语句由inline() 形式定义出目标函数 f ，然后将求解控制变量中的Display 属性设置为 iter，这样可以显示中间的搜索结果。用下面的语句求解出最优解。 f=inline(x(1)2-2*x(1)*exp(-x(1)2-x(2)2-x(1)*x(2),x); x0=0; 0; ff=optimset; ff.Display=iter;
8、x=fminsearch(f,x0,ff)IterationFunc-countmin f(x)Procedure01013-0.000499937initial simplex24-0.000499937reflect72137-0.641424contract outsideOptimization terminated:the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-004 and F(X) satisfies the convergence criteria using O
9、PTIONS.TolFun of 1.000000e-004x =0.6111-0.3056同样的问题用fminunc （）函数求解，则可以得出如下的结果。x=fminunc(f,0;.0,ff)IterationFunc-countf(x)Step-sizederivative12-2e-0080.001-429-0.5846690.3043530.343316-0.6413970.9503220.00191422-0.6414240.984028-1.45e-008x =0.6110-0.3055fminunc() 函数的效率明显高于fminsearch() 。所以在无比较两种方法，显然可
10、以看出用-2精选文库约束力优化问题求解时，如果安装了最优化工具箱则建议使用fminunc() 函数。练习：求解 min f (x) ex1 4x122x224 x1x2 2x2 1x1) 首先编写该函数的 M 文件： fun1.m2) x=-1,1 %估计初值 fminunc( fun1 ,x)7.2 有约束最优化问题求解有约束最优化问题的一般描述为minf ( x)（ 7-2-1 ）x s.t . G (x )0其中， x x1 , x2 , , xn T ，记号 s.t. 是英文 subject to 的缩写，表示满足后面的关系。该数学表示的含义为求取一组 x 向量，使得在满足约束条件 G ( x) 0 的前提下能够使目标函数 f (x) 最小化。在实际遇到的最优化问题中，有时约束条件可能是很复杂的，它既可以是等式约束，也可以是不等式约束等，既可以是线性的，也可能是非线性的，有时甚至可以不能用纯数学函数来描述。7.2.1 约束条件与可行解区域满足约束条件G( x)0的 x 范围称为可行解区域。下面通过例子演示二元问题的可行解范围与图解结果。【例 7-3 】考虑下面二元最优化问题的求解，试用图解方法对该问题进行研究max(x1 2x2 )x s.t. 922x1x2x1x21【求解】由约束条件可见，若在
