共查询到20条相似文献,搜索用时 15 毫秒
1.
Improving the convergence of non-interior point algorithms for nonlinear complementarity problems 总被引:1,自引:0,他引:1
Recently, based upon the Chen-Harker-Kanzow-Smale smoothing function and the trajectory and the neighbourhood techniques, Hotta and Yoshise proposed a noninterior point algorithm for solving the nonlinear complementarity problem. Their algorithm is globally convergent under a relatively mild condition. In this paper, we modify their algorithm and combine it with the superlinear convergence theory for nonlinear equations. We provide a globally linearly convergent result for a slightly updated version of the Hotta-Yoshise algorithm and show that a further modified Hotta-Yoshise algorithm is globally and superlinearly convergent, with a convergence -order , under suitable conditions, where is an additional parameter.
2.
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 相似文献
3.
Song Xu 《Mathematical Programming》2000,87(3):501-517
We propose an infeasible non-interior path-following method for nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. A key to our analysis is the introduction
of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods.
By restricting the iterates in the neighborhood of the central path, we provide a systematic procedure to update the smoothing
parameter and establish the global linear convergence of this method. Some preliminary computational results are reported.
Received: March 13, 1997 / Accepted: December 17, 1999?Published online February 23, 2000 相似文献
4.
Liu Yongjin Zhang Liwei Liu Meijiao 《高校应用数学学报(英文版)》2007,22(2):245-252
The paper uses Euclidean Jordan algebras as a basic tool to extend smoothing functions, which include the Chen-Mangasarian class and the Fischer-Burmeister smoothing functions, to symmetric cone complementarity problems. Computable formulas for these functions and their Jacobians are derived. In addition, it is shown that these functions are Lipschitz continuous with respect to parameter # and continuously differentiable on J × J for any μ 〉 0. 相似文献
5.
Failure of global convergence for a class of interior point methods for nonlinear programming 总被引:6,自引:0,他引:6
Using a simple analytical example, we demonstrate that a class of interior point methods for general nonlinear programming,
including some current methods, is not globally convergent. It is shown that those algorithms produce limit points that are
neither feasible nor stationary points of some measure of the constraint violation, when applied to a well-posed problem.
Received: December 1999 / Accepted: May 2000?Published online August 18, 2000 相似文献
6.
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 相似文献
7.
We propose a class of parametric smooth functions that approximate the fundamental plus function, (x)+=max{0, x}, by twice integrating a probability density function. This leads to classes of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equations as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter . Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter , generate an interior path, which is different from the central path for interior point method. Computational results for 52 test problems compare favorably with these for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris [6], Harker and Xiao [11] and Pang & Gabriel [28].This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479. 相似文献
8.
Smooth methods of multipliers for complementarity problems 总被引:2,自引:0,他引:2
This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs
of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual
formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating
three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general
collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it
corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function,
the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods
is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows
that this class of algorithms is effective at solving many of the standard complementarity test problems.
Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999 相似文献
9.
In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective. 相似文献
10.
Given a linear transformation L:?
n
→?
n
and a matrix Q∈?
n
, where ?
n
is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,?
n
+,Q) over the cone ?
n
+ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R
n×n
, we consider the linear transformation L
A
:?
n
→?
n
defined by L
A
(X):=AX+XA
T
and show that the P- and Q-properties for L
A
are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.
Received: March 1999 / Accepted: November 1999?Published online April 20, 2000 相似文献
11.
A.B. Levy 《Mathematical Programming》1999,85(2):397-406
n such that x≥0, F(x,u)-v≥0 , and F(x,u)-v T·x=0 where these are vector inequalities. We characterize the local upper Lipschitz continuity of the (possibly set-valued)
solution mapping which assigns solutions x to each parameter pair (v,u). We also characterize when this solution mapping is
locally a single-valued Lipschitzian mapping (so solutions exist, are unique, and depend Lipschitz continuously on the parameters).
These characterizations are automatically sufficient conditions for the more general (and usual) case where v=0. Finally,
we study the differentiability properties of the solution mapping in both the single-valued and set-valued cases, in particular
obtaining a new characterization of B-differentiability in the single-valued case, along with a formula for the B-derivative.
Though these results cover a broad range of stability properties, they are all derived from similar fundamental principles
of variational analysis.
Received March 30, 1998 / Revised version received July 21, 1998
Published online January 20, 1999 相似文献
12.
Stephen M. Robinson 《Mathematical Programming》1999,86(1):41-50
This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain
convex functions on ℝ
n
. Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method
in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method
given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions
covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin,
a property generalizing classical regularity conditions.
Received March 29, 1996 / Revised version received March 5, 1999? Published online June 11, 1999 相似文献
13.
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities 总被引:17,自引:0,他引:17
In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the
box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions,
we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent
nonsmooth equation H(u,x)=0, where H:ℜ
2n
→ℜ
2n
, u∈ℜ
n
is a parameter variable and x∈ℜ
n
is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z
k
=(u
k
,x
k
)} such that the mapping H(·) is continuously differentiable at each z
k
and may be non-differentiable at the limiting point of {z
k
}. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which
play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not
require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if
we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the
proposed methods for particularly chosen smoothing functions are very promising.
Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999 相似文献
14.
The modulus‐based matrix splitting algorithms for a class of weakly nonlinear complementarity problems 下载免费PDF全文
In this paper, we study a class of weakly nonlinear complementarity problems arising from the discretization of free boundary problems. By reformulating the complementarity problems as implicit fixed‐point equations based on splitting of the system matrices, we propose a class of modulus‐based matrix splitting algorithms. We show their convergence by assuming that the system matrix is positive definite. Moreover, we give several kinds of typical practical choices of the modulus‐based matrix splitting iteration methods based on the different splitting of the system matrix. Numerical experiments on two model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of our modulus‐based matrix splitting algorithms. Copyright © 2016 John Wiley & Sons, Ltd. 相似文献
15.
Received May 15, 1995 / Revised version received May 20, 1998 Published online October 21, 1998 相似文献
16.
Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation 总被引:2,自引:0,他引:2
Received April 10, 1996 / Revised version received April 30, 1998 Published online August 18, 1998 相似文献
17.
Basis- and partition identification for quadratic programming and linear complementarity problems 总被引:1,自引:0,他引:1
Arjan B. Berkelaar Benjamin Jansen Kees Roos Tamás Terlaky 《Mathematical Programming》1999,86(2):261-282
Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide
maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other
hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification
algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification
algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from
any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski
and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity
problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality
property of basis tableaus.
Received April 9, 1996 / Revised version received April 27, 1998?
Published online May 12, 1999 相似文献
18.
In this paper, we propose a new smooth function that possesses a property not satisfied by the existing smooth functions.
Based on this smooth function, we discuss the existence and continuity of the smoothing path for solving theP
0 function nonlinear complementarity problem ( NCP). Using the characteristics of the new smooth function, we investigate the
boundedness of the iteration sequence generated by the non-interior continuation methods for solving theP
0 function NCP under the assumption that the solution set of the NCP is nonempty and bounded. We show that the assumption that
the solution set of the NCP is nonempty and bounded is weaker than those required by a few existing continuation methods for
solving the NCP 相似文献
19.
We consider the diagonal inexact proximal point iteration where f(x,r)=c
T
x+r∑exp[(A
i
x-b
i
)/r] is the exponential penalty approximation of the linear program min{c
T
x:Ax≤b}. We prove that under an appropriate choice of the sequences λ
k
, ε
k
and with some control on the residual ν
k
, for every r
k
→0+ the sequence u
k
converges towards an optimal point u
∞ of the linear program. We also study the convergence of the associated dual sequence μ
i
k
=exp[(A
i
u
k
-b
i
)/r
k
] towards a dual optimal solution.
Received: May 2000 / Accepted: November 2001?Published online June 25, 2002 相似文献
20.
The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP 总被引:2,自引:0,他引:2
** Email: zhenghaihuang{at}yahoo.com.cn; huangzhenghai{at}hotmail.com In this paper, we propose a non-interior continuation algorithmfor solving the P0-matrix linear complementarity problem (LCP),which is conceptually simpler than most existing non-interiorcontinuation algorithms in the sense that the proposed algorithmonly needs to solve at most one linear system of equations ateach iteration. We show that the proposed algorithm is globallyconvergent under a common assumption. In particular, we showthat the proposed algorithm is globally linearly and locallyquadratically convergent under some assumptions which are weakerthan those required in many existing non-interior continuationalgorithms. It should be pointed out that the assumptions usedin our analysis of both global linear and local quadratic convergencedo not imply the uniqueness of the solution to the LCP concerned.To the best of our knowledge, such a convergence result hasnot been reported in the literature. 相似文献