Leo Liberti
email: liberti@lix.polytechnique.fr

Undecidability and hardness in mixed-integer nonlinear programming

Keywords: undecidability, hardness, mathematical programming

We survey two aspects of mixed-integer nonlinear programming which have attracted less attention (so far) than solution methods, solvers and applications: namely, whether the class of these problems can be solved algorithmically, and, for the subclasses which can, whether they are hard to solve. We start by reviewing the problem of representing a solution, which is linked to the correct abstract computational model to consider. We then cast some traditional logic results in the light of mixedinteger nonlinear programming, and come to the conclusion that it is not a solvable class: instead, its formal sentences belong to two different theories, one of which is decidable while the other is not. Lastly, we give a tutorial on computational complexity and survey some interesting hardness results in nonconvex quadratic and nonlinear programming.

This survey paper discusses two of the lesser known aspects of Mixed-Integer Nonlinear Programming (MINLP): computability and computational complexity. More precisely, we focus on their negative sides: undecidability and hardness.

Mathematical Programming (MP) formulations of the MINLP class can model any single-level, singleobjective MP problem, as long as it does not involve black-box functions or oracles. A MINLP formulation is formally written as follows:

min x∈F n f (x) g(x) ∈ [g L , g U ] x ∈ [x L , x U ] ∀j ∈ Z x j ∈ Z.        (1)
The symbols n, f, g, g L , g U , x L , x U , Z in Eq. ( 1) encode the input of the problem (also known as the instance). The formal sentence Eq. ( 1) reads informally as follows: given a positive integer n, a function f : F n → F (where F is a number field containing Z), a vector-valued function g : F n → F m , vectors g L ≤ g U ∈ F m and x L ≤ x U ∈ F n , and an index set Z ⊆ {1, . . . , n}, find a vector x * ∈ F n to be assigned to the decision variable vector x, such that x * minimizes the given objective function f (x) and is feasible with respect to (w.r.t.) the given constraints, i.e. g(x * ) ∈ [g L , g U ] and

x * ∈ [x L , x U ].
The field F is usually one of the following:

• the field R of reals (replaced for practical computation by the set of floating point representable reals);

• the field Q of rationals (for complexity results);

• the field C of complex numbers (which turns up in few but important applications, e.g. alternating current optimal power flow problems [START_REF] Salgado | Alternating current optimal power flow with generator selection[END_REF]);

• a cartesian product of an appropriate number of copies (matching the number of components of x) of any of the above.

The symbols f, g in Eq. (1) do not range over all possible functions: they are assumed to describe functions in "closed form". More formally, they are sentences of a formal language involving variable symbols, numerical constants from Q and a finite number of arithmetical, algebraic and possibly even transcendental operators, e.g. 3x 1 -4x 2 , x 2 1 x 3 and log( 1 x1 ). This language is used to represent functions in a way that can be encoded by a computer. Note that a well-formed string of this language corresponds to a unique function (however, the same function might have more than a single string description), and that there are countably many strings in this language, but uncountably many functions: it follows that we cannot represent every function. But since polynomials are representable in this form, and they are dense in all continuous functions over an interval, we can at least approximate all continuous bounded functions as closely as we wish, provided the string length is not bounded.

If the objective function and the continuous relaxation of the feasible region of Eq. (1) are convex, the formulation is called "convex MINLP" (cMINLP). Notice, however, that because of the integrality constraints, a convex MINLP is not in general a convex optimization problem. If Z = ∅ Eq. ( 1) is a Nonlinear Programming (NLP) problem, called "convex NLP" (cNLP) if the objective and feasible region are convex.

Natural processes are mostly nonlinear, whereas man-made processes are often linear or at least well-approximated by linear forms. As a result MINLP ends up being the tool of choice in manmade processes at the interface with natural phenomena, such as chemical and bio-chemical engineering [Grossmann, 1985, Grossmann, 1996, Floudas, 1995], electro-mechanical engineering [START_REF] Messine | Optimal design of electromechanical actuators: A new method based on global optimization[END_REF], Cafieri et al., 2013], energy management [START_REF] Pruitt | A mixed-integer nonlinear program for the optimal design and dispatch of distributed generation systems[END_REF], Quist et al., 1999, Bruglieri and Liberti, 2008],

