共查询到20条相似文献,搜索用时 15 毫秒
1.
《Optimization》2012,61(5):757-773
In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P 0 matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article. 相似文献
2.
By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose
a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region
radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global
convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict
complementarity conditions.
This work is supported by National Natural Science Foundation of China (No. 10671126) and Shanghai Leading Academic Discipline
Project (S30501). 相似文献
3.
We extend the Mizuno-Todd-Ye predictor-corrector algorithm for solving monotone linear complementarity problems. We prove that the extended algorithm is globally Q-linearly convergent and solves problems with integer data of bitlengthL in at most
iterations. We also prove that the duality gap converges to zero Q-superlinearly for problems having strictly complementary solutions. Our results generalize the results obtained by Ye, Tapia, and Zhang for linear programming. 相似文献
4.
Based on a well-known reformulation of the linear complementarity problem (LCP) as a nondifferentiable system of nonlinear
equations, a Newton-type method will be described for the solution of LCPs. Under certain assumptions, it will be shown that
this method has a finite termination property, i.e., if an iterate is sufficiently close to a solution of LCP, the method
finds this solution in one step. This result will be applied to a recently proposed algorithm by Harker and Pang in order
to prove that their algorithm also has the finite termination property. 相似文献
5.
A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When
M is a P-matrix, the sequence {ϑ(x
k, λ
k)} (where {(x
k, λ
k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations
if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising.
Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171 相似文献
6.
G. De Wit 《Journal of Optimization Theory and Applications》1992,72(1):65-90
A certain class of linear complementarity problems that appeared in an economical study concerning self-employment is investigated. The principal findings for this class of linear complementarity problems are: (i) there is always a solution, which can be found by the Lemke algorithm; (ii) characterizations are found for solutions, some typical for all solutions, some typical for locally nonunique solutions, and some typical for locally unique solutions; (iii) a sufficient condition is found to guarantee a globally unique solution.The research reported in this paper is part of the project Economics of Political Decision Making of the University of Amsterdam. The author acknowledges the financial support obtained from the Ministry of Economic Affairs by way of the Research Institute for Small and Medium-Sized Business as well as the financial support of the Netherlands Organization for Scientific Research. He is grateful to two anonymous referees for many helpful suggestions, to F. A. A. M. Van Winden for stimulating discussions, and to J. J. M. Evers, H. Neudecker, and A. J. J. Talman for comments. 相似文献
7.
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. 相似文献
8.
张立平 《数学物理学报(B辑英文版)》2007,27(2):243-253
A noninterior continuation method is proposed for semidefinite complementarity problem (SDCP). This method improves the noninterior continuation methods recently developed for SDCP by Chen and Tseng. The main properties of our method are: (i) it is well defined for the monotones SDCP; (ii) it has to solve just one linear system of equations at each step; (iii) it is shown to be both globally linearly convergent and locally quadratically convergent under suitable assumptions. 相似文献
9.
In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known. 相似文献
10.
LIDONGHUI 《高校应用数学学报(英文版)》1996,11(4):487-496
In this paper, we propose an inexact clamped Newton method for solving nonlinear complementarity problems based on the equivalent B-differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given. 相似文献
11.
12.
Stephen J. Wright 《Mathematical Programming》1994,67(1-3):29-51
We modify the algorithm of Zhang to obtain anO(n2L) infeasible-interior-point algorithm for monotone linear complementarity problems that has an asymptoticQ-subquadratic convergence rate. The algorithm requires the solution of at most two linear systems with the same coefficient matrix at each iteration.This research was supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38. 相似文献
13.
提出了求解非对称线性互补问题的并行二级多分裂迭代算法,并证明了该算法的收敛性,最后通过数值实验验证了算法的有效性和可行性. 相似文献
14.
XiuNaihua 《高校应用数学学报(英文版)》2000,15(4):433-442
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. 相似文献
15.
It has been shown by Lemke that if a matrix is copositive plus on
n
, then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350. 相似文献
16.
A proximal gradient descent method for the extended second-order cone linear complementarity problem
We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the unconstrained reformulations, which verify the effectiveness of the proposed method. 相似文献
17.
We give a bound on the distance between an arbitrary point and the solution set of a monotone linear complementarity problem
in terms of a condition constant that depends on the problem data only and a residual function of the violations of the complementary
problem conditions by the point considered. When the point satisfies the linear inequalities of the complementarity problem,
the residual consists of the complementarity condition plus its square root. This latter term is essential and without it
the error bound cannot hold. We also show that another natural residual that has been employed to bound errors for strictly
monotone linear complementarity problems fails to bound errors for the monotone case considered here.
Sponsored by the United States Army under contract No. DAAG29-80-C-0041. This material is based on research sponsored by National
Foundation Grant DCR-8420963 and Air Force Office of Scientific Research Grant AFOSR-ISSA-85-00080. 相似文献
18.
Newton's method for linear complementarity problems 总被引:2,自引:0,他引:2
Muhamed Aganagić 《Mathematical Programming》1984,28(3):349-362
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. 相似文献
19.
Feasible descent algorithms for mixed complementarity problems 总被引:6,自引:0,他引:6
In this paper we consider a general algorithmic framework for solving nonlinear mixed complementarity problems. The main features
of this framework are: (a) it is well-defined for an arbitrary mixed complementarity problem, (b) it generates only feasible
iterates, (c) it has a strong global convergence theory, and (d) it is locally fast convergent under standard regularity assumptions.
This framework is applied to the PATH solver in order to show viability of the approach. Numerical results for an appropriate
modification of the PATH solver indicate that this framework leads to substantial computational improvements.
Received April 9, 1998 / Revised version received November 23, 1998?Published online March 16, 1999 相似文献