2
$\begingroup$

Which are the most famous problems having an objective of maximizing a nonlinear convex function (or minimizing a concave function)? As far as I know such an objective with respect to linear constraints is np-hard.

$\endgroup$
1
  • $\begingroup$ Adding to the answer: Max-CUT problem is re-formulated as $$\max \frac{1}{4} x^T L x \\ s.t. \ x \in [-1,1]^n$$ where L is the Laplacian form of the graph, which is a PSD matrix. So this is another nice example. $\endgroup$ Nov 18 '18 at 20:47
1
$\begingroup$

THE most famous problem having an objective of maximizing a convex function (or minimizing a concave function), and having linear constraints, is Linear Programming, which is NOT np-hard.

Linear Programming is both a convex optimization problem (minimizing a convex function subject to convex constraints) and a concave optimization problem (minimizing a concave function subject to convex constraints). Therefore it has all the properties of both, to include, all local optima are global optima, and if the constraints are compact (bounded), then there is a global optimum at the extreme of the constraints.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer! However, I am looking for nonlinear objective. I am editing the question now. Can you give an example problem with i.e. quadratic objective and preferably linear constraints (or maybe SOC constraints)? $\endgroup$ May 1 '18 at 22:06
  • 1
    $\begingroup$ This may not be famous, but let's says you have a convex function (for instance, quadratic), and want to find the range of possible values it can obtain over a convex constraint region. Finding the least possible value will be a convex optimization problem. Finding the greatest possible value will be a concave optimization problem, So convex and concave optimization problems can always come in pairs this way. For instance, suppose a value of the variable x has been chosen, but you don;t know what it is, then solving both problems bounds the range of how good or bad things could be. $\endgroup$ May 1 '18 at 22:15
  • $\begingroup$ That's actually really helpful. I am now trying to formulate this in more structured way. Maybe I can try to find the best methods we have in the literature so far for such a concave problem. $\endgroup$ May 1 '18 at 22:32
  • $\begingroup$ Found these so far: 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. Anything to add? $\endgroup$ May 13 '18 at 23:47
0
$\begingroup$

Regarding convex maximization problems, I would recommend the paper by R.Enkhbat " Global Optimization approach to Malfatti's problem"(Journal of Global Optimization, 2016). I think Malfatti's problem which was formulated in 1803 will be a nice example of the convex maximization problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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