3
$\begingroup$

If you can not take the derivative of your objective function - is the idea of "convexity" irrelevant?

Whenever I look at the mathematical definitions of "convexity" - there always eventually seems to be a requirement that for the idea of "convexity" to apply, the function must be differentiable (i.e. you can take the derivative). For instance: we say that a Non-Convex Function can have Saddle Points - and Saddle Points are points on a function where the second derivatives of the function are 0, but this point is not a maximum nor a minimum.

In cases where you can not take the derivative of your objective function (As in most discrete combinatorics optimization problems, e.g. Travelling Salesman, Knapsack Optimization) - can we still describe the objective functions in these problems as "convex" or "non-convex"? Or does the idea of "convexity" only apply to problems where the objective function is differentiable?

Note: I have informally heard that Discrete Combinatoric Optimization problems are typically more difficult than optimization problems where the search space is continuous. Is this because of the fact that the objective function in discrete problems is non-differentiable?

$\endgroup$
6
  • 5
    $\begingroup$ Convexity stands apart from differentiability. The function abs(x) is convex everywhere, but not differentiable at 0. $\endgroup$ Jan 30 at 2:18
  • $\begingroup$ Thank you for this observation! In the case of the travelling salesman - do we know if the objective function is convex or non-convex? thanks! $\endgroup$
    – stats_noob
    Jan 30 at 2:41
  • $\begingroup$ For a standard TSP, the objective function is linear, hence both convex and concave. $\endgroup$
    – prubin
    Jan 30 at 16:23
  • $\begingroup$ Thank you! I just can't understand this :( . How can you "draw a graph" for the objective function of TSP? I can draw a graph of y = sin(x) . But how can I draw a graph of the "objective function of TSP" and figure out if its convex? Thank you! $\endgroup$
    – stats_noob
    Jan 30 at 17:51
  • $\begingroup$ For instance, the objective function of a combinatorial optimization problem have "saddle points"? Is this even possible? How can we make the convex or non-convex distinction in such cases? thank you! $\endgroup$
    – stats_noob
    Jan 30 at 17:54

3 Answers 3

6
+25
$\begingroup$

You need to make a distinction between the problem itself, and its individual components (objective and constraints).

What is a convex problem?

Consider a generic optimization problem \begin{align} (P) \quad \min_{x \in \mathbb{R}^{n}} \quad & f(x)\\ \text{s.t.} \quad & x \in \mathcal{X} \end{align} where $\mathcal{X} \subseteq \mathbb{R}^{n}$ . To settle the terminology: $x$ are the decision variables, $f$ is the objective function, and $x \in \mathcal{X}$ are the constraints.

The problem $P$ is convex if

  • $\mathcal{X}$ is a convex set
  • $f$ is a convex function, which can be relaxed to "$f$ is convex over $\mathcal{X}$".

For instance: \begin{align} \quad \min_{x \in \mathbb{R}} \quad & x^{2}\\ \text{s.t.} \quad & 0 \leq x \leq 1 \end{align} is a convex problem because $x \rightarrow x^{2}$ is convex and $\{x \in \mathbb{R} | 0 \leq x \leq 1\}$ is a convex set. On the other hand, \begin{align} \quad \min_{x \in \mathbb{R}} \quad & x^{2}\\ \text{s.t.} \quad & x \in \{0, 1\} \end{align} is not a convex problem because $\{0, 1\}$ is not a convex set.

Note that in both examples, the objective function is well-defined, continuous, differentiable, and convex. In the latter case, the non-convexity stems from the constraints, not in the objective.

What about differentiability?

Convexity is a geometric property, which is not tied to differentiability. For instance, the function $x \rightarrow |x|$ is convex, but it is not differentiable at zero.

Therefore, a problem can be convex even if some of its components are non-differentiable. For instance: \begin{align} \quad \min_{x \in \mathbb{R}} \quad & |x|\\ \text{s.t.} \quad & -1 \leq x \leq 1 \end{align} is a convex problem.

Differentiability influences the algorithm you can use to solve a problem: some require derivatives, others don't. For instance, gradient descent or Newton's method require derivatives, and cannot be applied out-of-the-box. The ellipsoid method does not use gradients, and is therefore applicable to convex problems with some non-differentiable components.

Does convexity still matter when we have discrete decisions?

TLDR: Yes, yes and absolutely yes!

You will often encounter in the optimization literature the term "Mixed-Integer XXX Programming", e.g., "Mixed-integer Linear Programming", "Mixed-Integer Convex Programming", etc. The first part indicates that some variables are restricted to take integer values. The second part usually refers to everything else.

For instance, a Mixed-Integer Linear Programming (MILP) problem is a problem where (i) some variables must be integer and (ii) everything else is linear. For Mixed-Integer Convex Programming (MICP) problems, (i) some variables must be integer and (ii) everything else is convex. Integrality constraints are non-convex, so mixed-integer problems are not convex.

However, drop the integrality requirements from an MICP problem, and you get a convex problem! This is known as a convex relaxation, and it's the fundamental building block of many optimization algorithms for mixed-integer programming.

$\endgroup$
3
$\begingroup$

If you formulate your problem as a MILP, then the formulation is convex since it is linear, but that doesn't change much for you.

If you formulate it as a MINLP, (Quadratic Assignment for example), then it is important. Some algorithms for MINLP are exact only when the problem is convex (NLP-based branch-and-bound, Outer approximations...). When the problem is non-convex, other methods, such as spatial branch-and-bound, need to be used to prove the global optimality

$\endgroup$
2
  • $\begingroup$ Thank you so much for your answer! I still don't understand - just because you can formulate the TSP problem as MILP, why does it make this convex? For instance, the objective function of a combinatorial optimization problem have "saddle points"? Is this even possible? How can we make the convex or non-convex distinction in such cases? thank you! $\endgroup$
    – stats_noob
    Jan 30 at 17:54
  • 5
    $\begingroup$ Yes, it's a bit abusive. Strictly speaking, it's the relaxation which is convex, since the domain is not continuous. But people say convex MINLP instead of MINLP with a convex NLP relaxation. Then, for LP, any linear function is convex, that's trivial if you apply the definition en.wikipedia.org/wiki/Convex_function#Definition $\endgroup$
    – fontanf
    Jan 30 at 18:06
3
$\begingroup$

I would argue with the previous comments, that MILP problem formulation is convex and that the theory of Convex Optimization could be applied to the MILP problems.

First I would recommend you to read Book about Convex Optimization by Stephen Boyd and Lieven Vandenberghe. Stephen Boyd is a very respectful and famous mathematician in the optimization field.

If we look at the definition of the convex function
enter image description here enter image description here

You can see that definition of the convexity does not have anything to do with whether the function is differentiable or not. However, the domain of a function f has to be a Convex Set. Now let us look at the definition of the Convex Set enter image description here enter image description here

Therefore, if the objective function has discreet variables, then we can never call it Convex function, because it is defined on the discreet space, and in this space, we can not draw an unobstructed straight path between two points.

But it could be, for example, if you have binary variables in your objective, and then you consider your function at point [ 0 ] or 1 , the function could be convex at exactly these points, but not on the whole discreet space.

$\endgroup$
1
  • 1
    $\begingroup$ See the comment I wrote below my answer $\endgroup$
    – fontanf
    Feb 3 at 13:05

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.