
Semidefinite Programming |
"Still, we are surprised to see the relatively small number of submissions to semidefinite programming (SDP) solvers, as this is an area of significant current interest to the optimization community. We speculate that semidefinite programming is simply experiencing the fate of most new areas: Users have yet to understand how to pose their problems as semidefinite programs, and the lack of support for SDP solvers in popular modelling languages likely discourages submissions." In broad terms, a semidefinite program is a convex optimization problem that is solved over a convex cone that is the positive semidefinite cone. Semidefinite programming has emerged recently to prominence primarily because it admits a new class of problem previously unsolvable by convex optimization techniques, secondarily because it theoretically subsumes other convex techniques such as linear, quadratic, and second-order cone programming. Determination of the Riemann mapping function from complex analysis, for example, can be posed as a semidefinite program. If one were faced with the choice of implementing a problem as a semidefinite program or as a linear program, one should always choose the linear program. The reason has only to do with contemporary implementation. Nearly all semidefinite program solvers employ an interior-point method of solution (eg, a log barrier method). The outcome of these techniques is to reduce relative numerical precision of an optimal solution to no more than 1E-8, whereas linear programs achieve 1E-15 accuracy. Most researchers regard poor accuracy as an insignificant problem. But we disagree - our methods for constraining rank are suffering limitations as a consequence. (confer IEEE floating point) Read more... |