Semidefinite Programming And Its Applications

Semidefinite programming, in particular, linear semidefinite programming is an extension of linear programming, with vector variables replaced by matrix variables and non-negativity elementwise replaced by positive semidefmiteness. In linear semidefinite programming one maximizes (minimizes) a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so linear semidefinite programs are nonsmooth convex optimization problems. In the past several years, linear semidefinite programming has been one of the most active research areas in mathematical programming. There are two major factors that are responsible for this increased interest in semidefinite programming. Firstly, semidefinite programming has found numerous applications in various fields, such as statistics, structural design, electrical engineering (design of FIR filters and multiuser detection in CDMA) and combinatorial optimization. Secondly, most interior-point methods for linear programming have been generalized to linear semidefinite programs. As in linear programming, these methods have polynomial worst-case complexity, and have proven to be reliable and effective in the solution of small to moderately sized problems. Investigating semidefinite programming is very significative both in theory and in practice. M. L. Overton said: "semidefinite programming is an exciting subject that remains very active, and will no doubt be so for some time to come. Here is an area where nonlinear convex programming has shown its strength, beauty, and versatility. One finds elegant theoretical results, provably efficient algorithms and a wide variety of applications. " In this paper, we firstly summarize the theory, algorithms, and research state of semidefinite programming, secondly introduce ours some works both in theory and in practice of semidefinite programming. For detail, we conclude them as follows:1. A tight semidefinite relaxation of the quadratically constrained quadratic -1\1 optimization problem is obtained, which improves several previous SDP relaxations in the literature. It is applied to Max cut (MC) problem and the quadratic knapsack problem. Numerical results demonstrate that the method is very effective, particularly in Max cut (MC) problem defined on random complete graph with nonnegative edge weights, we often can gain an optimal solution. The quality of feasible set of the tight semidefinite relaxation is studied, especially in Max cut (MC) problem, we obtain astrong result.2. A semidefinite programming bounding technique is presented for linearly constrained 0\1 quadratic programming problems, which could in turn be incorporated into the Brand-and-Bound scheme. In the bounding technique, we educe a nonlinear semidefinite programming and develop a spectral bundle method for the nonlinear semidefinite programming. The bounding technique is applied to the quadratic knapsack problem. Numerical results demonstrate that the bounding technique is very effective. Using the bounding technique, we can quickly find an optimal solution of the quadratic knapsack problem to a certainty size. A quadratic programming method based on semidefinite programming is given to solve the Max cut (MC) problem. This method can give a better bound than semidefinite programming relaxation. Numerical results demonstrate that we can quickly give an optimal solution of the Max cut (MC) problem to a certainty size using die quadratic programming.3. Samuel Burer and Renato D, C. Monterio proposed a rank-two relaxation heuristic for Max-cut and Max-bisection. We improve the method and develop a rank-two relaxation heuristic for the binary quadratic programs. In particular, we apply the method to the design of FIR filters and the multiuser detection hi CDMA. In the design of FIR filters, simulations demonstrate that near-optimal performances of the design based on the method is similar to that of the design based on the previous semidefinite relaxati...