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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

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

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.