Do they use semidefinite programming in industry?

Question

I can't see any mention of it in job listings. I've seen mentioned integer programming, MIP, mixed-integer nonlinear programming, LP, dynamic programming etc., but no SDP. Is it much trendier in the academy than in industry?

From my limited exposure to academics and industry participants in electric power systems, I think there's a good chance that SDP will be applied in optimal power flow problems by independent system operators, but that it depends on the extent to which the egg-heads can scale up current approaches to deal with bigger problem instances.

Answer 1

From my own limited experience in the power industry, no one is solving SDPs at that sort of scale. I have some limited knowledge of what the New England ISO is doing, and I think they are more interested in incorporating stochasticity into their existing MILP models. From friends who have worked on power systems at governmental research labs in the USA, they are also thinking about stochasticity (stochastic programming, chance constraints, robust optimization...).

From my experience in the large tech company sector, people are solving MILPs at the most complicated, and usually deterministic models.

I gather from the chemical engineering side they seem interested in MINLP, in particular nonconvex quadratically-constrained optimization, which arises naturally in mixing problems. There are also PDE constrained problems and all those other fun things, but thats mostly out of my expertise.

If I had to speculate, SDP might be used in semiconductor design as a subroutine (e.g. for MAXCUT), but given the lack of quality solvers I'm guessing there isn't a huge demand (yet, at least).

I'd say in academia, SDP is more interesting as a proof tool, i.e. "look, this problem is polynomial time!" if you can figure out how to wrangle as an SDP. SDP solvers are so touchy (compared to other convex problem classes) that I think people aren't really excited about the idea of having to actually solve them.

Answer 2

Semidefinite programming and second order cone programming have not been adopted as rapidly in practice as many of us hoped. I've been involved in this for the last 20 years, and it has been very disappointing to see slow progress. Let me point out some of the challenges:

1. Although we have polynomial time algorithms for SDP and SOCP, the widely used primal-dual interior point methods typically require $O(m^{2})$ storage where $m$ is the number of constraints. This makes solving problems with 50,000 constraints possible but solving problems with 500,000 constraints impractical today. Of course, memory capacity keep growing exponentially, so many important problems will eventually be solvable, but there are many problems that aren't practically solvable today or in the near future. First order methods that don't have $O(m^{2})$ storage requirements are an active topic of research but in the area of SDP they simply haven't proven to be robust enough for use in a general purpose solver.

2. The vendors of LP software haven't seen fit to include support for SDP in their products yet. Some limited support for SOCP is starting to appear.

3. Knowledge about semidefinite programming has spread slowly. The textbook by Boyd and Vandenberghe has been hugely helpful in this respect, but there's a long way to go before this technology will be as widely known as older optimization techniques.

4. Modelling languages and systems (such as GAMS, AMPL, etc.) don't yet provide good support for SOCP and SDP. The CVX package is the most interesting work in this direction, but even it requires some sophistication on the part of the user.

SDP has found applications at the research level in many areas of engineering and science. It seems likely that these will eventually become important in industry as well.

Answer 3

Most of the work I'm aware of at labs for power flow problems is on stochastic optimization also, focusing mostly on MILPs.

In chemical engineering, they are interested in MINLPs, and the classic example is a mixing problem (specifically, the prototypical Haverly pooling problem), so bilinear terms come up a lot. Trilinear terms occasionally pop up, depending on the thermodynamic mixing models or reaction models used. There's also a limited amount of interest in ODE-constrained or PDE-constrained optimization; none of that work uses SDPs.

Most of the PDE-constrained optimization work I've seen (I'm specifically thinking of topology optimization) does not use SDPs. The PDE constraints could be linear, and in theory, could admit an SDP formulation depending on what the objective and remaining constraints are. In practice, engineering problems tend to be nonlinear, and yield nonconvex problems that are then solved to local optima (possibly also using multistart). Sometimes, penalty formulations are used to exclude known suboptimal local optima.

I could see it maybe being used in control theory. The small amount of work I've seen on "linear matrix inequalities" suggests that it could possibly be useful there, but control theory in industry tends to rely on tried-and-true methods rather than bleeding edge mathematical formulations, so I doubt SDPs will be used for a while until they can prove their usefulness.

There are a few SDP solvers that are okay, and they've solved problems that are pretty big for academia (last I checked was 3-4 years ago, and they were solving tens to hundreds of thousands of variables), but power flow scenarios involve much larger problems (tens of millions to billions of variables), and I don't think the solvers are there yet. I think they could get there -- there's been a fair amount of recent work on matrix-free interior-point methods that suggests that it'd be feasible to scale up SDP solvers using those techniques -- but no one's done it yet, probably because LPs, MILPs, and convex NLPs come up much more frequently and are established technologies.