12
$\begingroup$

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 :)

$\endgroup$
1
  • $\begingroup$ DC Programming algorithms are interested in this kind of problems. Some examples: variations of clustering, modularity maximization, self-organizing maps, nonnegative matrix factorization, one-class Support Vector Machine, robust support vector machines, spherical separation, weakly supervised learning, semi-supervised classification, sparse-learning problems, learning under uncertain data. $\endgroup$ Jun 13, 2019 at 14:22

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ That's a great example! I am definitely going to read about that! $\endgroup$ May 30, 2019 at 22:47
  • 1
    $\begingroup$ It's a beautiful model IMO. Their algorithm is also very elegant, and efficient. $\endgroup$ May 30, 2019 at 22:49
  • $\begingroup$ Sorry I couldn't find the relevant part of the paper yet. Does it reduce to a concave quadratic minimization? $\endgroup$ May 30, 2019 at 22:54
  • 1
    $\begingroup$ In Shen, Coullard, and Daskin 2003, the objective function (11) is a concave function of the binary decision variables $Y_{ij}$, and they are minimizing. $\endgroup$ May 31, 2019 at 0:21
4
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ As far as I understand the question, he is asking about maximizing a convex function, which is not a convex optimization problem. $\endgroup$ May 30, 2019 at 23:00
  • $\begingroup$ Thank you for your long and nice answer! I had read Boyd's book and the socp paper already. But aren't these convex problems? I am looking for the opposite case. $\endgroup$ May 30, 2019 at 23:03
  • $\begingroup$ I don;t believe a downvote is or was appropriate, as the fault lies at least as much with the OP for poor wording, for which I chose a different interpretation than the OP intended. Even mention of log-sum-exp, wasn't a clincher for the OP's question, because, as I have seen used in a paper I was dealing with earlier today, log-sum-exp can be used in a concave fashion if it is preceded by a negative sign, as it was in the paper. $\endgroup$ May 30, 2019 at 23:23
  • $\begingroup$ I was not the one who downvoted. I can understand these thinks look quite similar :) I am now concentrating on your upper-lower bound suggestion. Many thanks! $\endgroup$ May 31, 2019 at 0:10
  • $\begingroup$ I downvoted because I think this is a low quality answer. There is a huge block of text which is not relevant at all (the second half), and the first half completly boils down to "take any convex problem and put a minus sign in front of the objective function" without any references. Surely if this is an important application of convex maximization it should be trivial to reference some of them. $\endgroup$ May 31, 2019 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.