共查询到10条相似文献,搜索用时 62 毫秒
1.
My master thesis concerns the solution linear complementarity problems (LCP). The Lemke algorithm, the most commonly used algorithm for solving a LCP until this day, was compared with the piecewise Newton method (PLN algorithm). The piecewise Newton method is an algorithm to solve a piecewise linear system on the basis of damped Newton methods. The linear complementarity problem is formulated as a piecewise linear system for the applicability of the PLN algorithm. Then, different application examples will be presented, solved with the PLN algorithm. As a result of the findings (of my master thesis) it can be assumed that – under the condition of coherent orientation – the PLN-algorithm requires fewer iterations to solve a linear complementarity problem than the Lemke algorithm. The coherent orientation for piecewise linear problems corresponds for linear complementarity problems to the P-matrix-property. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
2.
This paper discusses a kind of optimization problem with linear complementarity constraints, and presents a sequential quadratic
programming (SQP) algorithm for solving a stationary point of the problem. The algorithm is a modification of the SQP algorithm
proposed by Fukushima et al. [Computational Optimization and Applications, 10 (1998),
5-34], and is based on a reformulation of complementarity condition as a system of linear equations. At each iteration,
one quadratic programming and one system of equations needs to be solved, and a curve search is used to yield the step size.
Under some appropriate assumptions, including the lower-level strict complementarity, but without the upper-level strict
complementarity for the inequality constraints, the algorithm is proved to possess strong convergence and superlinear convergence.
Some preliminary numerical results are reported. 相似文献
3.
Angel E. R. Gutierrez Sandro R. Mazorche José Herskovits Grigori Chapiro 《Journal of Optimization Theory and Applications》2017,175(2):432-449
Nonlinear complementarity and mixed complementarity problems arise in mathematical models describing several applications in Engineering, Economics and different branches of physics. Previously, robust and efficient feasible directions interior point algorithm was presented for nonlinear complementarity problems. In this paper, it is extended to mixed nonlinear complementarity problems. At each iteration, the algorithm finds a feasible direction with respect to the region defined by the inequality conditions, which is also monotonic descent direction for the potential function. Then, an approximate line search along this direction is performed in order to define the next iteration. Global and asymptotic convergence for the algorithm is investigated. The proposed algorithm is tested on several benchmark problems. The results are in good agreement with the asymptotic analysis. Finally, the algorithm is applied to the elastic–plastic torsion problem encountered in the field of Solid Mechanics. 相似文献
4.
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. 相似文献
5.
Zhensheng Yu Yangchen Liu Xinyue Gan 《Numerical Functional Analysis & Optimization》2017,38(11):1458-1472
This paper presents a nonmonotone inexact Newton-type method for the extended linear complementarity problem (ELCP). We first reformulate the optimization system of the ELCP problem into a system of smoothed equations. Then we solve this system by a nonmonotone inexact Newton-type algorithm. The global convergence is obtained and numerical tests for some classes of ELCP include linear complementarity, horizontal linear complementarity, and generalized linear complementarity problems are also given to show the e?ciency of the proposed algorithm. 相似文献
6.
This paper discusses nonlinear complementarity problems; its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. Filter methods are extensively studied to handle nonlinear complementarity problem. Because of good numerical results, filter techniques are attached. By means of a filter strategy, we present a new trust region method based on a conic model for nonlinear complementarity problems. Under a proper condition, the superlinear convergence of the algorithm is established without the strict complementarity condition. 相似文献
7.
In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems. 相似文献
8.
9.
Roberto Andreani Joaquim J. Júdice José Mario Martínez Joao Patrício 《Numerical Algorithms》2011,57(4):457-485
Interior–point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure
for globalizing interior–point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact
interior–point and projected–gradient search techniques and employs a line–search procedure for the natural merit function
associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton
interior–point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm
is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing
with infeasible linear complementarity problems is introduced which, in practice, employs only interior–point search directions.
Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm
are included. 相似文献
10.
This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.AMS Subject Classification: 90C, 49MThis work was supported by the National Natural Science Foundation (10261001) and the Guangxi Province Science Foundation (0236001, 0249003) of China. 相似文献