0 引言

内点算法最初是由Karmarka^[1]于1984年为求解线性规划而提出的, 是求解互补问题的一类十分有效的算法.此后许多学者开始关注内点算法及其复杂度的研究.内点算法针对邻域的不同, 分为长步算法和小步算法.Monteiro^[2-3]和Kojima^[4]等研究了窄邻域小步算法及其复杂度, 叶荫予等^[5]提出了一个单调线性互补问题的预估矫正内点算法, 得到窄邻域小步算法的最好的复杂性.但是, 窄邻域算法的步长受制于邻域的宽度, 导致窄邻域算法的实际计算效果稍差.Gonzaga等^[6]和Kojima等^[7]研究了单调线性互补问题的宽邻域的长步内点算法, 其中Kojima^[7]获得了宽邻域长步算法的最好的复杂度O(n).对于非线性互补问题的内点算法及其复杂度也有许多研究, Guler等^[8]针对单调非线性互补问题的内点算法的内点以及中心路径存在性的相关基本理论进行了研究, 这对于设计内点算法有着非常重要的意义.Andersen等^[9]提出了求解单调非线性互补问题的小步齐次算法, 并得到了迄今为止非线性互补问题小步算法最好的复杂度.孙捷等^[10]提出了一个求解单调非线性互补问题的二次收敛大步校正内点算法并且给出算法的复杂度为O(n).可以看到宽邻域长步算法的复杂度较差, 但其在实际计算效果上要优于窄邻域的小步算法.鉴于此, 很多学者致力于研究缩小内点算法的这种理论与实践间的差距^[11-15].

一直以来, 学者们设计的宽邻域算法大多是基于负无穷邻域的, 直到艾文宝等^[16]定义了一个新的宽邻域, 并利用该宽邻域首次得到了和窄邻域小步算法复杂性等同的宽邻域长步内点算法, 且具有良好的计算效果.文献[17]将艾文宝邻域进行简化, 给出对称锥优化问题的不可行宽邻域长步内点算法, 也取得了一些较好的理论结果.本文基于文献[17]提出的宽邻域, 对求解单调非线性互补问题的长步齐次算法进行复杂度分析, 得出其理论复杂度与文献[9]的小步算法的理论复杂度相同.

1 齐次模型及齐次算法描述

单调非线性互补问题:求(y, z)∈ Rⁿ× Rⁿ, 使得

(1)

其中f(x)是可微的单调非线性映射且满足的假设条件:

假设1   (Scaled Lipschitz Condition)存在单调递增函数v:(0, 1)→(1, ∞), 使得

这里dy∈ Rⁿ, y∈ R₊ⁿ满足.

考虑非线性互补问题(1) 的齐次模型(MCP):求(y, τ; z, κ)∈ Rⁿ⁺¹× Rⁿ⁺¹, 使得

(2)

令, 则齐次模型(2) 变为:求(x, s)∈ Rⁿ× Rⁿ, 使得

(3)

由文献[4]知, Φ(x)的雅可比矩阵▽Φ(x)是半正定的, 且.

本文考虑下面的宽邻域.齐次算法描述如下:

给定初始点(x⁰, s⁰)∈N(γ, β), 允许误差ε>0, 令k=0.

步骤1  如果(x^k)^Ts^k≤ε, 则停止.

步骤2  解下列方程组求解方向(dx^k, ds^k)

(4)

其中

步骤3  更新的迭代点及互补间隙

这里步长α_k∈[0, 1]的选择满足下列条件:

步骤4  令转步骤1.

2 算法的复杂度分析

通过简单的计算可以得到下面的表达:

(5)

(6)

这里h(α)=Xs+α(D_xs+Xds), D_x=diag(dx)).则

(7)

这里

引理1^[9]  若假设1满足, 则存在函数v:(0, 1)→(1, ∞)使得函数Φ满足

这里.

引理2  方向(dx, ds)满足

证明   在式(4) 的第一个方程两边分别同乘以dx^T和(x^k)^T有

(8)

又因为-x^T▽Φ(x)=Φ(x)^T, 故有

(9)

联合式(8)，(9) 有

引理3   假设r(α), x(α), s(α), μ(α)由步骤3给定, 则有以下结论成立.

(1) r(α)=(1-α(1-γ))r.

(2) (x(α))^Ts(α)≥(1-α(1-γ))x^Ts.

(3) μ(α)≤μ[1+(βγ+(γ-1))α].

证明  由步骤4易得引理3中(1) 的结论, 下面来证明(2).

因为, 所以有

即μ(α)≤μ[1+(βγ+(γ-1))α].

引理4^[17]  当时, 有

引理5   令, 则有.

证明  由式(7) 及引理4易得结论成立.

引理6  当时, 则函数u(α)在α∈[0, 1]上为严格单调递减.

证明   由引理3可知

所以

当时, βγ+γ-1 < 0, 故μ′(α) < 0, 即μ(α)在α∈[0, 1]上为严格单减函数.

引理7^[17]  令μ(α)>0, 则∀α∈[0, 1]有

为了给出步长α的下界, 定义函数

由于μ(α)为严格单减函数, ▽Φ(x)为半正定的即dx^T▽Φ(x)dx≥0, 故g(α)在α∈[0, 1]上单调递增.

令α_c:=max{α:g(α)≤0, ∀∈[0, 1]}, 故∀α∈[0, α_c]都有

引理8    ∀α∈[0, α_c), 均有‖(γμ(α)e-X(α)s(α))₊‖≤βγμ(α).

证明   类似文献[17]中引理5.9.

引理9  令, 则.

证明  若则易知α_c的下界.下面求当的下界.由g(α)= 故有 而

故有

类似文献[17]中的方法, 易知当时有g(α)≤0.故.

从以上引理1~9可知, 满足步骤3的最大步长, 因此可得算法的复杂度.

定理1   令, 若假设1满足, 则算法复杂度为O((n+1)^1/2·logε^-1).

证明  取, 令ξ=-(βγ+(γ-1)), 则由引理3有

显然当时, 有故算法至少需步终止.所以算法的复杂度为O((n+1)^1/2·logε^-1).

3 数值实验

利用2个算例对本文中的宽邻域长步算法与文献[9]的窄邻域小步算法进行比较.这2个算例均为凸优化问题, 其KKT条件即为单调互补问题, 具体问题的转化及其次模型的建立详见文献[9].算法利用Matlab R2014a编程, 在CPU 2.0GHz, RAM 2GB的PC机上执行.这里gap表示对偶间隙, iter表示算法迭代的次数, t表示算法运行的时间, s, 误差ε=10^-6.

例1  求解线性约束的凸规划问题min -logx₁-logx₂.s.t x₁+2x₂=1, x₁≥0, x₂≥0.

例2  求解如下凸二次规划问题min q(x)=2x₁²+3x₂²+5x₃²+2x₂-3x₃.s.t x₁+x₂=5, x₂+x₃=10, x₁≥0, x₂≥0, x₃≥0.

计算结果见表 1和表 2.从数据结果可以看出, 本文提出的宽邻域长步算法不仅在理论上获得较好的结果, 而且在实际计算上也有较好的效果.

4 结束语

提出一种针对单调非线性互补问题的宽邻域长步齐次内点算法, 并且估计了该算法的理论复杂度.该宽邻域长步算法的理论复杂度为, 与现阶段最好的窄邻域小步算法的理论复杂度一致.数值实验表明该算法不仅具有较好的复杂度，且实际计算效果较好.