3
$\begingroup$

I have general question regarding the benefits of semi-definite programming.

Assuming I have a non-convex program which can by relaxed to an SDP. Why should I use the SDP formulation (and the corresponding SDP solvers) over a standard convex programming formulation (and its corresponding solvers) when I adopt the same relaxation?

To the best of my knowledge, many SDP solvers and many standard solvers for convex programs use interior point methods. Where are the advantages of the one over the other?

Edit (sorry for being so imprecise):

What I meant is the (corner ?) case in which I can relax a non-convex problem to an SDP (e.g. having actually a non-affine equality constraint and using Schur's complement to make it a SDP-conform inequality constraint) and then using an SDP solver like Sedumi. Compared to the case when applying the same/equivalent relaxation to the non-convex problem but then using standard interior points methods directly (e.g. using MATLABs fmincon).

Meaning in the example above, I assume that the objective is convex but there is non-convex constraint.

Edit 2

Assuming e.g. that I have a convex objective and and some convex constraint, and also one non-convex constraint of the form $\delta = d^2$ where $\delta$ is some slack variable. Then I can obtain a SDP-conform relaxation using Schur complement via

$$ S = \begin{bmatrix} 1 & d \\ d & \delta \end{bmatrix} \succeq 0 $$

Consequently, I am forcing all eigenvalues of $S$ to be non-negative. If I now obtain the corresponding constrains on $\delta$ and $d$ such that $S$ is PSD and use them e.g. in fmincon: What are the benefits of using an SDP solver in the example above, compared to the case where I incorporate the non-negative eigenvalue constraints in to e.g. into fmincon?

$\endgroup$
10
  • $\begingroup$ By "standard convex programming formulation" are you referring to a convex optimization problem with arbitrary (perhaps smooth) convex functions in the objectives and constraints? Or something else? $\endgroup$
    – Brian Borchers
    Dec 11, 2017 at 14:56
  • 1
    $\begingroup$ Similar question to Brian here. Do you have a specific example in mind of a non-convex problem with two different nonlinear convex relaxations---one SDP and one otherwise? $\endgroup$
    – Michael Grant
    Dec 11, 2017 at 16:19
  • 2
    $\begingroup$ Or, are you referring to situations where the convex relaxation can be formulated as an LP, CQP, or SOCP (all of which can be solved as SDP's)? $\endgroup$
    – Brian Borchers
    Dec 11, 2017 at 16:28
  • $\begingroup$ @BrianBorchers I made an edit that hopefully clarifies the questions. $\endgroup$
    – bonanza
    Dec 11, 2017 at 18:26
  • $\begingroup$ @MichaelGrant I made an edit that hopefully clarifies the questions. $\endgroup$
    – bonanza
    Dec 11, 2017 at 18:26

1 Answer 1

Reset to default
2
$\begingroup$

it certainly is possible to solve semidefinite programming problems by general purpose convex optimization solvers such as the analytic center cutting plane method (ACCPM). You might consider ACCPM to be an interior point method although it is far more general than the primal-dual interior point method for SDP. In practice, using a specialized primal-dual interior point method to solve an SDP is faster than using the more general ACCPM.

There are also first-order methods for convex optimization that have been specialized to solving SDP and other conic optimization problems. These are not considered interior point methods. See for example the Splitting Conic Solver package. Compared with interior point methods, the first order methods can often solve larger instances, but the accuracy of solutions produced by the first order methods is often poor in comparison with the accuracy of solutions produced by primal-dual interior point methods.

Interior point methods for smooth nonlinear programming problems (see for example the IPOPT software package) exist, but they aren't properly applicable to SDP because the semidefiniteness constraint isn't expressible in terms of a finite number of inequality constraints involving smooth functions. For the same reason, other commonly used nonlinear programming methods like sequential quadratic programming aren't useful for solving SDP.

Finally, you might consider applying a general purpose nonlinear programming solver to your original nonconvex formulation of the problem. However, most nonlinear programming solvers only ensure convergence to a local (not global) minimum of a nonconvex optimization problem, so there's no way to be sure that you've actually solved the problem correctly. There are specialized methods that do obtain globally optimal solutions to some nonconvex optimization problems, but these are typically limited to very small instances and aren't of much use in practice.

P.S. Added after the original poster explained their problem in more detail. For a single convex quadratic constraint, SDP is overkill- any solver that can handle a quadratically constrained quadratic program will handle this constraint.

$\endgroup$
1
  • $\begingroup$ Thank for your answer, please see also my second edit to the question where I try to formulate an example where the PSD constraint could be formulated by means of further constraints into a form that could be e.g. understood by fmincon. $\endgroup$
    – bonanza
    Dec 11, 2017 at 20:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .