对称锥规划的邻域跟踪算法.pdfVIP

刘长河等：对称锥规划的邻域跟踪算法 2 Euclid3ordan代数和对称锥 本节主要介绍 Euclid3ordan代数和对称锥的基本概念与相关理论，并给出在 内点算法分析中用 到的一些重要结果，详细内容参见文献 f6，12]．设 是实数域 上的n维向量空间，定义乘积 “。”使 得双线性映射 (，)_÷ 。 满足下面性质： (1) 。 = o ； (2) 。(。o)= 。(。)，其中， = 。 ， 则称 (，o)是一个 Jordan代数，简记为 ．若还存在一个对称正定的二次型 Q使得 Q(x。 ，) = Q(x，o)，则称 Jordan代数 是 Euclid的，简称为 EuclidJordan代数．若元素 e∈ 满足 。e= e。 = ，V ∈ ，则称 e为 3ordan代数 的单位元．Jordan代数 的平方锥定义为 ：=f。： ∈ ．下面的定理建立 了对称锥与EuclidJordan代数之间的联系，为利用 EuclidJordan 代数研究对称锥上的优化问题奠定了基础，参见文献 1『2，定理III．2．1和III．3．11． 定理 2．1 一个锥是对称锥当且仅当它是某个 EuclidJordan代数的平方锥． 由于乘积 o“”是双线性的，则对任意的 ∈ ，存在线性映射 使得 o =L ，Vy∈ ．特别 地，有 e= ．对于 ，∈ ，定义 Q ：=LL +LL 一L ，Q ：=Q =2 一L Q 称为 的二次表示，它将在对称锥规划的算法分析中起到重要作用，特别地，有 Q e： 。． 设 ∈ ，使得 {e，， …．，矿)线性相关的最小整数r称为 的次数，记为deg(x)．所有 deg(z) 的最大值称为 的秩，记为 rank(J)．若 中的非零元 c满足 c。=c，则称它是幂等的；若一个幂等 元不能表示成两个幂等元的和，则称它是本原的．若一个幂等元集合 fc1，c2… ．，c 满足 ct。cj=0， Vi≠J，且 c1+c2+… +c=e，则称该集合为正交幂等元完备系；进一步，若其中的每个幂等元都是 本原的，则称它为 的Jordan标架． 定理 2．2[121定理II1．1．2]f谱分解) 设 EuclidJordan代数 的秩为 r，则对于任意的 ∈ ，存 在 Jordan标架 {c1，c2… ．，}与一组实数 1，2…．， 使得 = lc1+A2c2+…+Arc，其中， 1， 2… ．， 是 的所有的特征值 (包含重数)． 定义下面运算：当全部特征值 九 ≠0，逆运算 z一 ：= c1+ c2+… + c；当全部特征 值 Ai≥0，平方根运算 zl／2：= ／。c1+A／。c2+…+ ／c；迹 tr(z)：= 1+ 2+…+ ；行列式 det(z)：= 12… ． ∈ 的最小和最大特征值分别记为 Amin()和 ()．若 ∈ 的所有特 征值都不等于零，则称 是可逆的．若 ∈ 的特征是都是非负的 (正的)，则称 是半正定的 (正定 的)，并记作 0( 0)．显然， 是半正定的 (正定的)当且仅当 属于 的平方锥 (平方锥的内 部)，即 ∈ (∈intlC)． 弓l理 2．1[13，引理0·5]若zo ∈int ，贝0det(z)≠0． 设 是秩为 r的EuclidJordan代数，由于对称二次型 tr(zo)满足结合性和正定性 (参见 文献 [12，命题III．1．5和II．4．3】)，则可定义内积 (，)：=tr(z。)．并且对任意的 ，， ∈ ，都有 (。 ，z)= (，。z)．设 ∈ 的特征值为 九，1≤i≤r，定义 Probenius范数和谱范数分别为 lIxllF：=、／／ =、／／ 和lIxll：=mxt _．显然，由于单位元e有r重特征值1，则llellF= ， l2=1．由于内积 (．，．)是结合的，则算子 和 关于内积对称，即 (L ，)= (，Lz)， ( ，)=(，L；-)．同时由定义可知，二次表示Q 也是关于内积对称的． 弓I理 2．2[，引理。]设 ，∈ ，贝0IIx。ylIF≤IIxllFIllIF． 设 是带有单位元 e 的Jordan代数，{c1，c2…．，c)是 的一组 Jordan标架．对于 ，J∈f1， 2…．，r)，定义Peirce空间： t：={ ∈ ：。c： )， J：：{∈ ：oCi：1= 。 )，当t≠J． 692