实验八 无约束优化问题 一.实验目的 掌握应用matlab 求解无约束最优化问题的方法 二.实验原理及方法 1：标准形式： 元函数 为其中n R R f X f n R x n →∈:) (min 2．无约束优化问题的基本算法一．最速下降法（共轭梯度法）算法步骤：⑴ 给定初始点 n E X ∈0，允许误差0>ε,令k=0； ⑵ 计算() k X f ?； ⑶ 检验是否满足收敛性的判别准则： () ε≤?k X f ， 若满足，则停止迭代，得点k X X ≈*，否则进行⑷； ⑷ 令() k k X f S -?=，从k X 出发，沿k S 进行一维搜索， 即求k λ使得： ()() k k k k k S X f S X f λλλ+=+≥0 min ； ⑸ 令k k k k S X X λ+=+1，k=k+1返回⑵. 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.．牛顿法算法步骤： (1) 选定初始点n E X ∈0，给定允许误差0>ε，令k=0； (2) 求()k X f ?,()() 1 2-?k X f ,检验：若() ε
无约束最优化问题及其Matlab 求解 一、教学目标 1. 了解悟约束规划的基本算法最速下降法（共轭梯度法）的基本步骤 2. 掌握用Matlab 求解五约束的一元规划问题、多元规划问题、以及Matlab 求解过程中参数的设置。 3. 针对实际问题能列出其无约束规划方程并用Matlab 求解。 二、 教学手段 1. 用Flashmx 2004制作课件，并用数学软件Matlab 作辅助教学。 2. 采用教学手法上采取讲授为主、讲练结合的方法。 3. 上机实践操作。 三、 教学内容 （一）、求解无约束最优化问题的基本思想 标准形式： ★（借助课件说明过程） （二）、无约束优化问题的基本算法 1．最速下降法（共轭梯度法）算法步骤： ⑴ 给定初始点n E X ∈0，允许误差0>ε,令k=0； ⑵ 计算()k X f ?； ⑶ 检验是否满足收敛性的判别准则： ()ε≤?k X f ， 若满足，则停止迭代，得点k X X ≈*，否则进行⑷； ⑷ 令()k k X f S -?=，从k X 出发，沿k S 进行一维搜索， 即求k λ使得： ()() k k k k k S X f S X f λλλ+=+≥0min ； ⑸ 令k k k k S X X λ+=+1，k=k+1返回⑵. 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢。 ★（借助课件说明过程,由于 算法 在实际中用推导过程比较枯燥，用课件显示搜索过程比较直观） 2. 采用Matlab 软件，利用最速下降法求解无约束优化问题 常用格式如下： （1）x= fminbnd (fun,x1,x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）[x ，fval]= fminbnd （...） （4）[x ，fval ，exitflag]= fminbnd （...） （5）[x ，fval ，exitflag ，output]= fminbnd （...） 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd ()X f n E X ∈min 其中 1:E E f n →
目录 1.多维有约束优化错误!未定义书签。 题目错误!未定义书签。 已知条件错误!未定义书签。 建立优化模型错误!未定义书签。 问题分析及设计变量的确定错误!未定义书签。 目标函数的确定错误!未定义书签。 约束条件的建立错误!未定义书签。 优化方法的选择错误!未定义书签。 数学模型的求解错误!未定义书签。 确定数学优化模型错误!未定义书签。 运用Matlab优化工具箱对数学模型求解错误!未定义书签。 1. 最优解以及结果分析错误!未定义书签。 2.多维无约束优化错误!未定义书签。 题目错误!未定义书签。 确定优化设计模型错误!未定义书签。 运用Matlab优化工具箱对数学模型求解错误!未定义书签。 编写目标函数错误!未定义书签。 绘制该函数的平面和空间等值线错误!未定义书签。 利用matlab工具箱fminunc函数对该模型进行求解错误!未定义书签。求解结果错误!未定义书签。
1.多维有约束优化 题目 对一对单级圆柱齿轮减速器，以体积最小为目标进行多维有约束优化设计。 已知条件 已知数输入功p=58kw ，输入转速n1=1000r/min ，齿数比u=5，齿轮的许用应力[δ]H=550Mpa ，许用弯曲应力[δ]F=400Mpa 。 建立优化模型 1.3.1问题分析及设计变量的确定 由已知条件得求在满足零件刚度和强度条件下，使减速器体积最小的各项设计参数。由于齿轮和轴的尺寸（即壳体内的零件）是决定减速器体积的依据，故可按它们的体积之和最小的原则建立目标函数。 单机圆柱齿轮减速器的齿轮和轴的体积可近似的表示为： ] 3228)6.110(05.005.2)10(8.0[25.087)(25.0))((25.0)(25.0)(25.02221222122212222122121222 21222120222222222121z z z z z z z z z z z g g z z d d l d d m u mz b bd m u mz b b d b u z m b d b z m d d d d l c d d D c b d d b d d b v +++---+---+-=++++- ----+-=πππππππ 式中符号意义由结构图给出，其计算公式为 b c d m umz d d d m umz D mz d mz d z z g g 2.0) 6.110(25.0,6.110,21022122211=--==-=== 由上式知，齿数比给定之后，体积取决于b 、z 1 、m 、l 、d z1 和d z2 六个参数，则设计变量可取为 T z z T d d l m z b x x x x x x x ][][21 1 65 4321== 1.3.2目标函数的确定 根据以上分析，可知，该齿轮减速器以体积最小的目标函数为： min )32286.18.092.0858575.4(785398.0)(26252624252463163212 51261231232123221→++++-+-+-+=x x x x x x x x x x x x x x x x x x x x x x x x x x f 1.3.3 约束条件的建立 (1)为避免发生根切，应有min z z ≥17=，得 017)(21≤-=x x g (2)齿宽应满足 max min ??≤≤ d b ，min ?和max ?为齿宽系数d ?的最大值和最小值，一般取min ?=，
无约束优化方法---鲍威尔方法 本实验用鲍威尔方法求函数f(x)=(x1-5)2+(x2-6)2 的最优解。 一、简述鲍威尔法的基本原理 从任选的初始点x⑴o出发，先按坐标轮换法的搜索方向依次沿e1.e2.e3进行一维搜索，得各自方向的一维极小点x⑴ x⑵ x⑶.连接初始点xo⑴和最末一个一维极小点x3⑴,产生一个新的矢量 S1=x3⑴-xo⑴ 再沿此方向作一维搜索，得该方向上的一维极小点x⑴. 从xo⑴出发知道获得x⑴点的搜索过程称为一环。S1是该环中产生的一个新方向，称为新生方向。 接着，以第一环迭代的终点x⑴作为第二环迭代的起点xo⑵,即 Xo⑵←x⑴ 弃去第一环方向组中的第一个方向e1，将第一环新生方向S1补在最后，构成第二环的基本搜索方向组e2,e3,S1，依次沿这些方向求得一维极小点x1⑵,x2⑵,x3⑵.连接 Xo⑵与x3⑵,又得第二环的新生方向 S2=x3⑵-xo⑵ 沿S2作一维搜索所得的极小点x⑵即为第二环的最终迭代点 二、鲍威尔法的程序 #include "stdafx.h" /* 文件包含*/ #include
#include
第五题： 解：选择类型为： 2/13()x t y t x e x =+ 其中123,,x x x 是待求参数。根据最小二乘原理，参数123,,x x x 是下面优化问题的解。 []2 8 1231 m in (,,)()i i i f x x x y t y == -? 用最速下降法求解这一无约束的最优化问题。 zuiyouhua.m function sh=zuiyouhua(x0) % x0为初始猜测值 syms x y z a al; %====================================== t=[0.2,1,2,3,5,7,11,16]; r1=[5.05,8.88,11.63,12.93,14.15,14.73,15.30,15.60]; minf=0; for i=1:8 r(i)=x*exp(y/t(i))+z-r1(i); %构造最小二乘最优化的目标函数 minf=r(i)^2+minf; end %====================================== f1=diff(minf,x); f2=diff(minf,y); f3=diff(minf,z); %求目标函数的梯度 F=[f1,f2,f3]; %====================================== Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); k=0; %====================================== %最速下降法核心迭代程序 while 1 x1=x0+a*Fx; P=subs(minf,{x,y,z},x1); xx1=xianxing(P); %调用线性搜索函数 al=huangjing(P,xx1); %调用黄金分割法函数； x0=x0+al*Fx; Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); if norm(Fx1)<5e-4 sh=x0; return; end end %====================================== function xx=xianxing(Pa) %一维搜索法线性搜索函数 aa=findsym(Pa); a1=1; h=0.5; k=0; t1=2; while 1 a2=a1+h; Pa1=subs(Pa,aa,a1); Pa2=subs(Pa,aa,a2); if Pa2< Pa1 h=t1*h; a0=a1; a1=a2; k=k+1; if k>1000 disp('迭代步数太多，可能不收敛！'); end else if k==0 h=-h; a0=a2; else c1=min(a0,a2); d1=max(a0,a2); xx=[c1,d1]; return; end end end %====================================== function al1=huangjing(Pb,xx2)
项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、Newton 法（修正Newton 法）的程序。 [实验学时] 2学时 [实验准备] 1．掌握最速下降法的思想及迭代步骤。 2．掌握Newton 法的思想及迭代步骤； 3．掌握修正Newton 法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题：【选作一个】 1．用最速下降法求 22120min ()25[22]0.01T f X x x X ε=+==，，，． 2．用Newton 法求 22121212min ()60104f X x x x x x x =--++-， 初始点 0[00]0.01T X ε==，，． 最速下降法 Matlab 程序： clc;clear; syms x1 x2; X=[x1,x2]; fx=X(1)^2+X(2)^2-4*X(1)-6*X(2)+17; fxd1=[diff(fx,x1) diff(fx,x2)]; x=[2 3]; g=0; e=0.0005; a=1; fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); step=0; while g>e step=step+1; dk=-fan; %点x(k)处的搜索步长
ak=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2); xu=x+ak*dk; x=xu; %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf(' x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); %计算目标函数点x(k+1)处一阶导数值 fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); end %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf('\n最速下降法\n结果：\n x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); c++程序 #include
分数: ___________任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间：
一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，
分数: ___________ 任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间：
一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，而且寻优的效率特别低下。
最速下降法求解无约束最优化问题 1 理论基础 已知问题模型为 ()min n x R f x ∈ 算法： 1) 选取初始点0x 与()00f f x =，初始化0k = 2) 验证迭代中止条件：k x eps ?<且()k f x eps ?<或lim k > 若是k x eps ?<且()k f x eps ?<，则输出解k x 及迭代次数k 若是lim k >，则输出error 信息 注：其中1010,lim 1000eps -== 3) 计算k x 点搜索方向：()k k d f x =-? 计算k x 点迭代步长：(){}0 arg min k k k f x d ααα≥=+ 更新点列：1k k k k x x d α+=+，1k k =+ 转第2步 2 MATLAB 程序 2.1 函数说明 文件名称：Opt_Steepest.m function [xo, fo] = Opt_Steepest(f, grad, x0, TolX, TolFun, dist0, MaxIter)
% 用最速下降法求最优化解 % 输入： % f——函数名 % grad——梯度函数 % x0——解的初值 % TolX——变量的误差阈值 % TolFun——函数的误差阈值 % dist0——初始步长 % MaxIter——最大迭代次数 % 输出: % xo——最小值的点 % fo——最小的函数值 %% 判断输入的变量数，设定一些变量为默认值if nargin < 7 MaxIter = 1000; %最大迭代次数默认为100 end if nargin < 6 dist0 = 10; %初始步长默认为10 end if nargin < 5 TolFun = 1e-10; %函数值误差为1e-8
第三章无约束最优化方法 本章内容及教学安排 第一节概述 第二节迭代终止原则 第三节常用的一维搜索方法 第四节梯度法 第五节牛顿法 第六节共轭方向法 第七节变尺度法 第八节坐标轮换法 第九节鲍威尔方法 第一节概述 优化问题可分为 无约束优化问题 有约束优化问题 无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想：
所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长
3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）1K K X X ε+-≤ 111/2 21K K K K n i i i X X X X ε++=??-=-≤???? ∑（） 2） 11()()()() () K K K K K f X f X f X f X or f X ε ε ++-≤-≤ 3）(1)()K f X ε+?≤ 第三节 常用的一维搜索方法 本节主要解决的是如何确定最优步长的问题。 从初始点(0)X 出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下： (1)(0)00(2)(1)11(1)() K K k k X X S X X S X X S ααα+=+=+= + 现在假设K S 已经确定，需要确定的是步长k α，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即 (1)()min ()min ()min ()K K K k k f X f X S f αα+=+= 由此可见，最佳步长*K α由一维搜索方法来确定 求*k α，使得()()()()()()min K K K K f f X S αα=+→ 一、一维搜索区间的确定 区间[,]a b 应满足 ()(*)()f a f f b α><
第四章 无约束优化方法 ——最速下降法,牛顿型方法 概述 在求解目标函数的极小值的过程中,若对设计变量的取值范围不加限制,则称这种最 优化问题为无约束优化问题。尽管对于机械的优化设计问题,多数就是有约束的,无约束 最优化方法仍然就是最优化设计的基本组成部分。因为约束最优化问题可以通过对约 束条件的处理,转化为无约束最优化问题来求解。 为什么要研究无约束优化问题? (1)有些实际问题,其数学模型本身就就是一个无约束优化问题。 (2)通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 (3)约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法就是优化设计方法的基本组成部分,也就是优化方法的基 础。 根据构成搜索方向所使用的信息性质的不同,无约束优化方法可以分为两类。 一:间接法——要使用导数的无约束优化方法,如梯度法、(阻尼)牛顿法、变尺度法、共 轭梯度法等。 二:直接法——只利用目标函数值的无约束优化问题,如坐标轮换法、鲍威尔法单纯形 法等。 无约束优化问题的一般形式可描述为: 求n 维设计变量 []12T n n X x x x R =∈L 使目标函数 ()min f X ? 目前已研究出很多种无约束优化方法,它们的主要不同点在于构造搜索方向上的差别。 无约束优化问题的求解: 1、解析法
可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方 程 0)(min *=X f 的解。也就就是求Ｘ＊使其满足 解上述方程组,求得驻点后,再根据 极值点所需满足的充分条件来判定就是否为极小值点。但上式就 是一个含有ｎ个未知量,ｎ个方程的方程组,在实际问题中一般就 是非线性的,很难用解析法求解,要用数值计算的方法。由第二章的讲述我们知道,优化问题的一般解法就是数值迭代的方法。因此,与其用数值方法求解非线性方程组,还不如用数值迭 代的方法直接求解无约束极值问题。 2、数值方法 数值迭代法的基本思想就是从一个初始点) 0(X 出发,按照一个可行的搜索方向)0(d ρ搜索,确定最佳的步长0α使函数值沿)0(d ρ方向下降最大,得到)1(X 点。依此一步一步地 重复数值计算,最终达到最优点。优化计算所采用的基本迭代公式为 ),2,1,0()()()1(Λρ=+=+k d X X K K K K α (4、2) 在上式中, ()K d r 就是第就是 k+1 次搜索或迭代方向,称为搜索方向(迭代方向)。 由上面的迭代公式可以瞧出,采用数值法进行迭代求优时,需要确定初始点)(k X 、搜索方向)(k d ρ与迭代步长K α,称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向)(k d ρ上确定最优步长K α的方法,本章我们将讨论如何确定搜索方向)(k d ρ。 最常用的数值方法就是搜索方法,其基本思想如下图所示: 无约束优化方法可以分为两类。一类就是通过计算目标函数的一阶或二阶导数值 确定搜索方向的方法,称为间接法,如最速下降法、牛顿法、变尺度法与共轭梯度法。另 一类就是直接利用目标函数值确定搜索方向的方法,称为直接法,如坐标轮换法、鲍威尔 法与单形替换法。各种无约束优化方法的区别在于确定其搜索方向0d 的方法不同。 0)(0)(0)(*2*1*=??=??=??n x X f x X f x X f M
无约束最优化直接方法和间接方法的异同
无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称
无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最
第四章 无约束优化方法 ——最速下降法，牛顿型方法 概述 在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这 种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的， 无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过 对约束条件的处理，转化为无约束最优化问题来求解。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。 一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度 法、共轭梯度法等。 二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯 形法等。 无约束优化问题的一般形式可描述为： 求n 维设计变量 []12T n n X x x x R =∈L 使目标函数 ()min f X ? 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 无约束优化问题的求解： 1、解析法 可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方 程 0)(min *=X f
的解。也就是求Ｘ＊使其满足 解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值 点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性 的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题 的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用 数值迭代的方法直接求解无约束极值问题。 2、数值方法 数值迭代法的基本思想是从一个初始点) 0(X 出发，按照一个可行的搜索方向)0(d ρ搜索，确定最佳的步长0α使函数值沿)0(d ρ方向下降最大，得到)1(X 点。依此一步一步地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为 ),2,1,0()()()1(Λρ=+=+k d X X K K K K α （4.2） 在上式中， ()K d r 是第是 k+1 次搜索或迭代方向，称为搜索方向（迭代方向）。 由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点)(k X 、搜索方向)(k d ρ和迭代步长K α，称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向)(k d ρ上确定最优步长K α的方法，本章我们将讨论如何确定搜索方向)(k d ρ。 最常用的数值方法是搜索方法，其基本思想如下图所示： 0)(0)(0)(*2*1*=??=??=??n x X f x X f x X f M
无约束优化选址问题 超市选址问题 问题的提出：怎么选择超市的地址，使得居民区离超市所在位置距离最近。 居民区位置用二维坐标表示，（X,Y）i=1,2,..n 。 此问题的优化模型为： min D = 实例分析 某投资商想在城市居民区新建一个超市，已知其五个居民区的位置坐标如下表： X Y 1 10 3 2 -4 11 3 6 -2 4 2 14 5 -5 1 为使超市离居民区距离之和达到最小，该如何选择超市的位置？
居民区坐标位置图绘制如下： 则此问题的优化模型为 minD=++ ++ 函数用MA TLAB画出曲面图以及等高线图 [X,Y]=meshgrid(-10:0.1:10); Z=sqrt((X-10).^2+(Y-3).^2)+sqrt((X+4).^2+(Y-11).^2)+sqrt((X-6).^2+(Y+ 2).^2)+... sqrt((X-2).^2+(Y-14).^2)+sqrt((X+5).^2+(Y-1).^2); surf(X,Y,Z) shading interp xlabel('X'); ylabel('Y'); zlabel('Z'); title('surf of surface')
[X,Y]=meshgrid(-10:0.1:10); Z=sqrt((X-10).^2+(Y-3).^2)+sqrt((X+4).^2+(Y-11).^2)+sqrt((X-6).^2+(Y+ 2).^2)+... sqrt((X-2).^2+(Y-14).^2)+sqrt((X+5).^2+(Y-1).^2); contour(X,Y,Z,100) shading interp xlabel('X'); ylabel('Y'); title('contour of surface')