Dissertation > Excellent graduate degree dissertation topics show

Researches on the Predictor-corrector Interior-point Algorithm

Author: BaiQinZuo
Tutor: HuangChongChao
School: Wuhan University
Course: Applied Mathematics
Keywords: Karmarkar’s algorithm interior-point method predictor-corrector interior- point algorithm the Newton direction the centered Newton direction
CLC: O241
Type: Master's thesis
Year: 2005
Downloads: 164
Quote: 1
Read: Download Dissertation

Abstract


In 1984, Karmarkar presented a new algorithm for linear programming—Karmarkar’s algorithm. It is not only a algorithm with polynomial complexity, superior to the simplex method in theory, but also more efficient than the simplex method in practice. A very important thing was that it established the connection between linear programming and nonlinear programming. Different from the simplex method, which chooses the solution along the boundary of the feasible region, Karmarkar’s algorithm is based on the structure of the simplex method, which starts from an originally feasible interior-point, moves in the feasible region to the optional solution following the steepest descent direction. So Karmarkar’s algorithm is also called interior-point method.This thesis is devoted to researching on the predictor-corrector interior-point algorithm. Firstly, we make this algorithm be easily applied to linear programming and convex quadratic programming with box constraints. Secondly, we give some new ideas to the algorithm; By taking the modified centered Newton direction in the corrector step, it not just shows the method is a polynomial-time algorithm but reduces the duality gap at each iteration.In this thesis, we separately present a polynomial predictor-corrector interior-point algorithm for linear programming with box constraints and convex quadratic programming with box constraints based on [46] and [48]. In the predictor step, we take the Newton direction. However, the direction in the corrector step is a modified centered Newton direction. And it is shown that the method is a polynomial-time algorithm and the iteration complexity is O{n1/2ln ε-1) . In addition, numerical tests are included at the base of MATLAB. The numerical examples are small on size, but the results show the algorithm is efficient and effective.

Related Dissertations

  1. Research on Optimization Algorithms of Transient Stability Control in Power System,TM712
  2. Researches on Reactive Power Optimization and Voltage Control in Ningbo Grid,TM714.3
  3. A Filter Line-search Interior Point Method for Nonlinear Constrained Optimization Problem,O221.2
  4. Research on Reactive Power Optimization of Regional Gird,TM714
  5. The Research of Synchronous Generator Excitation Control Based on Modern Interior Point Nonlinear Programming,TM341
  6. The Research on Reactive Power Optimization of Hybrid AC-DC Power System,TM721.3
  7. Research on Optimal Power Flow Algorithm for Large Scale Power System,TM744
  8. A Primal-Dual Interior-Point Method of Using the Augmented Lagrangian Function for Nonlinear Semidefinite Programming,O221.2
  9. On the Interior Point Algorithm for Optimization Problem with Free Variables,O224
  10. Reactive Power Optimization in Power System Based on Improved Trust Region Interior-point Algorithm,TM714.3
  11. A Primal-Dual Interior-Point FS Algorithm and Its Global Convergence,O221.2
  12. Research on Power System Unit Commitment with Dynamic Security Constraints,TM73
  13. Research on Transient Stability Constrained Optimal Power Flow in Power Systems,TM711
  14. Study of the Optimal Power Flow Based on Primal-Dual Interior Point Method,TM744
  15. Reactive power system mixed integer optimization problems precise method of continuous,TM744
  16. Research on the Numerical Prediction of Sound Radiation from Submerged Double Elastic Shell-structures,O422.2
  17. Available Transfer Capability of Power Network Considering the Static Synchronous Series Compensator,TM72
  18. The combination of linear programming algorithm direction,O221.1
  19. Based on OPF fault path simulation grid chain optimization and risk control,TM744
  20. Bilateral correction reduced Hessian matrix filter affine interior point method and its application,O224
  21. Research on Power Transfer Capability Computation Using Predictor-corrector Primal-dual Interior Point Method,TM744

CLC: > Mathematical sciences and chemical > Mathematics > Computational Mathematics > Numerical Analysis
© 2012 www.DissertationTopic.Net  Mobile