eryar

OPEN CASCADE Multiple Variable Function

eryar@163.com

Abstract. Multiple variable function with gradient and Hessian matrix is very very import in OPEN CASCADE optimization algorithms. In order to understand these optimization algorithm better, let’s study some basic knowledge about Gradient, Hessian Matrix.

Key Words. Multiple Variable Function, Gradient, Hessian Matrix, 最優(yōu)化算法,

1. Introduction

當(dāng)函數(shù)只有一個(gè)自變量時(shí)，感覺相對簡單，一切還在掌握之中。如參數(shù)u表示的B樣條曲線，當(dāng)參數(shù)u在[0，1]之間變化時(shí)，就可以得到與參數(shù)對應(yīng)的曲線上的點(diǎn)。當(dāng)函數(shù)有多個(gè)自變量時(shí)，就有點(diǎn)力不從心，畢竟人們都喜歡安穩(wěn)，不喜歡太多的變化。當(dāng)變化太多時(shí)，得到的結(jié)果也更豐富多彩。如有兩個(gè)參數(shù)u，v表示的B樣條曲面，參數(shù)變化的范圍是一個(gè)u∈[0，1]，v∈[0，1]矩形空間，與參數(shù)u，v對應(yīng)的是一片曲面上的點(diǎn)。

在實(shí)際應(yīng)用中，與多元函數(shù)的一階導(dǎo)數(shù)（Gradient梯度）、二階導(dǎo)數(shù)（Hessian Matrix）和多元函數(shù)的極值等概念也是理解非線性最優(yōu)化問題的基礎(chǔ)知識。

OPEN CASCADE中一些求極值和逼近等算法中就使用了非線性最優(yōu)化算法，如下類圖所示：

Figure 1.1 Multiple Variable Function in OPEN CASCADE

如上圖所示，具有二階導(dǎo)數(shù)（Hessian Matrix）的多元函數(shù)應(yīng)用到全局優(yōu)化的求極值算法中。在用能量法實(shí)現(xiàn)的曲線光順（Fair Curve）算法中也使用到了具有二階導(dǎo)數(shù)的多元函數(shù)。為了更好地理解最優(yōu)化的具體實(shí)現(xiàn)，先學(xué)習(xí)下OPEN CASCADE中與多元函數(shù)有關(guān)概念的表達(dá)方式：多元函數(shù)、梯度Gradient和Hessian Matrix。

2.Multiple Variable Function

在《高等數(shù)學(xué)》中給出了多元函數(shù)的定義：設(shè)D是平面上一個(gè)點(diǎn)集。如果對于每個(gè)點(diǎn)P(x,y)∈D，變量z按照一定法則總有確定的值和它對應(yīng)，則稱z是變量x,y的二元函數(shù)。點(diǎn)集D稱為該函數(shù)的定義域，x,y稱為自變量，z稱為因變量。當(dāng)自變量的個(gè)數(shù)大于1個(gè)時(shí)，即n≥2，n元函數(shù)統(tǒng)稱為多元函數(shù)。

在OPEN CASCADE中與多元函數(shù)最直接的對應(yīng)就是類Geom_Surface，即參數(shù)表示的曲面，參數(shù)u,v的取值區(qū)域?yàn)槎嘣瘮?shù)的定義域，當(dāng)指定uv時(shí)得到的曲面上的點(diǎn)即為多元函數(shù)值。OPEN CASCADE的數(shù)學(xué)包中還給出了更抽象地多元函數(shù)類：math_MultipleVarFunction。

Figure 2.1 math_MultipleVarFunction class diagram

由上面的類圖可知，類math_MultipleVarFunction是個(gè)抽象類，有兩個(gè)純虛函數(shù)：

v NbVariables() const = 0：自變量的個(gè)數(shù)；

v Value(const math_Vector& X, Standard_Real& F) = 0：計(jì)算指定自變量X對應(yīng)的函數(shù)值F。自變量X是個(gè)向量，其中的值分別對應(yīng)多個(gè)自變量；

下面給出一個(gè)多元函數(shù)的具體應(yīng)用，即計(jì)算二重積分。題目來源為《高等數(shù)學(xué)》教材習(xí)題9－2（1）：

在OPEN CASCADE中計(jì)算上述二重積分代碼如下所示：

通過從抽象類math_MultipleVarFunction派生出一個(gè)具體的多元函數(shù)類，在虛函數(shù)Value()計(jì)算指定向量X對應(yīng)的函數(shù)值，通過函數(shù)NbVariables()確定自變量的個(gè)數(shù)。為什么可以對類math_Vector的對象用括號直接進(jìn)行取值和賦值呢？因?yàn)樵谶@個(gè)類中重載了括號運(yùn)算符。計(jì)算結(jié)果如下圖所示：

