Where do these problems fall in the "convex problem class" hierarchy?

Question

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?

Answer 1

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)

Answer 2

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