非光滑凸半無限規(guī)劃的最優(yōu)性條件

戴素芬

(重慶師范大學(xué)，重慶 401331)

若R是有效域，一般的半無限規(guī)劃(SIP)有如下形式［1－7］:

其中:x∈R;T是一個(gè)無限集。

出于此目的，文獻(xiàn)［8］中，Pshenichny將(P)換為:的最優(yōu)性條件涉及到f(x)的次微分，但f是非光滑的。

一般來說，盡管函數(shù)ft(x)(t∈T)是凸函數(shù)且可微，且的直接轉(zhuǎn)換。應(yīng)當(dāng)指出的是，當(dāng)(P)退化到一個(gè)有限規(guī)劃后，利用有限最優(yōu)性理論，可以給出最優(yōu)性條件。

文獻(xiàn)［1］中，Ben-Tel，Kerzner和Zlobecgec給出了解凸SIP的不同方法，得到一個(gè)與原問題有相同最優(yōu)值的有有限約束的子問題他的特定方法基于水平集的凸性假設(shè)，哪怕將他的結(jié)論推廣到那些所涉及的函數(shù)是擬凸函數(shù)的問題和那些插入到子問題的約束中的函數(shù)是嚴(yán)格擬凸的問題也同樣適用。只有在的所有函數(shù)(包括目標(biāo)函數(shù))都是凸函數(shù)且(P)的最優(yōu)值v(P)有限時(shí)才能得到一個(gè)拉格朗日條件。

本文最優(yōu)性條件對于涉及標(biāo)準(zhǔn)拉格朗日鞍點(diǎn)概念的凸SIP是存在的，局部和全局的約束品性是給定的，對于特定線性化系統(tǒng)，它們展現(xiàn)了其超越F-M性質(zhì)的優(yōu)越性。

這篇文章結(jié)構(gòu)如下:第1部分引入了一些符號(hào)和初步結(jié)果;第2部分包含了對于非光滑凸SIP的拉格朗日鞍點(diǎn)的特征，給定2個(gè)約束品性:一個(gè)局部的，稱為拉格朗日準(zhǔn)則，另一個(gè)是Slater品性的推廣，論證了Slater品性蘊(yùn)含了所有可行點(diǎn)的拉格朗日準(zhǔn)則;第3部分介紹了一個(gè)全局約束品性，它蘊(yùn)含在Slater品性中，通過函數(shù)ft的次梯度給出可行集S的一個(gè)線性表示。函數(shù)ft的次梯度在S的某些邊界點(diǎn)上函數(shù)值為0。

將一個(gè)凸SIP的線性表示與F-M性質(zhì)的重要性聯(lián)系起來，可得出結(jié)論:Slater品性對于SIP太過嚴(yán)格。本文第3部分及文獻(xiàn)［3］中的定理3.2證明了Slater品性產(chǎn)生典型地閉線性系統(tǒng)，且F-M性質(zhì)更為廣泛，這些思想涉及到不同的可能性，如試圖將(P)的拓?fù)湫再|(zhì)利用到它在T上的獨(dú)立性。沿著這些方向，也可能會(huì)涉及到文獻(xiàn)［1］中的一致中值性質(zhì)。

1 符號(hào)和初步結(jié)果

令ft，t∈{}T是R中由有限凸函數(shù)構(gòu)成的集合，子標(biāo)集T是無限集，在R中考慮凸不等式系統(tǒng):{ft(x)≤0，t∈T}。

記S為該系統(tǒng)的解集，當(dāng)S≠?時(shí)，系統(tǒng)是相容的。當(dāng)2個(gè)系統(tǒng)有相等的解時(shí)稱它們是等價(jià)的。定義集合分量λt中只有有限個(gè)不為0，其余都為0}。

給定一個(gè)非空集C?R，記〈C〉為C的凸包，K(C)為由C生成的凸錐，clC為C的閉，intC為C的內(nèi)部，C*為C的對偶錐，R中的零向量記為0n。