Figure 2.2 Integration Value

因?yàn)槭褂胢ath_GaussMultipleIntegration時(shí)需要指定積分區(qū)域，且只能為常數(shù)，所以如下所示的積分區(qū)域中包含變量的多重積分就不能計(jì)算：

OPEN CASCADE中與多元函數(shù)對應(yīng)的一元函數(shù)的積分計(jì)算參考：

OPEN CASCADE Gauss Integration:

http://www.shnenglu.com/eryar/archive/2014/09/11/208275.html

3.Gradient

在二元函數(shù)情形，設(shè)計(jì)函數(shù)z=f(x,y)在平面區(qū)域D內(nèi)具有一階連續(xù)偏導(dǎo)數(shù)，則對于每一點(diǎn)P(x,y)∈D都可以定出一個(gè)向量：

這向量稱為函數(shù)z=f(x,y)在點(diǎn)P(x,y)的梯度(gradient)，記作gradf(x,y)。對于多元函數(shù)u=f(X)，X=(x1,x2, ..., xn)T，有如下定義：

設(shè)u=f(X)，X∈S，若在點(diǎn)x0=(x1(0),x2(0), ..., xn(0))T處對于自變量X=(x1,x2, ..., xn)T的各個(gè)分量的偏導(dǎo)數(shù)都存在，則稱函數(shù)u=f(X)在點(diǎn)x0處一階可導(dǎo)，并稱向量是u=f(X)在點(diǎn)x0處的梯度Gradient或一階導(dǎo)數(shù)。

無約束優(yōu)化最優(yōu)性的一階必要條件是：若x0是無約束優(yōu)化問題的局部最優(yōu)值點(diǎn)，則。

由數(shù)學(xué)分析可知，的方向?yàn)閒(X)的等值面（等值線）的法線在點(diǎn)x0處的方向，即沿梯度方向函數(shù)值變化最快。目標(biāo)函數(shù)梯度為零的點(diǎn)稱為無約束優(yōu)化問題的穩(wěn)定點(diǎn)。穩(wěn)定點(diǎn)可能是目標(biāo)函數(shù)的極大值點(diǎn)，也可能是極小值點(diǎn)，甚至二者都不是。最后一種情況對應(yīng)的點(diǎn)稱為函數(shù)的鞍點(diǎn)，即在從該點(diǎn)出發(fā)的一個(gè)方向上是函數(shù)的極大值，而在另一個(gè)方向上是極小值點(diǎn)。

對無約束優(yōu)化問題，目標(biāo)函數(shù)在最優(yōu)值點(diǎn)的任意方向上的導(dǎo)數(shù)都為零，即目標(biāo)函數(shù)在最優(yōu)值點(diǎn)的切平面是水平的。不過無約束優(yōu)化問題的局部最大值點(diǎn)和鞍點(diǎn)也滿足上述條件。因此，要確認(rèn)一個(gè)穩(wěn)定點(diǎn)是否為最優(yōu)值點(diǎn)，還需要考慮該點(diǎn)的二階最優(yōu)性條件。

在OPEN CASCADE中與此對應(yīng)的類是math_MultipleVarFunctionWithGradient，即具有梯度的多元函數(shù)。這個(gè)類也是抽象類，不能直接實(shí)例化，若要使用需要派生出新類，并實(shí)現(xiàn)以下幾個(gè)純虛函數(shù)：

v NbVariables() const = 0：多元函數(shù)自變量個(gè)數(shù)；

v Value(const math_Vector& X, Standard_Real& F) = 0：計(jì)算多元函數(shù)在指定變量X處對應(yīng)的函數(shù)值F，通過引用傳出；

v Gradient(const math_Vector& X, math_Vector& G) = 0：計(jì)算多元函數(shù)在指定變量X處的梯度值，通過引用傳出；

v Values(const math_Vector& X, Standard_Real& F, math_Vector& G) = 0：計(jì)算多元函數(shù)在指定變量X處的函數(shù)值F和梯度值G；

4.Hessian Matrix

多元函數(shù)的二階導(dǎo)數(shù)和Hessian Matrix的定義如下：設(shè)u=f(X)，x0∈S，若f在點(diǎn)x0∈S處對于自變量x∈S的各分量的二階偏導(dǎo)數(shù)都存在，則稱函數(shù)f(X)在點(diǎn)x0處二階可導(dǎo)，且稱矩陣

為f(X)在點(diǎn)x0處的二階導(dǎo)數(shù)或Hessian Matrix，Hessian Matrix有時(shí)也記作H(x0)。

無約束最優(yōu)化最優(yōu)性條件的二階必要條件為：設(shè)f(X)在點(diǎn)x0∈S處二次可微，若x0最f(X)的局部極小點(diǎn)，則且半正定。

