·288· 智能系统学报 第9卷 式(8)求解6。 活动约束的符号。 |x(x邓41-Y)|≤Ts1HyeT 综上所述，可以得到PD-Pursuit算法的伪代码 x(Xβ-Y)+8xXaB|≤Tk-δHy∈T 如下： PL(y) d() 原始-对偶算法： δ*=min Te -Pi(i)T+p(i') 给定一个迭代停止条件？，当k=1时，初始化： *er（1+d4(i)’1-d(i) Bg=0,入k=0,Tg=[],Ta=[],g=[],aa= []:T=xYIL; -B(i) -=min ,δ=min(8*,6) repeat: rera（B(i) k←k+1原始更新： (8) 根据式(8)、(10)计算P4、d、δ、p 式中：min(.),表示只接收正数并取最小的一个。其 B+1=Bg+δ那，Tk+1=Tk-8; 中i,分别表示88所对应的索引号。如果 Ifδ=8then δ*<δ，新的索引号进入索引集T,,否则留在 TB←Tei将从「g中移去并更新「B; 「g相应的符号g更新，同伦参数变成T+1=T4-8。 Ta←Ty选择一个索引号y并从T移出： 1.4.3对偶向量更新 之，=z(y）: 同理对于对偶向量，可以假设入k1=入：+入， 更新2B； 0>0,根据式(7)求得的入联合定义式(9)可以求0。 Else |xTX入+1l≤1Hv∈TB T,=T.U{*}把存入T但不更新T,; |xTXA:+BxTX8A≤1Hv∈TB a=sign[X,(X邓+1-Y)]; a(w） (p) y=i'; 1-a()1+a() (9) 之y=2(Y）; 0*=min °er（b(j产) '1-b() End if 对偶更新： -B.) 0=min ,0=min(0,8-) .rβ(U)J 根据式(9)、(11)计算a入、ak、b: If 6=5-&sign [a(i)]=sign [b(i)then 式中广广分别表示*、0所对应的索引号。如果 a入←--a入； 0*<0,新的索引号进入索引集T。,否则j留 bg←-bk; 在T相应的符号z更新。 End if 1.4.4方向更新 根据式(9)计算0 假设在一个参数τ：下可以得到一对原始对偶 入k+1=入k+60入； 解(B,入)，其支撑集和符号用(T,Tg,之，g) If =0 then 来表示。根据(K,~K,)的优化条件可以推导出原始 T←Ty将索引广从T中移去更新Ta: 向量和对偶向量的方向更新。对原始向量β：，在 更新2； B方向上使得r减少最大。利用(K)可以得到B Else 的更新方向邮： TB←TgU}把j存入Tg并更新IB; ∫-(xX)a,在集合TB上 那= (10) g=sign[XX入41]： 0,其他 End if 对于对偶向量的更新方向入，首先假设在原 直到Tk+1≤T停止迭代。 始更新阶段一个新的索引入进入集合T,利用原 上述算法的主要的时间复杂度来自于更新方向 始更新的附加条件和条件(K2),可以得到入：的更 Ta、TB以及入、邱和沿该方向的更新路径长度δ、 新aA: 日。每一步计算中都要计算一个方阵。X和它 -,(XX)-1X。,在集合上 的逆矩阵。因为该算法是每一次在原集合添加或移 a入= ,y更新 去一个元素，因此每一次计算的时候都不需要整个 0,其他 线性系统都计算。对于一个维数为n×p的矩阵 (11) X,假设第k步支撑集的长度是S,S:≤p,每一次 式中：x,表示集合X的第y列，，表示第y个原始 计算复杂度为O(S+Sn),对于X。Xr的求逆，式（８）求解 δ 。 ｘ Ｔ γ（Ｘβｋ＋１ － Ｙ） ≤ τｋ＋１∀γ ∈ Γλ ｘ Ｔ γ（Ｘβｋ － Ｙ） þ ï ï ý ï ï ü ｐｋ （γ） ＋ δ ｘ Ｔ}γＸ∂β ｄｋ （γ） ≤ τｋ － δ∀γ ∈ Γλ δ ＋ ＝ ｍｉｎ ｉ ＋∈Γλ τｋ － ｐｋ（ｉ ＋ ） １ ＋ ｄｋ（ｉ ＋ ） ， τｋ ＋ ｐｋ（ｉ ＋ ） １ － ｄｋ（ｉ ＋ ） æ è ç ö ø ÷ ＋ δ － ＝ ｍｉｎ ｉ －∈Γλ － βｋ（ｉ － ） ∂β（ｉ － ） æ è ç ö ø ÷ ＋ ，δ ＝ ｍｉｎ（δ ＋ ，δ － ） （８） 式中： ｍｉｎ（．） ＋ 表示只接收正数并取最小的一个。 其 中 ｉ ＋ 、ｉ － 分别表示 δ ＋ 、δ － 所对应的索引号。 如果 δ ＋ ＜ δ － ，新的索引号 ｉ ＋ 进入索引集 Γλ ，否则 ｉ － 留在 Γβ 相应的符号 ｚβ 更新，同伦参数变成 τｋ＋１ ＝ τｋ － δ 。 １．４．３ 对偶向量更新 同理对于对偶向量，可以假设 λｋ＋１ ＝ λｋ ＋ θ∂λ， θ ＞ ０， 根据式（７）求得的 λｋ 联合定义式（９）可以求 θ 。 ｘ Ｔ νＸλｋ＋１ ≤ １∀ν ∈ Γβ ｘ Ｔ}νＸλｋ ａｋ （ν） ＋ θ ｘ Ｔ}νＸ∂λ ｂｋ （ν） ≤ １∀ν ∈ Γβ θ ＋ ＝ ｍｉｎ ｊ ＋∈Γλ １ － ａｋ（ｊ ＋ ） ｂｋ（ｊ ＋ ） ， １ ＋ ａｋ（ｊ ＋ ） １ － ｂｋ（ｊ ＋ ） æ è ç ö ø ÷ ＋ θ － ＝ ｍｉｎ ｊ －∈Γλ － βｋ（ｊ － ） ∂β（ｊ － ） æ è ç ö ø ÷ ＋ ，θ ＝ ｍｉｎ（θ ＋ ，θ － ） （９） 式中 ｊ ＋ 、ｊ － 分别表示 θ ＋ 、θ － 所对应的索引号。 如果 θ ＋ ＜ θ － ，新的索引号 ｊ ＋ 进入索引集 Γβ ，否则 ｊ － 留 在 Γλ 相应的符号 ｚλ 更新。 １．４．４ 方向更新 假设在一个参数 τｋ 下可以得到一对原始对偶 解 （βｋ，λｋ） ， 其支撑集和符号用 （Γλ ，Γβ ，ｚλ ，ｚβ ） 来表示。 根据（Ｋ１ ～ Ｋ４ ）的优化条件可以推导出原始 向量和对偶向量的方向更新。 对原始向量 βｋ ，在 ∂β 方向上使得 τｋ 减少最大。 利用（Ｋ１ ）可以得到 βｋ 的更新方向 ∂β ： ∂β ＝ － （Ｘ Ｔ Γλ ＸΓβ ） －１ ｚλ ，在集合 Γβ 上 ０，其他 { （１０） 对于对偶向量的更新方向 ∂λ ，首先假设在原 始更新阶段一个新的索引 λ 进入集合 Γλ ，利用原 始更新的附加条件和条件（Ｋ２ ），可以得到 λｋ 的更 新 ∂λ ： ∂λ ＝ － ｚγ（Ｘ Ｔ Γβ ＸΓλ ） － １ Ｘ Ｔ Γ β ｘγ ，在集合 Γλ 上 ｚγ ，γ 更新 ０，其他 ì î í ï ï ï ï （１１） 式中： ｘγ 表示集合 Ｘ 的第 γ 列， ｚγ 表示第 γ 个原始 活动约束的符号。 综上所述，可以得到 ＰＤ⁃Ｐｕｒｓｕｉｔ 算法的伪代码 如下： 原始－对偶算法： 给定一个迭代停止条件 τ ，当 ｋ ＝ １ 时，初始化： βｋ ＝ ０，λｋ ＝ ０，Γβ ＝ ［］，Γλ ＝ ［］，ｚβ ＝ ［］，ｚλ ＝ ［］； τｋ ＝ Ｘ ＴＹ ¥ ； ｒｅｐｅａｔ： ｋ ← ｋ ＋ １ 原始更新： 根据式 （８）、（１０） 计算 ｐｋ、ｄｋ、δ、∂β βｋ＋１ ＝ βｋ ＋ δ∂β，τｋ＋１ ＝ τｋ － δ ； Ｉｆ δ ＝ δ － ｔｈｅｎ Γβ ← Γβ ＼ｉ － 将 ｉ － 从 Γβ 中移去并更新 Γβ ； Γλ ← Γλ ＼γ 选择一个索引号 γ 并从 Γλ 移出； ｚγ ＝ｚλ（γ） ； 更新 ｚλ 、ｚβ ； Ｅｌｓｅ Γλ ＝ Γλ ∪ ｛ｉ ＋ ｝ 把 ｉ ＋ 存入 Γλ 但不更新 Γλ ； ｚλ ＝ ｓｉｇｎ［Ｘ Ｔ Γλ （Ｘβｋ＋１ － Ｙ）］ ； γ ＝ ｉ ＋ ； ｚγ ＝ ｚλ（γ） ； Ｅｎｄ ｉｆ 对偶更新： 根据式（９）、（１１） 计算 ∂λ、ａｋ、ｂｋ Ｉｆ δ ＝ δ － ＆ ｓｉｇｎ ａｋ（ｉ － [ ） ] ＝ ｓｉｇｎ ｂｋ（ｉ － [ ） ] ｔｈｅｎ ∂λ ←－ ∂λ ； ｂｋ ←－ ｂｋ ； Ｅｎｄ ｉｆ 根据式 （９）计算 θ λｋ＋１ ＝ λｋ ＋ δ∂λ ； Ｉｆ θ ＝ θ － ｔｈｅｎ Γλ ← Γλ ＼ｊ － 将索引 ｊ － 从 Γλ 中移去更新 Γλ ； 更新 ｚλ ； Ｅｌｓｅ Γβ ← Γβ ∪ ｛ｊ ＋ ｝ 把 ｊ ＋ 存入 Γβ 并更新 Γβ ； ｚβ ＝ ｓｉｇｎ［Ｘ Ｔ Γ β Ｘλｋ＋１ ］ ； Ｅｎｄ ｉｆ 直到 τｋ＋１ ≤ τ 停止迭代。 上述算法的主要的时间复杂度来自于更新方向 Γλ 、Γβ 以及 ∂λ、∂β 和沿该方向的更新路径长度 δ、 θ 。 每一步计算中都要计算一个方阵 Ｘ Ｔ Γ β ＸΓλ 和它 的逆矩阵。 因为该算法是每一次在原集合添加或移 去一个元素，因此每一次计算的时候都不需要整个 线性系统都计算。 对于一个维数为 ｎ × ｐ 的矩阵 Ｘ ，假设第 ｋ 步支撑集的长度是 Ｓｋ，Ｓｋ ≪ ｐ ，每一次 计算复杂度为 Ｏ（Ｓ ３ ｋ ＋ Ｓ ３ ｋｎ） ，对于 Ｘ Ｔ Γ β ＸΓλ 的求逆， ·２８８· 智 能 系 统 学 报 第 ９ 卷