令 {a'tx≤βt，t∈T}是R中的一個(gè)線性無限系統(tǒng)，若該系統(tǒng)的每一個(gè)解都滿足關(guān)系a'x≤β，則稱a'x≤β是該系統(tǒng)的一個(gè)后承關(guān)系。

現(xiàn)介紹要用到的已知結(jié)論。

引理1(文獻(xiàn)［5］中的引理 14.1)a'x≤0是系統(tǒng) {a'tx≤0，t∈T}的一個(gè)后承關(guān)系，當(dāng)且僅當(dāng)a∈clK{ at，t∈T}。

引理2(文獻(xiàn)［5］中的引理 14.2)a'x≤β 是相容系統(tǒng) {a'tx≤βt，t∈T}的一個(gè)后承關(guān)系，當(dāng)且僅當(dāng)a'x+βτ≤0 是系統(tǒng) {a'tx+βτ≤0，τ≤0，t∈T}的一個(gè)后承關(guān)系。

定理1 a'x≤β 是相容系統(tǒng) {a'tx≤βt，t∈T}的一個(gè)后承關(guān)系，當(dāng)且僅當(dāng)

證明由引理2知，a'x≤β是系統(tǒng) {a'tx≤βt，t∈T}的一個(gè)后承關(guān)系，當(dāng)且僅當(dāng)a'x+βτ≤0是系統(tǒng){a'tx+ βτ≤0，τ≤0，t∈T}的一個(gè)后承關(guān)系，即蘊(yùn)含再由引理1知最終結(jié)論可由引理1得到。

定義1 對于相容系統(tǒng) {a'tx≤βt，t∈T}，若它的每一個(gè)后承關(guān)系都是一個(gè)有限子規(guī)劃的后承關(guān)系，則該相容系統(tǒng)滿足Farkas-Minkowski性質(zhì)(F-M性質(zhì))。

定義2 系統(tǒng) {a'tx≤βt，t∈T}是典型閉(CC)的，若滿足:

① 存在一個(gè)代數(shù)內(nèi)點(diǎn)，即?x0∈Rn，對于所有的 t∈T，有

定理2［6］相容系統(tǒng)滿足F-M性質(zhì)，當(dāng)且僅當(dāng)是閉集。

F-M性質(zhì)保證了對應(yīng)的系統(tǒng)產(chǎn)生一致LP對偶性。

推論1［6］系統(tǒng)滿足F-M性質(zhì)，當(dāng)且僅當(dāng)是閉集。

推論2［10］若相容系統(tǒng)滿足以下條件之一，則它是一個(gè)F-M系統(tǒng):

②系統(tǒng)是典型閉的。

在文獻(xiàn)［6］中由定理2.6直接推導(dǎo)出證明過程。條件②由文獻(xiàn)［4］中Duffin和Karloviz證明。

2 與拉格朗日鞍點(diǎn)有關(guān)的最優(yōu)性條件

將拉格朗日函數(shù)與問題(P)聯(lián)系起來:

以下命題刻畫了涉及給定的鞍點(diǎn)的存在性。

引理3 給定，存在一個(gè)與有關(guān)的拉格朗日鞍點(diǎn)，當(dāng)且僅當(dāng)?x∈S，且

證明假設(shè)是一個(gè)拉格朗日鞍點(diǎn)，由于是(P)的一個(gè)最優(yōu)解。此外是凸函數(shù)的一個(gè)全局最小，則

而

是一個(gè)閉凸錐，可證:

引理4 若，則。

證明對于，則對，若則

定義3 點(diǎn)稱為一個(gè)拉格朗日正則點(diǎn)，若:

條件②是Guignard品性到非光滑半無限情形的推廣。條件③是系統(tǒng)在處存在F-M性質(zhì)的充分必要條件。由于T是有限的，且為可微函數(shù)是一個(gè)多面體錐，所以條件③成立。

以下給出一個(gè)必要最優(yōu)性條件。

引理5 令是凸SIP的一個(gè)最優(yōu)解，若x是一個(gè)拉格朗日正則點(diǎn)，則存在是 ψ的一個(gè)鞍點(diǎn)。

在對凸SIP的Slater品性作出推廣之前，分析一個(gè)凸函數(shù)的水平集的代數(shù)內(nèi)部和拓?fù)鋬?nèi)部之間的關(guān)系。

引理6 令f(x)是R中的一個(gè)凸函數(shù)，且，則S0≠?蘊(yùn)含著intS=S0。