reservoir engineering [START_REF] Lizon | A mixed-integer nonlinear optimization approach for well placement and geometry[END_REF], alternating current optimal power flow [START_REF] Ruiz | A progressive method to solve large-scale AC optimal power flow with discrete variables and control of the feasibility[END_REF], Salgado et al., 2018] water network design [START_REF] Bragalli | On the optimal design of water distribution networks: a practical MINLP approach[END_REF]. Typically, the nonlinearities occur as a consequence of the natural processes, and the integer variables (which are often binary) model the turning on and off of certain man-made controllers. MINLP is also used to model some man-made processes, such as portfolio optimization [Bienstock, 1996, Mencarelli et al., 2017], trim loss minimization in the cutting industry [START_REF] Harjunkoski | Different transformations for solving nonconvex trim-loss problem by MINLP[END_REF], Kallrath, 2009], and more [D'Ambrosio, 2010, Lee and[START_REF] Lee | [END_REF]. Morever, MINLP occurs in purely mathematical problems, such as the Kissing Number Problem (KNP) [START_REF] Maculan | Bounds on the kissing numbers in R n : Mathematical programming formulations[END_REF], where the nonlinearities arising from packing spheres around a spherical surface, with binary variables that control the presence or absence of the spheres.

MINLP is by now a large field of study [START_REF] Lee | [END_REF]: large enough to make a "universal MINLP survey" impossible to write in the space of an article, and even a complete MINLP book a significant hurdle. This survey takes the point of view of computability and complexity. Most of the discussed results are "old" (by MINLP standards) and established. But not all may be widely known within the MINLP community. This survey does not aim at relating every co-occurrence of MINLP and computability or complexity: the choice is personal, and based on interest, usefulness and/or elegance. Many proofs are sketched only briefly. Many works in nonlinear discrete optimization do not appear here because a recent survey already exists [START_REF] Hemmecke | Nonlinear integer programming[END_REF].

For more information about MINLP, nonconvex NLP, applications, and solution algorithms, see the following surveys: [START_REF] Belotti | Mixed-Integer Nonlinear Optimization[END_REF], [START_REF] Burer | Non-convex mixed-integer nonlinear programming: A survey[END_REF], [START_REF] D'ambrosio | Mixed-integer nonlinear programming tools: a practical overview[END_REF], [Neumaier, 2004], [START_REF] Grossmann | Mixed-integer nonlinear programming: a survey of algorithms and applications[END_REF] and books: [START_REF] Lee | [END_REF], [Tawarmalani and Sahinidis, 2 [Floudas, 2000], [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF], [Floudas, 1995]. Some sources also delve in complexity issues, specially as regards efficiently solvable cases [START_REF] Hemmecke | Nonlinear integer programming[END_REF]. Further information in topics discussed in this survey can be found in more specialized surveys or books [Dür, 2010, Bomze, 2012, Vavasis, 1991].

Representability

The solutions of Linear Programs (LP) and Mixed-Integer Linear Programs (MILP) have rational components as long as the input data is rational. For MINLP, the situation is not so clear, as solution components might involve irrational numbers (both algebraic and transcendental, depending on the involved functions). To the best of our knowledge, there are three main approaches to representability.

The real RAM model

The computational complexity model of Blum, Shub and Smale [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines[END_REF] (often referred to as real RAM model) essentially eschews the problem of representation, as it defines the real equivalent of computational complexity classes such as P, NP and their relationships. In the real RAM model, storing or reading any real number has unit cost. This model of computation is mostly used for theoretical results concerning the complexity of algorithms in numerical analysis, scientific computing, and dynamical systems.

The real RAM computational model focuses on the complexity of the computational process while discounting the difficulties of representing real numbers. It extends the definitions of complexity classes such as P, NP and the notion of completeness for a complexity class. For example, the problem of solving the class of multivariate polynomial equations of degree 4 is shown to play the same role as satisfiability (sat) for the Turing Machine (TM) [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF] model: i.e., it is NP-complete.

Approximations

The approach taken by the Global Optimization (GO) community, specially those who develop sBB algorithms, consists in finding a (rational, or rather floating point encoded) solution x * yielding an objective function value f * = f (x * ) within a given ε > 0 of the true globally optimal function value f :

|f * -f | ≤ ε.
(2)

Note that, since the true optimal value f is not known, in practice Eq. ( 2) is enforced by requiring that |f * -f | ≤ ε, where f is a guaranteed lower bound to the optimal objective function value, usually computed by solving a convex relaxation [Liberti, 2009, §3.7] of Eq. ( 1).

The approach considered in [Hochbaum, 2005] is more accurate, as it insists that the solution x * is within a given ε > 0 tolerance of the true optimum x:

x * -x ∞ ≤ ε.
(3)

This means that x * is the same as x in O(log 1 ε ) decimal digits. Other than that, all arithmetical operations on reals take O(1) time. Since one only needs to consider O(log 1 ε ) decimal digits, this assumption places this representation approach within the TM model of computation.

Representability of algebraic numbers

Better representations, but limited to algebraic numbers, are based on their minimal polynomials. The most common is the Thom encoding, a pair (p α , σ), where p α (x) is the minimal polynomial of α (of degree d, say) and σ : {0, . . . , d} → {0, -1, 1} encodes the sign of the k-th derivative of p α at α [Basu et al., 2006, Prop. 2.28]. Simpler representations are possible for specific tasks, e.g. σ might be replaced by a rational number a which is closer to α than to any other real root of p α [START_REF] Beeker | Is the distance geometry problem in NP?[END_REF].

Identifying minimal polynomials can be achieved using Gröbner bases [Buchberger, 2006]. There are at least two papers [Hägglöf et al., 1995, Chang andWah, 1994] where Gröbner bases are used to diagonalize the polynomial Karush-Kuhn Tucker (KKT) system of a Polynomial Programming (PP) problem (though in those papers the last phase would perform back-substitution with floating point numbers -but those floating point numbers could in principle be used as "closest rationals" in the second representation mentioned in the above paragraph).

Gröbner bases can be found by Buchberger's algorithm [Buchberger, 2006]. It takes as input a rational multivariate polynomial equation system ∀i ≤ m p i (x) = 0.

(4)

It then proceeds by diagonalizing Eq. ( 4) to a new polynomial system ∀i ≤ m (q i (x) = 0) such that the leading terms of p i 's and q i 's (w.r.t. some given fixed monomial order) generate the same ideal.

Like Gaussian elimination, this diagonalization can be used for performing back-substitution as long as the equation q m (x) only depends on a single variable. Unlike Gaussian elimination, however, m generally exceeds m, and it does not yield a guarantee that q i will contain strictly fewer variables than q i+1 : the diagonal structure might contain blocks of polynomials depending on the same set of variables.

Buchberger's algorithm monotonically increases the size of the ideal generated by the leading terms of G. The algorithm terminates because, by Hilbert's basis theorem, ascending chains of ideals must eventually become stationary. The termination condition is verified even if the last considered polynomial is not univariate. Although the back-substitution process then generally fails (unless all polynomials are solvable after back-substitution), the diagonal form still holds. Unfortunately, Buchberger's algorithm has doubly exponential computational complexity in general, though it behaves singly exponentially in some cases [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]].

An interesting development of Gröbner's bases, involving chordal networks [START_REF] Cifuentes | Exploiting chordal structure in polynomial ideas: a Gröbner basis approach[END_REF], yields polynomial systems that are larger than Gröbner bases, but provide the same back-substitution functionality for finding a solution of a polynomial system of equations, and are cheaper to construct.

Decidability

Can we even solve MINLP? The short answer is no: we cannot solve them in full generality (see Sect. 3.2 below). But the full answer is rather more interesting: MINLP is a class of problems related to two different theories, one of which is decidable, while the other is not.

But first, what does decidability mean? This term is almost synonymous with computability: a function f : X → D is computable if there exists a TM that, for any input x ∈ X, provides f (x) as an output. The term "decidable" applies to relations instead of functions: a k-ary relation R on D k is decidable if, given d 1 , . . . , d k ∈ D, there exists a TM that decides whether the k-tuple d = (d 1 , . . . , d k ) is in R. Since "being in R" can be encoded as a YES/NO type of question, decidability applies to decision problems.

Polynomial feasibility in continuous variables

MINLP contains as a subset all Polynomial Feasibility Problems (PFP) where the variables range over the reals:

∀i ≤ m p i (x) R 0, (5)
where the p i 's are rational polynomials and the relation symbol R is one of {≥, =}. Note that Eq. ( 5) can in fact be expressed with a single relation R, either ≥ or =, since every equation can be expressed by a pair of inequalities with opposite sign, and every inequality p i (x) ≥ 0 can be rewritten as p i (x) + s 2 i = 0, where s i is an additional continuous variable. We consider the question whether there is an algorithm for deciding if an instance of Eq. ( 5) has a solution or not.

Quantifier elimination

Systems like Eq. ( 5) are decidable by [Tarski, 1951]. Most algorithms for deciding Eq. ( 5) are based on a technique known as quantifier elimination, which reformulates a quantified logical sentence with variable terms into one without quantifiers or free variables. Deciding truth or falsity can then be achieved by elementary manipulations leading to either a tautology 1 = 1 or a contradiction 0 = 1. Note that Tarski's algorithm can be applied to a larger class of polynomial systems than Eq. ( 5): the relation symbol R can actually range over {≥, >, =, =}.

Tarski's proof extends for 57 pages of a RAND Corporation technical report [Tarski, 1951]. To showcase an easier quantifier elimination example, we shall restrict our discussion to dense linear orders [Lyndon, 1966, p. 38]. This theory includes logical formulae involving ∀, ∃, ¬, ∧, ∨, the variable symbols x 1 , x 2 , . . ., the terms True, False, the real numbers as constants, and the relation symbols <, =. Sentences of this theory are inductively reduced to a standard form ∃x i s.t. q(x), where q has no quantifiers. Using the properties of linear order relations, each possible atomic formula involving s R t (where s, t are either variables or real constants, and R is a relation in {<, =}) is reduced to either True or False. The interesting "mixed" cases, where s is a variable and t is a constant (or vice versa) are reduced to intervals of the form r 1 < x i < r 2 where r 1 , r 2 are real constants, and henceforth to r 1 < r 2 , which evaluates to either True or False. Essentially, quantifier elimination reduces this theory to deciding whether an interval is empty or not. In the process, it eliminates variable symbols with the corresponding quantifier.

Cylindrical decomposition

Well after Tarski's 1948 quantifier elimination algorithm, it was discovered [Collins, 1974] that the decision procedure of systems such as Eq. ( 5) is in some sense a nontrivial extension of the dense linear order case. The solution set of Eq. ( 5) consists of finitely many connected components, which can be recursively built out of cylinders with bases shaped as points or intervals the extremities of which are either points, or ±∞, or algebraic curves depending on variables involved at previous recursion levels. Although Collins' algorithm is doubly exponential in the number of variables, a singly exponential algorithm was described in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF].

The cylindrical decomposition result of [Collins, 1974] consists of a topological and a geometric part. The topological part states that the feasible regions of Eq. ( 5) (where R ranges in {>, ≥, =, =}), also called semi-algebraic sets, can be decomposed into a finite number of connected components. The geometrical part gives the recursive description mentioned above in terms of cylinders. The topological part was known previous to Collins' contribution, see e.g. [Milnor, 1964].

Polynomial feasibility in integer variables

In this section, we shall consider Eq. ( 5) subject to integrality constraints on the vector x of decision variables (it suffices to consider equations only, since, as mentioned above, an inequality can be reduced to an equation by adding a single squared unrestricted slack variable):

∀i ≤ m p i (x) = 0 ∀j ≤ n x j ∈ Z, (6)
where we assume that that the p i 's are polynomials over Z. In other words: given a system Eq. ( 6) of polynomial equations in integers, can we decide whether it has a solution?

Undecidability versus incompleteness

We introduce the notion of a formal system S informally, as follows. S is a quadruplet (L, G, A, R) where L is a finite language, G is a grammar over L which defines a set of well-formed formulae called sentences, A is a set of given sentences called axioms, and R is a set of inference rules (e.g. modus ponens) which define relations over sentences. Given a sentence p, a proof for p in S is a sequence of iterative applications of inference rules to sentences that are either axioms or for which a proof was already provided.

Undecidability is sometimes related to Gödel's incompleteness theorem [Franzen, 2005]. Undecidability and incompleteness are, however, two different notions. A consistent formal system S is incomplete when it has at least a sentence p such that neither p nor ¬p are provable within S. Gödel's (first) incompleteness theorem states that any S capable of encoding arithmetic in N is either inconsistent or incomplete. This leaves open the question of decidability, i.e. of whether there exists an algorithm that, given any p in S, decides whether p is provable within S or not.

There is a common misconception that if a formal system S is decidable, then it cannot be incomplete. The (faulty) argument goes as follows. If a formal system S is decidable, then for any given sentence p it is possible to decide whether p is provable in S or not. So, in case p is provable, then ¬p cannot be, and vice versa. Hence, either p or ¬p must be provable within S, which implies that S cannot be incomplete.

The error arises in thinking that the "vice versa" above exhausts all possibilities. For two sentences p and ¬p in S, there are four assignments of the property "provability within S" to the two sentences: (i) both are provable, (ii) the first is provable and the second is not, (iii) the first is not and the second is, and (iv) neither is provable. The first assignment leads to the inconsistency of S: it should be discarded since we assumed that S is consistent. The second and third assignments are part of the above (faulty) argument. The error stems from forgetting the fourth assignment: i.e., that both p and ¬p may fail to be provable within S. This condition is described by saying that p is independent of S. If p is independent of S, a decision algorithm for provability in S would answer NO when given either p or ¬p as input. So a formal system can be decidable but incomplete. Let us see an example: the formal systems of algebraically closed fields of prime characteristic are both decidable and incomplete. Up to isomorphism, there is an algebraically closed field of prime characteristic for each distinct prime integer q. Given q, let us consider the formal system ACF q . Its axioms are: the field axioms, an axiom schema stating that every polynomial splits, and an axiom stating that the characteristic of the field is a finite prime q, namely C q ≡ i≤q 1 = 0 (the language, grammar and rules of inference are the ordinary ones from elementary mathematics). Because there exist algebraically closed fields of characteristic zero (e.g. C), it is clear that the finite characteristic axioms are independent of the rest of the axioms (otherwise, if there existed proofs of the finite characteristic axioms from the other field axioms, C could not have characteristic zero). And yet, the finite characteristic axioms are easy to recognize: a TM could scan a sentence and syntactically decide whether it is a finite characteristic axiom or not, for example using a regular expression. Therefore a decision algorithm for ACF q can be devised as follows. Given a sentence p:

(i) if p is a finite characteristic axiom for q return True (meaning: the sentence is an axiom of the FS so it is its own zero-line proof within the FS);

(ii) if p is a finite characteristic axiom for q = q return False (meaning: there is no proof for p within the FS);

(iii) if p is neither, use a quantifier elimination algorithm for finite fields (e.g. [START_REF] Gao | Quantifier elimination over finite fields using Gröbner bases[END_REF]) to determine whether the p is True or False.

So these formal systems are decidable but incomplete. Note that the decision algorithm operates within the FS, but the reason why it works has to be explained in the meta-language, outside of the FS.

As it turns out, if S encodes arithmetic in N and is consistent, it is not only incomplete (by Gödel's first incompleteness theorem) but also undecidable. This was settled by in [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF] by a diagonalization argument involving an undecidable decision problem called the Halting problem -is there an algorithm for deciding whether a given TM terminates or not?

Hilbert's 10 th problem

We now come back to our MINLP feasibility problem in Eq. ( 6). Each equation in the system is known as a Diophantine equation (DE). Let S be a formal system encoding arithmetic in N. Systems of DEs are certainly well-formed formulae within S. Although the set of all well-formed formulae in S is undecidable, we still do not know whether the limited subset described by the form of Eq. ( 6) is "general enough" to be undecidable. The common property of all feasibility systems is that the integer variables x 1 , . . . , x n are implicitly quantified by existential quantifiers "∃", but no universal quantifier "∀". Moreover, Eq. ( 6) only consists of sentences involving polynomials, whereas exponentiation is also part of arithmetic in integers. We can now frame the question as follows: is the set of all existentially quantified polynomial sentences of S decidable or not? This can be seen as a modern restatement of Hilbert's 10 th problem.

From the proof of Gödel's first incompleteness theorem [Gödel, 1930], it is clear that Gödel only used a finite number of bounded universal quantifiers in order to construct his argument. Davis, in [Davis, 1953], shows that a single bounded universal quantifier is sufficient to encode undecidable statements:

∃y∀z ≤ y∃x 1 , . . . , x n p(y, z, x) = 0, ( 7
)
where p is an integral polynomial, and x 1 , . . . , x n , y, z are all in N. In [START_REF] Davis | The decision problem for exponential Diophantine equations[END_REF], it is shown that there exist undecidable problems that are almost in the desired form:

∃x 1 , . . . , x n ∈ N η(x) = 0, (8)
but where η is an exponential DE (EDE), i.e. a function that can be written using arithmetical operations and exponentiation. In a landmark result, Matiyasevich proved in 1970 [Matiyasevich, 1970] that the exponential relationship a = b c can be expressed by means of a DE (i.e. without exponentiation), thereby settling Hilbert's 10 th problem in the negative. This result is now known as the Matiyasevich-Davis-Putnam-Robinson (MDPR) theorem. In the setting of this paper, the MDPR theorem means that

∃x 1 , . . . , x n ∈ N p(x) = 0, ( 9
)
where p is a polynomial, is generally undecidable. This makes Eq. ( 6) undecidable, which, by inclusion, makes MINLP undecidable, too.

The MDPR theorem is more general than it may seem at first sight.

(i) A system of DEs such as Eq. ( 6) is equivalent to a single DE such as Eq. ( 9): it suffices to write

p(x) = i≤m (p i (x)) 2 .
(ii) The undecidability results relate to N rather than Z, but this is without loss of generality: we can transform any DE with solutions in Z to one with solutions in N by writing

x i = y + i -y - i (where y + i , y - i ∈ N).
Conversely, since every non-negative integer is the sum of four squares, we can express the (non-negative integer) i-th component x i of the argument x of p(x) as

x i = a 2 i + b 2 i + c 2 i + d 2 i , where a i , b i , c i , d i are in Z.
(iii) The result also holds for polynomial DEs with coefficients over Q: it suffices to write rational coefficients as fractions, find the least common multiple L of the denominators, and consider Lp(x) instead of p(x).

Finally, it might seem strange to consider at a single polynomial equation such as Eq. ( 9), and claim that it is undecidable. To a theoretical computer scientist, it sounds like saying that a single instance of a problem is undecidable (this would be absurd: decidability applies to instance classes, not single instances). In fact, the variable vector x occurring as an argument of p(x) is partitioned in two (integer) subsequences α = (α 1 , . . . , α ) and y = (y 1 , . . . , y N ), so that α encodes the parameters of an "instance", and y the solution. The MDRP result in this setting follows because:

(a) every recursively enumerable set W can be encoded by a single polynomial equation p W (α, y) = 0 such that any string w is encoded in α, and w ∈ W iff p(α, y) = 0 has a solution in y (b) there exist recursively enumerable sets that are undecidable.

Recall that a subset of N is recursively enumerable if there exists an algorithm for listing all and only its elements (such sets are also called semi-decidable). We remark that a set W ⊆ N is decidable if both W and its complement W w.r.t. N are semi-decidable. To see this, it suffices to list elements of W alternately with elements of W : the algorithm will terminate in finite time and produce a YES or NO answer about membership of a given w in W .

Universality

As remarked in [Jones, 1982], recursively enumerable sets can be enumerated in some order W 1 , W 2 , . . . such that the relation w ∈ W v for some v is also recursively enumerable. This implies the existence of a DE U (w, v, y) = 0 (10) for some parameters w and v such that U (α, v, y) = 0 has an integer solution y iff w ∈ W v . Such polynomials U are known as universal Diophantine equations (UDE). This is equivalent to a universal TM (UTM), which takes as input an encoding of any TM T v and any instance w, and simulates T v (w).

In this setting, T v is a TM that is supposed to determine whether w ∈ W v .

UDEs present potential applications, as they allow the encoding of any computer program into a single polynomial. Studying its properties might help shed light on the program itself. Jones [Jones, 1982] conducted a thorough study of two complexity measures for UDEs: their degrees δ and the number ν of variables occuring in them.

The minimum known value for δ is 4, which yields ν = 58 [Jones, 1982]. It suffices to take any UDE, and repeatedly replace any degree 2 term by a new variable until we obtain a system of DEs ∀i ≤ m (t i (x) = 0) where each t i (x) consists of monomials of degrees 1 and 2. The equation

i≤m (t i (x)) 2 = 0 (11)
is therefore a UDE with degree δ = 4. In passing, we also conclude that, in general, systems of (many) quadratic DEs (QDE) are also undecidable. Decreasing ν unfortunately yields large increases on δ: a pair (δ, ν) = (1.638 × 10 45 , 9) was found by Matiyasevich [Jones, 1982].

The (4, 58) UDE, suitably modified to minimize the number B basic operations (additions and multiplications) required to evaluate the polynomial, yields B = 100 [Jones, 1982]. This implies that for any statement p which can be proved within the formal system S, p has a proof which only involves 100 integer additions and multiplications.

Coming back to MINLP, since UDEs are subsets of this class, it follows that MINLP inherits their properties. Thus, there exist universal MINLP formulations, though they may be hard to exploit in practice. The dynamics of a universal register machine have been modelled in [START_REF] Liberti | Mathematical programming: Turing completeness and applications to software analysis[END_REF] using an infinite MINLP which becomes finite, and practically solvable, on bounded executions (boundedness ensures termination of the underlying TM).

The cause of MINLP undecidability

Considering Sect. 3.1 and Sect. 3.2, we can ascribe the undecidability of MINLP to the presence of integer variables. This is apparently in contrast with the fact that any integer can be expressed within a theory encoding polynomials and just continuous variables: given any a ∈ Z, the equation x -a = 0 is polynomial and encodes the fact that the continuous variable x should take the integer value a. Taking this further, we can write x ∈ {a 1 , . . . , a k } for any integer values a 1 , . . . , a k using the polynomial equation

(x -a 1 ) • • • (x -a k ) = 0.
A different approach uses the length of the finite sum y + y + • • • + y (say it has occurrences of y) to express the integer using the polyomial equation xy = y. Aside from the zero solution, any other solution with y > 0 yields x = .

However, every finite set F is decidable, at least if its elements are all given explicitly: any total order on F provides an enumeration algorithm. Obviously, the complement F of F w.r.t. N is recursively enumerable: just list N and verify if the current element is in F or not.

To achieve undecidability, we have to look at infinite subsets of N. Is it possible to encode any such set as solutions over R of some (multivariate) polynomial equation? The answer is no: supposing there exists a real polynomial system with a countably infinite set of (integer) solutions would yield an infinite number of connected components in the corresponding variety, contrary to [Milnor, 1964]. Another way of proving this is that, if it were possible to encode N as the set of solutions of a real polynomial system in any (even nonstandard) way, then the theory of polynomials over R would be undecidable, contrary to Tarski's algorithm [Tarski, 1951]. It is common knowledge that, in order to encode all integers in a system of nonlinear equations with variables ranging over R n , one needs at least one periodic function, e.g. the set of solutions of sin(πx) = 0 is Z. If the polynomials range over C n , the exponential function (which is periodic over the complex numbers) is also a candidate.

These arguments suggest that a cause of undecidability is the issue of boundedness versus unboundedness of the decision variables. This is well known in polynomial optimization theory. Indeed, with unbounded variables, even the continuous relaxation of a MILP may need to be reformulated using nonlinear functions for practical usefulness [START_REF] Hijazi | Constraint qualification failure in action[END_REF].

Undecidability results in MP

Although the theories of polynomial equations over the reals and the natural numbers belongs de re to MINLP, since PFP is clearly a subclass of MINLP, the results above are traditionally a part of logic and axiomatic set theory. Here we focus on results which appeared in the MP literature.

As already mentioned above, [START_REF] Liberti | Mathematical programming: Turing completeness and applications to software analysis[END_REF] gives a practically useful proof of the universality of MINLP, and solves some specific instances of the universal MINLP. Moreover, it also proposes a MP formulation to solve an instantiation (in the interval domain) of an abstract interpretation of the execution of arbitrary programs [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction of approximations of fixed points[END_REF], in view of performing static analysis of computer code.

Quadratic integer programming

To the best of our knowledge, the earliest paper investigating MP and (un)decidability is Jeroslow's 1971 paper [Jeroslow, 1973] about the undecidability of quadratic integer programming. Consider the formulation min [Witzgall, 1963] solves Eq. ( 12) when each quadratic form x Q i x + a i x is parabolic, i.e. each Q i is diagonal with non-negative diagonal entries (for i ≤ m). In contrast, Jeroslow observed that this is a limiting case, since if the quadratic forms are diagonal but are allowed to have some negative entries, then they can encode an undecidable set, via the undecidability theory of DEs. The proof is as follows: given an undecidable DE p(x) = 0, we consider the following subclass of Eq. ( 12):

c x ∀i ≤ m x Q i x + a i x ≤ b i ∀j ≤ n x j ∈ Z,    (12) where c ∈ Q n , Q i are rational n × n matrices for each i ≤ m, A = (a i | i ≤ m) is a rational m × n matrix, and b ∈ Q m . Witzgall's algorithm
min x n+1 (1 -x n+1 )p(x) = 0 x n+1 ≥ 0 ∀j ≤ n x j ∈ Z.        (13)
Obviously, the minimum of Eq. ( 13) is 0 iff p(x) = 0 has a solution, and 1 otherwise. Now we follow the argument given above Eq. ( 11), and iteratively linearize products occurring in the k monomials of p(x) until p can be reformulated to a linear form y 1 + • • • + y k , subject to a set of defining constraints in the form y h = τ h (x, y), where each τ h only involves linear occurrences of variables, or their squares, or bilinear products of two variables. This is already undecidable, since finding the optimum of Eq. ( 13) would solve the undecidable DE p(x) = 0, but Jeroslow notes that one can write each bilinear product of decision variables uv (where u, v are decision variable symbols occurring in either x or y), by means of an additional variable w, as w = u + v while replacing uv by 1 2 (w 2 -u 2 -v 2 ). This yields the required form. Jeroslow also notes that whenever the integer variables are bounded, the problem becomes decidable (since there is only a finite number of possible solutions of p(x) = 0).

Polynomial minimization in integers

The paper [Zhu, 2006] focuses on undecidable problems in MINLP and global optimization, as detailed in this and the following subsections.

Consider min q(x) ∀j ≤ n x j ∈ Z, ( 14
)
where q is a polynomial. The proof given in [Zhu, 2006] that Eq. ( 14) is undecidable is as follows. Let p(x) = 0 be an undecidable DE. This can be written as (p(x)) 2 ≤ 0. Let ρ be the constant term in (p(x)) 2 and q(x) = (p(x)) 2 + ρ. Then we have q(x) ≤ ρ. We have reduced the DE to the problem of deciding whether there exists an integral solution to the problem q(x) ≤ ρ. Since this is a special case of the decision problem corresponding to Eq. ( 14), as the proof in [Zhu, 2006] argues, the result follows.

It appears that this proof lacks a key step. If we want to argue that Eq. ( 14) is undecidable iff its decision version q(x) ≤ ρ is, then we have to set ρ = q * , the globally optimal value of Eq. ( 14) (invoking bisection as an equivalence between decision and optimization problems is generally invalid in the current setting, since bisection calls for bounded variables, whereas undecidability requires the variables to be unbounded). Unfortunately, the proof already fixes the value of ρ to the constant term in (p(x)) 2 , which turns out to be the square of the constant term in p(x). Undecidable DEs are often constructed explicitly as UDEs, for which a common technique is the careful modelling of some UTM equivalent computational framework. If we tamper with the constant term, the modelling may become invalid. This proof could be fixed by exhibiting a specific undecidable DE for which the constant term just happens to be the optimal objective function value of min x q(x), but this task looks hard to achieve. Unfortunately, all the other results in the paper use this "equivalence" between decision and optimization.

Fortunately, however, the result is true, and has a very simple proof. We define q(x) = (p(x)) 2 so that min x q(x) = 0 iff p(x) = 0, since q is a square and its minimum value must be ≥ 0. If we could compute the minimum of q(x), we could decide on the solvability of p(x) = 0 according to whether min x q(x) = 0 or > 0. But this is impossible since p(x) = 0 is undecidable.

Systems of nonlinear equations

The paper [Zhu, 2006] shows that:

∀i ≤ m g i (x) = 0, (15)
where g i : R n → R are nonlinear functions, is undecidable. If p(x) = 0 is an undecidable DE, then

(p(x)) 2 + j≤n (sin(πx j )) 2 = 0, (16)
where x ranges in R n , is precisely a restatement of the DE, and so it is undecidable. Note that Eq. ( 16) is obviously a subclass of Eq. (15).

Unconstrained continuous global optimization

Consider: min

x q(x), (17)
for some nonlinear function q(x). It is shown in [Zhu, 2006] that Eq. ( 17) is undecidable, as follows. Let p(x) = 0 be an undecidable DE. Let q(x) = (p(x)) 2 + j≤n (sin(πx j )) 2 , and suppose q * = min x q(x) is computable. Then if q * = 0 we have p(x) = 0 and x j ∈ Z for all j ≤ n, otherwise we do not, which is equivalent to the decidability of p(x) = 0, against assumption.

Box-constrained continuous global optimization

Consider min

x L ≤x≤x U q(x), (18)
for some nonlinear function q(x) and some variable bound vectors x L , x U . It is shown in [Zhu, 2006] that Eq. ( 18) is undecidable. Let p(y) = 0 be an undecidable DE. Let

q(x) = (p(tan x 1 , . . . , tan x n )) 2 + j≤n (sin(π tan x j )) 2 ,
then we can enforce -π 2 ≤ x j ≤ π 2 for all j ≤ n, i.e. x L = -π 2 and x U = π 2 without changing the values of q(x). The argument runs as above: if we could compute the minimum q * of q(x) over x L ≤ x ≤ x U , we could establish whether p(y) = 0 has a solution or not, which is impossible.

Summary

The MINLP class was shown to contain undecidable formulations: by reduction from UDEs [Jeroslow, 1973], by inclusion of UDEs as pure integer polyonomial feasibility problems, and by modelling the dynamics of a UTM [START_REF] Liberti | Mathematical programming: Turing completeness and applications to software analysis[END_REF]. By [Zhu, 2006] there also exist undecidable non-polynomial NLPs in continuous variables. On the other hand, Tarski's algorithm establishes that semi-algebraic systems of polynomials in continuous variables are decidable.

Complexity

In this section, we look at the computational complexity of some MINLP problems. We shall mostly focus on nonconvex NLPs, since the presence of integer variables, even bounded to {0, 1}, makes it very easy to prove MINLP hardness, as shown in Sect. 4.2.

Tutorial

We briefly recap some basic notions about computational complexity. This section can be skipped by readers who are already familiar with this material.

Turing Machines

The computational model we use in this section is the TM model, an abstract computational process invented by Turing [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF]. It consists of an infinitely long tape divided into cells. Each cell can be read, written on, or ignored by a head operating on the tape, which can store the last read character. An engine can shift the tape one cell forward or backward. Each cell contains a character from a finite alphabet L decided a priori. |L| must be at least two, but most usually L consists of at least three symbols: 0, 1 and a space used to separate words. A TM obeys a set of instructions such as "move left", "move right", "read", "write", and "stop", as well as a mechanism for recognizing states, which provide the equivalent of "if" and "go to". Sequences of instructions are known as programs.

Polytime and exponential problems

Many TM variants have been proposed in the first years of research on theoretical computer science: larger alphabets, half-infinite or multiple tapes to name a few. For most of these variants, simulation proofs were quickly devised to show that none of them was more powerful than the "basic" TM. Driven by the need for faster computation, the issue of computational complexity became more pressing: given an algorithm and some input data, how many steps would a TM need to perform before termination (the issue of whether the TM would actually stop or not was discussed in Sect. 3)? Given that the same algorithm is routinely run on different inputs, the paradigm of worst-case complexity was brought to the attention. Infinite sets of input data of the same type and increasing size, together with a specification of the goal the algorithm is supposed to achieve, were grouped in classes named problems (conversely, each member of a given problem is an instance). If the task consists in answering a YES/NO question, the problem is a decision problem.

Given any problem P , if there exists an algorithm taking a number of steps bounded by a polynomial function the instance size n in the worst case, we denote its complexity by O(n d ), where d is the degree of the polynomial, and call the algorithm polynomial-time (or simply polytime). If we are only able to establish an exponential bound, we denote it by O(2 n ), and call the algorithm exponential-time.

The class P

The focus of computational complexity rapidly shifted from algorithms to problems. Given a decision problem P , the main issue of computational complexity is: what is the worst-case complexity of the best algorithm for solving P ? Edmonds [Edmonds, 1965] and Cobham [Cobham, 1965] remarked around 1965 that problems having a polytime complexity are invariant w.r.t. changes in the TM definitions concerning alphabet size (as long as it contains at least 3 characters), number of tapes, and more. This is the reason why today we partition decision problems into two broad categories called "tractable" and "intractable". The tractable problems are those having polytime complexity. The class of such problems is called P.

The class NP

Concerning those decision problems for which no-one was able to find a polytime algorithm, it was remarked that a somewhat "magic" TM, one that is able to pursue every test branch in parallel (this is called nondeterministic TM), gives another useful partition on the class of all decision problems. Those for which there exists a nondeterministic TM that runs in polytime are all grouped in a class called NP. It is not difficult to show that an equivalent definition of NP is: all problems for which YES instances come with a (deterministically) polytime checkable certificate. Given an instance of a problem in NP, a nondeterministic TM will explore all test branches in parallel. Since this TM runs in polytime by definition of NP, each branching sequence must have size bounded by a polynomial. If the instance is YES, take the branching sequence which yields the YES: this is a deterministically polytime checkable certificate. Conversely, let P be a problem the instances of which all have polytime checkable YES certificates. Then a nondeterministic TM will explore all polynomially-sized test branches in parallel, and find the YES certificate in polytime if it exists. If it does not exist, the work will still be carried out in polytime, since each polynomially-sized test branch is checked in polytime, and the TM runs in parallel over all such test branches. clique, for example, belongs to NP: given a graph G and an integer k, does G have a clique of size at least k? If the instance is YES, then it has a clique of size at least k, and this clique can be supplied as certificate to a verification algorithm which is able to establish in polytime whether the certificate is valid.

While it is easy to show that P ⊆ NP, no-one was ever able to establish whether P is different or equal to NP (this is the famous P vs. NP question).

Reductions

The class NP is very useful because, in absence of a complement of P allowing us to tell problems apart into "easy" and "hard", it provides a good proxy.

Given two problems P and Q in NP, suppose we know a polytime algorithm A to solve P but we know of no such algorithm for Q. If we can find a polynomial algorithm R which transforms a YES instance of Q into a YES instance of P and, conversely, a NO instance of Q into a NO instance of P , then we can compose R and A to obtain a polytime algorithm for Q. An algorithm R mapping Q → P while keeping instance membership in YES and NO classes invariant is called a polynomial reduction from Q to P .

Technically, this reduction is more precisely known as a Karp reduction. A Cook reduction occurs from Q to P if Q can be solved by a polynomial number of standard operations and calls to an oracle that solves P . A Karp reduction is like a Cook reduction allowing for a single oracle call. Karp reductions allow for a distinction between hard problems where polynomial certificates are available for YES instances and for NO ones -in other words, it allows for the definition of the class co-NP.

The hardest problem in the class

This gives an interesting way to define the "hardest problem in NP". Let P be a problem in NP such that any problem in NP polynomially reduces to P . Pick any Q ∈ NP: can Q be harder to solve than P ? Since there is a polynomial reduction R : Q → P , if we know how to solve P then we know how to solve Q, so there is no real additional difficulty in solving Q other than knowing how to solve P . In this sense, P is hardest in the class NP. The set of such problems are said to be NP-complete. Since this notion of hardness only depends on polynomial reduction rather than membership in NP, we also define as NP-hard those problems which are as hard as any problem in NP without necessarily being members of NP. Thus, NP-complete problems are a subset of NP-hard problems.

The landmark result [Cook, 1971] proves that the class of NP-complete problems is non-empty, since it contains sat. The sat problem involves a decision about the truth or falsity of sentences defined over variable symbols, the ¬ unary operator, the ∧ and ∨ binary operators, and the constants 0 and 1 (traditionally, in sat notation, one writes x instead of ¬x). A sentence is YES if there is an assignment of 0 and 1 to the variables that evaluates to YES, and NO otherwise. The evaluation uses the common meaning of the boolean operators ¬, ∧, ∨. Cook's result is based on the idea that sat can be used as a declarative language to model the dynamics of any polytime TM, which can be described by a sequence of 0-1 vectors, each component of which represents the value of a different sat variable for each time step. Since the definition of NP involves a polytime-checkable certificate, sat can be used to model the polytime TM used to verify the certificate. The sat instance modelling the given TM has finite length because we know that the number of steps of the TM is bounded by a polynomial in the input length.

The reduction digraph

After Cook's result, sat became known as the "primitive problem" in the theory of NP-hardness. While the first proof of NP-hardness was difficult to devise (since it necessarily has to encode every TM, following the definition), the following proofs are of an altogether different nature, as they can rely on the mechanism of reduction. Suppose we know that P is an NP-hard problem, and we want to establish the NP-hardness of Q. Can Q be any easier than P ? Suppose we find a polynomial reduction R : P → Q: if Q could be solved by an algorithm A that is asymptotically faster than that of P , then we could compose R with A to derive a better algorithm for P , which is impossible since P was defined to be hardest for NP. This idea is used in [Karp, 1972] to prove that many common problems are NP-complete. Since then, it has become commonplace in most publications in theoretical computer science that, when presenting a new problem, there should be a proof that either it is in P or it is NP-hard. Interestingly, some well-known problems (such as graph isomorphism or SDP feasibility [Liberti and Lavor, pear]) are not (yet) known to be either in P or NP-hard.

Note that polytime reductions define an asymmetric relation on the class NP, i.e. two problems P, Q in NP are related if there is a reduction R : P → Q. This turns NP in an (infinite) directed graph, called the reduction digraph, where the problems are represented by nodes, and reductions by arcs. This graph is strongly connected by virtue of Cook's result, which proves that there is a reduction from any problem in NP to sat.

Decision vs. optimization

A problem P is NP-complete if it is NP-hard and belongs to NP. Most theoretical results in computational complexity concern decision problems, but in practice we also need to solve function evaluation and optimization problems. Transforming evaluation and optimization into decision rpoblems does not usually change their computational difficulty.

The "decision version" of the MINLP in Eq. ( 1) adds a threshold value φ to the input and asks whether the system

f (x) ≤ φ g(x) ∈ [g L , g U ] x ∈ [x L , x U ] ∀j ∈ Z x j ∈ Z        (19)
is feasible. The class of optimization problems which can be reduced to their decision version Eq. ( 19) is called NPO (the "O" stands for "optimization"). It has the following properties: (i) the feasibility of any solution can be established in polytime; (ii) every feasible solution has polynomially bounded size; (iii) the objective function and constraints can be evaluated in polytime at any fasible solution.

When the input is numeric

For problems involving arrays of rational numbers in the input data, such as vectors or matrices, more notions are used to distinguish complexity in function of the numerical value of the input versus the number of bits of memory required to store it.

An algorithm is pseudopolynomial if it is polynomial in the value of the numbers in the input, but not in their size. E.g., testing whether a number n is prime by trying to divide it by 2, . . . , √ n takes √ n divisions, but if we take the classic TM computational model, the divisions involved take exponential time in the size of the input, which is log 2 (n) .

In the arithmetic computational model, where elementary operations on numbers take unit time, an algorithm is strongly polytime if its worst-case running time is bounded above by a polynomial in function of the length of the input arrays, and the worst-case amount of memory required to run it (a.k.a. the worst-case space) is bounded by a polynomial in the number of bits required to store their values, a.k.a. the size of the input (e.g. Dijkstra's shortest-path algorithm on weighted graphs is strongly polytime). On the other hand, if the running time also depends on the actual input size, including the bits required to represent the numbers in the arrays, the algorithm is weakly polytime (e.g. the ellipsoid method for LP is weakly polytime: whether there exists a strongly polytime algorithm for LP is a major open question).

A problem P is strongly NP-hard if there is a strongly polytime reduction algorithm R from every problem in NP to P , or, equivalently, from a single NP hard problem to P . P is strongly NP-complete if it is strongly NP-hard and also belongs to the class NP. An equivalent definition of strong NP-hardness is the class of those NP-hard problems that remain NP-hard even if the input is encoded in unary, i.e. when the value of all of their numerical data is bounded by a polynomial in the input size.

A problem P is weakly NP-hard when it is NP-hard but there exists a pseudopolynomial algorithm that solves it (e.g. often dynamic programming based algorithms search the set of values which a given variable can take, so that the number of iterations might remain polynomial in the value rather than the number of bits required to store it).

When proving NP-hardness for a new problem P , using reductions from a strongly NP-hard problem gives more flexibility, as one can use a pseudopolynomial reduction and still claim NP-hardness of P . This technique was used in [START_REF] Brandes | On modularity clustering[END_REF].

Lastly, a word of caution about these notions. An algorithm is either strongly or weakly polytime, in the sense that the two definitions are complementary. In the case of problems, strong and weak NP-hardness are not complementary in the same sense, as the weak version rests on pseudopolynomial reduction algorithms rather than weakly polytime ones.

Complexity of solving general MINLP

MINLP is not in NP because it is not a decision problem. It is NP-hard because it includes MILP as a subclass. MILP is NP-hard by means of a trivial reduction from sat. Transform the sat instance to conjunctive normal form (CNF), write x as 1 -x, ∨ as + and let ∧ mark the separation between constraints, which are all set to be ≥ 1. This yields a set of MILP constraints that are feasible if and only if the sat instance is YES. We denote these constraints by "sat → MILP" for future reference. This argument, however, only brushes the surface of the issue, as it is essentially an argument about MILP. We know by Sect. 3 that nonlinearity makes unbounded MINLP undecidable, whereas finite bounds make it decidable. But what about the continuous variables? We know that PP without integer variables is decidable, but is it NP-hard? The answer is yes, and it follows from the fact that polynomials can express a bounded number of integer variables (see the beginning of Sect. 3.4). All that the sat → MILP reduction above needs is a sufficient number of binary (boolean) variables, which can be defined by requiring a continuous variable x to satisfy the polynomial x(1 -x) = 0.

In the rest of this section, we shall survey the field of computational complexity of several different MINLP problems, with a particular attention to NLPs involving continuous variables.

Quadratic programming

The general Quadratic Programming (QP) problem is as follows:

min 1 2 x Qx + c x Ax ≥ b. ( 20
)

NP-hardness

QP was shown in [Sahni, 1974] to contain an NP-hard subclass of instances (and hence QP itself is NP-hard by inclusion). The reduction is from an NP-complete problem called subset-sum: given a list s of non-negative integers s 1 , . . . , s n and an integer σ, is there an index set J ⊆ {1, . . . , n} such that j∈J s j = σ? Consider the QP formulation:

max f (x) = j≤n x j (x j -1) + j≤n s j x j j≤n s j x j ≤ σ ∀j ≤ n 0 ≤ x j ≤ 1.        (21)
This defines a transformation from an instance of subset-sum to one of QP. Obviously, it can be carried out in polytime. We now prove that it maps YES instances of subset-sum to QP instances where f (x) < σ and NO instances to instances of QP where f (x) = σ.

Assume (s, σ) is a YES instance of subset-sum with solution J. Then setting x j = 1 for all j ∈ J satisfies all constraints of Eq. ( 21): in particular, the constraint is satisfied at equality. Solution integrality mkes the first sum in the objective function yield value zero, which yields f (x) = σ. Conversely, assume (s, σ) is a NO instance, and suppose first that Eq. ( 21) has an integer solution: then the constraint must yield j s j x j < σ; solution integrality again zeroes the first sum in the objective function, so f (x) < σ. Next, if Eq. ( 21) has no integer solution, there is at least one j ≤ n such that 0 < x j < 1, which makes the objective function term x j (x j -1) negative, yielding again f (x) < σ, as claimed.

The paper [Sahni, 1974] also contains another proof that shows that a NLP with just one nonlinear constraint of the form j x j (x j -1) ≥ 0 is also NP-hard.

Strong NP-hardness

A different proof, reducing from sat, was given in [Vavasis, 1991, Thm. 2.5]. It shows that the following QP subclass is NP-hard:

min f (x) = j≤n x j (1 -x j ) sat → MILP ∀j ≤ n 0 ≤ x j ≤ 1,      (22)
where sat → MILP indicates the MILP constraints encoding a sat instances which were discussed at the beginning of Sect. 4.2. The proof shows that the given sat instance is YES iff f (x) = 0. Assume first that the sat instance is YES: then there is an assignment of boolean values to the sat variables that satisfies the sat → MILP constraints. Moreover, since the solution is integral, we get f (x) = 0. Conversely, assume the sat instance is NO, and suppose, to aim at a contradiction, that a solution x * to Eq. ( 22) exists, and is such that f (x * ) = 0. Since the quadratic form j x j (1 -x j ) is zero iff each x j ∈ {0, 1}, we must conclude that x * is integral. Since the sat → MILP constraints are feasible iff the sat instance is YES, and x * satisfies those constraints, it follows that the sat instance is YES, against assumption. Hence, if the sat instance is NO, either Eq. ( 22) is infeasible or f (x * ) > 0.

These two arguments prove the same fact, i.e. that QP is NP-hard. However, the first reduction is from subset-sum, while the second is from sat. This has some consequences, since while sat is strongly NP-hard, subset-sum is not: namely, the first reduction only proves the weak NP-hardness of QP, leaving the possibility of a pseudopolynomial algorithm open. The second reduction rules out this possibility.

NP-completeness

While QP cannot be in NP since it is not a decision problem, the decision problem corresponding to QP is a candidate. The question is whether the following decision problem is in NP:

1 2 x Qx + c x ≤ φ Ax ≥ b, (23)
where φ is a threshold value that is part of the input.

As shown in [Vavasis, 1991], Eq. ( 23) turns out to be in NP. The proof is long and technical, and consists of many intermediate results that are very important by themselves.

1. If the QP of Eq. ( 20) is convex, i.e. Q is positive semidefinite (PSD), and has a global optimum, then it has a globally optimal solution vector where all the components are rational numbers -this was shown in [START_REF] Renegar | Unified complexity analysis for Newton LP methods[END_REF]. The main idea of the proof is as follows: only consider the active constraints in Ax ≥ b, then consider the KKT conditions, which consist of linear equations in x, and derive a global optimum of the convex QP as a solution of a set of linear equations.

2. Again by [START_REF] Renegar | Unified complexity analysis for Newton LP methods[END_REF], there is a polytime algorithm for solving convex QPs (cQP): in other words, cQP is in P. This is a landmark result by itself -we note that the algorithm is an interior point method (IPM) and that it is weakly polytime. Specifically, though, this result proves that the size of the rational solution is bounded by a polynomial in the input size. By [Vavasis, 1991, p. 77], this is enough to prove the existence of a polynomially sized certificate in case Eq. ( 23) is bounded.

3. The unbounded case is settled in [Vavasis, 1990].

This allows us to conclude that the decision version of QP is NP-complete.

Box constraints

A QP is box-constrained if the constraints Ax ≥ b in Eq. (20) consist of variable bounds x L ≤ x ≤ x U .
The hyper-rectangle defined by [x L , x U ] is also known as a "box". As for the NP-hardness proof of QP, there are two reductions from NP-complete problems to box-constrained QP: one from subset-sum [Murty and Kabadi, 1987, Eq. (3)] and one from sat [Vavasis, 1991, §4.2]. Since reductions from sat imply strong NP-hardness, we only focus on the latter.

We actually reduce from 3sat in CNF, consisting of a conjunction of m clauses each of which is a disjunction of exactly 3 literals. As before, we write the i-th literal as

x i or 1-x i if negated. A disjunction x i ∨ xj ∨ x k , for example, is written as a linear constraint x h + (1 -x j ) + x k ≥ 1, yielding ∀i ≤ m a i x ≥ b i (24)
for appropriate vectors a i ∈ Z m and b ∈ Z. By adding a slack variable v ∈ [0, 2] to each of the m clauses, Eq. ( 24) becomes ∀i ≤ m (a i x = b i + v i ). Next, we formulate the following box-constrained QP:

min f (x, v) = j≤n x j (1 -x j ) + i≤m (a i x -b i -v i ) 2 x ∈ [0, 1] n , v ∈ [0, 2] m . (25)
We are going to show that the 3sat instance is YES iff the globally optimal objective function value of Eq. ( 25) is zero.

Obviously, if the 3sat formula is satisfiable, there exists a feasible solution (x * , v * ) where x * ∈ {0, 1} n and v * ∈ {0, 1, 2} m that yields a zero objective function value. Conversely, suppose there exists (x * , v * ) such that f (x * , v * ) = 0, which yields

a i x * = b i + v * i ( 26
)
for all i ≤ m. Supposing some of the x variables take a fractional value, the corresponding term x * j (1-x * j ) would be nonzero, against the assumption f (x * , v * ) = 0. From integrality of the x variables, Eq. ( 26) ensures that v * i is integer, for all i ≤ m. Since integrality and feasibility w.r.t. Eq. ( 26) are equivalent to Eq. ( 24) and therefore encode the clauses of the 3sat instance, x * is a YES certificate for the 3sat instance. Thus, finding the global optimum of the box-constrained QP in Eq. ( 25) is NP-hard.

Trust region subproblems

Trust Region Subproblems (TRS) take their name from the well-known trust region method for black-box optimization. TRSs are essentially instances of QP modified by adding a single (convex) norm constraint x ≤ r, where r (which is part of the input) is the radius of the trust region. If the norm is 2 and Ax ≥ b has a special structure, then the problem can be solved in polytime [START_REF] Bienstock | Polynomial solvability of variants of the trust-region subproblem[END_REF]. In this case the solution is generally irrational (due to the nonlinear norm constraint -note that because of that constraint, the TRS is not formally a subclass of QP in general), though for the simple case of x 2 ≤ 1 and no linear constraints, the technical report [START_REF] Vavasis | Proving polynomial-time for sphereconstrained quadratic programming[END_REF] states that the decision problem is actually in P.

Most TRSs arising in practical black-box optimization problems, however, are formulated with an ∞ norm constraint. This makes the resulting QP easier to solve numerically, to a given ε > 0 approximation tolerance, using local NLP solvers. This is because the ∞ norm yields simple box constraints on the decision variables, and therefore the ∞ TRS does belong to the class QP, specifically it is a box-constrained QP. From a worst-case computational complexity point of view, however, we recall that box-constrained QPs form an NP-hard subclass of QP, as mentioned above.

Continuous Quadratic Knapsack

The reduction is from subset-sum. Consider the following formulation, called continuous Quadratic Knapsack Problem (cQKP):

min x Qx + c x j≤n a j x j = γ x ∈ [0, 1] n ,      (27)
where Q is a square diagonal matrix, a, c ∈ Q n , and γ ∈ Q.

We encode a subset-sum instance ({s 1 , . . . , s n }), σ) in Eq. ( 27) as follows [Vavasis, 1991, §4.2]:

min f (x) = j≤n x j (1 -x j ) j≤n s j x j = σ x ∈ [0, 1] n ,        (28)
We are going to show that the instance is YES iff the global optimum of Eq. ( 28) is zero. If the instance is YES, then there is a subset J ⊂ {1, . . . , n} such that j∈J s j = σ. Let x * j = 1 for all j ∈ J and x * j = 0 for all j ∈ J: then x * is feasible in the constraints of Eq. ( 27), and yields f (x * ) = 0. Conversely, if x * is a feasible solution of Eq. ( 27) yielding f (x * ) = 0, then each term x * j (1 -x * j ) in f (x) has value zero, which implies x * ∈ {0, 1} n . Now let J = {j ≤ n | x * j = 1} be the support of x * . By construction, J is a YES certificate for the subset-sum instance. Thus finding a global optimum of a cQKP is NP-hard.

Convex QKP

Since a convex QKP is a subclass of convex QP, it can be solved in polytime -but no strongly polytime algorithm is known. On the other hand, if Q is a diagonal matrix, then the objective function of Eq. ( 27) is separable. As remarked in [Vavasis, 1991, §3.1] there is an O(n log n) algorithm for solving this specific variant of convex QKP [START_REF] Helgason | A polynomially bounded algorithm for a singly constrained quadratic program[END_REF].

The Motzkin-Straus formulation

In 1965, Motzkin and Straus established an interesting relationship between the maximum clique C in a graph G = (V, E) and the following QP [START_REF] Motzkin | Maxima for graphs and a new proof of a theorem of Turán[END_REF]:

max f (x) = {i,j}∈E x i x j j∈V x j = 1 ∀j ∈ V x j ≥ 0 ;        (29)
namely, that there exists a global optimum x * of Eq. ( 29) such that

f * = f (x * ) = 1 2 1 - 1 ω(G)
,

where ω(G) is the size of a maximum cardinality clique in G. In other words, this gives the following formula for computing the clique number of a graph:

ω(G) = 1 1 -2f * .
Moreover, a maximum clique is encoded in a global optimum x * of Eq. ( 29), which has the form

∀j ∈ V x * j = 1 ω(G) if j ∈ C 0 otherwise.
Eq. ( 29) is called the Motzkin-Straus formulation for the max clique optimization problem. Its decision version clique is well known to be NP-complete, which makes the Motzkin-Straus formulation an appropriate candidate for reductions from clique to various problems related to QP and NLP.

We follow the proof given in [Aigner, 1995]. Let x * be a global optimum of Eq. ( 29) with as many components at zero as possible. Consider C = {j ∈ V | x * j > 0}. We claim that C is a maximum clique in G.

• First, we claim C is a clique. Suppose this is false to aim at a contradiction, and assume without loss of generality that 1, 2 ∈ C and {1, 2} ∈ E. For some in the interval [-x * 1 , x * 2 ], let x = (x * 1 + , x * 2 -, x * 3 , . . . , x * n ). Note that x satisfies the simplex constraint j x j = 1, as well as the non-negativity constraints. Since the edge {1, 2} is not in E, the product x 1 x 2 does not appear in the objective function f (x). This means that 2 never occurs in f (x ). In particular, f (x) is linear in . We temporarily look at f as a function of , parametrized by x * . By the choice of x * (a global optimum), f ( ) achieves its maximum at = 0. Since = 0 is in the interior of its range [-x * 1 , x * 2 ], f ( ) is constant over this range. Hence setting = -x * 1 and = x * 2 yields global optima with a smaller number of nonzero components x * , which is a contradiction as x * was chosen with the maximum number of zero components as possible. Thus C is a clique.

• Now, we claim C has maximum cardinality |C| = ω(G). Consider the simplex constraint j x j = 1 and square both sides:

1 =   j∈V x j   2 = 2 i<j∈V x i x j + j∈V x 2 j . (30)
Since by construction of C we have x * j = 0 iff j ∈ C, the above reduces to

ψ(x * ) = 2 i<j∈C x * i x * j + j∈C (x * j ) 2 .
Moreover, ψ(x) = 1 for all feasible x by Eq. ( 30). So the objective function f (x) = i,j x i x j achieves its is maximum when the second term of ψ(x) is minimum, i.e. when j∈C (x * j ) attains its minimum, which occurs at x * j = 1 |C| . Again by the simplex constraint, we have

f (x * ) = 1 - j∈C (x * j ) 2 = 1 -|C| 1 |C| 2 = 1 - 1 |C| ≤ 1 - 1 ω(G) ,
with equality when |C| = ω(G), as claimed.

By reduction from clique, it follows therefore that Eq. ( 29) describes an NP-hard subclass of QP. Using the same basic ideas, Vavasis gives a proof by induction on |V | in [Vavasis, 1991, Lemma 4.1].

An extension of this work shows that there exists a bijection between the local optima of Eq. ( 29) and the maximal cliques of G [Bomze, 1997].

4.3.9 QP on a simplex "QP on a simplex", refers to the following formulation:

min x Qx + c x j≤n x j = 1 ∀j ≤ n x j ≥ 0,      (31)
where Q is a square n × n rational matrix and c ∈ Q n . Since Eq. ( 29) describes a subclass of Eq. ( 31), the latter is NP-hard by inclusion.

QP with one negative eigenvalue

So far, we established that convex QPs are in P, and that a variety of nonconvex QPs are NP-hard (with their decision version being NP-complete). Where does efficiency end and hardness begin? In an attempt to provide an answer to this question, Pardalos and Vavasis proved in [START_REF] Pardalos | Quadratic Programming with one negative eigenvalue is NP-hard[END_REF]] that an objective function min x Qx where Q has rank one and has a single negative eigenvalue suffices to make the problem NP-hard. The problem of solving a QP with one negative eigenvalue is denoted by QP1NE.

The construction is very ingenious. It reduces clique to QP1NE in two stages. First, it provides a QP formulation having zero globally optimal objective function value attained iff the main decision variable vector x takes optimal values in {0, 1}. Second, it encodes a clique of given cardinality k in a given graph G = (V, E) by means of the following constraints:

∀{i, j} ∈ E x i + x j ≤ 1 (32) j∈V x j = k (33) 0 ≤ x ≤ 1. ( 34
)
The rest of the formulation, which essentially ensures integrality of the decision variables, is as follows:

min z -w 2 (35) w = j∈V 4 j x j (36) z = j∈V 4 2j x j + 2 i<j 4 i+j y ij (37) ∀i < j ∈ V y ij ≥ max(0, x i + x j -1). ( 38
)
Eq. ( 35) clearly is of rank one and has a single nonzero eigenvalue which is negative. Note that the definitions of w 2 (by means of Eq. ( 36)) and z in Eq. ( 37) almost match: we should have y ij = x i x j for them to be equal. Eqs. ( 34), ( 38) and (37) ensure that z cannot be negative, which also holds for w 2 since it is a square. A couple of technical lemmata ensure that the QP in Eqs. ( 35)-( 38) has optimal value zero iff the optimal solution is binary. Integrating the constraints Eqs. ( 32)-( 34) encodes clique in this QP so that G has a clique of cardinality k iff the optimal objective function value is zero, as claimed.

Bilinear programming

The Bilinear Programming Problem (BPP) reads as follows: min j≤n x j y j Ax + By ≥ b.

(39)

The NP-hardness of BPP has been established in [START_REF] Bennett | Bilinear separation of two sets in n-space[END_REF], by a reduction from a problem in computational geometry called 2-Linear Separability (2LS), consisting in determining whether two sets of points in a Euclidean space can be separated by a piecewise linear curve consisting of two pieces. In turn, 2LS was proven NP-complete in [Megiddo, 1988].

Bennett and Mangasarian show in [START_REF] Bennett | Bilinear separation of two sets in n-space[END_REF] that the 2LS reduces to one of three possible BPP formulations, all of which with general inequality constraints and non-negativity constraints on the decision variables.

An open question by Vavasis, settled by Matsui

In [Vavasis, 1995, p. 37], Vavasis proposes as an open question whether the following QP:

min f (x) = (c x + γ)(d x + δ) Ax ≥ b (40)
is NP-hard. Note that that although Eq. ( 40) is a subclass of QP, which is itself an NP-hard problem, there is the possibility that this might be a tractable case. Eq. ( 40), however, was shown to be NP-hard in [Matsui, 1996].

The proof is constructed very ingeniously by borrowing the functional form min x 1 -x 2 2 from QP1NE. First, a reduction of the (NP-complete) set partition problem to the formulation min

n i=1 n j=1 p i+j y ij - n i=1 p i x i 2 Sx = 1 ∀i = j ≤ n y ij ≤ x i ∀i = j ≤ n y ij ≤ x j ∀i = j ≤ n y ij ≥ x i + x j -1 ∀i ≤ n y ii = x i x ∈ [0, 1] n y ∈ [0, 1] n 2 ,                              ( 41
)
where p is any positive integer and Sx = 1 is a set of constraints modelling set partition. This is achieved by showing that the objective function is positive if and only if there are fractional feasible solutions x with 0 < x i < 1 for some i ≤ n. The crucial point of the proof is that the linearization constraints x i + x j + 1 ≤ y ij ≤ min(x i , x j ) and y ii = x i are exact only for x ∈ {0, 1}. A technical (but easy to follow) argument shows that the objective function is positive at the optimum if and only if some fractional solution exists.

This proof is then extended to the generalization of Eq. ( 41) where the objective function is replaced by a general function g(x 0 , y 0 ) where x 0 = i p i x i , y 0 = i,j p i+j y ij and two more conditions on x 0 , y 0 designed to endow g with positivity/negativity properties similar to that of the objective function of Eq. ( 41). This new problem also has non-positive objective function value at the optimum if and only if the optimum is binary. This provides the reduction mechanism from set partition (encoded in the constraints Sx = 1).

Finally, the function g(x 0 , y 0 ) = (y 0 -p + 2p 4n ) 2 -4p 4n x 2 0 -4p 8n is shown to satisfy the requirements on g and also to factor as a product of two linear forms plus a constant, which provides the necessary form shown in Eq. ( 40).

The same proof mechanism can also prove NP-hardness of the related problems

min {x 1 x 2 | Ax ≥ b} (42) min x 1 - 1 x 2 | Ax ≥ b (43) min 1 x 1 - 1 x 2 | Ax ≥ b . (44)

Establishing local minimality

The problem of deciding whether a given x is a local minimum of a QP or not has attracted quite a lot of attention in the late 1980s and early 1990s. There are at least three distinct proofs of this fact in the literature: in [Murty and Kabadi, 1987, Problem 1], in [Pardalos and Schnitger, 1988, §3], and in [Vavasis, 1991, §5.1]. The first [START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF] reduces subset-sum to the problem of deciding whether a quadratic form over a translated simplex is negative, shown to be equivalent to unboundedness of a constrained quadratic form, and to the problem of deciding whether a given point is not a local optimum of a given QP. Moreover, [START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF]] also shows that deciding copositivity of a given matrix is co-NP-hard; it further proves co-NP-hardness of verifying that a point is not a local optimum in unconstrained minimization (of a polynomial of degree 4). The second [START_REF] Pardalos | Checking local optimality in constrained quadratic programming is NP-hard[END_REF] presents a QP where a certain point is not a local minimum iff a given 3sat instance is YES. The third [Vavasis, 1991] is based on an unconstrained variant of the Motzkin-Straus formulation, where the zero vector is a local minimum iff a given clique instance is NO.

These proofs all show that it is as hard to prove that a given point is not a local minimum of a QP as to show that a given NP-hard problem instance is YES. Implicitly, using the reduction transformation, this provides certificates for the NO instances of the QP local minimality problem (QPLOC) rather than for the YES instances. In computational complexity, this shows that QPLOC is co-NP-hard (see Sect. 4.1.5) rather than NP-hard.

Currently, no-one knows whether NP = co-NP. Suppose we could prove that NP = co-NP ( †). We know that P = co-P (the whole polynomially long trace of the algorithm provides a polynomially long certificate of both YES and NO instances). If P = NP then it would follow from P = co-P that NP = co-NP, a contradiction with ( †), which would prove P = NP, the most famous open question in computer science and one of the most famous in mathematics.

It is interesting that many NP-hard problems have QP formulations, which proves that solving QPs is NP-hard. However, verifying whether a given point is a local optimum is co-NP-hard. Looking in more depth, most of the NP-hardness reductions about QP actually reduce to deciding whether a given QP has optimal objective function value equal to zero or not. On the other hand, the co-NP-hardness reductions in [START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF], Pardalos and Schnitger, 1988, Vavasis, 1991] all establish local optimality of a given solution vector. The former setting (testing the optimal objective function value) sometimes allows for clear dichotomies: for example, for the box-constrained QP in [Murty and Kabadi, 1987, Eq. (8)], it is shown that there is a finite gap between the optimal value being zero or less than a finite negative value (this implies that the corresponding decision problem is actually in NP). In practice, a sufficiently close approximation to zero can be rounded to zero exactly, which means that a certificate for "equal to zero" can be exhibited. Moreover, a YES instance of a problem might have multiple certificates, each of which is mapped (through the reduction) to a different solution of the corresponding QP having the same objective function value. The latter setting (testing local optimality) is about a specific point. Since QP involves continuous functions of continuously varying variables, it is harder to find cases where gap separations are possible. Encoding a YES instance (possibly with multiple certificates) in the verification of optimality of a single point, moreover, intuitively seems to be a harder task.

