Long-Step Primal Path-Following Algorithm for Monotone Variational Inequality Problems

In this paper, we present a long-step primal path-following algorithm and prove its global convergence under usual assumptions. It is seen that the short-step algorithm is a special case of the long-step algorithm for a specific selection of the parameters and the initial solution. Our theoretical result indicates that the long-step algorithm is more flexible. Numerical results indicate that the long-step algorithm converges faster than the short-step algorithm.     

单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的.     

Complexity of a Noninterior Path-Following Method for the Linear Complementarity Problem

We study the complexity of a noninterior path-following method for the linear complementarity problem. The method is based on the Chen–Harker–Kanzow–Smale smoothing function. It is assumed that the matrix M is either a P-matrix or symmetric and positive definite. When M is a P-matrix, it is shown that the algorithm finds a solution satisfying the conditions Mx-y+q=0 and in at most

A New Path-Following Algorithm for Nonlinear P*Complementarity Problems

Based on the recent theoretical results of Zhao and Li [Math. Oper. Res., 26 (2001), pp. 119—146], we present in this paper a new path-following method for nonlinear P* complementarity problems. Different from most existing interior-point algorithms that are based on the central path, this algorithm tracks the “regularized central path” which exists for any continuous P* problem. It turns out that the algorithm is globally convergent for any P* problem provided that its solution set is nonempty. By different choices of the parameters in the algorithm, the iterative sequence can approach to different types of points of the solution set. Moreover, local superlinear convergence of this algorithm can also be achieved under certain conditions. The research of the first author was supported by The National Natural Science Foundation of China under Grant No. 10201032 and Grant No. 70221001. The research of the second author was supported by Grant CUHK4214/01E, Research Grants Council, Hong Kong. An erratum to this article is available at .     

Superlinear Noninterior One-Step Continuation Method for Monotone LCP in the Absence of Strict Complementarity

We propose a noninterior continuation method for the monotone linear complementarity problem (LCP) by modifying the Burke–Xu framework of the noninterior predictor-corrector path-following method (Refs. 1–2). The new method solves one system of linear equations and carries out only one line search at each iteration. It is shown to converge to the LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution. Our analysis of the continuation method is based on a broader class of the smooth functions introduced by Chen and Mangasarian (Ref. 3).     

High Order Long-Step Methods for Solving Linear Complementarity Problems

The paper is concerned with methods for solving linear complementarity problems (LCP) that are monotone or at least sufficient in the sense of Cottle, Pang and Venkateswaran (1989). A basic concept of interior-point-methods is the concept of (perhaps weighted) feasible or infeasible interior-point paths. They converge to a solution of the LCP if a natural path parameter, usually the current duality gap, tends to 0.After reviewing some basic analyticity properties of these paths it is shown how these properties can be used to devise also long-step path-following methods (and not only predictor–corrector type methods) for which the duality gap converges Q-superlinearly to 0 with an arbitrarily high order.     

Superlinear Convergence of a Newton-Type Algorithm for Monotone Equations

We consider the problem of finding solutions of systems of monotone equations. The Newton-type algorithm proposed in Ref. 1 has a very nice global convergence property in that the whole sequence of iterates generated by this algorithm converges to a solution, if it exists. Superlinear convergence of this algorithm is obtained under a standard nonsingularity assumption. The nonsingularity condition implies that the problem has a unique solution; thus, for a problem with more than one solution, such a nonsingularity condition cannot hold. In this paper, we show that the superlinear convergence of this algorithm still holds under a local error-bound assumption that is weaker than the standard nonsingularity condition. The local error-bound condition may hold even for problems with nonunique solutions. As an application, we obtain a Newton algorithm with very nice global and superlinear convergence for the minimum norm solution of linear programs.This research was supported by the Singapore-MIT Alliance and the Australian Research Council.     

线性互补问题的宽邻域预估校正算法

对线性互补问题提出了一种新的宽邻域预估校正算法,算法是基于经典线性规划路径跟踪算法的思想,将Maziar Salahi关于线性规划预估校正算法推广到线性互补问题中,给出了算法的具体迭代步骤并讨论了算法迭代复杂性,最后证明了算法具有多项式复杂性为O(ηlog(X~0)~Ts~0/ε)。     

