How to judge whether an optimization problem is convex or non-convex?

Ingenious OR ingenious

Author: Qin Hanzhang

Editor’s note

This paper introduces the common methods to determine whether an optimization problem is convex/non-convex: based on definition/general form judgment; Derivation & First order/Second order sufficient and necessary condition judgment; Based on superposition/variation/composition; Numerical verification of monte Carlo sampling violence based on definition.

1. In general, it is strongly NP-hard to determine whether a problem is convex or not

First of all, this question is generally difficult. Such as: Strongly NP-hard to determine whether a polynomial of polynomial degree four (or more) is convex:

(web.mit.edu/~a_a_a/Publ…

2. General form of convex problem

So the real challenge is to tell whether a function is convex or not. \

3. Some tricks to determine whether a function is convex

Of course, if all else fails, we still have to go back to the initial center (the definition of a convex function) and do the Monte Carlo test numerically: take two points at a time and see if the convex combination is less than or equal to the convex combination of values… Take lots and lots of samples

The following SAO operations come from Stephen Boyd’s own convex optimization open class: If you sample monte Carlo many, many times and find no counterexamples, then you can assume that with a high probability the function is estimated to be convex, and you can put it in the paper as “conjecture”, Perhaps some enterprising young man AP will later write dozens of pages of proof proving your “conjecture” — a good way to tell if it is convex or not.

References:

Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

Highlights of past For beginners entry route of artificial intelligence and data download machine learning and deep learning notes such as printing machine learning online manual deep learning notes album "statistical learning method" code retrieval based album album download AI based machine learning mathematics This knowledge planet "Huang Bo circle of machine learning" (92416895) Site QQ group704220115. To join the wechat group, scan the code:Copy the code