求解非線性約束優(yōu)化問題的精確罰函數(shù)方法

譚　俊，陳建玲，蘇江波

（1.運城學院　應用數(shù)學系；2.運城學院　物理與電子工程系，山西　運城　044000）

·國家自然科學基金項目

求解非線性約束優(yōu)化問題的精確罰函數(shù)方法

譚俊1，陳建玲2，蘇江波2

（1.運城學院應用數(shù)學系；2.運城學院物理與電子工程系，山西運城044000）

非線性約束優(yōu)化問題屬于一般形式的非線性規(guī)劃問題范疇，它也是數(shù)學優(yōu)化研究中的關(guān)鍵難點.用非約束優(yōu)化問題來求解約束最優(yōu)化問題的主要方法有兩種：拉格朗日乘子函數(shù)法與罰函數(shù)法，本文將主要論述的就是求解非線性規(guī)劃中的精確罰函數(shù)法，通過這種算法的相關(guān)理論與實踐算例來求證它的有效性.

精確罰函數(shù)；非線性約束優(yōu)化；規(guī)劃；算例

罰函數(shù)法就是通過求解一個或多個罰問題來約束規(guī)劃目標問題的解，一般來說所得到罰問題的解就是初始問題的最優(yōu)解.如果罰參數(shù)達到一定指標時，單獨罰問題的最優(yōu)解就應該是原約束規(guī)劃問題的最優(yōu)解，所以此罰問題中的罰函數(shù)就應該被稱為精確罰函數(shù).精確罰函數(shù)也是求解非線性約束優(yōu)化問題的有效方法之一，它在一定條件下所呈現(xiàn)的光滑性與精確性都是值得借鑒的.

1　精確罰函數(shù)

對于非線性約束優(yōu)化問題而言，罰函數(shù)法是最有效的解決方法之一，但從方法屬性層面看，罰函數(shù)法的天生病態(tài)性質(zhì)又局限了它能力的發(fā)揮，所以人們希望給出一種基于精確角度的新罰函數(shù)法，以此來解決傳統(tǒng)罰函數(shù)法中所固有的天生病態(tài)性質(zhì).

1.1罰函數(shù)法與精確罰函數(shù)法

在傳統(tǒng)數(shù)學函數(shù)理論中，罰函數(shù)理論屬于經(jīng)典之一，它依靠對罰函數(shù)項的添加來實現(xiàn)對無約束優(yōu)化問題的解決，使罰函數(shù)能夠在趨于無限大的過程中獲取原始規(guī)劃問題的最優(yōu)解.相比較而言，精確罰函數(shù)理論則通過求解個體無約束優(yōu)化問題作為最優(yōu)解，這就暴露了傳統(tǒng)罰函數(shù)法的函數(shù)病態(tài)性質(zhì)缺陷，也就是由于病態(tài)罰因子無限制增大或減小所引起的求解不夠精確問題.精確罰函數(shù)法作為一類新的罰函數(shù)算法，可以將精確罰函數(shù)的非光滑屬性光滑化.不過精確罰函數(shù)方法也有一定缺點，例如在實際計算中由于無法得知罰函數(shù)的具體數(shù)值，所以這就影響了諸如Newton算法的有效性，因此可以見得使用罰函數(shù)法的要點就是在于它的可微性、精確性與光滑性.罰函數(shù)的選擇與計算應該滿足某個基本要求，比如迭代過程中對罰函數(shù)極小化的操作與應用，它能夠為原有非線性約束化問題尋找到一個局部的最優(yōu)解，并且在適當條件下確保罰函數(shù)算法的全局收斂性，使函數(shù)估值更加簡易化.

1.2精確罰函數(shù)的具體構(gòu)造

作為解決約束優(yōu)化問題精確罰函數(shù)，它解決問題的主要思路就是通過尋找某個容易的求解來替代問題，并滿足一定條件，使所找到的解恰好符合原問題的解，這樣整各求解問題就會變得相對簡易化.因此在構(gòu)造罰函數(shù)前，應該首先明確精確罰函數(shù)的構(gòu)造原理，即對某一個罰參數(shù)所對應ρ的無約束優(yōu)化問題最優(yōu)解也就是對原問題的最優(yōu)解.基于上述理論，可以闡述非線性約束優(yōu)化問題中精確罰函數(shù)方法的基本構(gòu)造結(jié)構(gòu):

