约束求解

2024-10-24

约束求解（精选9篇）

约束求解篇1

1 概述

计算机辅助设计 (Computer Aided Design, CAD) 是使用计算机来帮助人们进行产品设计的一项技术。在计算机辅助设计中, 几何约束求解是一项关键性技术, 能够缩短设计周期, 降低设计劳动和提高设计质量。目前, 几何约束求解方法主要包括:基于代数的求解方法、基于几何约束图的求解方法和基于规则推理的求解方法。在基于代数的求解方法中, 将几何约束问题转化为非线性方程组, 然后求解非线性方程组获取模型参数的数值[1]。在基于几何约束图的求解方法中, 使用无向图来表达几何约束关系。分析几何约束图, 形成一系列可求解的子问题, 组合子问题的解以获取整个问题的解[2]。在基于规则推理的求解方法中, 使用规则来建立模型构造步骤[3]。在二维绘图过程中, 复杂的图形可以利用简单的直线、圆弧和曲线合成, 比较适于使用这种求解方法。

2 交互方式几何约束求解框架

本文给出了一种基于交互方式的几何约束求解框架, 如图1所示。通过用户编辑界面, 绘图者输入建模命令。模型构建器对用户输入的建模命令进行分解, 建立若干个几何约束方程来实现建模命令。调用约束求解器对几何约束方程组进行求解, 获得模型的参数数值。模型构建器将该模型的几何约束方程存储在几何约束方程列表之中, 将模型参数数值存储在模型数据列表之中。在求得模型的几何参数数值之后, 约束求解器调用图形绘制器在图形显示界面中画出用户所需要的几何模型。

用户可以通过绘图系统画出所需要的目标模型。但是, 用户建模不是一次就能完成的。在建模过程中, 需要对模型参数进行多次修改。在每一次修改参数的过程中, 模型的约束关系都要发生改变, 诸如:模型元素之间的边界超出、边界交叠和边界错位等。这些问题会造成建模错误, 其具体反映形式为模型的几何约束方程组出现矛盾和无解的情况。单纯利用模型构建器来调整几何约束方程组是不能解决建模过程中出现的错误与矛盾。很多模型元素之间的冲突必须通过人机交互的方式来解决。

用户可以通过调整几何约束方程来解决建模过程中的矛盾。对于用户而言, 这种方式比较直接, 但是系统实现起来是比较复杂的而且也经常会出现问题。几何约束关系中的矛盾可以表现为模型参数之间的冲突。用户通过操作界面可以调整模型参数, 来解决几何约束关系中的冲突问题。这种约束关系的调整方式, 对于系统实现而言是比较容易的。但是, 需要用户计算模型元素的参数数值。例如:两个圆相切, 若其中一个圆的圆心发生变化, 则另一个圆的圆心坐标也要发生变化。在几何约束关系调整的过程中, 用户通过人机界面调整某一个模型元素的参数数值, 模型构建器调用约束求解器来计算几何约束方程组的解, 以获得其它模型元素的参数数值。

在模型建立和修改过程中, 用户需要与系统进行人机交互。几何约束关系的调整是以模型参数修改为基础的。在修改几何约束关系时, 用户应该分析约束方程之间的关系, 找出所涉及的最小约束方程组。在最小约束方程组中, 计算模型参数的关联度。按照关联度, 对模型参数进行排序。选取关联度最大的模型参数, 通过设定参数的数值来调节几何约束方程, 以消除约束关系中的冲突。若最小约束方程组依然存在矛盾, 则需要继续执行以上步骤, 直到所有的冲突消除为止。在消除了最小约束方程组的矛盾之后, 一部分参数数值由用户确定, 其余的需要调用约束求解器来进行求解。

用户编辑界面的设计应该便于模型参数的修改和几何约束关系的调整。在用户编辑界面中, 应该列出该模型的所有几何元素和几何约束方程。在系统实现时, 采用列表控件来显示几何约束方程。针对每一个模型元素, 应该列出它的所有模型参数。在系统实现时, 采用列表控件来显示模型参数。在设定模型参数数值时, 采用编辑框来实现。在用户界面中, 可以从列表控件中选择要修改的模型参数。在编辑框中, 可以设定模型参数的数值。在用户编辑界面中, 采用编辑框来实现几何约束方程的输入。在初始建立模型的过程中, 用户通过编辑框输入几何约束方程。在几何约束方程的编辑过程中, 用户从列表控件中选择目标约束方程。然后, 在编辑框中修改几何约束方程。在存储过程中, 按照模型元素来存储对应的参数信息, 按照模型来存储对应的几何约束方程。其目的是便于实现几何约束方程和模型参数的定位。采用CDC类来绘制目标模型。

采用了人机交互的方式来调整几何约束关系, 可以方便灵活地实现模型建立与修改, 降低了系统实现的难度, 具有较好的用户可操作性。

3 结论

本文给出了一种基于人机交互的几何约束求解方法。通过修改模型元素的参数数值来调整模型的几何约束关系, 将约束方程的调整归结为参数信息的修改。按照模型元素来存储参数信息以提高定位的效率。采用人机交互的方式来修改模型参数数值来降低建模和模型修改的难度。

摘要：本文提出了一种利用人机交互方式来实现几何约束求解的框架。用户通过CAD建模系统界面来改变模型参数的数值。系统的约束求解器对模型的几何约束方程进行求解, 获取约束方程的解。图形绘制器利用约束方程的解来绘制几何模型。

关键词：人机交互,几何约束求解,图形绘制器,几何模型

参考文献

[1]Gao X S, Lei D and Liao Q.Generalized stewart platforms and their direct kinematics.IEEE Transactions on Robotics, 2005, 21 (2) :141-151.

[2]黄学良, 李娜, 陈立平.三维装配几何约束闭环系统的递归分解方法[J].计算机辅助设计与图形学学报, 2013, 25 (9) :1296-1303.

[3]Essert-Villard C, Schreck P, Dufourd J F.Sketch-based pruning of a solution space within a formal geometric constraint solver.Artificial Intelligence, 2000, 124 (1) :139-159.

约束求解篇2

摘要：本文提出了一种用于解决约束多目标优化问题的方法。本算法在进化算法的基础上加入了邻里竞争与邻里合作算子，并通过引入agent-based模型的设计理念，更加注重个体变化对整个群体的影响。本算法首先使用约束偏离值的方法将约束多目标优化问题简化为多目标优化问题;然后使用自我更新算子，当新产生的个体优于原先的个体时予以替换;之后通过邻里竞争与邻里合作加快种群内部的信息交流;最后加入量子加速算子，通过使用量子旋转门来扩大计算搜寻范围提高程序计算速度。本文最后与两种已有算法进行对比，实验结果表明，本算法完成了设计目标。在运行时间和输出结果精度方面都有不错的表现。

关键词：约束多目标优化约束偏离值邻里竞争量子计算

一、引言

进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术。与传统的优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性。尤其是在处理多目标优化问题时，进化算法表现出很好的效果。

近年来，出现了很多优秀的算法用于解决约束多目标优化问题，其中Deb提出的NSGA-II算法是最为经典的一个算法。NSGA-II成功的将进化算法应用在约束多目标优化问题上，在进化算法的基础上引入了约束偏离值。Hongguang Li提出了基于agent的进化算法用于求解约束多目标优化问题。算法利用agent概念认为每个个体与其种群内其他个体都有相互的作用和影响，虽然算法精度不是很高但是计算速度很快。本文受到基于agent概念的启发，希望设计出一个计算速度快，精度高的算法。

二、量子进化算法

2.1 邻里竞争与邻里合作

agent-based模型是一种从底层到高层的数学模型，模型更加注重的是每个个体对整个群体的影响，通过改变个体的某些特征和表现从而影响整个整体。本算法在此基础上，通过模仿自然界种群内部个体之间既有竞争又有合作的关系，设计出了邻里竞争与邻里合作算子。邻里竞争算子采用的是吞并算子，算子表示如下：

设对于一个种群共有k个个体X1，X2，…，Xi，每个个体的目标函数值分别为，则：

(1)

其中表示的是新产生的个体。公式表达的意义是：每个个体与其排名靠后一位的个体进行竞争，将两者目标函数值进行对比，目标函数值较小的个体成为这一位置上的新个体。

邻里合作算子如下：

(2)

(3)

其中，是个体i、j的第k个决策变量，且。r，u是分布在[0，1]之间的随机数。

2.2 量子计算

加入量子算子是为了加快计算速度，希望通过更少的进化代数进化出更加优秀的种群。本算法通过设计出一个对周围区域具有自适应调整搜索步长的量子旋转门，从而提升量子计算运行效率。量子计算首先需要将个体的基因编码从实数编码形式转换为量子编码形式，之后通过量子旋转门的计算快速搜索周围空间寻找更加优秀的个体进行输出。

个体在完成量子旋转门的计算后，个体的基因编码需要映射回实数域，完成其他计算过程。量子算子的本质也就是通过将个体基因编码转换为量子域，通过利用量子计算在量子域具有指数级加速和指数级存储的能力，快速的寻找最优解的过程。

2.3 算法的主要流程

图1为本算法流程图。算法采用顺序结构设计，结构简单，在进化计算的基础上首先使用了约束偏离值的方法，将约束多目标问题进行简化。其次借鉴了基于agent模型里种群中个体之间又相互的影响和作用，设计了邻里竞争与邻里合作算子。又利用了量子计算的加速性能，提升了算法的运行速度。

若为第一代种群，本算法通过之前修正好的目标函数向量进行选择，首先在可行解里选取非支配解，形成种群FeaPop，并在全部种群中寻找非支配解，放入种群NonPop中;若不是第一代种群，则将上一代产生的父代FeaPop与当代的进化种群Pop合并形成NPop，在合并之后的种群里再去寻找可行非支配解形成当代的FeaPop种群，寻找非支配解形成当代的NonPop。变异算子对于防止种群陷入局部最优解起到了重要的作用，本算法采用文献中非一致性变异算子。

三、仿真实验与结果分析

