非線性半定規(guī)劃的雅可比唯一性定理

高 婕，張宏偉，張立衛(wèi)

（大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，遼寧 大連 116024）

0 引 言

最優(yōu)化問題的擾動分析是非常重要的專題，在數(shù)值算法實(shí)現(xiàn)的穩(wěn)健性分析和雙層規(guī)劃的理論研究中起著非常重要的作用.目前，擾動分析的研究已經(jīng)取得了豐富的進(jìn)展，比如近年來國際優(yōu)化領(lǐng)域出版了關(guān)于變分分析、擾動分析、非光滑方程和互補(bǔ)與變分不等式的著名專著［1－4］，在這些專著中最優(yōu)化的擾動理論都不同程度地被給予關(guān)注.文獻(xiàn)［5］詳細(xì)介紹了非線性規(guī)劃的擾動分析結(jié)果，文獻(xiàn)［2］詳細(xì)介紹了一般最優(yōu)化問題的擾動分析結(jié)果.

追溯到擾動分析的早期工作，討論的問題非常特殊，如討論問題的函數(shù)是二次連續(xù)可微的，擾動后的函數(shù)關(guān)于決策變量和擾動參數(shù)也是二次連續(xù)可微的，在此情況下，擾動問題解的存在性、連續(xù)性和微分性質(zhì).Fiacco等［6］在1968 年對非線性規(guī)劃在這種情況的擾動分析給出討論，提出了著名的雅可比唯一性條件（Jacobian uniqueness conditions）.對非線性半定規(guī)劃而言，類似的雅可比唯一性條件是什么樣的條件，由此條件出發(fā)得到什么樣的穩(wěn)定性理論，還沒有文獻(xiàn)涉及，本文討論這些問題.

1 雅可比唯一性定理

考慮非線性半定規(guī)劃問題：

其中f：Rn→R 與G：Rn→Sp是二次連續(xù)可微函數(shù)和映射.式（1）的Lagrange函數(shù)定義為

式（1）在穩(wěn)定點(diǎn)處的臨界錐C）定義為

設(shè)是可行點(diǎn)，所謂雅可比唯一性條件是指如下的4個(gè)條件成立：

（1）存在∈Sp滿足

（2）約束非退化條件在處成立，即

（3）嚴(yán)格互補(bǔ)條件成立，即

（4）二階充分條件成立，即

其中

定理1 設(shè)f：Rn→R與G：Rn→是二次連續(xù)可微函數(shù)和映射，Φ是式（1）的可行集合，∈Φ滿足條件（1）～（4），則映射

其中Λ＝diag｛λ1，…，λp｝，λ1≥… ≥λp是的p個(gè) 特 征 值，P∈Rp×p是正交矩陣，P＝（q1…qp），則映射在處沿H∈Sp的方向?qū)?shù)為

其中。為矩陣的Hadamard乘積運(yùn)算，Ω∈Sp的元素Ωij定義為

于是，映射F在處沿（Δx，ΔY）的方向?qū)?shù)為

引入指標(biāo)集合

則

記Pα＝（pi：i∈α），Pγ＝（pi：i∈γ）.由于嚴(yán)格互補(bǔ)條件成立，臨界錐C（）可以表示為

把Ω表示為

則Ωαα＝1｜α｜1T｜α｜，Ωγγ＝0｜γ｜×｜γ｜，

由式（5）可得

用Δx與式（4）兩邊的向量做內(nèi)積，并由式（9）可得

即根據(jù)在條件（3）成立的前提下臨界錐的表達(dá)式（6），式（9）的第一式意味著Δx∈C（），因此由二階條件和式（10）可推出Δx＝0.由式（4）可得

由此結(jié)合PTαΔYPγ＝0與PTγΔYPγ＝0以及約束非退化條件（2），得到PTαΔYPα＝0，于是得到ΔY＝0.證畢.

在雅可比唯一性條件成立的前提下，可以進(jìn)行式（1）的穩(wěn)定性分析.

命題1 考慮如下的擾動問題：

證明 定義映射

其中

由（x（·），Y（·））的連續(xù)性，對u∈B（0，ε），式（11）在x（u）處的約束非退化條件成立，嚴(yán)格互補(bǔ)條件成立.

在u＝0處連續(xù)（在變分分析的集值映射連續(xù)的意義下）以及

