多项式时间求解P_*(κ)对称锥线性互补问题的内点算法

154 浏览量更新于2024-09-04 收藏 187KB PDF 举报

"王国强和白延琴提出的新算法解决了笛卡尔P*(κ)对称锥线性互补问题，采用欧几里德若当代数，并在内点法基础上进行推广。该算法具有多项式时间复杂度，实现了大步校正和小步校正的优化迭代界。关键词涉及对称锥线性互补问题、笛卡尔P*(κ)性质、内点算法、核函数和欧几里德若当代数。" 这篇论文介绍了一种新的多项式时间内的内点算法，专门用于解决笛卡尔P*(κ)对称锥线性互补问题（P∗(κ)-SCLCP）。P*(κ)是对称锥的一种特殊形式，它在处理线性互补问题时具有重要的数学结构。线性互补问题在优化、经济学和工程领域有广泛应用，因为它可以用来模型化各种均衡和不等式约束的问题。内点法是一种在优化问题中寻找解的有效方法，特别是对于大型线性互补问题。传统的内点法通常适用于标准形式的线性规划问题，而王国强和白延琴的工作是将这种方法扩展到了更复杂的对称锥结构。他们利用了欧几里德若当代数，这是一种非交换但保持一定对称性的代数系统，能够更好地处理这类问题中的几何特性。论文中提到的“大步校正”和“小步校正”是指内点算法的迭代过程。这两种校正策略是为了确保算法的收敛性和效率。大步校正允许算法在每一步中取得较大的优化进步，从而可能减少总的迭代次数；而小步校正则提供了一种更稳定的方法，虽然每一步的进步较小，但在某些情况下可能更适合于避免算法陷入局部最优解。通过使用Nesterov-Todd标度方案，算法强制了搜索方向的对称性，这是保持算法稳定性和收敛性的一个关键因素。Nesterov-Todd标度是内点法中常用的一种技术，能够改进算法的性能并简化计算过程。论文的理论迭代界表明，算法的复杂度为O((1+2κ)√rlogrlogrε)和O((1+2κ)√rlogrε)，其中κ表示P*(κ)对称锥的特征，r是问题的尺寸，ε是所需的精度。这些界表示了解问题所需要的迭代次数与问题规模的关系，显示了算法的多项式时间复杂度。这篇论文提出的算法是针对特定类型线性互补问题的一个重要进展，它通过引入新的数学工具和优化策略，提高了求解效率，特别是在处理大规模问题时。这对于优化领域的理论研究以及实际应用都有着重要的意义。

˖ڍመ᝶஠ڙጲ

http://www.paper.edu.cn

Until now majority of well known polynomial interior-point methods (IPMs) have used

the so-called central path as a guideline to the optimal set, and some variants of the New-

ton’s method to follow the central path approximately. Kojima et al. [3] ﬁrst proved the

existence and uniqueness of the central path for P

∗

(κ)-LCP and generalized the primal-dual

interior-point algorithm for LO to P

∗

(κ)-LCP. Since then, several eﬃcient algorithms have been

provided for P

∗

(κ)-LCP [7, 8], SOCLCP [9, 10] and SDLCP [11, 12]. Via Euclidean Jordan

algebras, Faybusovich [13] ﬁrst studied the interior-point algorithm for monotone SCLCP and

proved the existence and uniqueness of the central path. Luo and Xiu [6] ﬁrst established a the-

oretical framework of path-following interior-point algorithms for the Cartesian P

∗

(κ)-SCLCP

and proved the global convergence and the iteration complexities of the proposed algorithms.

Wang and Bai [14] presented a class of polynomial interior-point algorithms for the Cartesian

∗

(κ)-SCLCP based on a parametric kernel function and obtained the currently best known

iteration bounds with the addition of a factor 1 + 2κ for large- and small-update methods. For

the smooth Newton methods on the Cartesian P

∗

(κ)-SCLCP we refer to [15, 16].

Recently, Bai et al [17] presented a new eﬃcient large-update primal-dual interior-point

method for LO based on a ﬁnite kernel function as follows

1,σ

(t) =

− 1

σ (1−t)

− 1

, σ ≥ 1, (3)

which is not a kernel function in the usual sense (see, e.g., [18]). It has a ﬁnite value at the

boundary of the feasible region, i.e.,

lim

t→0

1,σ

(t) = ψ

1,σ

(0) =

− 1

−

< ∞. (4)

Despite this, the iteration-bound of a large-update method based on this kernel function is

shown to be O(

√

n log n log

). Later on, Ghami et al. [19] considered the generalization of the

ﬁnite kernel function ψ

1,σ

(t) as follows

p,σ

(t) =

p+1

− 1

p + 1

σ (1−t)

− 1

, p ∈ [0, 1], σ ≥ 1. (5)

It is worth pointing out that the parametric kernel function also has ﬁnite value at the boundary

of the feasible region and its growth terms are between linear and quadratic. They proposed a

class of primal-dual interior-point algorithms for LO based on the parametric kernel function

p,q

(t), and derived the currently best known iteration-bounds for large- and small-update

methods, namely, O(

√

n log n log

) and O(

√

n log

), respectively. Meanwhile, the results for

LO in [17] were extended to P

∗

(κ)-LCP by Wang and Bai in [20], again matching the best

known iteration-bounds with the addition 1 + 2κ. An interesting question here is whether we

can directly extend the interior-point algorithms for LO in [17, 19] to the Cartesian P

∗

(κ)-

SCLCP. As we will see later, since the symmetric cone is nonpolyhedral, LO cannot be trivially

generalized to the Cartesian P

∗

(κ)-SCLCP context.

- 3 -

剩余13页未读，继续阅读

weixin_38514732

粉丝: 6
资源: 867

多项式时间求解P_*(κ)对称锥线性互补问题的内点算法

A Polynomial-time Algorithm for the Change-Making Problem.pdf

NEW POLYNOMIAL-TIME ALGORITHM.pdf

Interior methods for nonlinear optimization

polynomial space-time covariance matrix

Quasi-Polynomial Mapping-based Root-Finder

输入x和n的值，用递归法求n阶勒让德多项式的值，递归公司为：

使用递归方法求n阶勒让德多项式的值

请帮我写一个C++函数，有十个点，用一元三次多项式拟合曲线，使用最小二乘法

勒让德多项式型模糊基函数

最新资源