本文的测试问题是Deb提出的.六个经典的约束多目标最小化问题，算法参数设计为：初始种群大小为100，合作概率为0.9，合作指数为10，变异概率为0.5，非一致系数为2，自我更新指数为20。最大的可行非支配解集FeaPop大小为100，非支配解集NonPop大小为100。对比算法初始种群大小为100，交叉概率为0.9，交叉分布指数为15，变异概率为0.1，变异分布指数为20。

文中所有测试问题均独立运行30次，我们采用的度量指标分别为GD和算法运行时间。世代距离指标(GD)，是度量算法所得Pareto前端与真实前端之间的距离。其数学表达式如下式所示：

(4)

其中，，n为个体数目，是中第个个体的目标函数向量与中最近个体间的欧氏距离。GD值越小，所求得的前端就越接近真实前端，解集的收敛性就越好。运行时间则是算法的跑完相同进化代数所需要的时间，时间越短说明算法运行速度越快，本文中涉及到的几种算法运行代数均为1000代。

表1给出本文算法与两种对比算法运行6测试问题的结果。

CTP2、CTP7是寻找离散的几个线段，CTP3、CTP4两个问题要寻找的Pareto前端都是离散的端点，CTP5是离散点和线段的组合，CTP6问题是寻找连续的直线。从表中我们可以看出几种算法对于处理CTP2问题都有不错的结果，都可以很好地找到几个离散端点。对于CTP3和CTP4问题由于测试函数难度的加大，算法[3]已不能很好地找出真实Pareto前端所在位置，而NSGA-II、本算法还能找到真实Pareto前端所在区域，不过已经无法做到很精准的定位Pareto前端的位置。对于CTP5，几种算法在找离散点的能力都很不错。对于CTP6问题几种算法都找到了Pareto前端，只是均匀性稍有差异。CTP7问题，除了算法[3]之外也都很好的找到了前端所在区域。

4 总结与展望

约束求解篇3

摘要：结合子空间思想和LiuStorey （LS）共轭梯度法，提出了求解大规模非负约束优化问题的可行共轭梯度算法，并分析了算法在Armijo型线性搜索下的全局收敛性. 数值实例表明该算法是有效的.

关键词：非负约束优化；子空间；共轭梯度法；全局收敛性

中图分类号：O221.2文献标识码：A

非负约束优化问题广泛存在于许多学科及工程应用领域中，如：非线性回归分析、金融投资、大地测量、卫星导航等，并且有关的数据处理是非常庞大的，呈现的问题通常是大规模的. 因此，研究求解这些问题的高效算法具有重要的现实意义. 非负约束优化问题的一般形式

这里l和u是Rn中的有界向量.许多研究集中于求解大规模有界约束问题（3），人们提出了如谱梯度投影法、有限记忆拟牛顿法和共轭梯度法等有效算法＼[1， 4， 6＼].尽管问题（1）可以看作问题（3）的特殊情形，但不知这些方法能否经过适当的修改被用来求解非负约束问题.

众所周知，共轭梯度法及其修正形式是求解大规模无约束问题min f（x）， x∈Rn的有效方法＼[2， 7-8＼].因此，人们设想用共轭梯度法的思想求解约束问题. 文献＼[6＼]研究了用共轭梯度的思想求解有界约束问题（3），通过求解一个约束子问题来计算搜索方向，作者证明了在 Wolfe型线性搜索下所提出的方法是收敛的.然而已有研究表明在该研究上存在许多的困难[5].

在本文中，我们研究用共轭梯度型方法求解非负约束问题（1）. 结合已有求解有界约束问题的子空间思想[4]和求解无约束问题的LiuStorey （LS）共轭梯度法[3]，提出了一个求解问题（1）的可行LS共轭梯度法，与文献＼[6＼]的方法比较，本文提出的方法的优点是无需求解子问题，并且在Armijo搜索下具有全局收敛性，节省大量计算.

湖南大学学报（自然科学版）2014年

第7期刘陶文等：求解非负约束优化问题的可行LS共轭梯度法

证由KKT条件（2）以及（10）即可验证定理结论成立.

证毕

引理1和定理1表明，当dk=0时， xk必定是问题（1）的一个KKT点，而当dk≠0 时，必有gTkdk<0，即dk≠0是f（x）在xk处的一个下降可行方向.

2算法结构及其收敛性分析

3数值实验

在这一节，将所提出的算法应用于大地测量中数据处理问题[9]. 对一理想边坡因地质断层构成一可能的滑体，按地质学知识，滑体只能沿底盘向东北方向偏下移动. 选定三个基点，其坐标分别为A（500.00， 0， 100.00）， B（0.00， -500.00， 150.00）， C（500.00， 500.00， 200.00）. 在滑体上，取监测点P （0， 0， 100.00），分别在基点A，B，C处用边前方交会监测P点的位移（x，y，-z）， AP，BP和CP为3个观测边，且有先验信息x，y，z>0. 设观测向量为L∈R3，则有相应的误差方程：

L+V=（|AP|， |BP|， |CP|）T，

其中V为观察噪声向量. 设A，B，C 3个边观测的一次观测值分别为500.04， 502.52， 714.13. 试估计P点的位移（x， y， -z）.

当P点有位移（x， y， -z）时，观测向量L的误差方程为：

L+V=|AP||BP||CP|=

现在用可行LS共轭梯度法来求解问题（16）. 在算法1中，取初始点（x0， y0， z0）=（1， 1， 1）以及常数ρ=0.5， σ=0.001， ε=0.01. 算法1在7次迭代后求得P点位移估计（，，）=（0.022 0，0，-0.053 1），显然这一估计比文献＼[9＼]中的线性最小二乘估计（0.024 6，0，-0.064 0）更接近于实际的位移（0.004，0.02，-0.005），而且可以依据需要增加迭代次数提高精度.

参考文献

[1]BIRGIN E G， MARTINEZ J M， RAYDAN M. Nonmonotone spectral projection gradient methods on convex sets ＼[J＼]. SIAM Journal on Optimization， 2000， 10（1）： 1196-1211.

＼[2＼]DAI Y， YUAN Y. Nonlinear conjugate gradient methods ＼[M＼]. Shanghai： Shanghai Science and Technology Publisher， 2000.

＼[3＼]LIU Y， STOREY C. Efficient generated conjugate gradient algorithms Part 1： Theory ＼[J＼]. Journal of Optimization Theory and Applications， 1991， 69（1）： 129-137.

＼[4＼]NI Q， YUAN Y. A subspace limited memory quasiNewton algorithm for largescale nonlinear bound constrained optimization ＼[J＼]. Mathematics of Computation， 1997， 66（220）： 1509-1520.

＼[5＼]NOCEDAL J. Conjugate gradient methods and nonlinear optimization， In： Linear and nonlinear conjugate gradientRelated method ＼[M＼]. Philadelphia， SIAM Press， 1996， 9-23.

＼[6＼]PYTLAK R. An efficient algorithmfor largescale nonlinear programming problems with simple bounds on the variables ＼[J＼]. SIAM Journal on Optimization， 1998， 8（2）： 532-560.

＼[7＼]ZHANG L， ZHOU W J， LI D H. A descent modified PolakRebièrePolyak conjugate gradient method and its global convergence ＼[J＼]. IMA Journal of Numerical Analysis， 2006， 26（4）： 629-640.

＼[8＼]ZHANG L， JIAN S Y. Further studies on the WeiYaoLiu nonlinear conjugate gradient method ＼[J＼]. Applied Mathematics and Computation， 2013， 219 （14）： 7616-7621.

＼[9＼]宋迎春，朱建军，罗德仁，等. 附非负约束平差模型的最小二乘估计＼[J＼]. 武汉大学学报：信息科学版， 2008， 33（9）： 907-909.

SONG Yingcun， ZHU Jianjun， LUO Deren，et al. Leastsquares estimation of nonnegative constrained adjustment model ＼[J＼]. Geomatics and Information Science of Wuhan University：Information and Science， 2008， 33（9）： 907-909 .（In Chinese）

关键词：非负约束优化；子空间；共轭梯度法；全局收敛性

中图分类号：O221.2文献标识码：A

湖南大学学报（自然科学版）2014年

第7期刘陶文等：求解非负约束优化问题的可行LS共轭梯度法

证由KKT条件（2）以及（10）即可验证定理结论成立.

证毕

引理1和定理1表明，当dk=0时， xk必定是问题（1）的一个KKT点，而当dk≠0 时，必有gTkdk<0，即dk≠0是f（x）在xk处的一个下降可行方向.

2算法结构及其收敛性分析

3数值实验

L+V=（|AP|， |BP|， |CP|）T，

其中V为观察噪声向量. 设A，B，C 3个边观测的一次观测值分别为500.04， 502.52， 714.13. 试估计P点的位移（x， y， -z）.

当P点有位移（x， y， -z）时，观测向量L的误差方程为：

L+V=|AP||BP||CP|=

参考文献

[1]BIRGIN E G， MARTINEZ J M， RAYDAN M. Nonmonotone spectral projection gradient methods on convex sets ＼[J＼]. SIAM Journal on Optimization， 2000， 10（1）： 1196-1211.

＼[2＼]DAI Y， YUAN Y. Nonlinear conjugate gradient methods ＼[M＼]. Shanghai： Shanghai Science and Technology Publisher， 2000.

＼[3＼]LIU Y， STOREY C. Efficient generated conjugate gradient algorithms Part 1： Theory ＼[J＼]. Journal of Optimization Theory and Applications， 1991， 69（1）： 129-137.

＼[5＼]NOCEDAL J. Conjugate gradient methods and nonlinear optimization， In： Linear and nonlinear conjugate gradientRelated method ＼[M＼]. Philadelphia， SIAM Press， 1996， 9-23.

＼[6＼]PYTLAK R. An efficient algorithmfor largescale nonlinear programming problems with simple bounds on the variables ＼[J＼]. SIAM Journal on Optimization， 1998， 8（2）： 532-560.

＼[8＼]ZHANG L， JIAN S Y. Further studies on the WeiYaoLiu nonlinear conjugate gradient method ＼[J＼]. Applied Mathematics and Computation， 2013， 219 （14）： 7616-7621.