General Nonlinear Programming

The general NLP formulation is like Eq. ( 1) where Z = ∅. It obviously contains QP, so NLP is NP-hard in general. Murty and Kabadi's proof of co-NP-hardness of verifying whether a given point is a local minimum (see previous section) uses the following formulation min u (u 2 ) Qu 2 , where u 2 denotes the vector (u 2 1 , . . . , u 2 n ). This is a minimization of a quartic polynomial, and so it is not, strictly speaking, quadratic (although it is readily seen to be equivalent to the quadratic problem min x≥0

x Qx).

In Sect. 3.5 we discussed undecidable NLP problems, so the hardness issue is somewhat moot. It is worth mentioning two hardness results in NLP: deciding whether a given function is convex, and optimization over the copositive cone. These two problems are related by the notion of convexity -which, according to Rockafellar, is the real barrier between easy and difficult optimization problems. Given any function, can we efficiently decide whether it is convex? If so, then we may hope to optimize it efficiently using a special-purpose algorithm for convex functions. Rockafellar's belief was doubly shattered by relatively recent results. On the one hand, the NP-hardness of deciding convexity of polynomials of 4th degree was proved in [START_REF] Ahmadi | NP-hardness of deciding convexity of quartic polynomials and related problems[END_REF]. On the other hand, many NP-hard problems were shown to have natural copositive formulations [Dür, 2010]: copositive programs are convex NLPs where one of the constraints involves a description of the copositive cone.

