14
$\begingroup$

Given a general non-linear problem:

\begin{align}P:\qquad&\min_{x\in X} f(x)\\\text{s.t.}\qquad&g(x)\leq 0\end{align}

where $f$ is a non-linear function, $g$ is a vector of non-linear constraints, and $X$ is a box-constrained domain, is there a way to formulate an optimisation problem to prove whether $P$ is convex or not?

This is typically handled through heuristic procedures (symbolic compositions of functions, eigenvalue arithmetic, Dr. AMPL, etc.) but I'm curious about how to formulate an optimisation problem to definitively prove/disprove the convexity of a problem regardless of computing cost.

We know from the theory that proving/disproving convexity of an NLP is an NP-hard (global optimisation) problem in the general case, but I can't find a formulation. Does one exist? Are you aware of a reference describing the formulation?

$\endgroup$
  • 1
    $\begingroup$ If h(x) is nonlinear, then unless the feasible set is a singleton, such as $x^2 = 0$, the odds of the problem being convex are not good, to put it mildly. $\endgroup$ – Mark L. Stone Sep 3 '19 at 17:24
  • $\begingroup$ @MarkL.Stone You're right, I updated the question to restrict the scope to linear equality constraints. $\endgroup$ – nikaza Sep 3 '19 at 17:28
  • $\begingroup$ Now that you have edited the problem, the box constraints and (general) linear equality (as well as inequality) constraints, are convex, and therefore can be removed from the formulation without affecting the problem's convexity. $\endgroup$ – Mark L. Stone Sep 3 '19 at 17:30
  • $\begingroup$ Also true, I removed the equality constraints altogether. $\endgroup$ – nikaza Sep 3 '19 at 17:44
  • 1
    $\begingroup$ The problem is equivalent to deciding whether $\{x: f(x) \leq \theta, g(x) \leq 0\}$ is convex. One way to disprove convexity is to find a $x_1, x_2, \lambda$ so that $x_1, x_2$ are in the set but $\lambda x_1 + (1-\lambda)x_2$ is not. Therefore we can consider an optimization problem where we maximize the infeasibility of $\lambda x_1+(1-\lambda)x_2$ subject to the feasibility of $x_1, x_2$. The objective is bilinear but you could bisection search over $\lambda$. Of course, you need to be able to optimize over $g(x)$ for this formulation to work, so i'll keep this as a comment. $\endgroup$ – Ryan Cory-Wright Sep 3 '19 at 19:14
13
$\begingroup$

Based on the comment by Ryan Cory-Wright, you could formulate it like this.

Verify convexity of the domain $\{x \in X : g(x) \le 0\}$

Solve the following problem, and check the optimal value.

\begin{align} \max\qquad& g\left(\lambda x + (1-\lambda) y\right) && \small\textrm{(maximize constraint violation of convex combination)}\\ \text{s.t.}\qquad& g(x) \le 0 && \textrm{($x$ is feasible)}\\ & g(y) \le 0 && \textrm{($y$ is feasible)}\\ & 0 \le \lambda \le 1 && \textrm{(define convex combination)}\\ & x, y \in X && \textrm{(definitions $x$ and $y$)}\\ \end{align}

If the optimal value is (strictly) positive, then the set is not convex, as $x$ and $y$ are both in the set, while their convex combination $\lambda x + (1-\lambda) y$ is not. If the optimal value is non-positive, then the set is convex.

Verify convexity of $f$ on the domain $\{x \in X : g(x) \le 0\}$

Solve the following problem, and check the optimal value.

\begin{align} \max\qquad& \small f(\lambda x + (1-\lambda) y) - \left(\lambda f(x) - (1-\lambda) f(y)\right) && \small\textrm{(maximize violation of convex combination)}\\ \text{s.t.}\qquad& g(x) \le 0 && \textrm{($x$ is feasible)}\\ & g(y) \le 0 && \textrm{($y$ is feasible)}\\ & 0 \le \lambda \le 1 && \textrm{(define convex combination)}\\ & x, y \in X && \textrm{(definitions $x$ and $y$)}\\ \end{align}

If the optimal value is (strictly) positive, then there exists a convex combination such that $f(\lambda x + (1-\lambda) y) > \lambda f(x) + (1-\lambda) f(y)$, which violates convexity. If the optimal value is non-positive, $f$ is convex.

Solving the above problems

As you already mention, solving the above problems could be very difficult, even if $f$ and $g$ are actually convex. Things can become even more difficult if the functions are 'weird'. For example, $$g(x) = \begin{cases}\textrm{0 if $x \in \mathbb{Q}^n$}\\\textrm{1 if $x \notin \mathbb{Q}^n$}\end{cases}$$ seems very problematic!

$\endgroup$
  • 4
    $\begingroup$ You'll probably should add some benevolent assumptions about the functions, for example continuity or (sub-)differentiability. If you do not make any assumptions, functions like the example that you gave will complicate things extremely. $\endgroup$ – JakobS Sep 4 '19 at 8:26

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.