Convex Maximization with Linear Constraints

Question

I am doing active research in convex maximization w.r.t. linear constraints. There are many cases which can be efficiently approximately solved, e.g., convex quadratic maximization, log-sum-exp maximization.

I am quite sunk in the theory but want to learn more about the applications. For example, which important applicable problems in STEM fields are formulated as convex maximization (or concave minimization) problems?

I can think of Difference of Convex Functions Programming (or DC Programming), and related applications. For example, SVMs with latent variables problem reduces to this kind of optimization problem if I am not wrong. Also, there are some variants of sparse PCA methods which ultimately try to solve concave minimization problems.

This is another source showing in ML, we can use concave minimization on a polyhedron, but this is mainly for absolute value maximization which is not a big deal today, i.e., CPLEX can solve these problems very fast.

So, I am here, open for suggestions about new problems where I can benchmark different existing convex maximization techniques!

Other examples include MAX-CUT problem, economies of scale, fixed charge network flow, maximal volume sphere inscribed in a polyhedron, 0-1 loss function-based classification methods, misclassification minimization, feature selection, unlabeled data classification.

PS. I don't accept LP as an answer :)

Answer 1

The location-inventory problem by Shen, et al. and Daskin, et al. has a concave minimization objective. It's related to economies of scale (which you list in your PS 2) but not exactly the same.

Answer 2

Edit: I misinterpreted the question as asking about maximization problems which are convex optimization problems.

Here is a whole class of naturally occurring concave optimization problems, i.e., maximizing a convex function or minimizing a concave function, in both cases subject to convex constraints Linear constraints are of course a special case of convex constraints.

Consider a convex optimization problem: maximize $f(x)$ subject to convex constraints, where $f(x)$ is a concave performance function. The solution provides the best possible performance. For many engineering purposes, we are also concerned as to the worst possible case. That is achieved by solving its (anti-)twin problem, globally minimize $f(x)$ subject to those same convex constraints. That worst possible case problem is a concave optimization problem. And for the purpose I just stated, it is important that the global optimum be found, not a non-global local optimum.

Another way of looking at this is if we wish to find the possible range of a convex or concave function $f(x)$, subject to some convex constraints. We obtain lower and upper bounds as the solution to globally minimizing in one case, and globally maximizing in the other case, $f(x)$ subject to the convex constraints. The bound on one side is obtained by solving a convex optimization problem, and the bound on the other side is obtained by solving a concave optimization problem, its (anti-)twin, to a global optimum (the convex optimization problem of course has no non-global local optima). As a further special case, if the constraints consist only of lower and upper bound constraints, i.e., box constraints, this approach provides the interval evaluation of the function $f(x)$ over the box.

All the problems mentioned in my original answer below, except those having linear objective functions, have a concave optimization (anti-)twin, as described above. That is one heck of a lot of problems. In the case of linear objective functions, the (anti-)twin problem serves the same purpose, but is also a convex optimization problem.

Original answer for convex optimization:

You can start by reading the freely downloadable book "Convex Optimization" by Boyd and Vandenberghe https://web.stanford.edu/~boyd/cvxbook/, particularly chapter 6-8, but you should really read the earlier chapters as well.

These two authors were two of the authors on an earlier paper "Applications of second-order cone programming" published in Linear Algebra and its Applications in 1998 http://www.seas.ucla.edu/~vandenbe/publications/socp.pdf .

If you have a problem involving estimation or optimization of a possibly partially known covariance matrix, that leads to a semidefinite optimization problem, because a semidefinite constraint, i.e., that a matrix is symmetric positive semidefinite is the exact same thing (if and only if) as constraining a matrix to be a covariance matrix. If the objective (minimizing a convex function or maximizing a concave function) and other constraints are convex, and the decision variables appear linearly in the semidefinite constraint, then the problem is a convex optimization problem, which in many cases can be solved efficiently by highly refined semidefinite solvers such as Mosek.

Geometric Programming can be transformed to a convex optimization problem and solved using the convex "exponential cone". See https://web.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf for some of the modeling possibilities.

Many problems related to log, entropy, and relative entropy can also be handled as convex optimization problems via the exponential cone. Matrix log, matrix entropy, and matrix relative entropy problems can be handled by the matrix (operator) exponential cone, as for instance with CVXQUAD https://github.com/hfawzi/cvxquad . There are applications in quantum mechanics and in Operations Research (for instance, statistical model fitting and approximation).

And there's much, much more.