符号几何规划问题的求解新方法-论文.pdf

《符号几何规划问题的求解新方法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第22卷第2期河南机电高等专科学校学报Vo1．22№．22014年3月JournalofHenanMechanicalandElectricalEngineeringCollegeMar．2014符号几何规划问题的求解新方法靳利(河南机电高等专科学校基础部，河南新乡453000)摘要：对符号几何规划问题，给出一种求其全局最优解的分支定界算法。利用不同的凸化方法将算法中关键的定下界操作转化为易于求解的凸规划问题。最后给出算法的收敛性证明和数值实验结果。关键词：符号几何规划；凸化方法；分支定界中图分类号：O221．2文献标识码：A文章编号：1008—2093(

2、2014)02—0048—03性质1当n≥0，S≥0，rj∈R时，函数a1引言考虑问题：}在R上是凸的。SGP(S)minF。(z)性质2当n≤0，≥0且R一∑r≤1时，函S．t．F()≤0，一1，⋯，M数ax?z⋯zr在R上是凸的。l∈S。一{zl00，ri+1，

3、⋯，<0。下面分两种情集，m一0，1，⋯，M。况对多项式项分别进行凸化：SGP问题广泛应用于产品计划、生产管理、化(1)当n>0时，令z一1，i一1，⋯，J，则有：学平衡等实际问题中。但由于SGP问题是一个N—P难问题，使得求解起来十分困难。文献给f]．．一一1，⋯出了几个求SGP问题全局解的线性化松弛方法。⋯曲㈢1【一本文提出了一种新的分支定界算法。首先采用不xr1⋯x_rJz斩·⋯同的变量变换对多项式项进行凸化，接着对转化后(2)当a<0时，令z一x方，i一1，⋯，，z一的问题进行凸下界估计，建立SGP的凸松弛规划问题，然后通过对凸松弛问题的可行域进行

4、矩形对x击，i—J+1，⋯，，其中R一∑11，则：分把原问题的求解转化为求解一系列的凸松弛规船iz⋯xrn㈢划问题，最后从理论上证明了算法的收敛性。数值f．37一X声，i一1，⋯，J；z一X_壶，i—J+1，⋯，7z算例表明该方法是有效可行的。1。x⋯xx⋯x2松弛凸规划注：在(2)中，若R<1，只对带负指数的变量为求解问题SGP，首先对SGP问题中的多项按上述方法变换。式项进行凸化。首先给出如下性质：综合以上情况，对于多项式项-厂(z)一-z。*收稿日期：2013-10—13作者简介：靳利(1977一)，女，河南焦作人，讲师，硕士研究生，主要从事最优化理

5、论及应用研究。48靳利：符号几何规划问题的求解新方法⋯z给出如下凸化规则。对问题SGP中的符号项分别采用凸化规则和规则1当n≥0，rl≤0，i一1，⋯，时，厂(z)由定理1、2中对应的凸化方法。从而得到问题SGP性质1知在R阜上是凸的，不需凸化。的松弛凸规划问题RCP，为便于表示，不妨记为：规则2当口>0，<0，i一1，⋯，J，r>0，i—RCP(So)minRo(2)S．t．R，(2)≤0，J一1，⋯，m^J+1，⋯，时，令一，i—J+1，⋯，n，使厂(z)2∈S0一{∈RM：0≤≤≤，i一1，凸化为f(x，)一axe,⋯⋯。⋯，M}。规则3当a<0，≥

6、0，i===1，⋯，且R一其中R，(2)，J一0，⋯，是经过上述等价转换和凸化过程最后所得松弛凸规划问题中除去定∑≤1时，厂(z)由性质2知在R上是凸的，不界约束后的所有约束，表示RCP问题中出现的需凸化。所有变量，S。表示界约束。规则4当a<0且存在rl<0或a<0，r>显然，若问题RCP(S。)和SGP(S。)的最优值分别为VERCP(S。)]和V[SGP(S。)]，则V[RCP0，i一1，⋯，nRR一∑>1时，令z一x，i一(S。)]≤V／-SGP(S。)]。1，⋯，J(>0对应的变量)，z：X亩，i—J+1，3分支定界算法⋯，n(r<0对应的变量)

7、将厂(z)凸化为f(x，x)下面给出求解问题SGP的新的分支定界算：。x⋯x≯x⋯x。法。假定在算法的第k次迭代中，L表示可能存在SGP问题中采用上述凸化规则凸化多项式在全局最优解的子长方体构成的集合，胁和分项。在整个过程中，多项式项被凸化，而问题的非别是问题SGP最优值的下界和上界。凸性转移到添加的约束函数上。下面给出上述凸步1给定参数e>0，令k—l，L一{S。}，S化过程中产生的不同形式的非凸约束的凸化方法。一S。，一。。。求解问题RCP(S)，设其最优解和定理1当a>O，<0，i一1，⋯，J，ri>0，i一最优值分别为z和(S)，令一u(S)；若z

8、是+1，⋯，时，非凸函数厂(z)一日zizz⋯z的SGP的可行解，