Font Size: a A A

Study On The Multiplier Methods For Complementarity Problems

Posted on:2007-09-19Degree:MasterType:Thesis
Country:ChinaCandidate:S R N HuangFull Text:PDF
GTID:2120360185982061Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
The complementarity problem(CP) is a class of important optimization problems, which have important applications in engineering, economics and traffic equilibrium. A theoretical framework of a class of Lagrangian multiplier methods for CP was established in ([52]-[55]). This method is a class of methods which introduce nonsmooth equations containing Lagrangian function equivalent to CP and construct smooth merit function containing multiplier parameters. So we can reformulate CP as minimizing problem or nonlinear equations. Multiplier methods for CP are studied in this thesis. Two new multiplier merit functions are discussed.1. A new NCP function of CP is proposed. Equivalent semismooth equations reformulation of CP is obtained by this strong semismooth NCP function. With the combination of multiplier methods and semismooth Newton methods, a new generalized Newton method based on the new multiplier merit function is given. This method treats the merit function as square sum of the determinate semismooth equations. Generalized Newton direction as a descent direction makes the thought of algorithm clear and simplifies the structure and theoretical analysis of algorithm. Global convergence, local superlinear convergence, quadratic convergence and finite termination for nondegenerative linear complementarity problems are proved under the assumption that F is a uniform P— function. Numerical results indicate this algorithm is practically efficient.2. A new smooth multiplier merit function is proposed. Based on this new merit function, descent direction and multiplier adjusting method are constructed. The structure of this merit function is simple. Global convergence, local superlinear convergence and quadratic convergence are obtained under the assumption that F is a uniform P— function. For linear complementarity problems(LCP(q, M)), finite termination of the algorithm is proved under the assumption that Mis aP- matrix. Extensive numerical experiments indicate this algorithm is efficient.
Keywords/Search Tags:Complementarity problems, multiplier methods, generalized Newton methods, global convergence, local superlinear convergence, finite termination
PDF Full Text Request
Related items