證明由連續(xù)性S0?intS。給定y∈intS且x0∈S0。當(dāng)y≠x0時(shí)，取z∈S，s.t.y介于x0與z之間的內(nèi)部，由于f(x0)＜0且f(z)≤0，由連續(xù)性有f(y)＜0。

注:當(dāng)f(x)是一個(gè)下半連續(xù)的嚴(yán)格擬凸函數(shù)時(shí)，以上結(jié)論仍然成立。

定義4 凸SIP的Slater品性:

①T?R是一個(gè)緊集;

② ft(x)是T×R中(t，x)的一個(gè)連續(xù)函數(shù);

③ 存在一個(gè)點(diǎn)x0，使得對于所有的t∈t，ft(x0)＜0。

對于滿足條件①的凸SIP，利用文獻(xiàn)［9］中的定理10.7，條件② 可改為:對于每一個(gè)x∈R，f(·，x)是t處的連續(xù)函數(shù)。

對于定理3，需要一個(gè)初步引理，該引理是Gordon擇一性定理的一個(gè)推廣。

引理7對所有t∈T，令at∈R，若〈at，t∈{}T〉是一個(gè)閉集，則以下命題(Ⅰ)和命題(Ⅱ)有且僅有一個(gè)成立。

命題(Ⅰ):{a'tx＜0，t∈T}是相容的。

命題(Ⅱ):0n∈〈at，t∈{}T〉。

證明若?t∈T，at=0，則結(jié)論成立。

假設(shè)對所有的t∈T，at≠0n。首先，證明命題(Ⅱ)成立時(shí) 命題(Ⅰ)不成立。

采用反證法，假設(shè)命題(Ⅰ)成立，x是命題(Ⅰ)的一個(gè)解，則對。因?yàn)槊}(Ⅱ)成立，所以，因此0，矛盾，即命題(Ⅱ)成立時(shí)命題(Ⅰ)不成立。

現(xiàn)證命題(Ⅰ)不成立時(shí)命題(Ⅱ)成立。

采用反證法，假設(shè)命題(Ⅱ)不成立，即0?〈{at:t∈T}〉。由嚴(yán)格凸集分離定理可知，?c∈R，c≠0，s.t.c'at＜0(?t∈T)，所以c為命題(Ⅰ)線性系統(tǒng)的解，矛盾，即命題(Ⅰ)不成立時(shí)命題(Ⅱ)成立。

現(xiàn)依然假設(shè)〈{at，t∈T}〉是閉集。

定理3 假設(shè)凸SIP滿足Slater品性，所有可行點(diǎn)都是拉格朗日正則點(diǎn)。

證明令，對所有 t∈T}，定義

3 全局約束品性:F-M線性化

對于凸SIP，給定一個(gè)全局約束品性，在每一個(gè)最優(yōu)解x處與本文第2部分要求的拉格朗日正則點(diǎn)的局部條件交錯(cuò)開來以得到必要最優(yōu)性條件。事實(shí)上，Slater品性涉及了所有約束構(gòu)成的集合且該部分涉及的品性也蘊(yùn)含其中。

定義5 將非光滑凸SIP與以下線性不等式系統(tǒng)結(jié)合起來:

由凸性知，ft(y)≥ft(x)+▽ft(y)T(y－x)，即 ft(y)≥ft(x)+u'(y－x)，由于 ft(y)≤u'(y－x)，所以ft(x)≥0，即系統(tǒng)(1)的解集即為凸SIP的可行域S，因此，以上系統(tǒng)是凸SIP約束的一個(gè)線性表示。

定義6(F-M品性)凸SIP的約束滿足F-M品性，若與系統(tǒng)(1)等價(jià)的系統(tǒng)是一個(gè)F-M系統(tǒng)。

定理4 若是滿足F-M品性的一個(gè)凸SIP的一個(gè)最優(yōu)點(diǎn)，則是一個(gè)拉格朗日鞍點(diǎn)。

證明由于是問題mx∈inSψ(x)上的一個(gè)最優(yōu)解，所以對所有 x∈S，有

當(dāng) t=ti，令且若 t≠ti，令，則是ψ的一個(gè)鞍點(diǎn)。

在證明主要結(jié)論，即定理5(它給出了Slater品性與F-M品性之間的關(guān)系)的過程中，需要一個(gè)初步引理，其中用Sb表示S的邊界。