在u＝0處的連續(xù)性，對充分小的ε＞0，u∈B（0，ε）時(shí)，

即在（x（u），Y（u））處，式（11）的二階充分最優(yōu)性條件成立，因此x（u）是式（11）滿足二階增長條件的局部極小點(diǎn).

作為命題1的應(yīng)用，考慮擾動問題：

其中Z∈Sp.式（12）的最優(yōu)值函數(shù)被稱為擾動函數(shù)，記為ν（Z）.

定理2 設(shè)f：Rn→R與G：Rn→Sp－ 是二次連續(xù)可微函數(shù)和映射，∈Φ滿足條件（1）～（4），則

證明 由命題1，存在ε＞0，唯一的連續(xù)可微映 射（x，Y）滿足對任意的Z∈B（0，ε），（x（Z），Y（Z））滿足式（12）的KKT 條件，即

其中

由式（14）的第二式得

即

由于（1p1Tp－Ω）αα＝0｜α｜×｜α｜，Ωαα＝1｜α｜1｜α｜T，由式（15）得

根據(jù)

和式（16）得

得到結(jié)論.

2 一類雙層規(guī)劃的最優(yōu)性條件

考慮如下的雙層優(yōu)化問題，上層優(yōu)化問題定義為

下層為問題P（u），定義如下：

其中θ：Rn×Rm→R是連續(xù)可微函數(shù)，UadRm是非空閉凸集合，Sol P（u）表示問題P（u）的最優(yōu)解集合，B：Rm→Sp是一連續(xù)的線性算子.

對任何u∈Rm，設(shè)在（x（u），Y（u））處問題P（u）的雅可比唯一性條件成立，由命題1 得，（x（u），Y（u））是二次連續(xù)可微映射，滿足

其中

命題2 設(shè)f：Rn→R與G：Rn→Sp－ 是二次連續(xù)可微函數(shù)和映射，對每一u∈Rm，（x（u），Y（u））處問題P（u）的雅可比唯一性條件成立.如果u＊∈Uad是式（17）的局部極小點(diǎn)，則

其中（P1，P2）∈Rn×Sp滿足如下的伴隨方程：

證明 定義θ0（u）＝θ（x（u），u）.如果u＊∈Uad是式（17）的局部極小點(diǎn)，則

令

則

注意到式（21）可以表示為

得到對u∈Uad，即式（20）成立.

3 結(jié) 語

本文證明了非線性半定規(guī)劃的雅可比唯一性定理，擾動問題的函數(shù)是決策變量與擾動參數(shù)的二次連續(xù)可微函數(shù)時(shí)的擾動解的連續(xù)可微性質(zhì)，擾動函數(shù)的導(dǎo)數(shù)，以及一類下層為非線性半定規(guī)劃的特殊雙層規(guī)劃的最優(yōu)性條件.在雅可比唯一性條件中，嚴(yán)格互補(bǔ)條件是至關(guān)重要的，如果這一條件不成立，非線性半定規(guī)劃的擾動性分析需要用到正半定矩陣錐的非光滑分析.非線性系統(tǒng)的強(qiáng)正則性和映射的Lipschtz同胚，與約束非退化條件和強(qiáng)二階充分性最優(yōu)條件等詳見文獻(xiàn)［7］.

［1］ Rockafellar R T，Wets R J B.Variational Analysis［M］.Berlin：Springer，1998.

［2］ Bonnans J F，Shapiro A.Perturbation Analysis of Optimization Problems ［M］.Berlin：Springer，2000.

［3］ Klatte D，Kummer B.Nonsmooth Equations in Optimization：Regularity，Calculus，Methods and Applications ［M］.Boston：Kluwer Academic Publishers，2002.

［4］ Facchinei F，Pang Jong－shi.Finite－Dimensional Variational Inequalities and Complementarity Problems：Volume I［M］.Berlin：Springer，2003.

［5］ Fiacco A V.Introduction to Sensitivity and Stability Analysis in Nonlinear Programming ［M］.New York：Academic Press，1983.

［6］ Fiacco A V，McCormick G P.Nonlinear Programming：Sequential Unconstrained Minimization Techniques［M］.Philadelphia：Society for Industrial and Applied Mathematics，1990.

［7］ SUN De－feng.The strong second－order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications［J］.Mathematics of Operations Research，2006，31（4）：761－776.