＼[9＼]宋迎春，朱建军，罗德仁，等. 附非负约束平差模型的最小二乘估计＼[J＼]. 武汉大学学报：信息科学版， 2008， 33（9）： 907-909.

关键词：非负约束优化；子空间；共轭梯度法；全局收敛性

中图分类号：O221.2文献标识码：A

湖南大学学报（自然科学版）2014年

第7期刘陶文等：求解非负约束优化问题的可行LS共轭梯度法

证由KKT条件（2）以及（10）即可验证定理结论成立.

证毕

引理1和定理1表明，当dk=0时， xk必定是问题（1）的一个KKT点，而当dk≠0 时，必有gTkdk<0，即dk≠0是f（x）在xk处的一个下降可行方向.

2算法结构及其收敛性分析

3数值实验

L+V=（|AP|， |BP|， |CP|）T，

其中V为观察噪声向量. 设A，B，C 3个边观测的一次观测值分别为500.04， 502.52， 714.13. 试估计P点的位移（x， y， -z）.

当P点有位移（x， y， -z）时，观测向量L的误差方程为：

L+V=|AP||BP||CP|=

参考文献

[1]BIRGIN E G， MARTINEZ J M， RAYDAN M. Nonmonotone spectral projection gradient methods on convex sets ＼[J＼]. SIAM Journal on Optimization， 2000， 10（1）： 1196-1211.

＼[2＼]DAI Y， YUAN Y. Nonlinear conjugate gradient methods ＼[M＼]. Shanghai： Shanghai Science and Technology Publisher， 2000.

＼[3＼]LIU Y， STOREY C. Efficient generated conjugate gradient algorithms Part 1： Theory ＼[J＼]. Journal of Optimization Theory and Applications， 1991， 69（1）： 129-137.

＼[5＼]NOCEDAL J. Conjugate gradient methods and nonlinear optimization， In： Linear and nonlinear conjugate gradientRelated method ＼[M＼]. Philadelphia， SIAM Press， 1996， 9-23.

＼[6＼]PYTLAK R. An efficient algorithmfor largescale nonlinear programming problems with simple bounds on the variables ＼[J＼]. SIAM Journal on Optimization， 1998， 8（2）： 532-560.

＼[8＼]ZHANG L， JIAN S Y. Further studies on the WeiYaoLiu nonlinear conjugate gradient method ＼[J＼]. Applied Mathematics and Computation， 2013， 219 （14）： 7616-7621.

＼[9＼]宋迎春，朱建军，罗德仁，等. 附非负约束平差模型的最小二乘估计＼[J＼]. 武汉大学学报：信息科学版， 2008， 33（9）： 907-909.

三维装配几何约束问题求解研究篇4

几何约束求解问题有很广泛的应用,非常有必要对几何约束问题进行广泛深入地研究。目前,针对二维几何约束求解问题的研究成果比较多,但由于三维几何约束问题比二维几何约束问题复杂得多,故目前研究成果还比较少,本文对三维几何约束求解问题进一步进行讨论,研究其求解方法。

几何约束问题求解的方法可以分为两类:一类为构造性的方法[1,2,3];另一类为数值迭代的方法[4,5,6]。构造性的方法求解比较精确、求解速度较快;数值迭代方法对大规模几何约束问题存在计算时间长、计算过程不稳定的问题。

三维几何约束问题同二维情况有所不同。一般通过对二维草图进行拉伸旋转,采用特征造型的方法建立三维实体模型,然后对三维实体模型施加几何约束进行装配。因此,一般三维几何约束问题主要指三维装配几何约束求解的问题。

1基本几何元素的求解

在不考虑自由曲面和自由曲线情况下,几何元素间的约束可以转换为点、直线、平面之间的约束。对几何元素的求解,为三维几何约束问题求解的最基本问题,大部分有精确的代数公式可以进行计算。可以分为四种基本类型问题的求解:

(1) 根据一几何元素和一已知几何元素间的几何约束求解该几何元素。

可以分为点—点(A1)、点—直线(A2)、点—平面(A3)、直线—直线(A4)、直线—平面(A5)、平面—平面(A6)共六种求解类型。直线和直线间必须存在两个约束方可以进行求解。该6种类型有解析解法。

(2) 根据一几何元素和二已知几何元素间的几何约束求解该几何元素。

对点的求解有6种类型,分别为点与上述6种类型的组合(B1～B6)。对直线的求解有3种类型,为直线与A4～A6的组合(B7～B9),对平面的求解有1种情况(B10);对直线可以用解析算法进行求解。

(3) 根据一几何元素和三已知几何元素间的几何约束求解该几何元素。

对点的求解有10种类型(C1～C10),为点与B1～B10的组合,有解析算法;对直线的求解有4种类型,,为直线与B7～B10的组合情况(C11～C14),可能需要迭代计算。

(4) 根据一几何元素和四已知几何元素间的几何约束求解该几何元素。

由于直线的空间自由度为4,因此,有可能根据其与4几何元素间的几何约束关系进行求解,需要进行迭代计算。

从上述分析可以看出,三维情况下几何元素的求解可能需要迭代计算,而二维情况下则不需要。

2二体问题求解

二体问题指两个凝聚体间的凝聚计算[7]。固定两凝聚体间自由度较大的一个,对另一个凝聚体进行移动,使约束得到满足。

图1所示的三维几何约束问题,采用传统的求解方法进行求解是比较困难的。需要对刚体的6个空间位置变量进行迭代计算,计算过程不稳定,采用类似于解决二维二体几何约束问题求解,其求解原理参见文献[8]。

3几何约束复杂耦合情况下的求解

当需要同时进行凝聚的几何体个数大于2时,为几何约束复杂耦合情况。虽然三维几何约束问题在实际工程中,很少出现复杂耦合现象,但为了几何约束求解器的普遍适用性,本文对该问题的求解进行探讨。

由于三维几何约束问题存在大量冗余现象,在GCG图中寻找最小刚体为NP难度问题,因此,依靠求解系统发现复杂耦合情况下的最小刚体比较困难。如果系统存在欠约束和冗余约束情况时,问题求解就更加困难。对于三维几何约束问题,当存在几何约束复杂耦合的时候,问题求解比二维情况要复杂得多。设计者既可以利用系统把几何约束问题分解为树状依次求解的结构,也可以自底向上进行设计,然后把子结构组合为一个整体。在二维情况下,一般采用前者,即先画出草图,然后逐步施加约束由系统对几何约束进行分解,三维情况下,一般设计出零件模型,再在装配约束下进行组装。在三维情况下存在复杂耦合问题时,可以把复杂耦合问题看成一个子装配体,用于设计图形中,并不依赖系统自动进行识别。即二维几何约束问题的GCG图的有向化一般由系统完成,而三维几何约束问题的GCG图的方向由设计者指定。

复杂耦合问题涉及到多个凝聚体间几何约束被同时满足的问题,该问题目前还没有很好的解决办法。本文引进迭代变量约束的概念求解该类问题。当复杂耦合问题发生时,设计者应该清楚地了解到该类问题的存在。如图2所示为4个刚体构成的复杂耦合几何约束问题,一条直线表示两个刚体间的约束度为1的约束,Ri表示三维刚体。当单纯刚体内部的凝聚体数超过2个时就构成了复杂耦合问题,此时,该单纯刚体内的凝聚体可以看成为并联的关系,可以从两个几何约束度最大的凝聚体开始进行装配,采用二体问题的求解方法,合适的添加几何约束进行凝聚,直到该单纯刚体中所有的节点被凝聚成一个节点,这些被添加的几何约束的值被作为变量,以凝聚过程中没有用到的几何约束作为迭代的目标函数,进行迭代计算,采用数值导数求解的方法,得到迭代计算所需导数矩阵。

实际工程中,三维复杂耦合约束问题在装配的时候,总是对每个零件分别进行装配,在两个零件装配的时候,必须完全确定另一个零件的位置。比如,对图2的问题进行装配的时候,先固定R1,然后装配R2,由于R2和R1间的几何约束不足以完全确定R2的位置,因此,必须施加一些额外的几何约束c1,这些几何约束依靠设计者交互添加,同样在对R3进行装配时候,也要施加额外的几何约束c2,在对R4进行装配的时候,指定R4由那些几何约束来确定其空间位置,那些约束c3需要通过迭代才能够满足。系统根据所添加额外的几何约束c1、c2和被指定用来进行迭代的几何约束c3进行迭代计算使约束得到满足。

这种通过设计人员通过交互方式指定用于进行迭代计算的几何约束的方法,不采用系统进行判断,可以有效降低程序的复杂性,也比较符合实际工程情况。

通过这种方法,也可以对复杂机构运动进行模拟。当所添加的用于迭代计算的几何约束的约束度大于最终作为目标函数的几何约束的约束度的时候,说明系统是不完全约束的,可以发生运动。如上述所添加的几何约束c1、c2的总的约束度大于c3,那么可以指定c1、c2中那些几何约束的值进行固定,那些几何约束的值用于迭代使约束c3得到满足,那些约束的值进行变化,使机构不断运动。

上述复杂耦合凝聚模式在进行装配求解后,可以作为子装配体,与其它子装配体进行进一步装配。

4实例

图3(a)为一飞行模拟器[7],模拟器通过6个距离约束和基座相连,通过调整距离约束的大小调整模拟器的姿态,图3(b)为其几何约束图,E11、E12、E13为模拟器上的点,E21、E22、E23为基座上的点,该几何约束问题求解采用目前的方法是难以进行的。设E11E22的长度为k1,E11E23长度为k2,E12E21长度为k3,E12E23长度为k4,E13E21的长度为k5,E13E22的长度为k6,E21E22长度为l1,E21E23长度为l2,E22E23长度为l3,基座三点间所添加的定位约束如图3(b)中细实线所示,在E13和E23间添加一迭代几何约束,长度设为a,如图3(b)中虚线所示,一点到已知三点的距离约束确定该点的函数为f,那么采用本文提出的方法有下列关系式成立:

E23=f(k2,k4,a,E11,E12,E13)

E22=f(k1,k6,l3,E11,E13,E23)