Verifying convexity

The paper [START_REF] Pardalos | Open questions in complexity theory for numerical optimization[END_REF] presents a list of open questions in the field of computational complexity in numerical optimization problems. Problem 6, due to Shor, reads as follows.

Given a degree-4 polynomial of n variables, what is the complexity of determining whether this polynomial describes a convex function [in their whole range]? Polynomials of degree smaller than 4 are easy to settle: degree-1 are linear and hence convex, degree-2 have constant Hessian which can be computed in polynomial time, and odd-degree polynomials are never convex (although they may be pseudo-or quasi-convex, see [Lasserre, 2015, Thm. 13.11]). Degree-4, the smallest open question, was settled in [START_REF] Ahmadi | NP-hardness of deciding convexity of quartic polynomials and related problems[END_REF].

The proof provided in [START_REF] Ahmadi | NP-hardness of deciding convexity of quartic polynomials and related problems[END_REF] reduces from the problem of determining whether a given biquadratic form i≤j k≤ α ijk x i x j y k y is non-negative over all its range is strongly NP-hard by reduction from clique [START_REF] Ling | Biquadratic optimization over unit spheres and semidefinite programming relaxations[END_REF] by way of the Motzkin-Straus formulation Eq. ( 29). It shows how to construct a (variable) Hessian form from any biquadratic form such that the former is non-negative iff the latter is. This Hessian form allows the construction of a quartic polynomial that is convex over its range iff the original biquadratic form is non-negative.

