A smoothing Levenberg-Marquardt method for nonlinear complementarity problems

As is well-known, Jacobian smoothing method is a popular one to solve nonlinear complementarity problems, in which the Jacobian consistency is stressed. By investigating an element of related functions’ B-differential, a smoothing Levenberg-Marquardt(LM) method is proposed based on a Chen-Harker-Kanzow-Smale(CHKS) smoothing function, which satisfies a property called strongly Jacobian consistency. Finally, the numerical experiments illustrate the effectiveness of the given method.     

随机R0张量互补问题的投影Levenberg-Marquardt方法

本文考虑一类离散型随机$R_0$张量互补问题,利用Fischer-Burmeister函数将问题转化为约束优化问题,并用投影Levenberg-Marquardt方法对其进行了求解。在一般的条件下得到了该方法的全局收敛性,相关的数值实验表明了该方法的有效性。     

A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems

A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10 000 variables are presented. Partially supported by Agenzia Spaziale Italiana, Roma, Italy.     

A smoothing Levenberg-Marquardt method for the complementarity problem over symmetric cone

In this paper, we propose a smoothing Levenberg-Marquardt method for the symmetric cone complementarity problem. Based on a smoothing function, we turn this problem into a system of nonlinear equations and then solve the equations by the method proposed. Under the condition of Lipschitz continuity of the Jacobian matrix and local error bound, the new method is proved to be globally convergent and locally superlinearly/quadratically convergent. Numerical experiments are also employed to show that the method is stable and efficient.

     

Merit functions for nonsmooth complementarity problems and related descent algorithm

Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.     

Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power markets

This paper is dedicated to solving a nonsmooth second-order cone complementarity problem, in which the mapping is assumed to be locally Lipschitz continuous, but not necessarily to be continuously differentiable everywhere. With the help of the vector-valued Fischer-Burmeister function associated with second-order cones, the nonsmooth second-order cone complementarity problem can be equivalently transformed into a system of nonsmooth equations. To deal with this reformulated nonsmooth system, we present an approximation function by smoothing the inner mapping and the outer Fischer-Burmeister function simultaneously. Different from traditional smoothing methods, the smoothing parameter introduced is treated as an independent variable. We give some conditions under which the Jacobian of the smoothing approximation function is guaranteed to be nonsingular. Based on these results, we propose a smoothing Newton method for solving the nonsmooth second-order cone complementarity problem and show that the proposed method achieves globally superlinear or quadratic convergence under suitable assumptions. Finally, we apply the smoothing Newton method to a network Nash-Cournot game in oligopolistic electric power markets and report some numerical results to demonstrate its effectiveness.

     

A modified Broyden-like method for nonlinear complementarity problems

In this paper, we give a modified Broyden-like method for nonlinear complementarity problems, where we consider the smoothing parameter as an independent variable in the smoothing equation and adopt a modified nonmonotone step-length decision. We also analyze the global and local convergence of the modified method. Numerical experiments are also shown.     

A Newton-type method for positive-semidefinite linear complementarity problems

The paper presents a damped and perturbed Newton-type method for solving linear complementarity problems with positive-semidefinite matricesM. In particular, the following properties hold: all occurring subproblems are linear equations; each subproblem is uniquely solvable without any assumption; every accumulation point generated by the method solves the linear complementarity problem. The additional property ofM to be an R₀-matrix is sufficient, but not necessary, for the boundedness of the iterates. Provided thatM is positive definite on a certain subspace, the method converges Q-quadratically.The author would like to thank the anonymous referees and Dr. K. Schönefeld for their valuable comments and suggestions. He is also grateful to Prof. Dr. J. W. Schmidt for his continuous interest in this study.     

A projection-filter method for solving nonlinear complementarity problems

The Josephy-Newton method attacks nonlinear complementarity problems which consists of solving, possibly inexactly, a sequence of linear complementarity problems. Under appropriate regularity assumptions, this method is known to be locally (superlinearly) convergent. Utilizing the filter method, we presented a new globalization strategy for this Newton method applied to nonlinear complementarity problem without any merit function. The strategy is based on the projection-proximal point and filter methodology. Our linesearch procedure uses the regularized Newton direction to force global convergence by means of a projection step which reduces the distance to the solution of the problem. The resulting algorithm is globally convergent to a solution. Under natural assumptions, locally superlinear rate of convergence was established.     

A superquadratic infeasible-interior-point method for linear complementarity problems

We consider a modification of a path-following infeasible-interior-point algorithm described by Wright. In the new algorithm, we attempt to improve each major iterate by reusing the coefficient matrix factors from the latest step. We show that the modified algorithm has similar theoretical global convergence properties to those of the earlier algorithm while its asymptotic convergence rate can be made superquadratic by an appropriate parameter choice. The work of this author was based on research supported by the Office of Scientific Computing, US Department of Energy, under Contract W-31-109-Eng-38. The work of this author was based on research supported in part by the US Department of Energy under Grant DE-FG02-93ER25171.     

