Dissertation > Excellent graduate degree dissertation topics show

Interior Point Algorithms for Linear Complementary Problems in Matrices

Author: CuiNa
Tutor: YinHongYou
School: Nanjing University of Aeronautics and Astronautics
Course: Computational Mathematics
Keywords: Interior-point methods complementary problem complementary problem in symmetric matrices the central trajectory potential-reduction method monotone p (τ)arithmetic operator
CLC: O221
Type: Master's thesis
Year: 2007
Downloads: 63
Quote: 0
Read: Download Dissertation

Abstract


Complementary problem has wide applications in many fields such as economics, game theory. The research on nonlinear science and compute science is always active, and we got many good conclusions on the algorithms to solve the complementary problem. In these algorithms, interior point algorithm is especially active in mathematical programming. For interior point algorithm has a good polynomial complexity, especially for large-scale problems in practice.Thanks to these merits, we hope interior point algorithm can solve common complement ary problem not only in the Euclidean space but also in matrices. After much research, M Koji ma and S Shidoh and S Hara gave the definition of the semi-definite linear complementary problem in matrices.This problem enjoys a close analogy with the LCP in the Euclidean space. In particular, the central trajectory leading to a solution of the problem exists under the non emptyness of the interior of the feasible region and a monotonicity assumption on the affine subspace.In this paper, based on the theory of the monotone semi-definite linear complementary problem in symmetric matrices by M Kojima, we construct a new interior-point algorithm with the use of the Nesterov-Todd equation to solve the complementary problem. Nesterov-Todd equations are better than Newton directions, because the matrices in them are always symmetric in iterations.Respectively, we construct path-following algorithm and potential-reduction algorithm. In the path-following algorithm, we modify step size parameter equal to 1 and use a narrow neighborhood of the central trajectory. Then we discuss the feasibility and the convergence. In the potential-reduction algorithm, we choose initial point, which can be infeasible, and then we make use of linear detection to choose step size. And we prove its feasibility and compute the least reduction. In the end, due to the restrictions of monotonicity, we extend the result to p (τ) arithmetic operator in the path-following algorithm.

Related Dissertations

  1. The Convexity Characteristic of the Calder(?)n-Lozanovski(?) Sequence Spaces and Some Geometric Problems,O177
  2. The Solution Existence for Initial Value Problems of Fuzzy Functional Differential Equations,O175.8
  3. Monotone Iterative Method of Positive Solution to Boundary Value Problem of Nonlinear Differential Equation,O175.8
  4. About Chaotic sequence under Furuta inequality and other Operator Inequalities Related Issues,O178
  5. Trust Region Algorithms Based on the Conic Model,O224
  6. Fixed Point Theorems and Generalizations on Mixed Monotone Operators,O177.91
  7. The Convergence Behavior of A Non-interior Continuation Algorithm for the Monotone Symmetric Cone Complementarity Problem,O241.6
  8. Spectral-scaling Quasi-newton Method for Solving Nonlinear Monotone Equations,O241.6
  9. The Study of Existence of Positive Solutions for the Fourth-Order Four Point Boundary Value Problems with P-laplacian Operator,O175.8
  10. The Study of Some Optimization Problems,O224
  11. Random Fixed Point Theorems of Random Mixed Monotone Operator,O177.91
  12. Some New Algorithms for A System of Equilibrium Problems,O224
  13. A Hybrid Proximal Point Algorithm and a Hundle Method for Solving Nonlinear Variational Inclusions,O177.1
  14. The Splitting Algorithms and Resolvent Dynamic Systems for Monotone Inclusions,O224
  15. Study on Complementarity Problems in Banach Spaces,O177.2
  16. Existence of Solutions for Integer with Integral Boundary Conditions and Fractional Differential Equation,O175.8
  17. Qualitative Research for Solutions of Fractional Reaction-Diffusion Equations,O241.7
  18. Sensitivity Analysis in Semidefinite Programming,O221.2
  19. The Iterated Tikhonov Regularization Methods for Nonlinear Ill-Posed Problems with Monotone Operators,O177
  20. Quasilinearization Method for a Class of Nonlinear Singular Systems,O175.8
  21. Research of Traffic Equiliibrim Analysis Theory Based on Bounded Rationality,O242.1

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