Groebner基如何生成

1 前言

工程优化设计的理论和方法近些年来得到了很大的发展和提高。随着计算机技术的迅猛发展,基于智能的优化技术已成为设计自动化的重要方面。基于非线性规划理论的优化技术是工程优化设计的主要基础,如何求出问题的全部最优解和全局最优解一直是从事优化技术研究的人们努力探索的课题。对优化模型进行单调性分析是解决该问题的一种方法。文献〔1～6〕基于单调性分析的优化技术的基本思想是通过对目标函数和约束函数进行单调性分析,找出问题松、紧和控制约束,将原问题分解为较为简单和易于求解的子问题,并且大大提高了求得问题的全局最优解的可能性。子问题的特点是全部约束均为紧约束(等式约束),所以问题可归结为对一组非线性代数方程(或等式约束问题)的求解。

Powell、Yuan和Vardi等对上述等式约束子问题提出了一些方法〔7、8〕,但提出的方法一般都不能求得问题的全部解,因而容易出现将有用的子问题当做多余子问题使原问题的最优解丢失的情况。此外,传统的用数值迭代法求解该非线性代数系统也存在初值的选取问题且一般一次只能求出一个数值解。所有上述方法都只适用于数值优化模型,无法求解符号优化模型(即模型中的已知系数是符号而不是具体数值)。能求出符号模型的最优解显然是很有实用价值的,最优解的符号表达式是在各种参数取值条件下优化设计问题的通用解,它可以用来分析各参数对解的影响从而指导实际设计,它还简化了具体的设计。对符号模型的求解只能通过非数值迭代的代数方法来实现。

Groebner基方法是求解非线性代数系统的一种非数值迭代的代数方法。其基本思想是在原非线性多项式代数系统所构成的多项式环内,通过对变量和多项式的项的适当排序,对原系统进行约简,最后生成一个与原系统等价且便于直接求解的标准基（Groebner基）。传统的结式消元法也可是解符号形式非线性代数系统的代数法,但它需要高度依赖于具体问题的消元技巧,且会产生增根。

文献〔9〕、〔10〕提出了一种基于单调性分析和Groebner基法的求解符号模型优化问题最优解的方法,但他们在用Groebner基法求解子问题时,采用了传统的变量替代和消元的方法,没有解决Groebner基法的重要的排序问题,从而影响了方法的有效程度。本文在用单调性分析和Groebner基法对符号优化问题求解时,根据子问题等价等式方程组的特点提出了两个项及变量排序的法则,从而较快和更有效地生成符号形式的“三角化”的Groebner基,也即优化问题解的符号表达式。文中给出的计算实例说明了所提出的方法在求优化问题符号最优解方面的优越性和有效性。

2 Groebner基方法简介〔11〕

有关Groebner基(以下简写为GB)法的知识可在有关文献(例如文献[11])中找到,我们在此通过一个简单的例子来说明如何用该法生成一个多项式代数系统的GB。

设有一个多项式系统F＝｛f1，f2｝,其中:

f1＝ax2＋bxy

f2＝cx2＋dy2 （1）

式中:x，y——变量;

a，b，c，d——符号形式的系数。

对于f1，f2的项按字典法排序,变量的序为y＜Tx，则各多项式对应的主幂乘积为:LPP（f1）＝x2，LPP（f2）＝x2，由于LPP（f1）／LPP（f2）＝1，所以f1可相对于f2约简为f1′：

f1′＝cf1－af2＝cbxy－ady2 （2）

现在求f1′与f2的S－多项式f3：

f3＝S（f1′，f2）＝xf1′－byf2＝－adxy2－bdy3 （3）

由于LPP（f2）能被LPP（f1′）整除,即LPP（f2）／LPP（f1′）＝xy2／xy＝y，所以f3可相对于f1′约简为f3′:

f3′＝cbf3＋adyf1′＝（－cb2d－a2d2）y3 （4）

接着求f1′与f3′的S－多项式f4：

f4＝S（f1′，f3′）＝y2（－cb2d－a2d2）f1′－cbxf3′＝ad（cb2d＋a2d2）y4

（5）

f4又可相对于f3′约简为f4′:

f4′＝f4＋adyf3′＝0 （6）

同理,f2与f3′的S－多项式也可相对于f3′约简为零。最后得到F的等价Groebner基（GB）为G＝｛g1，g2，g3｝＝｛f3′，f1′，f2｝,且G是“三角化”的,即:

g1＝f3′＝g1（y）

g2＝f1′＝g2（x，y） （7）

g3＝f2＝g3（x，y）