E21=f(k3,l1,l2,E12,E22,E23)

k5=E13E21

前三式代入第四式中,可得到k5和a的函数关系,k5已知时,进行方程求解可以得到a的大小。这样,可以依次求得E21、E22、E23的确定位置,进而确定飞行模拟器的空间位置。用上述函数关系还可以推导出在某特定状态时,距离约束大小的变化率和飞行模拟器速度间的关系,由于此为纯粹数学问题,本文不作详细介绍。

5结论

本文对三维几何约束求解问题进行了改进。通过空间转换的方法,可以有效减少基本几何元素的求解类型,简化程序设计,在此基础上,对二体几何约束问题的求解进行了研究,所提出的方法,可以适用于一般情况下几何约束的求解问题,通过指定用于迭代计算的几何约束和作为目标函数的几何约束,能够对复杂耦合情况下几何约束问题进行求解。实例表明本文所提出的方法可以有效解决三维几何约束问题。

参考文献

[1]Solano L,Brunet P.Constructive constraint-based model for parametricCAD system.Computer Aided Design,1994,26(8):614-621.

[2]Joan Arinyo R,Soto A.A correct rule-based geometric constraint sol-ver,Computer&Graphics 1997,21(5):599-609.

[3]Lee KY,Kwon OH,Lee JY,Kim TW.A hybrid approach to geometricconstraint solving with graph analysis and reduction.Advances in Engi-neering Software,2003,34(2):103-113.

[4]Ge Jian Xin,Chou ShangChing,Gao XiaoShan.Geometric constraintsatisfaction using optimization methods.Computer-Aided Design,1999,31(14):867-879.

[5]Liu ShengLi,Tang Min,Dong JinXiang.Solving geometric constraintswith genetic simulated annealing algorithm.Journal of Zhejiang Univer-sity.Science,2003,4(5):532-541.

[6]Lamure H,Michelucci D.Solving geometric constraints by homotopy.IEEE Trans Visual Compute Graphics 1996,2(1):28-34.

[7]Seybold B,Metzger F,Ogan G,et al.Spatial Modelling with GeometricConstraints.In 3rd International Conference of Practical Application ofConstraint Technology.The Practical Application Ltd.,Blackpool april1997:307-320.

参数化造型中的几何约束求解方法篇5

传统CAD系统无法很好的支持功能设计、概念设计等操作, 为了弥补传统CAD系统的不足, 更好地满足概念化设计的要求、提高设计效率, 在20世纪70年代, CAD系统首次引入了人工智能的思想, 其主要特征和标志为参数化和变量化技术。

参数化技术与变量化技术的核心是:当设计者指定了草图的尺寸和拓扑关系后, 系统能够自动生成相应的结果图形。这一求解过程称为几何约束求解。几何约束求解对CAD系统的性能起着至关重要的作用, 并可应用于其他众多的工程领域。

几何约束求解的数学思想是:将几何约束转化为代数方程组, 然后对方程组进行求解, 得到问题的解。几何约束涉及大量几何元素, 在转化为代数方程组时会产生大型非线性方程组。目前还没有求解大型非线性方程组的稳定方法, 为了提高求解效率、减小求解复杂度, 一个基本思想是将大型系统分解为若干个较小规模的子系统, 分别求解, 然后将各个求解结果组装为整个系统的最终解。几何约束的求解方法融合了很多领域的知识, 如几何、图论、矩阵、组合优化、人工智能和离散数学等, 根据不同的求解方式, 可将几何约束求解方法分为:基于代数的求解方法、基于几何约束图的求解方法和基于人工智能的规则推理法。

2 约束求解方法

2.1 基于代数的求解方法

基于代数的求解方法是将几何约束问题转化为非线性方程组来进行求解。这种方法利用变量和方程表达几何约束系统, 具有很强的通用性和直观性。代数求解法中常用的方法是数值法和符号法。

数值法是直接将几何约束转化为非线性方程组, 然后采用整体数值迭代求解。Newton-Raphson迭代法是使用最多的一种数值计算方法, 通过迭代过程Xk+1=Xk-J (Xk) -1F (Xk) 逐渐逼近方程组的解, 这里J (Xk) 是F (Xk) 在点Xk的Jacobi矩阵, F= (f1, f2, …, fm) T:是方程组向量, X= (x1, x2, …, xm) T是变元向量。这种方法的求解速度快, 使用范围广, 但只能求得一个解。为了求得问题的全部解, 可以将几何约束满足问题转化为优化问题进行求解。Joan利用遗传算法来求解几何约束问题, 但是这种方法只能处理规模较小的问题。欧阳应秀提出将混沌方法嵌入BFGS算法的混合求解方法, 能求解欠约束和过约束情况。

用符号法求解几何约束时, 首先将几何约束映射为代数方程组, 然后利用消元法化简代数方程组, 并采用数值回代的方法进行求解。符号法主要可以分为Grobner基法、吴方法以及结式法。高小山将吴方法应用于几何约束求解。这种方法可以判断完备约束、欠约束和过约束的情况, 但是时间复杂度和空间复杂度都较大。

2.2 基于几何约束图的求解方法

基于几何约束图的方法是对几何约束图进行分析, 将问题分解为可分别求解的子问题, 然后将各个子问题的解合并为最终问题的解。根据分析策略的不同, 可将基于几何约束图的方法分为构造法和自由度分析法。

在构造法中, 根据几何约束图的不同分解形式, 可以将构造法分为递归分割法和递归装配法。递归分割法是通过一定的规则, 将几何约束系统分割为若干子系统, 再继续递归分割各个子系统。Owen首次提出递归分割法, 该方法以图论中的关节点、双连通和三连通等概念为基础, 与深度优先搜索和广度优先搜索算法相结合, 自顶向下分割几何约束图。Joan提出了Deficit的概念, 在保持约束图的Deficit不变的条件下, 分解二叉树s-tree。张桂芳将三维完备几何约束图分解为k-连通子图, 如果其中一个子图是完备约束的, 则求解该子图后, 可以将这些子图的解合并为原问题的解。递归装配法以迭代的方式将刚性体组合成更大的刚性体。如果约束系统中包含完备约束和欠约束子系统, 则递归装配法返回一个完备约束组件的最大集合。Podgorelec通过变换点和直线之间的角度和距离约束, 将复杂约束转化为简单约束;将复杂几何元素映射为辅助线和辅助点, 来处理复杂几何元素。

Kramer以刚体运动学为基础提出了几何约束系统的自由度分析法, 给出了链路搜索和环路搜索算法, 并提出:“几何约束满足问题的核心是实现约束的最大分解”。

彭小波分析了几何约束系统的奇异性, 提出了一种基于有向约束图的欠约束系统的求解的方法, 通过分解几何约束来减小约束求解的规模。蒋丹东引入了点簇的概念, 综合了基于图和基于规则的约束求解方法, 运用图论的原理建立了基于点簇的图形约束模型。李彦涛引入形状自由度的概念, 将剪枝和凝聚相结合, 实现欠约束和完备约束系统的分解, 并使用解析法和数值法对约束进行求解。在欠约束系统分解方面, Lee将非尺规可构造构型分离出来并利用数值计算法进行求解, 利用分类规则找出欠约束子图, 并得到求解序列。Joan通过添加几何约束, 将欠约束转化为可求解的完备几何约束问题。高小山以D-Tree的分解方法为基础, 通过自动添加几何约束, 将欠约束问题转化为可求解的完备几何约束问题, 使分解后的几何约束问题具有最小的规模。

2.3 基于人工智能的规则推理法

基于人工智能的规则推理法利用谓词和一系列重写规则来构造几何元素, 从而将几何约束问题转化为可构造的形式。

Aldefeld采用基于符号推理和操作的专家系统来建立规则体系, 用一阶谓词描述几何约束关系, 然后利用推理机对知识库进行规则匹配, 从而构造出整个图形。

日本东京大学Kimura的研究小组提出了基于规则的构造方法, 通过两种方法得到约束:一种是由系统模型自动生成, 另一种是由用户交互定义。这种方法考虑了系统的多解情况, 但没有考虑约束的一致性检验问题。Verroust提出了面向规则的平行四边形变换方法, 该方法能够解决多边形的所有完备约束问题, 但应用范围有限。高曙明引入已知元素和已知约束的概念, 利用普通算法实现几何推理。Dufourd采用延拓法对几何约束系统进行自动符号推理, 并提出以树的形式表达解空间, 通过剪枝法处理多解性问题。Schreck利用距离比率约束来替换距离约束, 将几何约束问题转变为相似群中的不变形式, 并进行构造求解。Podgorelec给出了分析几何约束是否可解的规则, 并提出了简化几何约束和冗余校验的方法。Fabre将符号法和数值法相结合来简化几何约束, 但该方法仍然以牛顿迭代法为基础, 求解的稳定性和效率有待进一步提高。

3 结论

本文分析介绍了国内外现有的几何约束求解方法。几何约束求解是CAD造型系统的关键技术, 对CAD系统的性能起着至关重要的作用。在造型系统中, 合理有效的几何约束求解机制将会有效地提高造型效率。因此, 研究几何约束求解方法具有重要的现实意义。

摘要：本文介绍了参数化造型中的几何约束求解方法的发展状况, 从基于代数的求解方法、基于几何约束图的求解方法和基于人工智能的规则推理法等方面分析了目前造型系统中采用的几何约束求解方法。

关键词：约束求解,几何约束图,人工智能

参考文献

约束求解篇6

全局优化问题在科学计算、工程技术、经济管理等领域得到越来越广泛的关注和应用, 近些年来, 人们相继提出一些求解全局优化问题的算法, 填充函数法属于其中的确定型算法, 最早由Ge[1]提出, 用来求解无约束多极值函数的全局极小点。这种算法的关键是构造一个称为填充函数的辅助函数, 其基本思想是借助辅助函数, 从目标函数的当前局部极小点找到另一个目标函数值更小的局部极小点, 直至找到全局最小点为止。

