13
$\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?

Improve this question
$\endgroup$
6
  • 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, 2019 at 17:24
  • $\begingroup$ @MarkL.Stone You're right, I updated the question to restrict the scope to linear equality constraints. $\endgroup$
    – Nikos Kazazakis
    Sep 3, 2019 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, 2019 at 17:30
  • $\begingroup$ Also true, I removed the equality constraints altogether. $\endgroup$
    – Nikos Kazazakis
    Sep 3, 2019 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, 2019 at 19:14

1 Answer 1

Reset to default
14
$\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!

Improve this answer
$\endgroup$
1
  • 5
    $\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, 2019 at 8:26

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.