Dissertation > Excellent graduate degree dissertation topics show

Researches on the Potential Reduction Interior-point Algorithm

Author: WangXue
Tutor: HuangChongChao
School: Wuhan University
Course: Applied Mathematics
Keywords: Karmarkar’s algorithm interior point methods potential reduction interior point algorithm linear complementarity problems
CLC: O221.1
Type: Master's thesis
Year: 2005
Downloads: 132
Quote: 3
Read: Download Dissertation

Abstract


Although the simplex method is efficient in practical application, it is not the polynomial time algorithm in theory, which led to the research on polynomial algorithm for the linear programming problem. In 1978 the first polynomial algorithm for the linear programming problem, the ellipsoidal method, was presented by L.G Khachiyan and resulted in great impact on the theory of complexity, but unfortunately the practical implementations of the algorithm have been inefficient than the simplex method. In 1984, N.Karmarkar found a new algorithm for linear programming— Karmarkar’s algorithm, which makes a great breakthrough in linear programming. Karmarkar’s algorithm not only has a better polynomial complexity than the ellipsoid method, but also is a challenging competitor of the simplex method in practice, especially for large-scale problems. Different from the simplex method, which choose the optional point along the boundary of the feasible region, Karmarkar’s algorithm is based on the construction of the simplex method, which starts from the originally feasible interior-point, walks up in the feasible region to the optional point following the steepest descent direction. So Karmarkar’s algorithm is also called interior-point method. Since the publication of Karmarkar’s paper, interior point methods theory has been a very active research direction in mathematical programming.This thesis is devoted to researching on the potential reduction interior point algorithm. Using partial updating and the Sherman-Morrison-Woodbury rule on the top of the frame work developed by Kojima, Minzuno, Yoshise, we developed a modified potential reduction interior point algorithm to solve the linear complementarity problems with positive semi-definite matrices. The total number of iterations requiredby our algorithm is at most O(1/2nL), and the total number of arithmetic operationsis O（rn2）, and its steps are not constrained by the need to remain approximatelycentered. The global convergence results for these algorithms are established and some numerical test also included.

Related Dissertations

  1. The Research on the Algorithms of Some Quadratic Programming,O221.2
  2. Sensitivity Analysis in Semidefinite Programming,O221.2
  3. Affine-scaling Interior-point Methods for Optimization with Linear Constraints,O221
  4. The Application of Linear Complementarity Problem in the Economics,O221
  5. The LCP problem of theoretical analysis and research,O221
  6. Optimal Selection of Flood Control Plans of Reservoir and United Operation of Reservoirs and Baiyang Pond,TV697.13
  7. Interval Method for generalized linear complementarity problems,O241.6
  8. The complementarity problem solution research,O221
  9. The Existence of Solution for Lcp(M,q) and Related-Matrices,O221
  10. Error Bound Estimation for the Generalized Variational Inequalities and Complementarity Problem Over a Polyhedron Cone,O178
  11. Two kinds of generalized linear complementarity problems neural networks,O241
  12. Smooth Methods for Two Kinds of General Linear Complementarity Problems,O221.1
  13. Researches on the Combined Homotopy Interior Point Method,O241
  14. Researches on the Predictor-corrector Smoothing Method,O241
  15. FIR Filter Design Based on Convex Optimization Theory and Its Application in LAS-CDMA System,TN929.533
  16. Study on the Rules of Alternative Selection in Group Decision Mking,O225
  17. The Convergence of Affine-scaling Interior-point Trust-region Methods for Optimization with Simple Bounds,O241
  18. Two iterative algorithm linear complementarity problems and related research,O221
  19. Interior Point Algorithms for Linear Complementary Problems in Matrices,O221
  20. Robust Solutions to Uncertain Linear Complementarity Problems,O221

CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > Planning Theory ( mathematical programming) > Linear programming
© 2012 www.DissertationTopic.Net  Mobile