This result is extended also to deciding other forms of convexity: strict and strong convexity, as well as pseudo-and quasi-convexity.

The copositive cone

First, a square symmetric matrix A is copositive if x Ax ≥ 0 for all x ≥ 0. If we removed the nonnegativity condition x ≥ 0, we would retrieve a definition of A being PSD: while every PSD matrix is copositive, the converse is not true. Establishing copositivity of non-PSD matrices is NP-hard, as it involves verifying whether the optimal objective function value of the QP P ≡ min{x Ax | x ≥ 0} is ≥ 0, or either < 0 or unbounded [START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF].

We consider a variant of Eq. ( 31) where c is the zero vector (so the objective function is purely quadratic). This variant is called Standard Quadratic Programming (StQP). It is NP-hard by inclusion of Eq. ( 29). The reformulation of the (NP-hard) StQP to a convex continuous NLP, reported here below, is a surprising result.

(a) We linearize each product x i x j occurring in the quadratic form x Qx to a new variable X ij . This yields min Q • X j≤n

x j = 1 ∀j ≤ n x j ≥ 0 X = xx ,         
where • denotes trace(Q X). Note that X = xx encodes the whole constraint set ∀i < j ≤ n X ij = x i x j .

(b) We square both sides of the simplex constraint j x j = 1 to obtain i,j x i x j = 1, which can be written as 1 • X = 1, where 1 is the all-one n × n matrix.

