非線性半定規劃的雅可比唯一性定理

高 婕，張宏偉，張立衛

（大連理工大學 數學科學學院，遼寧 大連 116024）

0 引 言

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

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

1 雅可比唯一性定理

考慮非線性半定規劃問題：

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

式（1）在穩定點處的臨界錐C）定義為

設是可行點，所謂雅可比唯一性條件是指如下的4個條件成立：

（1）存在∈Sp滿足

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

（3）嚴格互補條件成立，即

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

其中

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

其中Λ＝diag｛λ1，…，λp｝，λ1≥… ≥λp是的p個 特 征 值，P∈Rp×p是正交矩陣，P＝（q1…qp），則映射在處沿H∈Sp的方向導數為

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

于是，映射F在處沿（Δx，ΔY）的方向導數為

引入指標集合

則

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

把Ω表示為

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

由式（5）可得

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

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

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

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

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

證明 定義映射

其中

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

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

在u＝0處的連續性，對充分小的ε＞0，u∈B（0，ε）時，

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

作為命題1的應用，考慮擾動問題：

其中Z∈Sp.式（12）的最優值函數被稱為擾動函數，記為ν（Z）.

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

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

其中

由式（14）的第二式得

即

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

根據

和式（16）得

得到結論.

2 一類雙層規劃的最優性條件

考慮如下的雙層優化問題，上層優化問題定義為

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

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

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

其中

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

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

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

令

則

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

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

3 結 語

本文證明了非線性半定規劃的雅可比唯一性定理，擾動問題的函數是決策變量與擾動參數的二次連續可微函數時的擾動解的連續可微性質，擾動函數的導數，以及一類下層為非線性半定規劃的特殊雙層規劃的最優性條件.在雅可比唯一性條件中，嚴格互補條件是至關重要的，如果這一條件不成立，非線性半定規劃的擾動性分析需要用到正半定矩陣錐的非光滑分析.非線性系統的強正則性和映射的Lipschtz同胚，與約束非退化條件和強二階充分性最優條件等詳見文獻［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.