0

I've been going through some notes on convex optimization which partition the space of convex optimization problems into:

  1. Linear programs
  2. Quadratic programs
  3. Semi-definite programs
  4. Conic programs

with each tier containing the problems in the classes above it.

Given this arrangement, I'm curious which tier a problem like logistic regression falls into.

Also, where does geometric programming fit into this hierarchy?

ted
  • 1,725
  • 1
    Conic programs are "universal", in that every convex optimization problem can be expressed as one. But that's not a particularly practical category. – Michael Grant Feb 06 '18 at 17:44
  • Thanks Michael. So then it seems that conic programs contain the set of convex optimization problems. Can I assume this is strict containment? I.e, are there conic programs which are not convex optimization problems? And if so, is this the case when the cones are not convex cones, or the objective is not convex? Thanks. – ted Feb 06 '18 at 18:21
  • That's not quite what I said. I said that every convex optimization problem can be expressed as a conic program. What I mean by that is given a convex optimization problem that is not conic, you can convert it to conic form through transformations. So conic programs are a strict subset of convex optimization problems, and yet every convex program is equivalent to a member of that strict subset. – Michael Grant Feb 07 '18 at 05:42
  • I see. Are these transformations typically polynomial time? – ted Feb 07 '18 at 06:24

2 Answers2

2

You can start by looking at Convex Optimization by Stephen Boyd and Lieven Vandenberghe, which shows how geometric programming problems and logistic regression problems can be formulated as convex optimization problems.

Within the set of conic programming problems, it's worthwhile to distinguish between LP, SOCP, and SDP problems for which there are polynomial time interior point methods and more general conic programming problems for which we don't have polynomial time algorithms. The most important cone in this broader class is the exponential cone.

Geometric programming problems can be transformed into convex programming problems involving the log-sum-exp function and then expressed as conic optimization problems over the exponential cone. Conic solvers that can exploit this exponential cone structure can solve these problems. For example, the YALMIP modeling package can use the SCS solver to solve geometric programming problems.

Similarly, logistic regression problems can be formulated as conic optimization problems over the exponential cone and solved using software for exponential cone programming. Thus both of these problems can be formulated as conic programming problems, but they fit into the upper end of the hierarchy above SDP.

Although specialized solvers for exponential cone programming problems are available, they haven't been very widely used. Other alternative approaches are more often used in practice.

One alternative is to use semidefinite programming to approximate the log functions and solve the SDP approximation. The approximation can be refined as needed to get a sufficiently accurate solution. This allows the use of a polynomial time SDP solver. This approach is used for example by the CVX modeling package.

In statistical packages that implement logistic regression, a variety of optimization algorithms have been used, included Expectation-Maximization (EM) methods and Iteratively Reweighted Least Squares (IRLS)

Brian Borchers
  • 10,563
  • 2
    "Although specialized solvers for exponential cone programming problems are available, they haven't been very widely used." This might change with the forthcoming release of MOSEK version 9, which adds native support of the exponential and power cones https://docs.mosek.com/generic/workshop/2018/mixed-int-conic/dahl.pdf . Indeed as discussed in https://docs.mosek.com/generic/workshop/2018/mixed-int-conic/dahl.pdf , the exponential and power cones are non-symmetric (vs. previously supported cones being symmetric), which is a key attribute contributing to their difficulty. – Mark L. Stone Feb 04 '18 at 20:46
  • We don't have polynomial time algorithms for the exponential cone? I'm aware we don't get the performance of a symmetric primal/dual method, but surely a primal path-following method can be constructed. – Michael Grant Feb 06 '18 at 17:45
  • @MichaelGrant I'm not aware of any interior point methods to these problems that have polynomial iteration complexity- I'd be interested if that has changed since I last looked at this years ago. – Brian Borchers Feb 06 '18 at 21:27
  • Hmm. I'm surprised because frankly I didn't think this was controversial. Santiago Akle Serrano, one of Yinyu Ye's students, did his Ph.D. dissertation on this, and demonstrated $O(\sqrt{\nu})$ complexity. But he says the complexity results were known already. – Michael Grant Feb 06 '18 at 21:51
  • 1
    I stand corrected. I wasn't aware of this result. – Brian Borchers Feb 06 '18 at 22:03
  • What have heard is that it is difficult to get good practical performance! I'm glad MOSEK is on the case. – Michael Grant Feb 07 '18 at 03:18
0

You might want to add

5) Convex programs

as this contains geometric programming via the log-sum-exp function; see https://en.wikipedia.org/wiki/Geometric_programming

max_zorn
  • 4,875