(c) We replace the (nonconvex) set C = {X | X = xx ∧ x ≥ 0} by its convex hull C = conv(C). This yields min Q

• X 1 • X = 1 X ∈ C.    (45)
The set C is a convex combination of rank-one matrices, and as such forms a convex cone.

(d) We write the dual of Eq. ( 45):

max y Q -y1 ∈ C * , ( 46
)
where C * is the dual cone of C. Unlike the PSD cone, which is self-dual, C * = C. In fact, C * turns out to be the cone of all copositive matrices:

C * = {A | ∀x ≥ 0 (x Ax ≥ 0)},
see [Hall, 1986, Thm. 16.2.1] for a detailed proof. Both cones are convex and achieve strong duality. Again, Eq. ( 46) is a convex NLP.

Convex NLPs are known to be "easy to solve", since every local optimum is also global: thus a local solution algorithm should immediately find the global optimum (this proabably motivated Rockafellar to put the barrier of complexity in MP at the frontier of convexity and nonconvexity). Accordingly, Eq. ( 46) is surprising and unexpected. One might object that convex hulls naturally turn hard problem classes into tractable ones. For example, convex hulls of integer programs allows us to write MILP as LP; in general, however, the resulting LP involves an exponentially long description, thereby yielding an LP which is polytime solvable in its own (exponential) description size, and thus takes exponential time to be solved in function of the description size of the original MILP. Our own practical experience with most convex NLPs suggests that any reasonable local NLP solver would find their global optima efficiently. In view of Eq. ( 46), the consequences would be formidable: are there efficient algorithms for NP-hard problems?

