Dissertation > Excellent graduate degree dissertation topics show

Algorithms for Semidefinite Programming and Its Applications in Combinatorial Optimization

Author: XuFengMin
Tutor: LiuSanYang
School: Xi'an University of Electronic Science and Technology
Course: Operational Research and Cybernetics
Keywords: Semidefinite programming Projection algorithm Gauss-Newton direction The max-cut problem The graph max-bisection problem Relaxation
CLC: O221.1
Type: Master's thesis
Year: 2001
Downloads: 249
Quote: 1
Read: Download Dissertation

Abstract


Semidefinite programming (denoted SDP) is an extension of linear programming(LP), with vector variables replaced by matrix variables and nonnegativity elementwisereplaced by positive semidefinite. It is well known that the constraint of semidefiniteprogramming is nonlinear and nonsmooth , but convex, so semidefinite programming isconvex optimization problems. Semidefinite programming unifies several standardproblems (e.g., linear and quadratic programming) and finds many applications fromsystem and control theory to combinatorial optimization as well as eigenvalueoptimization, so semidefinite programming is viewed as a new and important researchdirection in mathematical programming. This paper consists of there parts:1.A new projection algorithm solving semidefinite programming is attainted by theequivalence of the optimality conditions and the variational inequality. Theconvergence analysis and numerical experiment are also contained.2.We translate the perturbed optimality conditions of semidefinite programminginto the least squares problem, a new primal-dual direction (Gauss-Newtondirection) is achieved by solving the least squares problem. An infeasibleshort-step path-following algorithm based on the Gauss-Newton direction andConvergence analysis are given. The empirical evidence suggests the directionoffer more robust than other directions currently in use.3.The strengthened SDP relaxation is based on applying a lifting procedure to thiswell-know SDP relaxation after adding the nonlinear constraints. It is shown thatthe new bound obtained this way strictly improves the previous SDP boundboth empirically and theoretically.

Related Dissertations

  1. The Study on Search Directions of Interior-point Methods for Semidefinite Programming,O221.2
  2. The Study on Several Algorithms for Semidefinite Programming,O221.2
  3. MTO supply chain 3PL Transportation Scheduling Problem,F224
  4. A Alternating Direction Method for Quadratic Semidefinite Programming,O221.2
  5. Study of Filter-Type Algorithms in Solving Constrained Optimization Problems,O221.2
  6. The Applications of Alternating Projections Method,O224
  7. Nonsingularity Study of the Parametric FB System for Nonlinear Semidefinite Programming,O221.2
  8. Sensitivity Analysis in Semidefinite Programming,O221.2
  9. A Globally Convergent Interior-Point Algorithm for Inequality-Constrained Nonlinear Semidefinite Programming,O221.2
  10. LMI-Based Set-Membership Estimation of Uncertain Dynamic Systems Research and Application,TP13
  11. On the Interior Point Algorithm for Optimization Problem with Free Variables,O224
  12. Research on Thulium-doped Fiber Lasers Cross-Relaxation Features,TN248
  13. Effect of Hyperbranched Polyesteramide on the Rheological Characteristics of Filled Styrene-butadiene Rubber,TQ330.1
  14. The Study of the Structure, Properties and the Blending Structure Homogenization of Star-SSBR/BR Blending,TQ330.1
  15. Study on the Regeneration Technology of Weast Rubber,X705
  16. Study on the Mechanisms and Effects of KB-R7943 on Isolated Aorta and Arteriole Rings of Rats,R96
  17. Research on Power System Unit Commitment with Dynamic Security Constraints,TM73
  18. The Study on Optimal Reactive Power of Oilfield Distribution,TM714.3
  19. Study on Nuclear Magnetic Resonance Relaxation of Polymer,O631.3
  20. Deformation Anisotropy Study of Columnar Jointed Rock Masses,TU452
  21. Magnetic Resonance Imaging of Denervated Muscle and Peripheral Nerve,R746

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