劉林娜， 楊永建， 余 峰

(上海大學理學院，上海200444)

近年來，人們已經較為深入地研究了凸規(guī)劃問題，并且給出的方法大多非常有效［1］.但是，對于在生活中有著很強實際應用背景的一些問題，如金融經濟［2-3］、工程設計和非線性系統(tǒng)的魯棒穩(wěn)定性分析［4］等卻只能表示為非凸規(guī)劃問題.雖然非凸二次規(guī)劃問題是困難的多極值全局優(yōu)化問題，但仍有不少學者在這方面取得了一定的進展［5-8］.本工作主要研究一類特殊的非凸二次規(guī)劃問題——凹極小化問題.凹極小化問題是一種比較常見的多極值優(yōu)化問題，在全局優(yōu)化領域有著重要的應用.許多類型的優(yōu)化問題，如0-1整數(shù)規(guī)劃問題、雙線性規(guī)劃問題、互補問題和某些乘積問題等都可以轉化為等價的凹極小化問題.如

式中，f(x)∶Rn→R在非空集合D上是凹的，D為Rn中非空凸集(假設D為多面體).事實上，如果問題(P)的最優(yōu)值不是∝，則一定可以在D的頂點處找到一點，使f(x)在該點取到最優(yōu)值，即凹函數(shù)在多胞形上的全局極小值一定是在多胞形的某個頂點取到，并稱該性質為極點最優(yōu)性.進一步來說，當可行域為緊凸集時，凹函數(shù)的極點最優(yōu)性仍然成立.本工作先作以下2個假設.

假設1 凹函數(shù)f(x)：D→R可延拓到F(x)：Rn→R，且F(x)為可微函數(shù).

假設2 凸集D為多胞形，且有非退化的頂點，即int D≠?.

下面對以上假設作進一步說明.

命題1 令D?Rn是凸的，int D≠?，f：D→R

在D上是凹函數(shù)，并且是連續(xù)的.假設‖Δf(x)‖在集合DΔ={x∈D：f(x)在x點是可微的}上是有界的，其中 Δf表示 f的梯度，‖·‖為歐幾里得范數(shù)，則

在Rn上是凹的，且在D上，有F(x)=f(x).

證明 對任意的y∈DΔ，令

對于每個y，hy是仿射的，F(xiàn)(x)是仿射函數(shù)的下確界，所以F(x)在Rn上是凹的.對于所有的x，y∈DΔ，hy(x)≥f(x).在DΔ上，有hx(x)=f(x)，因此，F(xiàn)(x)=f(x).由于DΔ在int D內是稠密的，根據(jù)f在D上的連續(xù)性可知，在D上有F(x)=f(x).

假設D是多胞形，且int D≠?，顯然等價于dim D=n.若dim D=d＜n，則可以在一個包含D的d維空間內進行討論.

割平面的概念是由Gomory在1958年首先提出用來構造整數(shù)規(guī)劃的算法.Gomory割平面是通過不斷求解其線性規(guī)劃松弛形式，構造合適的割平面，從而去掉松弛形式的非整數(shù)解，最終找到一個整數(shù)向量的最優(yōu)解.該算法能夠保證整數(shù)規(guī)劃在有限步內求得最優(yōu)解.后來，Tuy［8］又提出了一種求解凹極小化問題的割平面，其中心思想是：基于以上2條假設，易求得可行域D的一些可行點，通過傳統(tǒng)的線性規(guī)劃算法(如單純形方法)可以找到D的一個頂點v1.由f(x)的可微性可知，D的發(fā)自v1的邊方向d，由此可找到滿足dtΔf(v1)＜0的方向d.對于v1的鄰點v2=v1+ λd，可根據(jù)f(x)的凹性，即f(v2)≤f(v1)+(v2－v1)t· Δf(v1)(由于(v2－v1)tΔf(v1)＜0，且f(v2)＜f(v1))，通過轉軸方法或者標準的非線性規(guī)劃的局部算法，總可以找到f(x)在D上的一個局部極小點x0.令γ=f(x0)≥min{f(x)：x∈D}，由此構造超平面H，一般稱之為割或者割平面，使得對于所有的x∈D∩H－，有f(x)≥γ，即試圖通過割掉一部分可行域，來保證該部分上的目標函數(shù)值不小于f(x0).若可行域剩下的部分不為空集，則可用同樣的方法應用到剩余部分.