According to [Bomze, 2012, Dür, 2010], no-one knows of an efficient algorithm for solving the convex NLP in Eq. ( 46), exactly because of the copositive cone C * . The most common convex NLPs are defined over the non-negative orthant (or translations and/or scalings thereof). This cone has a very simple and compact description: ∀j ≤ n (x j ≥ 0). The PSD cone {A | A 0} also has a compact description: it consists of all the square symmetric matrices with non-negative eigenvalues. Since we can test whether a given matrix is PSD in polytime [Schrijver, 2003[Schrijver, , p. 1152]], the polynomially long traces of the checking algorithm provide compact certificates for both YES and NO instances: this is the next best thing to an explicit formulation. Testing copositivity, however, is NP-hard, so there is little hope of achieving such compact descriptions for the copositive cone C * .

A different way to see this issue is to consider that convex NLPs over matrix cones are routinely solved by IPMs, the polytime analysis of which rest on the existence of some functions called "self-concordant barriers", which deviate the search path for the optimum away from the border of the cone. Barrier functions are used as penalty functions to be added to the objective function, which tend to infinity towards the boundary of the cone. Self-concordant barriers can be optimized efficiently using Newton's method. It seems that we know self-concordant barriers for many convex cones (orthants, PSD and more), but not for C * . In [START_REF] Bomze | On copositive programming and standard quadratic optimization problems[END_REF], an IPM-based heuristic is proposed to solve copositive programs such as [START_REF] Bomze | On copositive programming and standard quadratic optimization problems[END_REF]].