Ge之后, 不少学者相继提出了不少性质良好的填充函数, 但基本上都是针对无约束优化问题的, 对于求解约束优化问题的填充函数虽有讨论, 如文献[2,3,4,5,6,7], 但都有各自不同程度的缺陷。本文在无强制性条件下给出了一类性质良好的求解带一般约束优化问题的单参数填充函数, 并讨论了其填充性质。

1 基本概念

考虑带约束全局优化问题 (P) : min f (x) , s.t.x∈S={x∈Rn|gi (x) ≤0, i∈Γ}, 其中f (x) , gi (x) , i∈Γ:Rn→R是连续可微函数, Γ={1, 2, …, m}是下标集。对上述问题假设如下。

假设1 问题 (P) 的不同局部极小点的个数可以是无限的, 但不同局部极小值个数是有限的。

假设2 用L (p) 表示问题 (P) 的局部极小点集合, 若x*是问题 (P) 的局部极小点, 则Lx*={x∈L (p) |f (x) =f (x*) }是一个有界闭集, 且问题 (P) 存在全局极小点。

注:在很多全局优化的实际问题中, f (x) 的强制性条件不一定满足, 因此这里对问题 (P) 的假设中没有考虑到目标函数f (x) 的强制性条件。下面针对问题 (P) 给出有约束优化问题的填充函数定义。

定义1[4] 函数p (x, x*, a) 称为f (x) 在局部极小点x*处的填充函数, 如果它满足:

(1) 在Rn空间中, x*是p (x, x*, a) 的严格局部极大点;

(2) 对x∈S1∩S且x≠x*或x∈Rn＼S有∇p (x, x*, a) ≠0, 这里S1={x∈Rn|f (x) ≥f (x*) };

(3) 如果x*不是全局极小点, 那么p (x, x*, a) 一定在S2={x∈S|f (x) <f (x*) }上有局部极小点。

以上定义的填充函数的意义为:对于有约束最优化问题, 首先要考虑的就是求出来的点是否可行。由条件 (2) 知, 要找的点一定在可行域内;其次, 对于全局最优化问题的填充函数法, 关心的是比当前局部极小点更好的那些点, 由条件 (2) 知, 要找的点一定不会再比当前局部极小点差的水平集上达到。若x*是局部极小点但不是全局极小点, 由定义中的条件 (1) 和条件 (3) , 则可以从x*的邻域中的任意一点出发, 用求无约束最优化问题的极小化方法极小化填充函数, 总能找到填充函数的局部极小点x*0, 由条件 (3) 知, f (x*0) <f (x*) , 再由条件 (2) , 对x∈S1∩S且x≠x*或x∈Rn＼S有∇p (x, x*, a) ≠0, 得知x*0∈S。

2 填充函数及其性质

针对问题 (P) , 设x*是当前局部极小点, 构造单参数填充函数如下。

1) p (x, x*, a) =-φ (1+‖x-x*‖3) +amin [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]。

其中a>0是参数, 函数φ (t) 满足:1) φ (0) =0, 2) φ′ (t) >0, 这样的函数有 $1 - e^{- t}, \arctan t, \frac{t}{1 + t}$ 等。

当参数a>0充分大时, 下面的几个定理表明p (x, x*, a) 是满足定义1的一类填充函数。

定理1 对任意a>0, x*是p (x, x*, a) 的严格局部极大点。

证明因为x*是f (x) 的局部极小点, 则存在它的一个邻域N (x*, δ) (δ>0) , 使得∀x∈N (x*, δ) ∩S, 有f (x) ≥f (x*) , gi (x) ≤0, i∈Γ。

下面分两种情况来证明对∀x∈N (x*, δ) , p (x, x*, a) <p (x*, x*, a) 成立。

(1) 当x∈N (x*, δ) ∩S, x≠x*时, 由于f (x) ≥f (x*) , 则有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0于是p (x, x*, a) =-φ (1+‖x-x*‖3) <-φ (1) =p (x*, x*, a) 。

(2) 当x∈N (x*, δ) ∩ (Rn＼S) 时, 则至少存在一个指标i0∈Γ, 使得gi0 (x) >0, 故min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0, 于是同 (1) 有结论成立。

综上, p (x, x*, a) <p (x*, x*, a) 对于∀x∈N (x*, δ) 都成立。因此, x*是p (x, x*, a) 的严格局部极大点。

定理2 若x*是f (x) 的局部极小点, 则p (x, x*, a) 在 (S∩S1) ＼{x*}或Rn＼S上有∇p (x, x*, a) ≠0成立。

证明易得对∀x∈S∩S1或Rn＼S都有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ) ]=0, 此时, p (x, x*, a) =-φ (1+‖x-x*‖3) , 显然∇p (x, x*, a) ≠0。

定理3 若x*是f (x) 的局部极小点, 但不是f (x) 的全局极小点, 且cl (int S) =cl (S) , 则当a>0充分大时, 一定存在x*0∈S2, 使得x*0是p (x, x*, a) 的局部极小点。

证明因为x*是f (x) 的局部极小点但非全局极小点, 则存在f (x) 的另一个局部极小点x*1, 使得f (x*1) <f (x*) , gi (x*1) ≤0, i∈Γ。

由于f (x) , gi (x) , i∈Γ是连续函数, 且cl (int S) =cl (S) , 则一定存在x*2∈Rn, 使得f (x*2) <f (x*) , gi (x*2) <0, 故有

p (x*2, x*, a) =-φ (1+‖x*2-x*‖3) +amax {f (x*2) -f (x*) , gi (x*2) , i∈Γ}。

显然Lx*1⊂S, x*2∈int S∩S2。