無約束最優(yōu)化最優(yōu)性條件的二階充分條件為：設(shè)f(X)在點(diǎn)x0∈S處二次可微，若且正定，則x0是函數(shù)f(X)的嚴(yán)格局部極小點(diǎn)。

二次型是X=(x1,x2,...,xn)T的二次齊次函數(shù)，它在研究非線性最優(yōu)化問題中具有重要作用。通過線性代數(shù)中正定二次型相關(guān)定理，可以得出Hessian Matrix正定的判斷條件。相對于高等數(shù)學(xué)中關(guān)于二元函數(shù)極值充分條件的定理，使用Hessian Matrix更具一般性，適用于任意多元函數(shù)。終于知道正定二次型的一個(gè)應(yīng)用，將原來在線性代數(shù)課本中突然冒出這么個(gè)抽象概念，能與實(shí)際應(yīng)用有些關(guān)聯(lián)。看來線性代數(shù)必需在實(shí)際應(yīng)用中才能有所理解，如關(guān)于現(xiàn)代控制工程中的微分方程組的求解，會用到特征值的理論；無約束最優(yōu)化問題中極值充分條件的說明要用到正定二次型理論等。難怪當(dāng)時(shí)在學(xué)習(xí)線性代數(shù)的時(shí)候那么吃力，對這些抽象概念不理解，學(xué)習(xí)的時(shí)候就只能是機(jī)械的記憶，如果以后用不到，肯定都還給老師了。OPEN CASCADE中與Hessian Matrix對應(yīng)的類是math_MultipleVarFunctionWithHessian，其類圖如下所示：

Figure 4.1 math_MultipleVarFunctionWithHessian class diagram

由上面類圖可知，math_MultipleVarFunctionWithHessian派生自帶梯度的多元函數(shù)類math_MultipleVarFunctionWithGradient。因此，比帶梯度的多元函數(shù)類多個(gè)求值的虛線函數(shù)：

Values(const math_Vector&X, Standard_Real&F, math_Vector&G, math_Matrix&H) = 0

通過這個(gè)線虛函數(shù)計(jì)算出多元函數(shù)在指定變量X處的函數(shù)F，梯度值G和Hessian Matrix H。

因?yàn)閙ath_MultipleVarFunctionWithHessian有純虛函數(shù)，所以也不能直接實(shí)例化，需要根據(jù)實(shí)際情況從其派生類來使用。正如本文開頭所示的類圖中幾個(gè)類一樣，從帶有Hessian Matrix的多元函數(shù)派生出新類來計(jì)算全局極值和曲線光順，如下類圖所示：

Figure 4.2 math_MultipleVarFunctionWithHessian class diagram

5.Conclusion

在OPEN CASCADE的數(shù)學(xué)包Package math中不僅描述了只有一個(gè)自變量的一元函數(shù)math_Function，也描述了具有多個(gè)自變量的多元函數(shù)，及其一階導(dǎo)數(shù)（梯度）和二階導(dǎo)數(shù)（Hessian Matrix）。通過應(yīng)用多元函數(shù)的積分計(jì)算，可以看出OCC對這些概念進(jìn)行的類封裝還是很清晰，便于理解和使用。對于這些基礎(chǔ)概念的介紹，便于理解后面具體的優(yōu)化算法的使用。

從OPEN CASCADE中的優(yōu)化算法可以看出，核心是數(shù)學(xué)這個(gè)精巧工具的熟練應(yīng)用。可以找出《高等數(shù)學(xué)》、《線性代數(shù)》、《最優(yōu)化方法》、《非線性最優(yōu)化理論與方法》、《數(shù)值分析》等相關(guān)書籍，通過對比OPEN CASCADE中的程序?qū)崿F(xiàn)有效的理論聯(lián)系實(shí)踐，提高學(xué)習(xí)效率。而對高等數(shù)學(xué)和線性代數(shù)可以做到溫故知新，對原來百思不解的問題可以有個(gè)Aha!的恍然大悟，找到學(xué)習(xí)的樂趣。

6. References

1. 同濟(jì)大學(xué)數(shù)學(xué)教研室. 高等數(shù)學(xué). 高等教育出版社. 1996

2. 同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系. 線性代數(shù). 高等教育出版社. 2003

3. 易大義, 陳道琦. 數(shù)值分析引論. 浙江大學(xué)出版社. 1998

4. 《運(yùn)籌學(xué)》教材編寫組. 運(yùn)籌學(xué). 清華大學(xué)出版社. 2012

5. 何堅(jiān)勇. 最優(yōu)化方法. 清華大學(xué)出版社. 2007

6. 楊慶之. 最優(yōu)化方法. 科學(xué)出版社. 2015

7. 王宜舉, 修乃華. 非線性最優(yōu)化理論與方法. 科學(xué)出版社. 2012