工程優化設計的理論和方法近些年來得到了很大的發展和提高。隨著計算機技術的迅猛發展,基於智能的優化技術已成為設計自動化的重要方面。基於非線性規劃理論的優化技術是工程優化設計的主要基礎,如何求出問題的全部最優解和全局最優解壹直是從事優化技術研究的人們努力探索的課題。對優化模型進行單調性分析是解決該問題的壹種方法。文獻〔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．之間。