另一方面, 对∀x∈∂S, 至少存在一个指标i1∈Γ, 使得gi1 (x) =0, 于是当x∈∂S时有min [0, max (f (x) -f (x*) , gi (x) , i∈Γ]=0, 从而p (x, x*, a) =-φ (1+‖x-x*‖3) 。

所以, 当a>0充分大时, 对∀x∈∂S, 有p (x*2, x*, a) <p (x, x*, a) 。显然, S＼∂S是开集, 于是当a>0充分大时存在一点x*0∈S＼∂S使得

$\begin{array}{l} \min_{x \in S} p (x ‚ x^{*} ‚ a) = \min_{x \in S \partial S} p (x ‚ x^{*} ‚ a) = \\ p (x_{0}^{*} ‚ x^{*} ‚ a) \leq p (x_{2}^{*} ‚ x^{*} ‚ a) ‚ \end{array}$

故x*0∈int S, 且f (x*0) <f (x*) 。

定理4 若x*是f (x) 的全局极小点, 则对∀x∈S, x≠x*都有p (x, x*, a) <0。

证明由于x*是f (x) 的全局极小点, 则对所有的x∈S都有f (x) ≥f (x*) 成立。因此, 由定理1, 对∀x∈S, x≠x*有p (x, x*, a) <0成立。

定理5 任给x1, x2∈Rn, 若f (x1) ≥f (x*) , f (x2) ≥f (x*) , 则‖x2-x*‖>‖x1-x*‖当且仅当p (x2, x*, a) <p (x1, x*, a) 。

证明若f (x1) ≥f (x*) , f (x2) ≥f (x*) , 则min [0, max (f (xj) -f (x*) , gi (x) , i=∈Γ) ]=0, j=1, 2, 此时有p (xj, x*, a) =-φ (1+‖xj-x*‖3) , 显然有p (x2, x*, a) <p (x1, x*, a) , 反之亦然。

定理6 如果x1, x2∈Rn并且满足f (x1) ≥f (x*) ≥f (x2) 和‖x2-x*‖>‖x1-x*‖, 则p (x2, x*, a) <p (x1, x*, a) 。

证明由条件, p (x2, x*, a) =-φ (1+‖x2-x*‖3) +amax [f (x2) -f (x*) , gi (x2) , i∈Γ]。

且p (x1, x*, a) =-φ (1+‖x1-x*‖3) , 显然结论是成立的。

注:定理4-定理6说明目标函数当前的极小点x*被淘汰, 而新的填充函数的极小点将会被找到, 并且目标函数在这个点的函数值不比当前极小点处的函数值大。这也正是本文的填充函数所具有的良好性质之一。

3 算法和数值实验

3.1 算法

根据上述理论, 参考文献[7]给出下述算法。

(0) 初始步:选取初始点xk∈S;选取A>0作为可接受的终止参数;令a=1, k=1;

(1) 以xk为初始点, 应用局部下降算法求得问题 (P) 的一个局部极小点, 记作x*k;

(2) 选取初始点列{x $_{k + 1}^{i}$ :i∈Γ}, 使得对于某个δk>0有x $_{k + 1}^{i}$ ∈S＼N (x*k, δk) ;

(3) 令i=1;

(4) 若i≤m, 令x=x $_{k + 1}^{i}$ , 转步 (5) ;否则, 转步 (7) ;

(5) 若f (x) <f (x*k) , 且x∈S, 则以x为初始点, 应用已有局部下降算法求问题 (P) 的局部极小点x*k+1, 使得f (x*k+1) <f (x*k) , 令x*k=x*k+1, k=k+1, 转步 (2) ;否则, 转步 (6) ;

(6) 沿方向D1=-∇p (x, x*k, a) 或者 $D_{2} = - \frac{\nabla f (x)}{∥ \nabla f (x) ∥} - \frac{\nabla p (x, x_{k}^{*}, a)}{∥ \nabla p (x, x_{k}^{*}, a) ∥}$ , 找到一个新的点x, 使得p (x, x*, a) 能下降到一定程度。若在极小化过程中, x超出S的边界, 则令i=i+1, 转步 (4) , 否则, 转步 (5) ;

(7) 令a=2a。若a≤A, 转步 (3) ;否则, 算法终止, 视x*k为问题 (P) 的全局极小点。

注:下降方向D1、D2的合理性及优越性在文献[7]中有详细的说明, 不再赘述。

3.2 实验

通过两个算例的数值实验验证算法的可行性与有效性。算例都是在Matlab7.1.0运行环境中实现的。

算例1

$\min f (x) = 4 x_{1}^{2} - 4 x_{2}^{2} + 4 x_{2}^{4} - 2.1 x_{1}^{4} + \frac{1}{3} x_{1}^{6} - x_{1} x_{2}$

$s . t . x \in {(x_{1} ‚ x_{2}) | - 3 \leq x_{1} ‚ x_{2} \leq 3}$ 全局极小点x*= (0.090 1, 0.712 2) T, 全局极小值f (x*) =-1.133 1。

算例2

min f (x) = (x $_{1}^{6}$ -16x $_{1}^{5}$ +86x $_{1}^{4}$ -176x $_{1}^{3}$ +105x $_{1}^{2}$ ) /100+x $_{2}^{2}$ (x $_{2}^{2}$ -6x2+8) (x $_{2}^{2}$ -14x2+48) /100。

$s . t . x \in {(x_{1} ‚ x_{2}) | x_{1} + x_{2} \leq 10 ‚ x_{1} ‚ x_{2} \geq 0 ‚ 0 \leq x_{1} ‚ x_{2} \leq 8}$ 。

全局极小点x*= (2.174 0, 7.341 9) T, 全局极小值f (x*) =-9.123 1。

用k表示迭代次数, xk1表示第k次迭代初始点, x*k表示第k次迭代的局部最优解。迭代过程见表1。

参考文献

[1] Ge R P, Qin Y F. A class of filled functions for finding a global minimizer of a function of several variables.Journal of Optimization Theory and Applications, 1987;54 (2) :241—252

[2]Yang Yongjian, Shang Youlin.A filled function method for uncon-strained global optimization.Shanghai:Science College, Shanghai Univevs:ty, 2006;503—504

[3] Zhang L S, Kong Chi, Duan N G, et al.A new filled function method for global optimization.Global Optim, 2004;28:17—43

[4] Wang Weixiang, Shang Youlin, Zhang Liansheng. A filled function method with one parameter for box constrained global optimization.Applied Mathematics and Computation, 2007;194:54—66

[5] Wang Changyu, Li Duan. Unified theory of augmented Lagrangian methods for constrain-ed global optimization.J Glob Optim, 2009;44:433—458

[6] Wang Weixiang, Shang Youlin, Zhang Liansheng. A filled function method with one parameter for constrained global optim-ization.Journal of Engineering Mathemati-cs, 2008;25 (5) :795—803

约束求解篇7

1 问题描述及建模

设G=(V,A)为有向网络图，V={v1,v2,…,vn}为节点集合，A={aij|aij=(vi,vj),vi,vj∈V}为有向边集合。R为资源种类集合，|R|≥1。Wr为资源r(r∈R)的消耗量上限。对G中的每一条有向边aij∈A，定义长度为cij(cij≥0)，资源消耗向量为wij={w1ij,w2ij,…,wrij}，且wrij≥0(∀r∈R)。令P为G中的一条路径，A(P)为组成路径的有向边集合，定义路径的长度路径的资源消耗向量则约束最短路问题可以描述为在指定的两个节点之间寻找一条路径P，使得C(P)最小且

为求解该问题，不妨设v1和vn分别代表起点和终点。并引入决策变量xij，若有向边aij包含在路径中，xij=1;反之，xij=0。那么，问题可以表示为：

式(1)为目标函数，要求路径的长度最小。式(2)～式(4)为流平衡约束。式(5)为资源消耗约束，要求路径的资源消耗量不得超过规定的上限。式(6)为变量取值约束。

2 求解算法

2.1 相关定义

介绍标号设定算法之前，先给出如下定义：

定义1令Pi为由起点至节点vi的一条代价为c(Pi)和资源消耗向量为w(Pi)的路径，路径Pi的标号L(Pi)=(c(Pi),w1(Pi),…,wr(Pi))。节点的不同标号对应着从起点到该节点的不同路径。

定义2令L(Pi)和L(Pi’)为自起点到节点vi的两条不同路径Pi和Pi’各自对应的标号。若c(Pi)≤c(Pi’)，w1(Pi)≤w1(Pi’)，…，wr(Pi)≤wr(Pi’)，且两个标号不相等，称L(Pi)支配L(Pi’)。

定义3若对∀r∈R，路径P的资源消耗量不大于Wr，即称路径P为可行路径，称其对应的标号L(Pi)为可行标号。

定义3令节点vi的可行标号为L(Pi)，且未被节点的其它标号支配，称L(Pi)为有效标号，称其对应的可行路径Pi为有效路径。

定义5令节点vi的标号为L(Pi)，对于有向边aij∈A，扩展标号L(Pi)就是生成节点vj的标号L(Pj)=(c(Pi)+cij,w1(Pi)+w1ij,…,wr(Pi)+wrij)，记为L(Pi)aij。

2.2 算法流程

基于上述定义，标号设定算法的基本思想是遍历生成G中所有节点的有效标号。对节点vi，令Ui为所有标号的集合，Di为已扩展标号的集合。初始化起点的标号为(0,…,0)，其它节点的标号集合为空。算法迭代的由集合中选择标号L(Pi)，将其加入Di，并沿有向边aij扩展L(Pi)生成L(Pj)，若L(Pj)为有效标号，则将其加入Uj，并删除Uj中被L(Pj)支配的标号，直至算法的关键步骤为选择标号、标号扩展和标号支配检查。

1、选择标号：为提高算法寻优效率，本文提出一种凝聚函数以选择将被扩展的标号。

定义6令L(Pi)为节点vi的标号，L(Pi)的凝聚函数F(Pi)=α1c(Pi)+α2w1(Pi)+…+αr+1wr(Pi)。其中，α1,…,αr+1为权重系数。

算法由集合中选择凝聚函数值最小的标号进行扩展。

2、标号扩展：将节点vi的标号L(Pi)沿有向边aij∈A扩展，生成节点vj的标号L(Pj)。并检查L(Pj)是否为可行标号，即对∀r∈R，是否满足wr(Pi)+wrij≤Wr。

3、标号支配检查：判断L(Pj)是否被Uj中的标号支配。若被支配，删除该标号;反之，保存L(Pj)至Uj，并将Uj中被L(Pj)支配的标号删除。

得标号设定算法的具体步骤为：

步骤1初始化，令

步骤2判断是否为空集。若是，算法结束，根据vn的有效标号可以获得满足资源约束的最短路径;否则转到步骤3。

步骤3选择标号L(Pi)，满足

步骤4遍历aij∈A,L(Pj)=L(Pi)aij，若L(Pj)为可行标号，转到步骤5。遍历结束，转到步骤6。

步骤5若L(Pj)被Uj中的标号支配，删除该标号;否则，L(Pj)为有效标号，Uj=Uj∪{L(Pj)}，并将Uj中被L(Pj)支配的标号删除。转到步骤4。

步骤6 Di=Di∪{L(Pi)}，转到步骤2。

3 实验与结果分析

3.1 实验

为了验证本文提出算法的有效性，随机生成三个有向网络图作为算例进行实验。算例的相关统计数据如表1所示。其中，|V|、|A|和|R|分别表示节点数量、有向边数量和资源种类数量。

为比较算法性能，引入选择字典序最小的标号进行扩展的标号算法[6](LLSA)，将其与本文算法(ALSA)一起求解上述算例。

计算平台：Intel 3.00 GHz CPU+1G RAM+Win XP。采用MATLAB编码。

4.2 结果分析

表2记录了算法求解结果。其中，S为最优解的长度，P为标号扩展次数，T为计算时间，单位为s。可以看出，网络规模较小时，两种算法均可在较短时间内生成满足资源消耗约束的最短路径;但随着网络规模的扩大，ALSA的计算时间和标号扩展次数逐渐少于LLSA。可见，ALSA的算法性能优于LLSA;引入凝聚函数能够有效加快算法收敛速度、减少计算量。

5 结论

约束最短路问题是网络分析中的一个重要问题，被应用于现实生活中的诸多领域。本文采用标号设定算法求解约束最短路问题，设计一种凝聚函数以确定标号扩展次序，避免生成未来将被支配的标号，达到改善算法性能的目的。实验结果表明，改进的标号设定算法能够有效求解约束最短路问题。

摘要：为了提高标号设定算法求解约束最短路问题时的寻优效率,引入一种凝聚函数,综合考虑长度因素和资源消耗因素以确定标号扩展次序,避免生成将被支配的标号,达到改善算法收敛速度、减少计算量的目的。实验结果表明:改进的标号算法能够有效求解约束最短路问题。

关键词：约束最短路径,标号设定,凝聚函数,有效标号

参考文献

[1]罗宏伟,吴斌,况中林,等.快速启发式多约束优化路径算法研究[J].自动化与仪表,2008,9(1):5-8.

[2]胡耀民,刘伟铭.多约束最短路径模型与求解[J].湖南科技大学学报:自然科学版,2010,25(1):87-90.

[3]何方国,齐欢,范琼.有约束的随机最短路问题模型及算法[J].武汉理工大学学报(交通科学与工程版),2008,32(6):1125-1128.

[4]宿洁,韩强.一类多约束最短路问题的模拟退火算法[J].计算机工程,2004,30(19):21-22.

[5]王莹,刘军,苗建瑞.客运专线乘务交路计划编制的优化模型和算法[J].铁道学报,2009,31(1):15-19.

[6]Boland N,Dethridge J,Dumitrescu I.Accelerated label setting algorithms for the elementary resource constrained shortest path problem[J].Operations Research Letters,2006,34(1):58-68.

约束求解篇8

程序分析技术可用于检验程序的正确性。程序分析分为动态分析和静态分析。动态分析是指通过执行被测程序来观察其行为是否满足要求。静态分析是指在不执行被测程序的情况下,验证程序代码是否符合正确性、安全性等指标。相比动态分析,静态分析可以尽早地发现软件漏洞及缺陷,并验证更多的程序路径[1]。

从较早的静态分析工具Lint[2],到如今的Java Path Finder( JPF)[3],近年来涌现出一批优秀的静态分析工具。静态分析过去大多应用于软件,然而在硬件设计中也需要大量验证测试工作以确保硬件逻辑正确性。静态验证的引入可提高硬件设计阶段的错误检测能力。

本文提出一种基于静态分析的硬件设计正确性分析方法,并用布尔求解过程实现了对Verilog程序中寄存器数组越界行为的检测。实现难点在于: 1) 传统的程序静态分析技术针对顺序语句,在硬件设计语言中需考察不同类型赋值语句的并发行为。2) 程序设计中存在对同一变量多次赋值,如何在编码过程中确保上下文信息完整并避免赋值冲突。