Yet another interpretation of the complexity inherent in the copositive cone is the classiication of extremal matrices of copositive cones of small dimension, pursued in [Hildebrand, 2012]. This paper emphasizes that the description complexity of these extreme rays increases dramatically as the dimension increases.

Conclusion

We reviewed some MINLP results from the point of view of computability and complexity. We introduced the basic notions of decidability and computational complexity, and then applied them to problems modelled naturally as MINLP or some of its subclasses. While this is by no means a complete survey, we mentioned where to find additional information. We hope this paper will help clarify doubts -but also raise questions and draw attention to some of the theoretical issues related to MINLP. anecdotes strewn all around the place, and the whole paper written in the first singular personal pronoun. Apparently, the unwritten standards of scientific writing, which I know and abide by, but thought could be a matter of personal choice in an invited survey, are in fact vigorously enforced (trust me). This paper has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement n. 764759 (ITN "MINOA").

  real RAM model . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Representability of algebraic numbers . . . . . . . . . . . . . . feasibility in continuous variables . . . . . . . . . . . . 5 3.1.1 Quantifier elimination . . . . . . . . . . . . . . . . . . . . . 5 3.1.2 Cylindrical decomposition . . . . . . . . . . . . . . . . . . 6 3.2 Polynomial feasibility in integer variables . . . . . . . . . . . . . . 6 3.2.1 Undecidability versus incompleteness . . . . . . . . . . . . 6 3.2.2 Hilbert's 10 th problem . . . . . . . . . . . . . . . . . . . . 7 3.3 Universality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 The cause of MINLP undecidability . . . . . . . . . . . . . . . . . 9 3.5 Undecidability results in MP . . . . . . . . . . . . . . . . . . . . . 10 3.5.1 Quadratic integer programming . . . . . . . . . . . . . . . 10 3.5.2 Polynomial minimization in integers . . . . . . . . . . . . . 11 3.5.3 Systems of nonlinear equations . . . . . . . . . . . . . . . . 11 3.5.4 Unconstrained continuous global optimization . . . . . . . 11 3.5.5 Box-constrained continuous global optimization . . . . . . . 12 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.1.1 Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . 12 4.1.2 Polytime and exponential problems . . . . . . . . . . . . . 12 4.1.3 The class P . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1.4 The class NP . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1.5 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.1.6 The hardest problem in the class . . . . . . . . . . . . . . . 14 4.1.7 The reduction digraph . . . . . . . . . . . . . . . . . . . . 14 4.1.8 Decision vs. optimization . . . . . . . . . . . . . . . . . . . 15 4.1.9 When the input is numeric . . . . . . . . . . . . . . . . . . 15 4.2 Complexity of solving general MINLP . . . . . . . . . . . . . . . . 16 4.3 Quadratic programming . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3.1 NP-hardness . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3.2 Strong NP-hardness . . . . . . . . . . . . . . . . . . . . . 17 4.3.3 NP-completeness . . . . . . . . . . . . . . . . . . . . . . . 17 4.3.4 Box constraints . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3.5 Trust region subproblems . . . . . . . . . . . . . . . . . . . 18 4.3.6 Continuous Quadratic Knapsack . . . . . . . . . . . . . . . 19 4.3.7 Convex QKP . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3.8 The Motzkin-Straus formulation . . . . . . . . . . . . . . . 20 4.3.9 QP on a simplex . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3.10 QP with one negative eigenvalue . . . . . . . . . . . . . . . 21 4.3.11 Bilinear programming . . . . . . . . . . . . . . . . . . . . . 22 4.3.12 An open question by Vavasis, settled by Matsui . . . . . . . 22 4.3.13 Establishing local minimality . . . . . . . . . . . . . . . . . 23 4.4 General Nonlinear Programming . . . . . . . . . . . . . . . . . . . 24 4.4.1 Verifying convexity . . . . . . . . . . . . . . . . . . . . . . 24 4.4.2 The copositive cone . . . . . . . . . . . . . . . . . . . . . . 25

Conclusion

Acknowledgments

I am grateful to the scientific committee of the Aussois Combinatorial Optimization Workshop (C.O.W.) 2017 for inviting me to give the opening tutorial talk (which forced me to study computability and complexity through the Christmas break 2016), as well as to R. Mahjoub for having invited this survey to be published on RAIRO-RO. I am grateful to F. Raimondi and F. Roda for a twenty-year long (and counting) discussion on incompleteness and undecidability, and to S. Iwata for bringing the paper [Matsui, 1996] to my attention. I am also grateful to two referees for helping me improve the style and presentation of the material: without them, you would have found odd personal comments and