资源描述：
《最优化方法及其在计算机图形学中的应用_马小虎.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、·研究与探讨·1997.7计算机工程与应用最优化方法及其在计算机图形学中的应用浙江大学CAD&CG国家重点实验室马小虎潘志庚石教英摘要最优化方法是对极值问题进行数值分析的有效手段,它在计算机图形学中已获得广泛应用。本文概述了最优化方法并简要介绍了最优化方法在计算机图形学中已有的若干应用,阐述了作者把最优化方法用于限时计算和限时图形绘制所做的研究工作。关健词最优化方法限时计算网格优化曲面设计1引言数,D为f(x)的定义域。也可以写成更一般的形式:最优化方法是对极值问题进行数值分析的有效minf(x)……(2-2)x∈D手段[1]。极值
2、问题历史悠久而其内容不断地更新,它满足:φ(x)=0来源于科学和技术的各个方面,问题的深度和广度也ψ(x)≤0随着各个不同阶段的科学技术水平而有所发展。T其中,x=(x1,x2,…,xn),近2、30年来,由于科学技术的需要,以及计算机φ(x)=(φ1(x),φ2(x),…,φp(x))T,技术的飞速发展,为求解各种极值问题的最优化方法ψ(x)=(ψ1(x),ψ2(x),…,ψq(x))T。和理论提供了坚实的基础和有效手段。最优化的应用在(2-1)中,自变量x可以取遍定义域D内的值范围愈来愈广,几乎在设计、操作、工业过程、生产装而不
3、受限制,故称为无约束极值问题。而在(2-2)中,置分析乃至生产计划之类的有关问题中,最后都归结x∈D必须受到一定的约束,即:为确定某个目标函数的最优值——极大或极小。随着φi(x)=0,i=1,2,…,p……(2-2a)计算机运算能力的增强,使得我们有可能在资源(计ψj(x)≤0,j=1,2,…,q……(2-2b)算资源、存储资源等)容许的条件下追求最优解,在计故称(2-2)为约束极值问题.(2-2a)、(2-2b)算机图形学中的许多问题(光照、曲面、动画设计;动都称为约束条件,其中(2-2a)是等式约束,(2-2b)画的运动合成;
4、几何造型等)可以用最优化方法来求是不等式约束。解[2]。2.1.2分类上述问题又统称为数学规划,按目标本文第二节对最优化方法作一简要介绍,第三节函数以及约束条件中约束函数的类型和自变量取值介绍了最优化方法在计算机图形学中已有的几个典状态,还可以区分为不同形式的数学规划。型实例,第四节简单介绍作者把最优化方法用于限制当f(x)、φi(x)、ψj(x)均为线性函数时,称为线性计算和限时图形绘制方面所做的工作,最后是结论。规划,当其中任一个为非线性函数时,称为非线性规划;当f(x)为二次函数,φi(x)、ψj(x)均为线性函数时,2最优化
5、方法概述称为二次规划;当x的各个分量全部或部分只取离散2.1最优化问题的提法及分类值(如取整数值)称为整数规划;在整数规划中,若x2.1.1描述最优化问题通常可以表示为目标函数的各个分量只取0、1两个值时,称为0-1规划。还有的极值问题,其形式化表示为:几何规划,动态规划等等。minf(x)……(2-1)求解问题(2-1)或(2-2)的目的,是要确定一个X∈D*其中,f(x):DRn→R为实值函数,称为目标函向量x,本研究课题得到国家自然科学基金资助—38—计算机工程与应用1997.7·研究与探讨·*满足f(x)=minf(x)。对
6、于(2-2),还要满足:φ3.1.2求解方法网格优化的目的是获得一个能够x∈D(x*)=0,ψ(x*)=0我们称x*为最优点。较好地拟合给定的数据点集合X,并且只有少量顶点对于极大问题maxF(x),如果令f(x)=-F(x),的网格。为此只要求得一个简单复合形K和一组顶则转化为极小问题。因此,最优化问题表示为(2-1)点V,即求出一个网格M=(K,V)使得如下构造的能[5]或(2-2)的形式不失其普遍意义。量函数:E(K,V)=Edist(K,V)+Erep(K)+Espring(K,V)2.2最优化问题的计算方法…(3-1)实际
7、问题中多数极值问题都是以约束问题的形达到极小。式出现。对于约束最优化问题,尽管早已有了La-在(3-1)中,V={v31,v2,…vm},vi∈R,i=1,2,grange函数法,但现实生活中大量出现的问题远远地…,n。K是表示顶点、边、面之间连接性的简单复合超出了古典极值方法研究的范围。继Kuhn-Tucker形,它决定了网格的拓扑类型。于是网格M可形式化(1951)的工作之后,约束最优化问题引起了学者们的表示为二元组(K,V)。(3-1)式右边的每一项分别广泛重视,得到了极大的发展。约束最优化问题中常为:用的算法包括二次规划法、
8、直接法、系列无约束最优n化方法、容许方向法、简约梯度法、约束变尺度法[3]2·Edist(K,V)=∑d(xi,ψv(
9、K
10、)),其表示点集i=1虽然实际问题中多数极值问题都是以约束问题X中每一点到网格M的距离平方和。的形式出现的,但