1 Verilog HDL赋值语句语义

1. 1 赋值语句

根据IEEE 1364 标准,Verilog包含连续赋值和过程性赋值两种赋值语句。其中连续赋值语句由关键字assign引导,一般用以描述组合逻辑电路,完成连续赋值语句的声明后赋值关系不再改变; always语句块中的赋值语句为过程性赋值,主要运用于寄存器类型变量的赋值操作,该赋值语句中左值在程序中能被再次赋值。

1. 2 Verilog HDL代码分析

例1 Verilog程序片段1

1.module top(in1,in2);

2.input[7:0]in1,in2;

3.reg[99:0]arr;

4.reg r1;

5.integer index;

6.wire[7:0]cond1,cond2;

7.assign cond1=in1;

8.always@(*)

9.begin

10.cond2 = in2;

11.if(cond1>cond2)

12.index=16;

13.else

14.index = 256;

15.r1=arr[index];

16.end

17.endmodule

例1 中,语句7 是连续赋值语句,语句12 和语句14 是过程性赋值语句,这两种赋值语句并发执行; 由于变量cond1,cond2分别被输入类型变量in1,in2 赋值,语句11 中布尔值( cond1 >cond2) 不能预先确定。若( cond1 > cond2) 取非,程序将进入假分支,index取值256,这将导致语句15 中寄存器数组arr位索引越界。

2静态分析的理论基础

2. 1 模型检验与符号执行

模型检验是用状态迁移系统( M) 表示系统的行为,用模态逻辑公式( p) 描述系统的性质,并检验系统M是否满足性质p,用公式表示即M ╞ p,并可通过反例生成可得到公式p不满足时系统M的状态。

符号执行是一种基于模型检验的静态分析技术。使用符号执行技术分析程序时,使用符号值替换具体值作为输入,在达到目标代码时,分析工具可以得到相应的路径约束,再通过约束求解器来得到触发目标代码的具体值[4]。JPF是近年来热门的基于符号执行的验证工具,它实现了对可执行Java二进制代码程序系统的验证[5]。JPF从系统上探测程序所有可能的执行路径,以检查是否存在异常。

本文将基于模型检验的理论基础,采用符号执行的方法对Verilog程序进行分析。分析过程分为建模、规约和验证三个阶段,描述如下:

SAT ( M &! p)

其中M为路径约束和赋值关系,p为待检验属性的描述,SAT( M &! p) 检验在模型M中性质p是否可能不成立。

例1 中,我们设计模型M可表示为以下语句的合取,记为M0:

1.(cond1==in1)2.(cond2==in2)

3.(!(cond1>cond2))4.(index=256)

其中,子句3 是程序路径约束; 子句1,2,4 是赋值关系,包含连续性赋值和过程性赋值。

由例1 中语句3 可知,寄存器数组arr的合法取值范围是[99,0],对应的( ! p) 即( index < 0 | index > 100) ,记为p0。此时,若( M0&! p0) 可满足,则可以判定越界行为存在,并在此基础上生成反例。

2. 2 布尔问题求解过程

布尔可满足性问题SAT( Boolean satisfiability problem) 即判定给定的布尔方程式是否存在一组变量赋值,使问题为可满足[6]。可满足性问题求解器( SAT Solver)[7]能实现对上述问题的求解。

在例1 中,我们将上述模型M0与期望性质p0进行合取,得到以下表达式:

(cond1==in1)&(cond2==in2)&!(cond1>cond2)&(index==256)&(index<0|index>100)

将上述布尔表达式作为SAT Solver的输入,经SAT Solver求解可判定index是否越界: 若SAT Solver判定结果为“可满足”,则越界行为存在,并由SAT Solver给出待检测属性p的反例; 若判定结果为“不满足”,则可判定越界行为不会被触发。

3 实现过程描述

3. 1 并发赋值语句的编码框架

如图1 所示,实现过程将分为三个步骤: 变量表预处理、恒定赋值关系编码和always块的编码。变量表预处理完成变量到其编码的映射; 恒定赋值关系编码完成对持续性赋值和常量声明的编码; always块编码完成过程块的编码,包括过程赋值,条件语句等。

恒定赋值与always块中的赋值语句存在以下差异: 恒定赋值关系在语句声明后,不允许对左值更新赋值,而在always块中可存在对同一变量的多次赋值。根据此特点,采用图1 所示的分步编码方法以实现两种不同赋值行为的并发。并为always块中同一变量的多次赋值保存完整赋值关系,处理其赋值冲突。

为实现图1 所示的流程,我们首先定义三元组< T,P,L > ,其中T代表变量配置表,P代表路径节点,L代表路径查询表。变量配置表T记录变量到其编码的映射v→E( v) ,E( v) 是对v进行符号编码的表示; 路径节点P保存二元组< data,parent > ,其中data表示当前表达式的编码,parent表示前驱路径节点; 路径查询表L记录程序中所有表达式到路径节点P的映射。

以下通过例2对图1所示的编码过程进行说明。

例2程序片段2

1.wire a,b;

2.reg x,m,n;

3.assign a=b;

4.always@(*)

5.x=m;

6.…

7.x = n;

3. 2 变量表预处理

通过遍历模块中的变量声明,建立变量表T。

在例2中,建立得到的T如下所示:

3. 3 恒定赋值关系处理

处理恒定赋值时,先对恒定赋值关系编码,用得到的编码值更新P的data域,并在parent域中记录上一赋值语句。此外,在L中记录语句左值到P的映射,从而在访问到变量a时获得其赋值关系。

例2 中,处理语句3 后的P如下所示,记为P0:

由于语句3是第一次恒定赋值,前驱路径节点记为空。

得到P0后,更新路径查询表L为:<a→P0>。

3. 4 Always块编码

在Verilog的always块中,可能会对同一变量多次赋值。在语句编码过程中,对同一变量多次赋值的行为将导致赋值关系冲突。为此,我们采取变量拷贝的策略来解决赋值冲突,并建立动态映射表Ttmp,以记录变量到编码的最新映射关系。

例2 中出现了对x二次赋值。执行语句5 时,建立P1

执行至语句5 时,创建x的拷贝x_1,同时在Ttmp中更新x的映射为x→E( x_1) ,并规定在查询变量编码时优先访问临时映射表,这样可确保变量得到最新赋值,并能避免复制冲突。语句7 执行完成后的P、Ttmp和L如下所示:

3. 5 表达式编码

encode_exp处理表达式编码,它接受输入四元组< exp,T,P,L > ,其中exp为待编码表达式。函数返回更新后的三元组< T,P,L > ,encode_exp以如下方式递归调用:

1) 单目运算表达式

函数输入< u_op( exp) ,T0,P0,L0> ,其中u_op( exp) 表示单目运算表达式,如对表达式逻辑取非、按位取反等; T0,P0,L0分别为输入的变量配置表,当前路径节点和路径查询表。我们首先调用encode_exp对exp进行编码,得到中间输出< T0,P1,L1> ,其中P1. data记录exp的编码结果。E ( u _op ( P1. data) ) 表示对P1. data做单目运算操作后的编码,并以此作为当前路径节点的更新值Pret。然后将当前表达式到Pret的映射加入L1,得到路径查询表的更新Lret。最后将三元组< T0,Pret,Lret>作为函数输出。

2) 双目运算表达式

对双目运算表达式的处理过程中,我们分别对双目操作符的左右操作数分别进行编码,其中左操作数的输出将成为右操作数的输入参数,以使P和L得到及时更新。最后用双目运算的编码值E( P1. data bi_op P2. data) 更新P,并将编码映射关系记录到L中。

3) 条件表达式

处理条件语句时,我们把条件表达式作为真分支的路径约束,即把b编码输出的三元组< T0,P1,L1> 作为对a编码时的输入; 再将条件表达式取反,作为假分支的路径约束,即将! b编码输出的三元组< T0,P!b,L! b > 作为c编码时的输入。然后对条件语句编码,以此更新当前路径节点。

3. 6 赋值语句编码

encode_stat处理赋值语句编码,包括恒定赋值关系、过程赋值语句和条件语句。encode_stat以< stat,T,P,L > 为输入,其中stat为赋值语句,输出更新后的三元组< T,P,L > 。

1) 恒等赋值关系( 常数声明、连续性赋值语句)

对恒等赋值关系处理时,分别对赋值语句左值和右值分别编码,接着为他们建立等式关系的编码E( P1. data = = P2. data) ,并记录在当前路径节点的data域。

2) 过程式赋值语句

对过程式赋值语句处理时,我们在T1中创建等式左值的拷贝,; 然后为该拷贝与等式右值建立等式关系,即E( a': = exp) 并以此更新P。通过变量拷贝的方式,可以在避免复制冲突的前提下,保存多次赋值关系。

3) 条件语句

条件语句的编码过程与条件表达式类似,但编码结束时需要对条件语句块中的语句进行合并操作: 对于变量x,若在Ta和Tb中的编码都不一致,则x取条件值Tt( x) bTf( x) ; 若在Ta或Tb有一项编码不一致,则x取相应的条件值T0( x)bTf( x) 或Tt( x) bT0( x) ; 若在Ta和Tb中x的编码均一致,则对x不作处理。对所有更新后的变量合取后,更新当前路径节点Pret。

4)顺序语句

处理顺序语句时,将前一语句输出的三元组< T,P,L > 作为后一语句的输入参数。处理顺序语句块时,通过递归调用该编码函数记录顺序语句块中的赋值关系。

4 实例研究

本节将结合例1 具体描述我们设计的方法。在该程序中包含了连续性语句与过程模块的并发,我们将考察语句15 中索引值index是否可能超出寄存器arr的范围。本实例的验证过程采用了可满足模理论求解工具Boolector[8]。

第一步创建变量配置表T。通过遍历模块,在T中加入变量声明:

第二步处理恒定赋值关系。语句7 是连续性赋值语句,对语句7 编码后得到P的更新:

第三步对过程模块编码。处理语句10 时,建立新的路径节点P1:

处理语句11 时,建立路径约束节点P2和P3,表示约束取真或约束取非:

语句11—15 是条件语句块,我们分别对真假分支语句块处理,最后对其进行合并操作。

处理至条件分支语句12 时,index被第二次赋值,为此我们分别更新Ttmp,P:

处理至条件分支语句14 时,index被第三次赋值,更新Ttmp和P为:

最后合并分支语句。创建index的编码拷贝index_3,为index_3 建立与条件选择表达式的等式关系,Ttmp与P更新如下:

此时已经获取了index的所有赋值关系和路径约束。待考察的index的越界行为即:

在验证过程中,将路径约束和赋值关系与p合取后作为求解工具Boolector的输入,Boolector通过求解验证给出“可满足”的结论,从而判定程序中index存在越界行为。

通过Boolector考察对index产生影响的变量集合{ in1,in2} ,得到一组造成越界行为产生的输入值:

上述过程有效地验证了例1 中程序的正确性,并发现了例1 中存在的潜在错误隐患。

5 结语

静态分析是程序正确性分析的重要手段,我们将静态分析方法应用于硬件设计阶段,以发现硬件设计时的逻辑错误。本文提出了基于模型检验的硬件验证方法,通过符号执行与布尔求解过程分析了寄存器数组越界行为,尽早地发现并定位了程序设计中的缺陷。在今后的工作中,我们将对Verilog程序中的函数及任务调用进行处理,进一步研究静态分析方法在硬件设计中的应用。

参考文献

[1]Bessey A,Block K,Chelf B,et al.A few billion lines of code later:using static analysis to find bugs in the real world[J].Communications of the ACM,2010,53(2):66-75.

[2]Boe B,Hill C,Len M,et al.Hairball:Lint-inspired static analysis of scratch projects[C]//Proceeding of the 44th ACM technical symposium on Computer science education.ACM,2013:215-220.

[3]Pǎsǎreanu C S,Rungta N.Symbolic Path Finder:symbolic execution of Java bytecode[C]//Proceedings of the IEEE/ACM international conference on Automated software engineering.ACM,2010:179-180.

[4]Tillmann N,Grieskamp W,Schulte W.Symbolic execution of object oriented programs with axiomatic summaries:U.S.Patent 8,046,746[P].2011-10-25.

[5]Zhang X,van Breugel F.Model checking randomized algorithms with java pathfinder[C]//Quantitative Evaluation of Systems(QEST),2010 Seventh International Conference on the.IEEE,2010:157-158.

[6]张建民,沈胜宇,李思昆.可满足性求解技术研究[J].计算机工程与科学,2010,31(1):50-54.

[7]Jarvisalo M,Le Berre D,Roussel O,et al.The international SAT solver competitions[J].AI Magazine,2012,33(1):89-92.

约束求解篇9

求解如下一般形式的非线性规划全局优化问题: (P0) minx∈Rnf (x) 在许多领域有广泛的应用, 如机算机科学, 经济管理, 资源管理, 工程设计等。自70年代以来, 有关全局最优化的新的理论及计算方法层出不穷[1,2,3,4,5,6]。在这些新的理论及计算方法中, 由Levy和Montalvo提出的打洞算法和由西安交通大学的葛仁溥教授等人提出的填充函数法是两个特别有用的求解非线性规划全局优化问题的方法, 它解决了如何从一个局部极小解出发找到更好的局部极小解的问题。在本文中, 把上述求解元约束全局优化问题的填充函数法思想拓广到有约束的全局优化问题中, 提出了求解有约束非线性规划全局优化的拟填充变换函数方法。拟填充变换函数法由一系列循环组成, 每个循环包括两阶段:极小化目标函数阶段和极小化变换函数阶段。这两个阶段交替进行直到找到全局最优解或近似全局最优解为止。在引进了有约束非线性规划全局优化的拟填充变换函数的概念, 提出了拟填充变换函数并详细讨论了其性质。按照拟填充变换函数的理论性质, 设计了一个算法, 给出了数值实验结果, 结果表明所给的方法是有效的。

1拟填充变换函数和它的性质

考虑问题

(1) 式中X是一个有界闭箱, 且其内部intX≠θ, f (x) , gi (x) , i=1, …, m:X→R是连续可微函数。本文总是认为以下假设成立:

(1) f (x) 只有有限个不同的极小值。

(2) 问题 (P) 的可行域S⊆intX。

(3) intS的闭包等于S的闭包, 即cl (intS) =clS。

下面给出问题 (P) 在给定的局部极小点处的拟填充变换函数的定义。

定义:函数T (x, x*) 称为f (x) 在局部极小点x*处的拟填充变换函数, 如果满足:

(1) T (x, x*) 在Xx∈S:f (x) <f (x*) }上的梯度不等于零。

(2) 如果x*不是全局极小点, 那么T (x, x*) 一定在S2={x|f (x) <f (x*) , x∈S}上有局部极小点。

现在给出问题 (P) 在局部极小点x*处的一个拟填充变换函数如下:

这里x0∈RnX是一个预置固定点。

下面将证明当h>0充分大时, T (x, x*, h) 是一个拟填充变换函数。

定理1:对任意h>0, T (x, x*, h) 在Xx∈S:f (x) <f (x*) }上梯度不等于零。

证明:当x∈Xx∈S:f (x) <f (x*) }, 即x∈{x∈S:f (x) ≥f (x*) }或x∈XS, 则有

于是

因而

定理得证。

定理2:设x*不是问题 (P) 的全局极小点, 假定cl (intS) =clS。如果h>0充分大, 那么存在一点x′∈S, 使f (x′) <f (x*) , x′是T (x, x*, h) 的局部极小点。

证明:因为x*不是问题 (P) 的全局极小点, 则一定存在 (P) 的另外一个局部极小点x*1, 使

由于f (x) , gi (x) , i=1, 2, …, m是连续可微函数, 且cl (intS) =clS, 则存在一点 $\bar{x_{1}^{*}} \in X$ 使

成立。

可以得到

假设

那么

因此, 存在一点x′∈X使

因为当x∈XS或x∈{x∈S:f (x) ≥f (x*) }或x∈∂S时, 这里∂S记为S的边界, 故有

所以x′∈intS⊆f (x′) <f (x*) 。

定理得证。

2拟填充换函数算法和数值结果

根据上述拟填充变换函数的理论性质, 现提出了下列拟填充变换函数算法。

(1) 初始步:

选取一个初始点x0∈RnX, 使对任意x∈X, 有‖x-x0‖≥1。选取hU>0作为可接收的终止参数。选取一个初始点x0∈X。令h=1及k=1。

(2) 从x0出发, 用罚函数法或SQP法或其它可行方向法求得问题 (P) 的一个最优解x*k。

(3) 选取一串初始点{x $_{k + 1}^{(0) i}$ :i=1, 2, …, r}使得对某些ϵk>0, 有x $_{k + 1}^{(0) i}$ ∈XN (x*k, ϵk) 。

(4) 置i=1。

(5) 如果i≤r, 令x=x $_{k + 1}^{(0) i}$ , 转步 (6) ;否则, 转步 (8) 。

(6) 如果f (x) <f (x*) 且x∈S, 则令x作为初始点去用罚函数法或SQP法或其它可行方向法求得问题 (P) 的一个最优解x*k+1, 使得f (x*k+1) <f (x*k) 且x*k+1∈S。然后令k=:k+1, 转步 (3) ;否则, 转步 (7) 。

(7) 沿方向D=-ᐁT (x, x*k, h) , 找到一个新的点x, 使得T (x, x*k, h) 能下降到一定程度。在极小化过程中, 如果x到达X的边界, 则令i:=i+1, 转步 (5) ;否则, 转步 (6) 。

(8) 置h=10h。如果h≤hU, 转步 (4) ;否则, 算法终止, 把x*k视为原问题的一个全局极小点。

根据上述拟填充变换函数算法, 对以下经典算例进行了数值试验。计算结果表明本文所给出的变换函数算法是有效的。

算例1:

全局极小点是:

算例2:

全局极小点是:

算例3:

全局极小点是:x*= (0.109 001 8, -0.622 339 7) ,

f (x*) =-0.971 103 2。上述3个算列的具体迭代过程见下面表1, 2, 3。

3结论

在本文中, 对于连续全局最优化问题 (P) , 给出了求解有约束的全局优化的拟填充变换函数方法, 讨论了所构造的变换函数的几个性质, 按照其理论性质设计了一个变换函数算法, 并进行了数值试验。数值实验表明, 所给的方法是有效的。

摘要：给出了求解一般的有约束非线性规划问题全局最优解的拟填充变换函数方法, 而且讨论了所构造的变换函数的几个性质, 按照其理论性质设计了一个变换函数算法, 并进行了数值试验。数值实验表明, 所给的方法是有效的。

关键词：非线性规划,有约束全局优化,拟填充换函数法

参考文献

[1] Ge P R, A filled function method for finding a global minimzer of a function of several variables, Mathematical Programming, 1990;46:191—204

[2]Shang Y L, Wang W X, A class of generalized filled function for un-constrained global optimization, Applied Mathematics E-Notes, 2007; (7) :147—153

[3]Zhang L S, Ng C K, Li D, et al, Anewfilled function method for glob-al optimization, J.of Global Optimization, 2004;28:17—43

[4] Yang Y J, Shang Y L, A new filled function method for unconstrained global optimization, Applied Mathematics and Computation, 2006;173:501—512

[5]Levy A V, Montalvo A.The tunneling algorithm for the global minimi-zation of functions, SIAMJournal on Scientific and Statistical Compu-ting, 1985;6 (1) :15—29

【约束求解】推荐阅读：

求解约束最优化问题KKT系统的BFGS方法07-08

一种改进的蚁群算法用于灰色约束非线性规划问题求解08-28

混合求解07-28

优化求解08-15

函数求解09-30

联合求解10-23

规划求解法10-17

求解新方法07-24

线性优化求解09-07

求解视角论文09-14

>> 查看更多相关文档