引理8 令S?R是一個(gè)閉凸集，{ct'x≤δt，t∈T}是滿足以下條件的一個(gè)系統(tǒng):

①S的每一個(gè)點(diǎn)都是該系統(tǒng)的解;

② ?x0∈S，s.t.ct'x0＜ δt，t∈T;

③ 給定?y∈Sb，?t∈T，s.t.c'ty= δt。

現(xiàn)闡述該部分的主要結(jié)果，其中給出Slater品性的有限性質(zhì)，從這一結(jié)論中得到F-M性質(zhì)的重要性。

定理5 若凸SIP滿足Slater品性，且S有界，則該凸SIP滿足F-M品性。

證明回憶，且，系統(tǒng)為

該系統(tǒng)構(gòu)造S的一個(gè)線性表出，可以看出引理8的假設(shè)成立:

①S的每一個(gè)點(diǎn)都是系統(tǒng)(2)的一個(gè)解;

②x0是系統(tǒng)(2)的一個(gè)代數(shù)內(nèi)點(diǎn);

③給定y∈Sb，存在滿足等式的系統(tǒng)系統(tǒng)(2)的關(guān)系。

應(yīng)證系統(tǒng)(2)是典型閉，從而系統(tǒng)(2)是F-M系統(tǒng)。令集合

需證A是緊集。

另一方面，知道?f在R×R上的圖像是一個(gè)閉集，因此u∈?f(y)［9］233。

以下可得A是閉集。由Schwarz不等式知A是有界的，取和，向量 A的范數(shù)以為上界。

若只有解集S的線性化 {a'px≤βp，p∈P}要求滿足F-M性質(zhì)，定理4同樣適用，它證實(shí)了以下性質(zhì):

對每一個(gè) p∈P，?tp∈T，s.t.對于所有

任何這樣的線性系統(tǒng)都構(gòu)造了文獻(xiàn)［7］中介紹的一個(gè)特定例子，一般來說，系統(tǒng)(1)和(2)結(jié)合凸SIP，證實(shí)了性質(zhì)(3)。

根據(jù)這一可能的準(zhǔn)則，F(xiàn)-M品性非常弱，幾乎給出在一個(gè)最優(yōu)點(diǎn)產(chǎn)生一個(gè)鞍點(diǎn)的充分必要條件，不管目標(biāo)函數(shù)是什么，在這種想法的驅(qū)使下，若約束的原始系統(tǒng)展現(xiàn)了一致凸對偶性，得出結(jié)論:將一個(gè)線性正則變形(它可以產(chǎn)生一個(gè)F-M系統(tǒng))與約束的初始系統(tǒng)聯(lián)系起來是有可能的。

［1］Ben-Tal A，Kerzner L ，Zlobec S.Optimality conditions for convex semi-infinite programming problems［J］.Naval Research Logistics Quarterly，1980，27:413 －435.

［2］Ben-Tal A，Rosinger E E，Ben-Israel A.A Helly-type theorem and semi-infinite programming［M］//Coffman C V，F(xiàn)ix，eds G J.Constructive approaches to mathematical models.New York:Academic Press，1979:127 －135.

［3］Borwein J M.Direct theorems in semi-infinite convex programming［J］.Mathematical Programming，1981，21:301 －318.

［4］Duffin R J，Karlovitz L A.An infinite linear program with a duality gap［J］.Management Science，1965，12:122 －134.

［5］Eremin I I，Astafiev N N.An introduction to the theory of linear and convex programming［M］.Moscow:［s.n.］，1976.

［6］Goberna M A，Lopez M A，Pastor J.Farkas-Minkowski systems in semi-infinite programming［J］.Applied Mathematics and Optimization，1981，7:295 －308.

［7］Jeroslow R G.Uniform duality in semi-infinite convex optimization［J］.Mathematical Programming，1983，27.

［8］Pshenichnyi B N.Necessary conditions for an extremum［M］.New York:Dekker，1971.

［9］Rockafellar R T.Convex analysis［M］.Princeton，NJ:Princeton University Press，1970.

［10］Lopez M A，Vercher E.Optinality conditions for nondifferentiable convex semi-infinite programming［J］.Mathwmatial Programming，1983，27:307 －319.