对应于式(7)的方程组即为F所对应的方程组的解的符号表达式。若要求具体的解,可通过式(7)中的g1＝0求出y，再将y代入g2＝0和g3＝0,则g2、g3之GCD(最大公因式)的根即为x的解。显然,上述例的约简是很简单的,我们只是为了说明生成GB的约简过程,对于复杂的系统,其约简和生成GB是通过专用的算法(例如Buchberger算法)程序在计算机上自动完成的。

3 基于单调性分析和Groebner基法的符号优化

3.1 确定优化符号解的方法概述

在文献〔9、10〕中提出了一种确定优化设计符号优化解的方法。该方法的基本思路如下:

(1)通过单调性分析和符号处理把优化设计的原问题转换成若干个子问题[2、11]；

（2）子问题的所有约束都是紧约束(等式约束),每个子问题的紧(等式)约束集组成一个等价系统;

(3)对于每个由等价等式约束集组成的代数系统,确定其GB,此GB即为对应的子问题的优化解的符号表达式;

(4)采用任一种传统的数值算法解对应于各个GB的“三角化”的代数方程组,可求出各个子问题的全部数值最优解;

(5)由于子问题与原问题的等价性,于是也就求出了原问题的优化解符号表达式与全部数值最优解。

如果没能生成GB,则采用同伦连续法求数值解。在他们的研究中,生成GB的约简过程用的是传统的代入消元法。

3.2 子问题的数学模型

考虑如下的优化设计问题（PL）:

min． f（X）

s．t． hj（X）＝0 （j＝1，2，…，q） （8）

gi（X）≤0 （i＝1，2，…，r）

式中:X＝（x1，x2，…，xn）T——设计变量;

f（X）——目标函数;

hj（X）与gi（X）——分别为等式与不等式约束,边界约束(变量的上下界)包含在不等式约束中。

通过单调性分析和符号处理,优化设计问题（PL）可转换成若干个子问题（SPL）,其数学模型如下:

min． f（X）

s．t． hj（X）＝0 （j＝1，2，…，q） （9）

gi（X）＝0 i∈K

式中:K——原问题（PL）的对应于紧约束的编号集。

3．3 确定子问题符号解的GB法

显然,若生成的对应于子问题的等价约束多项式方程系统的GB是“三角化”的,则这个由一序列单变量方程表达的GB可以看成该子问题最优解的符号表达式,它同样可看作原问题（PL）的最优解的符号表达式。

因为不同的变量和项的排序将导致代数系统的不同的多项式约简,所以变量和项排序是影响生成GB的效率和结果的关键因素,只有恰当的排序才能生成GB。到目前为止,最常用的选择排序的方法是试凑,这就限制了生成GB的效率。通过对子问题等价等式方程系统特征的分析,本文提出了选取排序的两个准则,根据这两个准则可以较快地和有效地生成“三角化”的GB。子问题等价等式方程系统的主要特征有:

(1)系统中的多项式是符号多项式（signomial）,其有的变量的幂是负的整数;

(2)一些来自边界约束的多项式是单变量的线性多项式,它们有如xi－ximin or xi－ximax的样子;

(3)各个方程的项数通常都很少。

特征1:表明系统的数学模型必须进行变换以便应用现有的算法如Buchberger算法来生成GB。符号多项式需转换成等价的多项式。

提出的下列选取排序的两个准则是基于特征2和特征3:

准则1:给定项的字典法排序。如果变量数n≥4，仅取变量的n种排序,且在这n种排序中分别将n个变量的每一个置于该种排序的最后。

当变量数n较大时,可能的排序数,即n！很大,而排在序最后的变量将是生成的“三角化”GB中仅含单个变量的第一个多项式中的变量,此时,其余变量的序的选择都不会影响所生成基的结构。因此准则1可省去（n！－n）种不重要的排序。

准则2:给定项的字典法排序。设变量数为n,其中具有上下界约束的变量数为ns,则仅取（n－ns）！种变量排序。

事实上,不管对带边界约束的变量如何排序,这些变量总是相应多项式的主幂乘积（LPP）,因而都可用来对其它的多项式进行约简,因此这些变量的排序不会影响所生成的GB的结构形式。准则2可大大提高n较小和ns较大时生成GB的计算效率。

下面我们提出生成优化设计子问题的GB的算法:

(1)对一个子问题,将其数学模型转换成与Buchberger算法相适应的形式;

(2)选定项的字典法排序;

(3)确定变量的排序。若n－ns＜4，按准则2选取排序,否则按准则1选取排序;

(4)用Buchberger算法生成GB,如果(“三角化”的)GB已经生成,转向（7）,否则转向下一步;

(5)将项按总幂次数法排序,再用Buchberger算法生成GB；

(6)将生成的GB转换成“三角化”的GB；

(7)输出结果并停止。

4 算例

下面是一个普通圆柱蜗杆传动减速器的符号优化设计数学模型〔10〕：

