共查询到20条相似文献,搜索用时 15 毫秒
1.
A class of stochastic linear complementarity problems (SLCPs) with finitely many realizations is considered. We first formulate the problem as a new constrained minimization problem. Then, we propose a feasible semismooth Newton method which yields a stationary point of the constrained minimization problem. We study the condition for the level set of the objective function to be bounded. As a result, the condition for the solution set of the constrained minimization problem is obtained. The global and quadratic convergence of the proposed method is proved under certain assumptions. Preliminary numerical results show that this method yields a reasonable solution with high safety and within a small number of iterations. 相似文献
2.
A new smoothing algorithm for the solution of nonlinear complementarity problems (NCP) is introduced in this paper. It is
based on semismooth equation reformulation of NCP by Fischer–Burmeister function and its related smooth approximation. In
each iteration the corresponding linear system is solved only approximately. Since inexact directions are not necessarily
descent, a nonmonotone technique is used for globalization procedure. Numerical results are also presented.
Research supported by Ministry of Science, Republic of Serbia, grant No. 144006. 相似文献
3.
4.
In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP. 相似文献
5.
A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems 总被引:14,自引:0,他引:14
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. 相似文献
6.
Andreas Fischer 《Mathematical Programming》1997,76(3):513-532
The paper deals with complementarity problems CP(F), where the underlying functionF is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equationsφ(x)=0 or as the problem of minimizing the merit functionΘ=1/2∥Φ∥
2
2
, we extend results which hold for sufficiently smooth functionsF to the nonsmooth case.
In particular, ifF is monotone in a neighbourhood ofx, it is proved that 0 εδθ(x) is necessary and sufficient forx to be a solution of CP(F). Moreover, for monotone functionsF, a simple derivative-free algorithm that reducesΘ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed.
To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended top-order semismooth functions. Under a suitable regularity condition and ifF isp-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the
order of 1+p. 相似文献
7.
In this paper, we discuss how the basic Newton method for solving the nonlinear complementarity problem can be implemented in a parallel computation environment. We propose some synchronized and asynchronous Newton methods and establish their convergence.This work was based on research supported by the National Science Foundation under grant ECS-8407240 and by a University Research and Development grant from Cray Research Inc. The research was initiated when the authors were with the University of Texas at Dallas. 相似文献
8.
Qingna Li 《Operations Research Letters》2011,39(2):103-108
In this paper we propose a projected semismooth Newton method to solve the problem of calibrating least squares covariance matrix with equality and inequality constraints. The method is globally and quadratically convergent with proper assumptions. The numerical results show that the proposed method is efficient and comparable with existing methods. 相似文献
9.
M. J. Smith 《Journal of Optimization Theory and Applications》1984,44(3):485-496
The paper provides a descent algorithm for solving certain monotone variational inequalities and shows how this algorithm may be used for solving certain monotone complementarity problems. Convergence is proved under natural monotonicity and smoothness conditions; neither symmetry nor strict monotonicity is required.The author is grateful to two anonymous referees for their very valuable comments on an earlier draft of this paper. 相似文献
10.
In this paper, we propose a modified semismooth Newton method for a class of complementarity problems arising from the discretization of free boundary problems and establish its monotone convergence. We show that under appropriate conditions, the method reduces to semismooth Newton method. We also do some preliminary numerical experiments to show the efficiency of the proposed method. 相似文献
11.
12.
S.Z. Németh 《Journal of Mathematical Analysis and Applications》2009,350(1):340-893
In this paper we present a recursion related to a nonlinear complementarity problem defined by a closed convex cone in a Hilbert space and a continuous mapping defined on the cone. If the recursion is convergent, then its limit is a solution of the nonlinear complementarity problem. In the case of isotone projection cones sufficient conditions are given for the mapping so that the recursion to be convergent. 相似文献
13.
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. 相似文献
14.
Inexact Newton methods for the nonlinear complementarity problem 总被引:2,自引:0,他引:2
Jong-Shi Pang 《Mathematical Programming》1986,36(1):54-71
An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity
subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact
Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only
up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton
method are established and analyzed. We also discuss some extensions as well as an application.
This research was based on work supported by the National Science Foundation under grant ECS-8407240. 相似文献
15.
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. 相似文献
16.
The well-known logarithmic-quadratic proximal (LQP)method has motivated a number of efficient numerical algorithms for solving
nonlinear complementarity problems (NCPs). In this paper,we aim at improving one of them, i.e., the LQP-based interior prediction-correction
method proposed in [He, Liao and Yuan, J. Comp. Math., 2006, 24(1): 33–44], via identifying more appropriate step-sizes in
the correction steps. Preliminary numerical results for solving some NCPs arising in traffic equilibrium problems are reported
to verify the theoretical assertions. 相似文献
17.
We study convergence of a semismooth Newton method for generalized semi-infinite programming problems with convex lower level
problems where, using NCP functions, the upper and lower level Karush-Kuhn-Tucker conditions of the optimization problem are
reformulated as a semismooth system of equations. Nonsmoothness is caused by a possible violation of strict complementarity
slackness. We show that the standard regularity condition for convergence of the semismooth Newton method is satisfied under
natural assumptions for semi-infinite programs. In fact, under the Reduction Ansatz in the lower level and strong stability
in the reduced upper level problem this regularity condition is satisfied. In particular, we do not have to assume strict
complementary slackness in the upper level. Numerical examples from, among others, design centering and robust optimization
illustrate the performance of the method.
相似文献
18.
A generalized Newton method for absolute value equations 总被引:4,自引:1,他引:4
O. L. Mangasarian 《Optimization Letters》2009,3(1):101-108
A direct generalized Newton method is proposed for solving the NP-hard absolute value equation (AVE) Ax − |x| = b when the singular values of A exceed 1. A simple MATLAB implementation of the method solved 100 randomly generated 1,000-dimensional AVEs to an accuracy
of 10−6 in less than 10 s each. Similarly, AVEs corresponding to 100 randomly generated linear complementarity problems with 1,000 ×
1,000 nonsymmetric positive definite matrices were also solved to the same accuracy in less than 29 s each. 相似文献
19.
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. 相似文献
20.
The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P0 function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P0 function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions. 相似文献