单调线性矩阵互补问题路径跟踪法.pdfVIP

单调线性矩阵互补问题的路径跟踪法 崔娜 南京航空航天大学理学院，南京 (210016) E-mail ：grace991@163.com 摘 要：线性矩阵互补问题是从欧式空间下的线性互补问题推广得到的，最早是由 M.Kajima 等人提出的，他们同时给出了对于该问题的内点法的理论框架及若干算法。本文 用另一个搜索方向重新构造路径跟踪法，并证明了该算法的可行性及收敛性。 关键词：单调线性矩阵互补问题，中心路径，路经跟踪法 引言 单调线性互补问题可在多项式时间内求解，而且人们已经设计出了多种求解单调线性 互补问题的有效内点算法[1]。 线性矩阵互补问题是从欧式空间下的线性互补问题推广得到的，最早是由 M.Kajima 等人在[2]中提出的，他们同时给出了对于该问题的内点法的理论框架及若干算法。本文用 另一个搜索方向重新构造路径跟踪法，并证明了该算法的可行性及收敛性。 1. 线性矩阵互补问题 n×n 本文用R n×n 表示全体n 阶实对称矩阵的集合，用S ，S n×n ，及S n×n 分别表示n 阶实 + ++ 对称矩阵，实对称半正定矩阵及实对称正定矩阵的集合；用Tr( X ) 表示矩阵X 的迹，对 X ,Y ∈R n×n , 定义内积为X •Y Tr (X TY ) 。 线性矩阵互补问题的一般形式是：求X ,Y ∈S n×n 使其满足： Y L( X ) =+ Q, X ≥ O, Y ≥ O, 且X • Y 0 (*) 其中Q ∈ S n×n , L : S n×n → S n×n 为线性算子，而X ≥ O 表示X ∈ S n×n ，O 表示零矩阵。 + 记 Ω {(X ，Y ) =∈ S n×n |Y L (X ) =+ Q , X ≥ O ,Y ≥ O } ， ⎧ n×n ⎫ (X ，Y ) ∈S |Y L (X ) =+Q , Ω+ ⎨ ⎬ ， X O ,Y O ⎩ ⎭ 称Ω 为问题(*)的可行域，称Ω 为问题(*)的严格可行域。 + 定义 1.1 若L : S n×n → S n×n , Y L( X ) + Q, 满足X •Y ≥ 0, ∀X ∈S n×n , 则称L 为单调算 子，而相应的问题(*)称为单调线性矩阵互补问题。 本文采用记号如下：用 M 表示矩阵M 的谱范数；用 M 表示矩阵M 的 Frobenius F 范数；用I 表示单位矩阵。 记 ⎧ 1 1 ⎫ 2 2 C ⎨( X , Y ) =∈ Ω+ | X YX µ I , 0 = µ +∞⎬