如果:?（y）=maxβ（0，y），β∈N，就可以基于?（y）推導出y的連續(xù)一階導數(shù).如果y≥0，就有?'（y）=βyβ-1，當y＜0時，就有:?'（y）=0.基于上述理論推理，對罰函數(shù)F（x，u）進行推導:

當F（x，u）≥0時，就可以考慮基于精確罰函數(shù)法下所對應的無約束優(yōu)化問題:

在上式中當設置最優(yōu)解為xu*時，x，u取任意值，就有0≤F（xu*，u）≤（x，u），而且有F（xu*，u）=0，它的充要條件為:

1.3精確罰函數(shù)的算法說明

根據(jù)精確罰函數(shù)的基本性質(zhì)及原理，并參考P （x，M）函數(shù)的連續(xù)性就可以得知，如果選擇已知函數(shù)f*的近似值，就能夠通過對問題求解來得到非線性約束問題的最優(yōu)解.所以在運用精確罰函數(shù)方法是可以基于這一思想來推導出該算法的具體流程步驟.

步驟1:首先輸入函數(shù)f*的下界初值并滿足f*≥α0，由此可以取得可行點x0.當有F（x0）=0時，將β0作為f*的上限值，并滿足β0=f（x0）.或者在滿足f*≤β0時，也可以求得minF（x）的值.

步驟2:當Mk=（1-θ）αk+θβk時，若參數(shù)θ的取值范圍在0＜θ＜0.5，假設θ=0.3，就可以求解minP

步驟4:重復第二、三步驟就可以得到算式βk+1-αk≤ε，此時問題的最優(yōu)解就應該為:x*=x*Mk.在上述算法的四個步驟中，f*作為下界不能選擇過小，選擇過小就很容易產(chǎn)生溢出而導致計算無法成功，因此根據(jù)收斂性定理可知，當上述算法中若產(chǎn)生αk，βk時，它們應該滿足αk≤f*≤βk，而且由于兩參數(shù)之差等于0，因此可以得出結(jié)論，精確罰函數(shù)的算法是應該具備收斂性的.

通常情況下，傳統(tǒng)的一般罰函數(shù)構(gòu)造都是按照約束問題所給出的，所得到的罰問題的解也符合原始問題的近似解.而精確罰函數(shù)所能實現(xiàn)的就是一般罰函數(shù)的精確解，這也是精確罰函數(shù)的最重要特性.如上述算法步驟中如果f（x）在一階具有可微性，那么精確罰函數(shù)P（x，M）在一階也同樣具有可微性.同理，f（x）與P（x，M）在二階也具有可微性，因此可以證明罰函數(shù)P（x，M）應該是關(guān)于M的減函數(shù)，并且在滿足相應條件下，精確罰函數(shù)的最優(yōu)解就能夠符合原問題規(guī)則，成為原問題的最優(yōu)解，這就是對原問題的一種新形式算法設計，精確罰函數(shù)目前已經(jīng)被廣泛應用到計算機編程工作當中，應用相當靈活實用［1］.

2　逼近l1的精確罰函數(shù)算法

針對逼近l1的精確罰函數(shù)形式是一種全新的近似漸進計算方法，它能夠證明罰函數(shù)的近似算法所能在序列上得到的聚點數(shù)量，并根據(jù)聚點來為原問題求得最優(yōu)解.如果所得序列無界，就要根據(jù)實際狀況相應的展示序列值的收斂性，直到為最優(yōu)解創(chuàng)造充分條件［2］.另外，在Fromovitz約束規(guī)范下也可以證明一點［3］，即當β越大時，γ的充分值就越小，但是由此所產(chǎn)生的迭代極小點都存在可行性，它們間接為l1精確罰函數(shù)在不精確罰函數(shù)的情形下進行推廣并允許通過簡易化算例進行驗證.

2.1逼近l1的精確罰函數(shù)算法的相關(guān)問題及方法解析

在對逼近l1精確罰函數(shù)算法進行解析之前，要考慮可微非線性規(guī)劃問題，例如為ε≥0定義設計松弛可行集合，有:

在公式中，當Ω0是精確罰函數(shù)的可行集合時，就可以列出以下假設:

當罰函數(shù)式中存在ε＞0，Ωε就是有界限的；