A power penalty method for linear complementarity problems

We propose a power penalty approach to a linear complementarity problem (LCP) in Rⁿ based on approximating the LCP by a nonlinear equation. We prove that the solution to this equation converges to that of the LCP at an exponential rate when the penalty parameter tends to infinity.     

A new hybrid method for nonlinear complementarity problems

In this paper, a new hybrid method is proposed for solving nonlinear complementarity problems (NCP) with P ₀ function. In the new method, we combine a smoothing nonmonotone trust region method based on a conic model and line search techniques. We reformulate the NCP as a system of semismooth equations using the Fischer-Burmeister function. Using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing nonmonotone trust region algorithm of a conic model for solving the NCP with P ₀ functions. This is different from the classical trust region methods, in that when a trial step is not accepted, the method does not resolve the trust region subproblem but generates an iterative point whose steplength is defined by a line search. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, the superlinear convergence of the algorithm is established without a strict complementarity condition.     

一类非光滑凸优化问题的邻近梯度算法

考虑求解目标函数为光滑损失函数与非光滑正则函数之和的凸优化问题的一种基于线搜索的邻近梯度算法及其收敛性分析,证明了在梯度局部Lipschitz连续条件下该算法是R-线性收敛的,并在非光滑部分为稀疏块LASSO正则函数情况下给出了误差界条件成立的证明,得到了线性收敛率.最后,数值实验结果验证了方法的有效性.     

非线性互补问题的SQP方法

In this paper, the nonlinear complementarity problem is transformed into the least squares problem with nonnegative constraints ,and a SQP algorithm for this reformulation based on a damped Gauss-Newton type method is presented. It is shown that the algorithm is globally and locally superlinearly (quadratically) convergent without the assumption of monotonicity.     

非光滑最优控制问题的一种数值解法

针对非光滑最优控制问题提出一种分段数值解法.首先对问题进行全局拟谱离散,然后选取分点,将时间区域进行剖分,在每段区域上对问题进行离散,离散过程采用Chebyshev-Legendre拟谱方法,可以有效借助快速Legendre变换提高算法的运算效率,比现有算法在很大程度上节省了计算时间.给出了相关的理论分析,数值结果表明方法的高精度和有效性.     

Newton's method for linear complementarity problems

This paper presents an iterative, Newton-type method for solving a class of linear complementarity problems. This class was discovered by Mangasarian who had established that these problems can be solved as linear programs. Cottle and Pang characterized solutions of the problems in terms of least elements of certain polyhedral sets. The algorithms developed in this paper are shown to converge to the least element solutions. Some applications and computational results are also discussed.     

Constrained gradient method for nonsmooth optimization problems

Journal of Mathematical Sciences -     

A modified damped Newton method for linear complementarity problems

We present a modified damped Newton method for solving large sparse linear complementarity problems, which adopts a new strategy for determining the stepsize at each Newton iteration. The global convergence of the new method is proved when the system matrix is a nondegenerate matrix. We then apply the matrix splitting technique to this new method, deriving an inexact splitting method for the linear complementarity problems. The global convergence of the resulting inexact splitting method is proved, too. Numerical results show that the new methods are feasible and effective for solving the large sparse linear complementarity problems.     

A new method for solving Pareto eigenvalue complementarity problems

In this paper, we introduce a new method, called the Lattice Projection Method (LPM), for solving eigenvalue complementarity problems. The original problem is reformulated to find the roots of a nonsmooth function. A semismooth Newton type method is then applied to approximate the eigenvalues and eigenvectors of the complementarity problems. The LPM is compared to SNM_min and SNM_FB, two methods widely discussed in the literature for solving nonlinear complementarity problems, by using the performance profiles as a comparing tool (Dolan, Moré in Math. Program. 91:201–213, 2002). The performance measures, used to analyze the three solvers on a set of matrices mostly taken from the Matrix Market (Boisvert et al. in The quality of numerical software: assessment and enhancement, pp. 125–137, 1997), are computing time, number of iterations, number of failures and maximum number of solutions found by each solver. The numerical experiments highlight the efficiency of the LPM and show that it is a promising method for solving eigenvalue complementarity problems. Finally, Pareto bi-eigenvalue complementarity problems were solved numerically as an application to confirm the efficiency of our method.     

A non-interior continuation method for generalized linear complementarity problems

In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP) introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions, it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results are also reported. Received September 3, 1997 / Revised version received April 27, 1999?Published online July 19, 1999