1 變上限積分函數(shù)方法

考慮變上限積分函數(shù)［9］

式中，x*為f(x)在可行域D上的局部極小點，d是一個已知方向，r=f(x*)是局部極小值.若f(x)為強制函數(shù)，則F(x*，t)也為強制函數(shù).下面給出F(x*，t)的一些性質.

定理1 設x*是f(x)的一個局部極小點，若f(x)在以 x*為起點，以 d為方向的射線上恒有f(x)≥r，即對于任意的s≥0，有f(x*+sd)≥r，那么函數(shù)F(x*，t)是一個關于t的增函數(shù).

證明 對函數(shù)F(x*，t)求導，可得

由條件f(x)≥r可知，F(xiàn)'(x*，t)≥0，故F(x*，t)是關于t的增函數(shù).

定理2 設x*是f(x)的一個局部極小點，若f(x)在以x*為起點，以d為方向的射線上存在函數(shù)值小于r的點x，那么在該射線上一定存在一點x0，使得f(x0)=r，并使得對應的t0是函數(shù)F(x*，t)的局部極大點，其中x0=x*+t0d.

證明 假設在射線上存在一點x'，使得f(x')＜r.因為f(x)連續(xù)，由介值性定理可知，在該射線上一定存在一點x0，使得

并且存在t0的一個鄰域(t0－δ，t0+δ)(δ＞0)，使得當t∈(t0－δ，t0］時，f(x*+td)≥r;當t∈(t0，t0+δ)時，f(x*+td)≤r.

任取t∈(t0－δ，t0］，有

任取t∈(t0，t0+δ)，有

故t0為函數(shù)F(x*，t)的局部極大點.

定理3 設x*是f(x)的一個局部極小點，對于某個方向d，若t*是函數(shù)F(x*，t)的一個平穩(wěn)點，則有f(x*+t*d)=r.

證明 對函數(shù)F(x*，t)求導，得到

由于t*是F(x*，t)的穩(wěn)定點，則有

即有f(x*+t*d)=r.

下面，考慮問題

可以利用局部算法來求解問題(P1)，這里采用Newton算法，算法步驟如下.

步驟1 初始化.給定初始點tk，誤差控制?＞0，記k=0.

步驟4 迭代改進.通過線搜索確定步長參數(shù)αk，令tk+1=tk+αkek，置k+1→k，轉步驟2.算法終止.

Newton算法比最速下降法的收斂速度要快，固定步長αk=1，則迭代產生的序列{tk}是收斂于點t*的，且為二階收斂.通過Newton算法可以找到問題(P1)的極大點t*.

2 割平面算法

首先，假設凹極小化問題(P)的可行域

是非空閉凸集，式中，A為m×n階矩陣，b為歐式空間的n維向量.通過傳統(tǒng)的線性規(guī)劃(如單純形法)可求出 f在 D上的一個局部極小點 x0.顯然有f(x0)≥min{f(x)：x∈D}，令γ=f(x0)，我們感興趣的區(qū)域為D(γ)=D∩{x∈Rn|f(x)＜γ}.在求解凹極小化問題的算法中，首要任務是在以x為起點，d為方向的射線ρ(x，d)={y：y=x+td，t≥0}上找到最長的線段［x，x+t*d］，使得對所有的y∈［x，x+ t*d］，有f(x)≥γ.特別地，γ是在極小化過程中的某一階段得到的最佳目標函數(shù)值.在區(qū)間［x，x+t*d］中，不會有比當前局部最優(yōu)值更佳的最優(yōu)值.若f(x)為嚴格凹的，且上水平集L(f(x);γ)={x：f(x)≥γ}有界，則y=x+t*d是射線ρ(x，d)與L(f(x);γ)的邊界的交.若L(f(x);γ)沿d無界，則t*=+∝，即在整個射線ρ(x，d)上有f(y)≥γ，這時一般取t*=t1，其中t1為充分大的正數(shù).

下面給出γ-擴張的定義.

定義1 令f：Rn→R是凹函數(shù)，x∈Rn，γ是滿足γ≤f(x)的實數(shù)，并且t1＞0充分大.稱點y∈Rn為x沿方向d∈Rn