Combined Entropic Regularization and Path-Following Method for Solving Finite Convex Min-max Problems Subject to Infinitely Many Linear Constraints

In this paper, we study the minimization of the max function of q smooth convex functions on a domain specified by infinitely many linear constraints. The difficulty of such problems arises from the kinks of the max function and it is often suggested that, by imposing certain regularization functions, nondifferentiability will be overcome. We find that the entropic regularization introduced by Li and Fang is closely related to recently developed path-following interior-point methods. Based on their results, we create an interior trajectory in the feasible domain and propose a path-following algorithm with a convergence proof. Our intention here is to show a nice combination of minmax problems, semi-infinite programming, and interior-point methods. Hopefully, this will lead to new applications.     

A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems

We consider the standard linear complementarity problem (LCP): Find (x, y) R ²ⁿ such that y = M x + q, (x, y) 0 and x _i y _i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P ₀ LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in Newton iterations where is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.     

广义线性互补问题的改进SLP算法及收敛性

考虑广义线性互补问题,提出一个求解它的改进的序列线性规划算法,并在一定条件下证得该法具有良好的收敛性质。此外,顺便给出该问题解集非空有界的一个充分条件。     

基于凝聚函数的互补问题的光滑化算法

对于不可微的"极大值"形式的函数,可以利用凝聚函数对其进行光滑逼近.借助这个技术,给出了求解线性互补问题的光滑方程组算法.首先是将互补问题转化为等价的非光滑方程组,再利用凝聚函数进行光滑逼近,从而转化为光滑方程组的求解问题.通过一些考题对这个算法进行了数值试验,结果显示了该算法的有效性和稳定性.     

A Finite Algorithm for Almost Linear Complementarity Problems

We present an algorithm for solving a class of nonlinear complementarity problems called the almost linear complementarity problem (ALCP), which can be used to simulate free boundary problems. The algorithm makes use of a procedure for identifying an active index subset of an ALCP by bounding its solution with an interval vector. It is shown that an acceptable solution of the given ALCP can be obtained by solving at most n systems of equations. Numerical results are reported to illustrate the efficiency of the algorithm for large-scale problems.     

M-矩阵线性互补问题模系多分裂迭代方法的收敛性

首先证明了M-矩阵的H-相容分裂都是正则分裂,反之不成立.这表明对于M-矩阵而言,其正则分裂包含H-相容分裂.然后针对系数矩阵为M-矩阵的线性互补问题,建立了两个收敛定理:一是模系多分裂迭代方法关于正则分裂的收敛定理;二是模系二级多分裂迭代方法关于外迭代为正则分裂和内迭代为弱正则分裂的收敛定理.     

A Linearly Convergent Derivative-Free Descent Method for Strongly Monotone Complementarity Problems

We establish the first rate of convergence result for the class of derivative-free descent methods for solving complementarity problems. The algorithm considered here is based on the implicit Lagrangian reformulation [26, 35] of the nonlinear complementarity problem, and makes use of the descent direction proposed in [42], but employs a different Armijo-type linesearch rule. We show that in the strongly monotone case, the iterates generated by the method converge globally at a linear rate to the solution of the problem.     

On the Global Convergence of a Modified Augmented Lagrangian Linesearch Interior-Point Newton Method for Nonlinear Programming

We consider a linesearch globalization of the local primal-dual interior-point Newton method for nonlinear programming introduced by El-Bakry, Tapia, Tsuchiya, and Zhang. The linesearch uses a new merit function that incorporates a modification of the standard augmented Lagrangian function and a weak notion of centrality. We establish a global convergence theory and present promising numerical experimentation.     

Feasible Semismooth Newton Method for a Class of Stochastic Linear Complementarity Problems

We consider a class of stochastic linear complementarity problems (SLCPs) with finitely many realizations. In this paper we reformulate this class of SLCPs as a constrained minimization (CM) problem. Then, we present a feasible semismooth Newton method to solve this CM problem. Preliminary numerical results show that this CM reformulation may yield a solution with high safety for SLCPs.     

A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties

In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems

Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P _* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves `-feasibility and `-complementarity in at most O(n ² ln(1/`)) iterations with a properly chosen starting point.     

基于一类新方向的宽邻域路径跟踪内点算法

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.