第三周读书笔记
1. 牛顿法
Pure Newton's Method
在上一章中具体讨论了梯度方法，该类方法只应用了一阶最优条件的信息，即梯度。此外，在讨论标度梯度法时还简单地讨论到Newton方法，该类方法进一步地应用到二阶最优条件地信息，即Hessian矩阵。该章重点介绍牛顿法，与梯度方法利用梯度进行新点迭代的方法不同，牛顿法的点更新方法如下：若假设函数在处的Hessian矩阵是正定矩阵，即。那上面的最小化问题有唯一的稳定点，也是全局最小点：
其中，向量也被称作牛顿方向，利用以上更新公式进行迭代的方法也被称作纯粹牛顿方法。算法流程图如下：
牛顿法要求在每次更新处的Hessian矩阵为正定矩阵。或者我们可以放宽一点条件——即在定义域内的任意点处的Hessian矩阵均为正定，这说明了存在一个唯一的最优解。但是，这并不能保证算法的收敛性。
事实上，牛顿法在某些假设下具备很好的收敛性能（称局部二次收敛）——令在上二阶连续可导，假设：
存在，对任意有
存在，对任意，有
令是牛顿方法得到的序列，是在上唯一最小值。那么对任意，以下不等式成立：
此外，如果，那么
证明如下：
事实上，对于某些不满足上述条件（正定、李普希兹连续）的优化问题，牛顿方法也能表现出收敛性。但是，总的来说，当缺少这些严格假设时收敛性无法得到保障。为了解决即使在Hessian矩阵正定也无法保障牛顿法的收敛性问题下，进一步地提出一种步长解决方案，即阻尼牛顿法。
阻尼牛顿法
在纯粹牛顿法的基础上，我们在进行迭代更新时，重新加入步长选择机制，如利用回溯法进行步长选择的阻尼牛顿法，算法流程如下：
cholesky分解
这一小节是针对前部分的补充知识——在利用牛顿法解决相关优化问题的时候，我们会遇到判断Hessian矩阵是否正定，以及求解线性系统的问题，这两个问题都可以通过cholesky分解来解决。
给定一个的正定矩阵，cholesky分解的形式为，其中是一个的下三角矩阵且其对角元素为正数。一般利用cholesky分解去解决线性系统分为以下两步：
1. 找到的解
2. 找到的解
可以通过一个简单的递推公式计算cholesky因子。如下：
在求解L的过程中，需要保证L的对角线元素为正数。
此前我们讨论的牛顿方法都是建立在Hessian矩阵正定的基础上，因此，可以改进牛顿方法——将其与梯度方法结合，判断Hessian矩阵是不是正定的。若是正定则利用牛顿法迭代，若不是正定则利用梯度方法。
2.凸集
凸分析和凸优化的基础需要我们对基础的凸集理论知识有一定的认识，本章即介绍相关的知识点。
定义和例子
首先，定义凸集——如果集合C中任意两点之间的线段仍在C中，即对于任意和满足，有。通俗的讲，即集合中的每一点都可以被其他点沿着它们之间的一条无阻碍的路径达到（所谓无阻碍，即整条路径都在集合中）。
例：（直线为凸集）
事实上，如果从直观的角度来看的话，直线中任意两点连成的线段一定在该直线上，因此，直线一定是一个凸集。当然，也可以从定义的角度进行证明，首先，定义在上的直线可以用集合
来表示，接着证明其凸性。
任取两点，则两点依次对应使得。对任意，有
。
得证。
同样的，常见的凸集还有闭线段、开线段、空集、全空间、超平面以及半空间。
以下再给出两个典型的凸集
例：（范数球为凸集）
令且，为定义在上的范数。则open ball为
closed ball为
以上均为凸集。（利用凸集的定义、范数的齐次性以及三角不等式可证）例：（椭球为凸集）
首先，椭球的定义——椭球是具备以下形式的集合，
其中，为一个半正定矩阵，。
以下证明其为凸集。
凸集的代数运算
首先介绍交集这种保凸运算。
引理：令有限个集合均为凸集，那么他们的交集也是凸集。
由该引理可以得到一个主要的凸集——多面体。
上一节中，我们提到一个重要的凸集——半空间，有限个半空间的交集即为多面体，可用如下公式表示。
所以多面体是一个凸集。
当然，凸集不仅对交运算封闭，对加法、笛卡尔积、线性映射和逆线性映射也是封闭的。
凸包
首先，引入凸组合的概念——对于k个向量，凸组合可以表示为
，其中且和为1。
因此，之前提到凸集的定义可以重新定义为包含集合中任意两点凸组合的集合即为凸集。该定义可以进一步引申为集合中任意数量的点。定理如下：
令为一个凸集，其中有个点。那么，对于任意和为1的，有
。（可用数学归纳法证明）
凸包的定义：集合S的凸包即为S中所有点的凸组合的集合，记为。（其中，所有点的概念是指任意正数数量的点）。凸包是包含集合S的最小凸集。
接下来是é。可以解释为，某给定集合的子集的凸包中的任意元素可以用中不超过个矩阵的凸组合表示出来。
定理：令，并令。那么存在，有
，即。
凸锥
集合，当它满足以下性质：对于任意，。
引理：当且仅当以下性质满足时，S是凸锥。
A:
B:
常见的凸锥有诸如非负象限、冰淇淋锥、非负多项式。
与凸集有凸组合一样，凸锥也有锥组合。以下给出定义：
给定空间中的个点，这个点的锥组合可以表示为，其中为非负数。
进一步地，可以给出锥包的概念。令，则由中所有点的锥组合的集合，通常记作。有以下表达式：
锥包是包含的最小凸锥。
接下来是conic representation theorem。令且，那么存在个线性无关的向量，有，即存在，使得。
基础可行解：令，其中。假设的各行线性无关，其可行解中的正元素对应的A中的列线性无关。
可行解的相关定理：令，其中。如果P有解，那么至少包含一个基础可行解。
凸集的拓扑性质
1. 闭合条件下的保凸性：若是一个凸集，那么它的闭包也是一个凸集。（闭包是包含C
的最小闭集）
2. （line segment principle）令为一个凸集，假设的内部不为空集，且
。那么对于任意的，。
3. 若为一个凸集，那么它的内部也是一个凸集。
4. 令为一个凸集并且内部非空，那么。
5. 若为一个紧集，那么它的凸包为紧集。
6. 令，那么这些点的锥包是闭集。
无约束优化方法---鲍威尔方法 本实验用鲍威尔方法求函数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
第三周读书笔记 1. 牛顿法 Pure Newton's Method 在上一章中具体讨论了梯度方法，该类方法只应用了一阶最优条件的信息，即梯度。此外，在讨论标度梯度法时还简单地讨论到Newton方法，该类方法进一步地应用到二阶最优条件地信息，即Hessian矩阵。该章重点介绍牛顿法，与梯度方法利用梯度进行新点迭代的方法不同，牛顿法的点更新方法如下：若假设函数在处的Hessian矩阵是正定矩阵，即。那上面的最小化问题有唯一的稳定点，也是全局最小点： 其中，向量也被称作牛顿方向，利用以上更新公式进行迭代的方法也被称作纯粹牛顿方法。算法流程图如下： 牛顿法要求在每次更新处的Hessian矩阵为正定矩阵。或者我们可以放宽一点条件——即在定义域内的任意点处的Hessian矩阵均为正定，这说明了存在一个唯一的最优解。但是，这并不能保证算法的收敛性。 事实上，牛顿法在某些假设下具备很好的收敛性能（称局部二次收敛）——令在上二阶连续可导，假设： 存在，对任意有 存在，对任意，有 令是牛顿方法得到的序列，是在上唯一最小值。那么对任意，以下不等式成立： 此外，如果，那么
证明如下： 事实上，对于某些不满足上述条件（正定、李普希兹连续）的优化问题，牛顿方法也能表现出收敛性。但是，总的来说，当缺少这些严格假设时收敛性无法得到保障。为了解决即使在Hessian矩阵正定也无法保障牛顿法的收敛性问题下，进一步地提出一种步长解决方案，即阻尼牛顿法。 阻尼牛顿法 在纯粹牛顿法的基础上，我们在进行迭代更新时，重新加入步长选择机制，如利用回溯法进行步长选择的阻尼牛顿法，算法流程如下：
cholesky分解 这一小节是针对前部分的补充知识——在利用牛顿法解决相关优化问题的时候，我们会遇到判断Hessian矩阵是否正定，以及求解线性系统的问题，这两个问题都可以通过cholesky分解来解决。 给定一个的正定矩阵，cholesky分解的形式为，其中是一个的下三角矩阵且其对角元素为正数。一般利用cholesky分解去解决线性系统分为以下两步： 1. 找到的解 2. 找到的解 可以通过一个简单的递推公式计算cholesky因子。如下：
行域 φ 内，选择一个初始点 X 然后确定一个可行 得一个目标函数有所改善的可行的新点 X 即完成了 第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： s .t . min f (x ) g u (x ) ≤ 0 h v (x ) = 0 x ∈ R n u = 1, 2,..., m v = 1, 2,..., p < n 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于 这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由 m 个不等式约束条件 gu(x )≤0 所确定的可 0 搜索方向 S ，且以适当的步长沿 S 方向进行搜索，取 1 一次迭代。以新点为起始点重复上述搜索过程，每次 均按如下的基本迭代格式进行计算： X k+1=X k +α k S k (k=0,1,2,..) 逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算 不论何时终止，都可以获得比初始点好的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局 部最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集
φ(X,μ1,μ2)=F(X)+∑μ 1 G??g j X)??+∑μ2H??h k(X)?? a)可行域是凸集；b)可行域是非凸 集 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数 结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优 化问题。 m l j=1k=1 新目标函数 然后对新目标函数进行无约束极小化计算。 加权因子 间接法是结构优化设计中广泛使用的有效方法，其特点： 1）由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和数值计算的稳定性大有提高； 2）可以有效处理具有等式约束的约束优化问题； 3）目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精度，甚至导致计算失败。
项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、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
第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由m 个不等式约束条件g u (x )≤0所确定的可行域φ内，选择一个初始点0 X 然后确定一个可行搜索方向S ，且以适当的步长沿S 方向进行搜索，取得一个目标函数有所改善的可行的新点1 X 即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算： k+1k k k =+S (k=0,1,2,..)X X α逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好 的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部 最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集 1,2,...,1,2,...,u m v p n == 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。 然后对新目标函数进行无约束极小化计算。 间接法是结构优化设计中广泛使用的有效方法，其特点： 1） 由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和 数值计算的稳定性大有提高； 2） 可以有效处理具有等式约束的约束优化问题； 3） 目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精 度，甚至导致计算失败。 a) 可行域是凸集；b)可行域是非凸集 () ()()()121211 ,,m l j k j k X F X G g X H h X φμμμμ==??=++? ?????∑∑ 新目标函数 加权因子 分数: ___________任课教师签字：___________ 课程作业 学年学期：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 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差， 多维无约束优化算法 多维无约束优化问题的一般数学表达式为： 求n 维设计变量 使目标函数 多维无约束优化算法就是求解这类问题的方法，它是优化技术中最重要最基础的内容之一。因为它不仅可以直接用来求解无约束优化问题，而且实际工程设计问题中的大量约束优化问题，有时也是通过对约束条件的适当处理，转化为无约束优化问题来求解的。所以，无约束优化方法在工程优化设计中有着十分重要的作用。 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 各种优化方法之间的主要差异是在于构造的搜索方向，因此，搜索方向的构成问题乃是无约束优化方法的关键。 下面介绍几种经典的无约束优化方法。 1、梯度法 基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。 搜索方向s 取该点的负梯度方向 (最速下降方向) ，使函数值在该点附近的范围内下降最快 。 为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有 12[]T n x x x = x ()min f →x ()k f -?x k αmin ()n f R ∈x x 1(0,1,2,)k k k k s k α+=+= x x 1(0,1,2,) k k k k s k α+=+= x x 1()(0,1,2,) k k k k a f k +=-?= x x x 1()[()]min [()]min ()k k k k k k k a a f f a f f a f ?α+=-?=-?=x x x x x 单纯形法 1. 算法原理 单纯形法的基本思想是： 设(0)(1)(),,...,n x x x 是n R 中的1n +个点，构成一个当前的单纯形，max min ,x x 定义如下： {}(0)(1)()max ()max (),(),...,()n f x f x f x f x = {}(0)(1)()min ()min (),(),...,()n f x f x f x f x = 记x 为这个单纯形除去max x 外的所有顶点的形心， ()max 01n i i x x x n =??=- ??? ∑ 取max x 关于x 的反射点(1)n x +，(1)max ()n x x x x +=+-构成新的单纯形，反复上述过程，直到达到停止条件。 2. 函数min f search 1） 函数语法 min (,0)x f search fun x = min (,0,) [,]min (...) [,,]min (...) [,,,]min (...) x f search fun x options x fval f search x fval exitflag f search x fval exitflag output f search ==== 函数输入： fun ：目标函数 0x ：迭代初始点 options ：函数参数设置 函数输出： x ：最优点 fval ：最优点对应的函数值 exitflag ：函数停止信息 1：函数收敛正常停止 0：迭代次数，目标函数计算次数达到最大数 -1：算法被输出函数停止 output ：函数运算信息 2）函数使用 BanaFun m （1）目标函数程序. function f BanaFun x =不含导数解析式 ()() f x x x =-+- 100*((2)(1)^2)^2(1(1))^2 -函数不需要导数信息。 Nelder Mead Simplex SimplexUnc m （2）算法参数设置：. ('arg','','','','',250,'','') = options optimset L eScale off gradobj off MaxFunEvals display iter SimplexUnc m （3）函数调用运算：. = ('arg','','','','',250,'','') options optimset L eScale off gradobj on MaxFunEvals display iter x=- [ 1.9,2] x fval exitflag output f search BanaFun x options = [,,,]min(@,,) 3）计算结果 Iteration Func-count min f(x) Procedure 0 1 267.62 1 3 236.4 2 initial simplex 2 5 67.2672 expand 3 7 12.2776 expand 4 8 12.2776 reflect 5 10 12.277 6 contract inside 6 12 6.76772 contract inside 7 13 6.76772 reflect 8 15 6.76772 contract inside 9 17 6.76772 contract outside 10 19 6.62983 contract inside 11 21 6.55249 contract inside 12 23 6.46084 contract inside 13 24 6.46084 reflect 14 26 6.46084 contract inside 15 28 6.45544 contract outside 16 30 6.42801 expand 17 32 6.40994 expand 18 34 6.32449 expand 19 36 6.28548 expand 20 38 6.00458 expand 21 39 6.00458 reflect 22 41 5.43287 expand 第三章无约束最优化方法 本章内容及教学安排 第一节概述 第二节迭代终止原则 第三节常用的一维搜索方法 第四节梯度法 第五节牛顿法 第六节共轭方向法 第七节变尺度法 第八节坐标轮换法 第九节鲍威尔方法 第一节概述 优化问题可分为 无约束优化问题 有约束优化问题 无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想： 所以迭代法要解决三个问题 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 的解。也就是 求Ｘ＊ 使其满足 解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，0)(0)(0)(*2*1*=??=??=??n x X f x X f x X f M 例4-1 MA TLAB实现，用M函数文件形式求解： syms s t; f=s^2+3*t^2-2*t*s+4*t+3*s; [x,minf]=minZBLH(f,[-2 6],[0.2 0.2],1.5,[t s],0.0001,0.0001) 坐标轮换minZBLH函数文件如下： function [x,minf] = minconPS2(f,x0,delta,u,var,eps1,eps2) %目标函数：f; %初始点：x0; %收缩系数：u; %自变量向量：var; %步长精度：eps1; %自变量精度：eps2； if nargin == 7 eps2 = 1.0e-6; end n = length(var); y = x0; bmainCon = 1; while bmainCon yf = subs(f,var,y); yk_1 = y; for i=1:n tmpy = zeros(size(y)); tmpy(i) = delta(i); tmpf = subs(f, var,y+tmpy); if tmpf < yf bcon = 1; while bcon tmpy(i) = 2*tmpy(i); tmpf_i = subs(f, var,y+tmpy); if tmpf_i 第四章 无约束优化方法 ——最速下降法，牛顿型方法 概述 在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这 种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的， 无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过 对约束条件的处理，转化为无约束最优化问题来求解。 为什么要研究无约束优化问题? （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 无约束最优化直接方法和间接方法的异同 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最 目录 1.多维有约束优化............................................. 错误!未定义书签。 题目.................................................... 错误!未定义书签。 已知条件................................................ 错误!未定义书签。 建立优化模型............................................ 错误!未定义书签。 问题分析及设计变量的确定............................. 错误!未定义书签。 目标函数的确定....................................... 错误!未定义书签。 约束条件的建立...................................... 错误!未定义书签。 优化方法的选择.......................................... 错误!未定义书签。 数学模型的求解.......................................... 错误!未定义书签。 确定数学优化模型.................................... 错误!未定义书签。 运用Matlab优化工具箱对数学模型求解.................. 错误!未定义书签。 1. 最优解以及结果分析................................ 错误!未定义书签。 2.多维无约束优化............................................. 错误!未定义书签。 题目.................................................... 错误!未定义书签。 确定优化设计模型........................................ 错误!未定义书签。 运用Matlab优化工具箱对数学模型求解...................... 错误!未定义书签。 编写目标函数........................................ 错误!未定义书签。 绘制该函数的平面和空间等值线........................ 错误!未定义书签。 利用matlab工具箱fminunc函数对该模型进行求解........ 错误!未定义书签。 求解结果............................................. 错误!未定义书签。 1、一维搜索 function f=myfun_yi(x) f=(x-2)^2-1 》》fminbnd(@myfun_yi,1,12) 2、无约束搜索 function f=myfun_wuyueshu(x) f=3*x(1)^2+2*x(1)*x(2)+x(2)^2 >> x0=[1,1] >> [x,fval]=fminunc(@myfun_wuyueshu,x0) 3、约束搜索 min f(x) x 设计变量 b Ax ≤ 线性不等式约束 eq b x A =eq 线性等式约束 ()0≤x C 非线性约束 0=eq C 非线性等式约束 b b u x l ≤≤ 上下限边界约束 例题: ()222 13)(min x x x f +-= ()042211≤-+=x x x g ()012≤-=x x g ()023≤-=x x g 目标函数： function f=myfun_constrain(x) f=(x(1)-3)^2+x(2)^2; 非线性约束函数定义 function [c,ceq]=mycon(x) c=x(1)^2+x(2)-4; ceq=[]; 初始条件及函数调用： %3初始条件 A=[-1,0;0,-1]； b=[0;0]； aeq=[]; beq=[]; lb=[]; ub=[]; x0=[9;9] %函数定义 [x,fval]=fmincon(@myfun_constrain,x0,A,b,aeq,beq, lb,ub,@mycon)%如果x0,A,b,aeq,beq,lb,ub,@mycon中没有某项，用[]代替单纯形法解决无约束优化问题
多维无约束优化算法
无约束优化算法：单纯形法
第三章 无约束最优化方法
无约束优化方法
无约束优化方法与MATLAB实现
无约束优化方法(最速下降法_牛顿法)
无约束最优化直接方法和间接方
无约束最优化直接方法和间接方法的异同
优化设计 有约束优化 无约束优化
约束优化、一维搜索、无约束优化MATLAB程序语句用法
相关主题
文本预览