第38卷 第3期吉林大学学报(工学版)
Vol.38 No.32008年5月
Journal o f Jilin U niv ersity (Engineering and T echnolo gy Edition)
M ay 2008
收稿日期:2007-02-18.
基金项目:国家自然科学基金项目(60573182);高等学校博士学科点专项科研基金项目(20060183042);吉林省科技
发展计划项目(20060527,20040531).
作者简介:赵伟(1967-),男,博士研究生.研究方向:数据库系统,虚拟现实技术等.E -mail:pr ince1205@https://www.doczj.com/doc/9315718313.html, 通讯联系人:李文辉(1961-),男,教授,博士生导师.研究方向:计算机图形学.E -mail:liw h@https://www.doczj.com/doc/9315718313.html,
基于非线性规划的凸多面体间碰撞检测算法
赵 伟1,2,李文辉1,夏云飞2
(1.吉林大学计算机科学与技术学院,长春130012; 2.长春工业大学计算机科学与工程学院长春130012)
摘 要:为了提高碰撞检测算法的速度,提出用顶点的凸包表示凸多面体,将两个凸多面体间距离的问题归结为一个带约束条件的非线性规划问题,利用模拟退火遗传算法对该问题进行求解。利用模拟退火的接收准则进行交叉、变异,降低了时间复杂度。结果表明,模拟退火遗传算法计算效率高、速度快。
关键词:计算机软件;碰撞检测;凸多面体;非线性规划;模拟退火遗传算法
中图分类号:T P311.132 文献标识码:A 文章编号:1671-5497(2008)03-0676-04
Research on convex polyhedron collision detection algorithm
based on non -linear programming
Zhao Wei 1,2,Li Wen -hui 1,Xia Yun -fei 2
(1.College of Comp uter Science and T echnolog y ,J ilin Univer sity ,Changchun 130012,China;2.College of Comp uter Science and Eng ineer ing ,Chanchun Univers ity o f T echnology ,Changchun 130012,China)
Abstract:To increase the running speed of the co llision detectio n algo rithm,a new appro ach is pro posed,w hich uses convex Bounding Volume H ierarchies (BVH s)to express convex poly hedron.Thus the distance problem of tw o convex polyhedro ns is com e dow n to a no n -linear pr ogram ming pro blem w ith constraints.T he non -linear prog ramm ing pro blem can be solved by sim ulated annealing
genetic algor ithm.Apply ing the acceptance criter io n of the simulated annealing genetic algo rithm,intersection and variation are carried out to optimize the tim e com plex ity.Results show that the efficiency of the sim ulated annealing genetic alg orithm is high and the computing speed is faster.Key words:computer softw are;collision detection;convex poly hedr on;non -linear pro gramm ing;anneal genetic algorithms
求解物体间最短距离是碰撞检测算法的关键技术之一[1],该类算法通过寻找和跟踪两个多面体之间的最近点来计算它们之间的距离,当距离小于或等于零时,两者就发生了碰撞[2]
。目前著名的碰撞检测算法有Lin -Candy 算法[3]和Enhanced G J K 算法[4]。两种算法均借鉴了时
空连续性和几何连续性的原理来提高算法的速
度。
本文提出的方法是将碰撞检测中物体间距离的计算问题归结为带约束条件的非线性规划问题。传统的求解非线性规划的方法有很多种[5]。每种方法都有其适用范围和局限性。与以上方法
第3期赵 伟,等:基于非线性规划的凸多面体间碰撞检测算法
相比,遗传算法具有极强的鲁棒性和自适应搜索能力,可以在一个复杂的、多极值点的、具有不确定性空间中寻找到最优解。但是遗传算法容易过早收敛,使搜索陷入局部最优解。把模拟退火引入到遗传算法中,可以防止遗传算法过早收敛,容易得到全局最优解,本文采用模拟退火遗传算法来求解带约束条件的非线性规划问题。
1 理论基础
1.1 非线性理论
定义1 给定m 个点V 1,V 2,,,V m I R n
和实数K 1,K 2,,,K m ,称表达式K 1V 1+,+K m V m 为点V 1,V 2,,,V m 的线性组合,特别的当K 1+,+K m =1,且K 1,K 2,,,K m \0时,称K 1V 1+K 2V 2+,+K m V m 为点V 1,V 2,,,V m 的凸组合。其中R n 为n 维空间[5]。
定义2 设s A R n
,则s 中任意有限个点的所有凸组合称为s 的凸包(convex hull ),记为H (s),即H (s)=
E m
i=1
K i V
i
|V i I s,K i \0,i =1,,,
m
E m i =1
K i
=
1,m I N +
式中:N +为所有正数的集合。
1.2 凸多面体的距离模型
用Mind A,B =||x -y ||表示凸多面体A 和B 之间的最短距离,其中x 表示物体A 上的一点y 表示物体B 上的一点。根据上面的理论可以将物体间最短距离表示为
Mind A,B =
E m
i=1
K i
V
i
-
E n
j =1
R j y
j
式中:
E m
i =1
K i V
i
表示A 上的一点x ;
E n j =1
R j
y
j
表示B
上的一点y ;K i 和R j 分别满足:
st E n
i=1K i
=1,K i \0,i =1,2,,,n;st
E n
j =1
R j
=
1;R j \0,j =1,2,,,n 。
这样通过用顶点的凸包来表示凸多面体,可将求解物体间最短距离的问题转化为带有约束条件的非线性规划问题。在满足约束的等式和不等式中寻找使Mind A,B 取最小值的点,设为K i 和R j 。如Mind A,B =0,则物体A 和B 碰撞;如果Mind A,B >0,则物体A 和B 分离。由于A 和B 的顶点信息已知,所以主要是求解优化的时间复
杂度,本文将采用模拟退火遗传算法进行求解。
2 模拟退火遗传算法
2.1 遗传算法
遗传算法是模拟自然界生物进化过程的一种计算模型。它不需要求导或其他辅助知识,只需要确定搜索方向的目标函数和相应的适应度函数,它强调概率转换规则,而不是确定的转换规则[6,7]
。
2.2 模拟退火算法
模拟退火算法是利用固体物质退火过程的热平衡问题与随机搜索寻优问题的相似性寻找全局最优或近似全局最优的一种算法[8]。在搜索最优解的过程中,模拟退火算法除了可以接受优化解外,还有一个随机接受准则,即有限度地接受恶化解,并且接受恶化解的概率慢慢趋向于0,这使得算法有可能从局部极值区域中跳出,即可能找到全局最优解,并保证了算法的收敛性。2.3 约束条件的处理
将模拟退火遗传算法应用于约束最优化问题的关键是对约束条件的处理。本文提出的数学模型只需对等式约束条件进行处理和对只含上、下限的约束条件进行处理。
对等式约束条件的处理:假设等式约束中有m 个独立的等式,则m 个变量可以用剩余的n -m 个变量线性表示。将转换后的等式带入含上、下限的约束条件或不等式约束条件,从而消除了等式约束件。m 个变量消除后,若原约束条件不存在不等式约束,则原约束条件全部转化为新的只含上、下限的约束;若原约束条件存在不等式约束,则原等式约束条件转化为新的不等式约束,
且原上、下限约束同时被改变。
对只含上、下限约束条件的处理:对于变量的上、下限约束,依据解的精度要求利用二进制码表示变量,将n 个二进制位串顺序连接起来,完成一个编码。
2.4 算法思想
虽然遗传算法使用简单、鲁棒性强、应用范围广,但是它本身也存在着许多不足。尤其是容易过早收敛,使搜索陷入局部最优解,因此把模拟退火引入到遗传算法中,既可以防止求解过程的过早收敛,也可以防止使搜索陷入局部最优解,从而保证了算法的收敛性。
本文所采用的模拟退火接收准则为
#
677#
吉林大学学报(工学版)第38卷
Metropolis准则,即
P(T k+1)=1,f k+1 P(T k+1)=ex p-f k+1-f k T k+1 ,f k+1\f k T k+1=T k A 式中:f k+1为新解的适应函数值;f k为原解的适应函数值;P(T k+1)为在温度T k+1下的接受概率; A为降温系数,一般为0.1左右。 每一代做完即降温一次,将温度乘以系数A 得出接受新解的概率P(T k+1)后,将它与0到1之间的某个数比较,若P(T k+1)大于这个数则接受新解,否则放弃新解。如此建立的模拟退火模型具有特殊的功能:高温时,P(T k+1)值相对较大,容易接受新解;而低温时几乎只能接受优化解,很难(甚至不能)接受劣于本身的解。 适应函数选为 Fit(f(x))=2-f(x),f(x)<2 Fit(f(x))=0,其他情况 实验证明,取最大值为2效果较好。 实现算法总体思想的步骤如下: 步骤1形成初始解群,对其进行若干代的交叉变异,找到一个相对较好的局部最优解。 步骤2升高温度,使变异接受新解的概率增大,强迫解群接受新特性。 步骤3消除局部收敛特性,再交叉变异达到一个新的更好的局部最优点。 步骤4升温消除局部收敛特性,再交叉变异。 步骤5重复步骤2至步骤4,直至达到理论上全局最优。 2.5遗传的具体算子 选择:选择是指染色体是否被选择或复制下来的操作。首先选择满足x i[x i[x i的染色体,其中x i和x i分别为x i的上界和下界,本文中x i 指K和R。其次群体中第j个染色体被选择繁衍 后代的概率p j=Fit(f(x j))/E M j=1Fit(f(x j))。适应性强的染色体有更多繁衍后代的机会,从而使 优良的特征得以遗传。 交叉:本文采用单点交叉。单点交叉可分两步,首先对配对库中个体进行随机配对,其次配对个体交换部分信息。例如: A1A2A3A4A5 B1B2B3B4B5交叉到 A1A2A3B4A5 B1B2B3A4B5 这样就形成了新的染色体。 变异:变异就是随机地改变染色体中的某一 个值。变异时随机产生染色体中某个变异位置, 然后产生m in{x i}和max{x i}中的随机数,替换 该位置的染色体基因。 2.6算法的实例分析 步骤1输入原始数据及所需的参数。 步骤2形成初始化解群。 步骤3赋初值T k=T0,A=A1,计算适应函 数值,操作数oper ator num=0。 步骤4交叉、变异取舍新解,采用上面给出 的交叉、变异方法。 步骤5操作数加一,即operatornum++。 步骤6如果满足最优解,则输出结果结束; 否则T k+1=T k,A=A k1,转到步骤4。 3实验结果与性能分析 为了便于性能评价,实验时选定惩罚函数法、 遗传算法、模拟退火遗传算法。计算两个多面体 之间的距离及所用的时间并进行比较。 其测试环境为Window s XP操作系统,CPU 为赛扬IV1.7GH z,内存256M B,磁盘盘页大小 1024字节,采用随机数据进行性能测试。 分别作两个相交多面体和两个分离多面体的 碰撞检测试验。每个实验选定四组随机实验数 据,每组的实验数据个数分别为:500,1000,5000, 10000,用G表示实验数据的个数,每个实验数据 为两个多面体的顶点坐标。分别采用3种算法计 算当两个物体之间的距离达到最小时(即碰撞)所 需要的时间,然后对每组实验数据取平均值,这样 会得到实验数据近似精确的结果。 (1)选取两个相交的多面体 任意给定两个多面体的坐标。多面体A的 顶点坐标为 x1(0,0,0),x2(0,0,1),x3(0,1,0),x4(1,0,0) 多面体B的顶点坐标为 y1(3,-2,0),y2(0,-2,3),y3(1,0,0),y4(0,-2,0) 则多面体间的距离求解过程如下 m in d A,B=E4i=1K i x i-E4j=1R i y j s.t E 4 i=1 K i=1;E4j=1R j=1 K i\0,i=1,2,3,4,R j\0,j=1,2,3,4 分别采用惩罚函数法,遗传算法,模拟退火遗传算 # 678 # 第3期赵伟,等:基于非线性规划的凸多面体间碰撞检测算法 法进行求解,结果如表1所示。 (2)选择两个分离多面体 可以采用同样的方法进行计算,分别取多面体A和B坐标为: x1(0,0,0),x2(1,0,0),x3(1,1,0),x4(0,1,0), x5(-1,1,0),x6(0,0,1)y1(3,-2,0),y2(3,-1,0),y3(-3,-2,0), y4(-3,-1,0),y5(-3,-2,7),y6(3,-5,0)同样采用以上三种方法进行求解,结果如表2所示。根据表2可以看出模拟退火遗传算法无论在计算效率和精度上都比惩罚函数法和遗传算法好。 表1相交多面体间不同算法的性能分析 Table1Between intersection polyhedron different algorithm perform ance analysis 算法 G=500G=1000G=5000G=10000 平均时间平均距离平均时间平均距离平均时间平均距离平均时间平均距离 惩罚函数法6.3332.774@10-326.3212.632@10-326.2832.511@10-326.1052.474@10-32遗传算法1.6861.454@10-341.6711.422@10-341.6551.420@10-341.6331.415@10-34模拟退火遗传算法1.9221.334@10-341.9151.320@10-341.9081.311@10-341.9991.307@10-34 表2分离多面体间不同算法的性能分析 Table2Between separation polyhedron different algorithm perf ormance analysis 算法 G=500G=1000G=5000G=10000平均时间平均距离平均时间平均距离平均时间平均距离平均时间平均距离惩罚函数法7.2250.9867.1880.9757.1670.9777.1680.986 遗传算法1.5540.9881.5110.9861.5150.9891.5050.991 模拟退火遗传算法1.8420.9981.8310.9961.4220.9951.8170.995 4结束语 采用空间物体的凸包来表示凸多面体,将空间多面体之间的碰撞检测问题转化为带约束条件的非线性规划问题,并采用模拟退火遗传算法进行求解,结果表明,模拟退火遗传算法在求解这类问题上具有可行性和高效性。 在今后的研究工作中,还需要对以下两方面进行改进:1动态的物体求解,考虑时间的约束条件。o根据实际情况选择合适的适应度函数。 参考文献: [1]Camero n S.A co mpar ison of tw o fast algo rit hms for computing t he distance betw een convex polyhedr on [J].IEEE T r ansactio ns on Ro bo tics and A utoma-tio n,1997,13(6):915-920. [2]Selim S Z,Almohamad H A.Collisio n co mputation of mov ing bodies[J].Euro pean Journal of Opera-tional Research,1999,119(1):121-129. [3]L in M C,M anocha D.F ast inter ference det ection betw een g eometr ic mo dels[J].T he V isual Co mput-er,1995,11(10)542-561.[4]Gilber t E G,Johnso n D W,K eerth i S S.A fast pr ocedure fo r computing the distance betw een com-plex objects in three dimensional space[J].IEEE T rans on Robot ics and A uto mation,1988,4(2): 193-203. [5]谢政.非线性最优化[M].长沙:国防科技大学出版 社,2003. [6][美]Zbigniew M ichalewicz.演化程序:遗传算法和 数据编码的结合[M].周家驹,何险峰译.北京:科学出版社,2000. [7]张玲,张钹.遗传算法机理的研究[J].软件学报, 2000,11(7):945-952. Zhang L ing,Zhang Bo.Research on the mechanism of g enetic algo rit hms[J].Jounr al of So ftwar e,2000, 11(7):945-952. [8]王森,蔡理,刘河潮.基于遗传模拟退火算法的量子 细胞自动机电路仿真[J].系统仿真学报,2005,17 (8):2027-2029. Wang Sen,Ca i Li,L iu H e-chao.Simulation o f quantum cellaular auto maton circuits based o n g enet-ic simulated annealing algo rithm[J].A cta Simulata Systematica Sinica,2005,17(8):2027-2029. # 679 # 简介 本文是阐述如何在2D动作游戏中进行精确而高效的碰撞检测。这里的碰撞是基于多边形而不是基于精灵的。这两者之间在设计上会有不同。 基于精灵的碰撞检测是通过精灵之间的重叠的像素来完成的。而多边形使用向量数学来精确计算交点，时间和碰撞方向。虽然多边形仅仅是精灵的一个近似，但是它比精灵系统要高级。 ?可以精确模拟逼真的简单物理学，例如反弹，摩擦，斜面的滑行 ?碰撞检测可以更精确的用于高速精灵系统。在基于精灵的系统中，如果物体移动过快就会在跳过另一个物体。 ?基于向量数学因此可以扩展到3D，然而精灵碰撞系统被严格限制在2D的情况下。 特性 本文使用的算法只适用于凸多边形，例如三角形，四边形，六边形，圆形。对于非凸多边形，你可以将其分解为多个凸多边形，例如三角形。 算法可以用于快速移动或慢速移动的多边形。不管物体移动多快，碰撞都不会丢失。它也可以处理重叠的问题，并促使交叠物体分离。 演示也支持分割多边形交叉。这可以用于子弹的建模。 同时提供了简单的物体系统，弹力，一些基本的摩擦和静摩擦力。用于确保物体不会从斜面上滑落。 有一个刚体系统的例子，使用了Chrsi Hecker的物理教程。 限制 有序碰撞。就是说并不是有序的进行碰撞。这对于快速移动的物体会出现一定的问题。一旦碰撞被检测到，它就被直接处理了。理想状态下你可能需要找到一个碰撞点并处理它，然后寻找更多的碰撞。但是对于2D动作游戏，这通常是不必要的。 一、分离坐标轴方法 这个方法是碰撞检测的核心。它的规则非常简单并且非常易于实现。这个方法也非常快并且非常可靠，因为计算中没有使用除法操作，下面给出一个简单的基于两个BOX的碰撞检测的例子。 第四章 非线性规划 ???? ???? 无约束最优化问题线性规划约束最优化问题非线性规划 ?? ?凸规划约束最优化问题非凸规划 ?? ?直接解法约束最优化问题求解方法间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。 直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。 第一节 目标函数的约束极值问题 所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。 对于带有约束条件的目标函数，其求最优解的过程可归结为： 一、约束与方向的定义 一）起作用约束与松弛约束 对于一个不等式约束()0g X ≤来说，如果所讨论的设计点() k X 使该约束()0g X =(或 者说() k X 当时正处在该约束的边界上)时，则称这个约束是() k X 点的一个起作用约束或紧约 束，而其他满足()0g X <的约束称为松弛约束。 冗余约束 40g ≤ 当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为 {}()()()|()0,1,2, ,k k u I X u g X u m === 其意义是对() k X 点此时所有起作用约束下标的集合。 二）冗余约束 如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影 响，或是约束面不与可行域D 相交，即此约束称为冗余约束。 三）可行方向 可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。 1）设计点为自由点 设计点() k X 在可行域内是一个自由点，在各个方 向上都可以作出移动得到新点仍属于可行域，如图所示。 2）设计点为约束边界点 当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。此时，()k X 点的可行方向S 必满足条件： ()0T k i S g X ?≤ （解释：()()cos ,()T k k T k i i i S g X S g X S g X ?=??，,()90T k i S g X ?≥?）） 当,()90T k i S g X ?=?时，方向S 是约束函数i g 在()k X 点处的切线方向，即()0T k i S g X ?=。 当某个设计点x 同时有几个约束起作用时(如 非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1 无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 此类问题即为无约束的非线性规划问题 1.1 无约束非线性规划的解法 1.1.1 一般迭代法 min f X 即为可行方向法。对于问题x R X0 给出f(x)的极小点的初始值X(0)，按某种规律计算出一系列的X (k) (k 1,2,)，希望点 阵｛X(k)｝的极限X就是f (x)的一个极小点。 由一个解向量X(k)求出另一个新的解向量x(k1) 向量是由方向和长度确定的，所以X(k1) X k k P k(k 1,2, ) 即求解k和P k，选择k和P k的原则是使目标函数在点阵上的值逐步减小，即 检验｛ X (k)｝是否收敛与最优解，及对于给定的精度0，是否|| f(X k1)|| 。 1.1.2 一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维 分数: ___________任课教师签字：___________ 课程作业 学年学期：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 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差， 运 筹 学 实 习 报 告 姓名： xxxxxxxxxx 学号： xxxxxxxxxxx 专业班级： xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日 题目：用最速下降法求解无约束非线性规划问题 摘要： 无约束最优化问题的求解方法分为解析法和直接法两大类。解析法需要计 算函数的梯度，其中最速下降法就属于解析法中的一种。对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。本文通过理论的计算方法，进一步分析，最后用c++编程实现求出允许误差内的最优解。此编程可用于计算符合下列形式的函数求最优解过程： f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中：a[i] (i=0,1,2,3,4,5) 为函数的系数。 本文以“ 李占利 主编，中国矿业大学出版社出版”的《最优化理论与方法》 第五章 “无约束最优化方法，5.1 最速下降法 ”例5—1为实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。然后应用c++语言编程，得到在精度范围内的精确最优解。 C++编程计算的最优解为 : T x x ]0329218.0,00823045.0[)3(*-==。 即转化为分数结果为：?? ????-==412432) 3(*x x 。 满足精度要求的模为： 101 0736154.0||||)3(= <=εp 。 关键词：无约束非线性规划 解析法 最速下降法 梯度 模 最优解 分数: ___________ 任课教师签字：___________ 课程作业 学年学期：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 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，而且寻优的效率特别低下。 非线性规划（nonlinear programming） 1.非线性规划概念 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。 2.非线性规划发展史 公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为0.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。 最优化方法不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。 (1)解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。 (2)直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。 (3)数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。 (4)其他方法：如网络最优化方法等。 无约束非线性规划求解方法及其实现 作者：杨玲指导老师：陈素根 摘要: 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程，管理，经济，科研，军事等发面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果，无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 关键词最优化共轭梯度法非线性无约束 1 引言 1.1 无约束非线性规划问题是最基本的非线性规划问题，在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP变尺度法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了许多新的算法。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 1.2 本文主要研究无约束非线性规划问题，将文章分成四个部分，首先会具体介绍无约束非线性规划的相关概念，并在此基础上研究非线性规划的相关理论与基本算法问题，接着详细介绍无约束非线性规划的几种主要的求解方法，最后举例说明他在实际生活中的应用，并编程实现它。 2 正文 2.1主要介绍无约束非线性规划的相关概念 一个非线性规划问题的自变量x没有任何约束，或说可行域即是整个n维向量空间：n 错误！未找到引用源。,则称 x R 第二节 SUMT 方法（罚函数法） 一、SUMT 方法的原理 SUMT （sequential unconstrained minimization technique ）法，序列无约束极小化方法,亦称为罚函数法。它是一种不等式约束最优化问题的间接解法 它的基本思想是将原来的目标函数和约束函数按一定的方式构成一个新的函数，在这个新函数中，既包括目标函数，又包括全部约束函数和一个可以变化的乘子。 当这个乘子按一定的方式改变时，就得到一个新函数序列，求每一个新函数的最优解都是一个无约束最优化问题，这样就把一个约束最优化问题转化为一系列无约束最优化问题进行求解。所得到的最优解序列将逐步逼近原问题的最优解。 引例一：min ()f X ax = s.t ()0g X b x =-≤ 显然f （X ）的最优点为x*=b ，对应的最小值为f （X*）=ab 用SUMT 求解函数的最优解 构造函数 11(,)()()k k k X r f X r ax r g X b x Φ=-=-- 0k r >—可变化乘子，它是一个很小的正数。 其最优解为： *()k X r b =+ 此时对应的(,)k X r Φ的最小值为 ***1(,)k k X r ax r b x ab Φ=--=+ 最优点 *()k X r 和最小值*(,)k X r Φ均是k r 的函数。当k r 取不同值时，它们有不同的值，而当 0k r →时，**()k X r X b →=，*(,)*k X r f X ab Φ→=（），即最后收敛于约束最优点。 min lim[min (,)]() {|()0}k k i r X r f X R X g X X R →Φ==≤∈ 以上分析从理论上说明了无约束最优化问题 min (,) k X r Φ与约束优化问题 min () {|()0}i f X R X g X X R =≤∈之间的联系：约束非线性规划问题可以通过构造新目标函数序 列，用无约束优化方法求其极小点，并逐次逼近原问题的最优点。 问题：如何构造新函数？或者说新函数具有什么特点？ 特点：对于某一个k r （即当它为某一定值时），当设计点在可行区中且距离边界较远时，其对应的新 无约束非线性规划求解方法及其实现 摘要: 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程，管理，经济，科研，军事等发面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果，无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 关键词最优化共轭梯度法非线性无约束 1 引言 1.1 无约束非线性规划问题是最基本的非线性规划问题，在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP变尺度法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了许多新的算法。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 1.2 本文主要研究无约束非线性规划问题，将文章分成四个部分，首先会具体介绍无约束非线性规划的相关概念，并在此基础上研究非线性规划的相关理论与基本算法问题，接着详细介绍无约束非线性规划的几种主要的求解方法，最后举例说明他在实际生活中的应用，并编程实现它。 2 正文 2.1主要介绍无约束非线性规划的相关概念 一个非线性规划问题的自变量x没有任何约束，或说可行域即是整个n维向量空间：n 错误！未找到引用源。,则称 x R 百度文库- 让每个人平等地提升自我 运 筹 学 实 习 报 告 姓名： xxxxxxxxxx 学号： xxxxxxxxxxx 专业班级： xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日 题目：用最速下降法求解无约束非线性规划问题 摘要： 无约束最优化问题的求解方法分为解析法和直接法两大类。解析法需要计 算函数的梯度，其中最速下降法就属于解析法中的一种。对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。本文通过理论的计算方法，进一步分析，最后用c++编程实现求出允许误差内的最优解。此编程可用于计算符合下列形式的函数求最优解过程： f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中：a[i] (i=0,1,2,3,4,5) 为函数的系数。 本文以“ 李占利 主编，中国矿业大学出版社出版”的《最优化理论与方法》 第五章 “无约束最优化方法， 最速下降法 ”例5—1为实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。然后应用c++语言编程，得到在精度范围内的精确最优解。 C++编程计算的最优解为 : T x x ]0329218.0,00823045.0[)3(*-==。 即转化为分数结果为：?? ????-==412432) 3(*x x 。 满足精度要求的模为： 101 0736154.0||||)3(= <=εp 。 关键词：无约束非线性规划 解析法 最速下降法 梯度 模 最优解 非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()min 0 x R f X X ∈??? ≥?? 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1一般迭代法 即为可行方向法。对于问题()min 0x R f X X ∈??? ≥?? 给出)(x f 的极小点的初始值)0(X ，按某种规律计算出一系列的),2,1()( =k X k ，希望点阵}{)(k X 的极限*X 就是)(x f 的一个极小点。 由一个解向量) (k X 求出另一个新的解向量)1(+k X 向量是由方向和长度确定的，所以),2,1()1( =+=+k P X X k k k k λ 即求解k λ和k P ，选择k λ和k P 的原则是使目标函数在点阵上的值逐步减小，即 .)()()(10 ≥≥≥≥k X f X f X f 检验}{)(k X 是否收敛与最优解，及对于给定的精度0>ε，是否ε≤?+||)(||1k X f 。 1.1.2一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法，0.618法等）； （2）插值法（抛物线插值法，三次插值法等）； （3）微积分中的求根法（切线法，二分法等）。 求解无约束最优化问题的方法主要有两类，即直接搜索法（Search method）和梯度法（Gradient method） 直接搜索法适用于目标函数高度非线性，没有导数或导数很难计算的情况，由于实际工程中很多问题都是非线性的，直接搜索法不失为一种有效的解决办法。常用的直接搜索法为单纯形法，此外还有Hooke-Jeeves搜索法、Pavell共轭方向法等，其缺点是收敛速度慢。 在函数的导数可求的情况下，梯度法是一种更优的方法，该法利用函数的梯度（一阶导数）和Hessian矩阵（二阶导数）构造算法，可以获得更快的收敛速度。函数f(x)的负梯度方向-▽f(x)即反映了函数的最大下降方向。当搜索方向取为负梯度方向时称为最速下降法。当需要最小化的函数有一狭长的谷形值域时，该法的效率很低，如Rosenbrock函数 9.2.3.2 相关函数介绍 fminunc函数 功能：求多变量无约束函数的最小值。 数学模型： 其中，x为一向量，f(x)为一函数，返回标量。 语法格式： x = fminunc(fun,x0) x = fminunc(fun,x0,options) x = fminunc(fun,x0,options,P1,P2,...) [x,fval] = fminunc(...) [x,fval,exitflag] = fminunc(...) [x,fval,exitflag,output] = fminunc(...) [x,fval,exitflag,output,grad] = fminunc(...) [x,fval,exitflag,output,grad,hessian] = fminunc(...) 描述： fminunc给定初值，求多变量标量函数的最小值。常用于无约束非线性最优化问 题。 x = fminunc(fun,x0)给定初值x0，求fun函数的局部极小点x。x0可以是标量、 向量或矩阵。 x = fminunc(fun,x0,options)用options参数中指定的优化参数进行最小化。 x = fminunc(fun,x0,options,P1,P2,...)将问题参数p1、p2等直接输给目标函数fun， 将options参数设置为空矩阵，作为options参数的缺省值。 [x,fval] = fminunc(...)将解x处目标函数的值返回到fval参数中。 [x,fval,exitflag] = fminunc(...)返回exitflag值，描述函数的输出条件。 [x,fval,exitflag,output] = fminunc(...)返回包含优化信息的结构输出。 [x,fval,exitflag,output,grad] = fminunc(...)将解x处fun函数的梯度值返回到grad碰撞检测教程(C++)
第四章 非线性规划1-约束极值问题
非线性规划模型
单纯形法解决无约束优化问题
用最速下降法求解无约束非线性规划问题
单纯形法解决无约束优化问题
非线性规划
无约束非线性规划求解方法及其实现
第四章非线性规划2-SUMT方法罚函数法
无约束非线性规划求解方法及其实现--论文
用最速下降法求解无约束非线性规划问题
非线性规划模型
无约束线性规划问题
相关主题
文本预览