而如果罰函數(shù)式滿足Fromovitz約束規(guī)范，就可以得到一個任意的最優(yōu)解x*，當h∈Rn且ρ＞0時，罰函數(shù)式就會滿足▽fi（x*）Th＜-ρ.如果對任意數(shù)i=1，…，m，設定條件為fi（x）＜0，則點x∈Rn就可以被稱之為內(nèi)點，此時按照Fromovitz約束規(guī)范就可以證明內(nèi)點是一定存在的.以下可以給出逼近l1精確罰函數(shù)具有可微性的罰函數(shù)形式公式為:

再進一步推算得出一階導數(shù)應該為:

2.2逼近l1的精確罰函數(shù)算法的相關(guān)算法解析

為了證明逼近l1精確罰函數(shù)算法的可行性，本文假設了適應于任意函數(shù)的β、γ值，假設其滿足: β0≥1，γ∈（0，1］，當fβ、γ（·）中含有極小點時，它的算法步驟如下:

步驟1:設置β0=1，γ0=1，且k=0.

步驟2:根據(jù)步驟1帶入?yún)?shù)計算可得:

步驟3:γk+1=γk/2，如果xk為可行點，就有βk+1=βk；如果xk為不可行點，就有βk+1=2βk.

步驟4:當k=k+1時，按照步驟2就可求得逼近l1精確罰函數(shù)的值.

根據(jù)上述4步驟算法就可以得出以下結(jié)論，如果存在任意條件如t≤0或t＞1時，θγk（t）的逐點收斂值就應該為t+.而如果當βkγk≤1時，它的可行域內(nèi)點x~就有:

3　基于精確罰函數(shù)方法的非線性約束優(yōu)化問題算例解析

3.1算例1

假設有:minx1+x2，且s.t.x12-x2≤0，-x1≤0

根據(jù)上述假設條件可以看出該算例的最優(yōu)解應該為（x1*，x2*）=｛0，0｝，它的最優(yōu)目標值應該是0，而其對應的非線性法函數(shù)應該被定義為以下:

具體到各個參數(shù)則分別取值為:?=5，β=3， λ=100.當u=-1時，非線性約束化問題minx∈XF（x，-1）就可以得出最優(yōu)解x*的值就應該為（1/3，2/3），它所對應的目標數(shù)值就應該為F（x，-1）=0.

3.2算例2

通過上述兩個基于精確罰函數(shù)方法的非線性約束優(yōu)化問題的計算就證明了該方法對解決原罰函數(shù)問題的有效性［6］.

4　總結(jié)

本文通過對精確罰函數(shù)的理論闡述與對非線性約束優(yōu)化問題計算求解得出了諸多結(jié)論，例如關(guān)于逼近l1精確罰函數(shù)若干性質(zhì)的實現(xiàn).更重要的是對非線性約束優(yōu)化問題中原罰函數(shù)的精確求解，在保留原有罰函數(shù)問題中不可微部分函數(shù)值不變的基礎上，滿足了罰函數(shù)式中的可微性與光滑性，進而提升了精確罰函數(shù)算法的效率與質(zhì)量，提升了算法的收斂速度，證明了精確罰函數(shù)方法在非線性約束優(yōu)化問題中求解的有效性與實用性.

〔1〕王桂艷.求解非線性約束優(yōu)化問題的精確罰函數(shù)方法［D］.北京交通大學，2009.5-18.

〔2〕王銀河.非線性優(yōu)化問題的罰函數(shù)算法和擬Newton算法［D］.重慶大學，2010.10-22.

〔3〕魏大松.非線性優(yōu)化問題的精確罰函數(shù)算法研究［D］.重慶大學，2007.13-15.

〔4〕程桂香.非線性最優(yōu)化問題的一族新的罰函數(shù)方法研究［D］.首都師范大學，2006.15-34.

〔5〕張春慨，李霄峰，邵惠鶴，等.基于線性搜索的混沌優(yōu)化及其在非線性約束優(yōu)化問題中的應用［J］.控制與決策，2001，16（1）：123-125，12.

〔6〕蔡力，朱德通.整體收斂的非線性等式約束優(yōu)化問題的不精確修正正割方法［J］.上海師范大學學報（自然科學版），2011，40（5）：441-45.

O221.2

A

1673-260X（2016）07-0001-03

2016-04-08

運城學院博士啟動基金項目資助（YQ-2012011，YQ-2014013）；國家自然科學基金項目資助（U1431125）