min．f（X）＝0．25πψx32x3（ux1－3x－11－2）2x－21

s．t．

g4： Z2min≤ux1≤Z2max ：g5

g6： Mmin≤x2≤Mmax ：g7

g8： qmin≤x3≤qmax ：g9

式中:x1，x2和x3——分别为蜗杆的头数、模数和特性系数;

x4——简化求解过程而设的辅助中间变量;

T2——输出轴扭矩;

u——传动比;

[σF]和[σH ]——许用应力;

YF2——齿宽系数;

η——传动的效率;

K，ψ和q2——常数。

通过单调性分析和计算机符号处理,得到如下的十个子问题〔9、10〕：

SPL1： g1，g2，g3，h3 SPL6： g1，g2，g8

SPL2： g3，g2，g4，h3 SPL7： g2，g4，g8

SPL3： g2，g3，g6，h3 SPL8： g2，g6，g8

SPL4： g1，g2，g7 SPL9： g3，g5，g6，h3

SPL5： g2，g4，g7 SPL10： g5，g6，g8

为了简化起见,设，，Q1＝q21，2，F＝，A＝4q2，B＝6q22，C＝4q32，D＝q42，G＝Z2min，H＝Mmin，I＝Mmax，J＝qmin，K＝Z2max，x1＝a，x2＝b，x3＝c，x4＝d。子问题中的符号多项式可转换成如下的多项式:

g1＝a3b3c－q0 g4＝ua－G

g2＝a2b6＋b6c2－a2Q1 g5＝ua－K

g3＝b5c4－Ab5c3＋Bb5c2－Cb5c＋Db5－d g6＝b－H

h3＝d2c2－Ea2－Fc2 g7＝b－I

g8＝c－J

下面我们对子问题逐个求解。

子问题1（SPL1）的等价等式方程组中不含单变量多项式,因而是最难解的。当选取项的字典法排序时,所有4！＝24种变量排序都未能生成GB。选取项的总幂次数排序时,取任一种变量排序都得到了“非三角化”的GB,例如取b＜Ta＜Td＜Tc，生成的GB为:

b6a6＋coef11．a6＋coef12＝0 （a）

b2a4c3＋coef21．a4c2＋coef22．b2a4c＋coef23．b2c＋coef24．d＋coef25．a4

＋coef26．b2a4＋coef27．a2＋coef28．b5＋coef29＝0 （b）

b3c＋coef31．b6a4＋coef3．a4＝0 （c）

a6c＋coef41．c＋coef42．a4＝0 （d）

d2＋coef51．a6＋coef52＝0 （e）

（10）

此处coefij（i＝1，2，…，5；j＝1，2，…，9）均为由已知参数表达的符号系数,由于篇幅所限,我们在此仅列出coef11的表达式:

coef11＝（－（（－（－Q1）／（－q0））））／（－（－1／（q0）））

方程式(10)中的多项式的结构显示出很易通过代入和消元将它转换成“三角化”形式。从式（a），（b），（e）我们分别得到：

（f）

c＝－coef42．a4（a6＋coef41）－1 （g）

（h）

将方程式（f）、（g）、（h）代入方程式（b）、（c）,我们得到两个仅含变量a的多项式,它们与方程式（f）、（g）、（h）形成SPL1的新的“三角化”的GB,这个GB即SPL1的最优解的符号表达式。我们还要指出,文献〔9、10〕提出的方法没有能生成此子问题的GB。

对于子问题SPL2,有一个单变量线性多项式,即:q4＝ua－G。此时可用准则2,也就是选项的字典法排序及（4－1）！＝6种变量a任意排序的变量排序。对于下列四种变量排序我们都得到了相同的“三角化”的GB：

a＜Tc＜Tb＜Td， c＜Ta＜Tb＜Td，

c＜Tb＜Ta＜Td， c＜Tb＜Td＜Ta

生成的GB为:

a＋coef11＝0

c2＋coef21．c＋coef22＝0

b2＋coef31．c＋coef32＝0 （11）

d＋coef41．cb＋coef42．b＝0

式中:coefij（i＝1，2，…，4；j＝1，2）的意义与SPL1中的相同不过具有不同的表达式,例如,coef11＝－G／u。

对于SPL3到SPL9,有一到两个单变量线性多项式,我们用与SPL2中同样的方法可生成相应的GB。由于篇幅的限制,在此省略了求解结果。

对于SPL10,有三个单变量线性方程,我们直接得出结果:

a＝－K／u，b＝H，c＝J

生成子问题SPL1～9的“三角化”的GB是在Sun工作站上用Buchberger算法完成的,采用Fortran语言,CPU时间分别为0．08sec．到0．28sec．之间。