Some NP-complete Problems in Quadratic and Nonlinear Programming Katta G. Murty* Dept. of Industrial and Operations Engineering The University of Michigan 1205 Beal Avenue Ann Arbor, MI 48109-2117, USA Santosh N. Kabadi Faculty of Administration University of New Brunswick Fredericton, NB, Canada E3B 5A6 Technical Report 85-23 June 1985 *Research Partially supported by NSF Grant No. ECS-8401081

ABSTRACT: The motivation for this study is to analyze the complexity of the problems of checking whether a given feasible solution is not a local minimum, and that of checking whether the objective function is not bounded below on the set of feasible solutions, in continuous variable, smooth, nonconvex nonlinear programming problems. We construct a very special instance called the simplest nonconvex NLP in this class (this is an indefinite quadratic programming problem with very simple objective and very simple constraints) with integer data and show that checking either of the above problems on this instance is an NP-complete problem. As a corollary we obtain the result that the problem of checking whether a given integer square matrix is not copositive, is NP-complete. KEYWORDS: Convex or nonconvex nonlinear programming problems, local minimum, global minimum, unboundedness of the objective function, computational complexity, NP-completeness, indefinite quadratic programming, copositive matrices, positive semidefinite matrices. ABBREVIATED TITLE: NP complete QPs.

INTRODUCTION Consider the smooth nonlinear program (NLP) minimize O(x) (1) subject to gi(x) > 0, i = 1 to m where each of the functions is a real valued function defined on Rn, with high degrees of differentiability. Here x = (xl,...xn)T E Rn This NLP is said to be a convex NLP if O(x) is convex and gi(x) are concave for all i, nonconvex NLP, otherwise. Without any loss of generality, we assume that the NLP is always stated in minimization form. For a convex NLP, under some constraint qualifications, necessary and sufficient optimality conditions are known. See [1, 3, 5]. Given a feasible solution satisfying the constraint qualification, it is possible to check very efficiently, using these optimality conditions, whether that point is a (global) optimum solution of the problem or not. For nonconvex NLPs, under constraint qualifications, some necessary conditions for a local minimum are known, and there are some sufficient conditions for a point to be a local minimum. See [1, 3, 5]. But there are no simple conditions known, which are both necessary and sufficient for a given point to be a local minimum. The complexity of checking whether a given feasible solution is a local minimum in a nonconvex NLP is not usually addressed in the literature. When they discuss algorithms, many text books in NLP leave the reader with the impression that these algorithms converge to a global minimum in convex NLPs, and to a local minimum in nonconvex NLPs. The documentations for many professional software packages for NLP also create the same impression. This impression could be quite erroneous. In this paper, we study this problem by examining the computational complexity of determining whether a given feasible solution is not a local minimum, and that of determining 1

whether the objective function is not bounded below on the set of feasible solutions, in smooth continuous variable nonconvex NLPs. For this purpose, we analyze an indefinite quadratic program (QP) with integer data, which may be considered as the simplest nonconvex NLP. It turns out that the questions of determining whether a given feasible solution is not a local minimum in this problem, and to check whether the objective function is not bounded below in this problem, can both be studied using the discrete techniques of computational complexity theory, and in fact these questions are NP-complete. This clearly shows that in general, it is a hard problem to check whether a given feasible solution in a nonconvex NLP is a local minimum or not, or to check whether the objective function is bounded below or not on its set of feasible solutions. This indicates the following: when a nonlinear programming algorithm is applied on a nonconvex NLP, unless it is proved that it converges to a point satisfying some known sufficient condition for a local minimum, claims that it leads to a local minimum are hard to verify in the worst case. Also, in continuous variable smooth nonconvex minimization, even the down-to-earth goal of guaranteeing that a local minimum will be obtained by an algorithm (as opposed to the lofty goal of finding the global minimum) may be hard to attain. We make some more comments on this issue at the end of the paper. FINDING A GLOBAL MINIMUM IN A SMOOTH NONCONVEX NLP IS A HARD PROBLEM The problem of computing a global minimum, or checking whether a given feasible solution is a global minimum, for a smooth nonconvex NLP, may be hard problems in general. We provide two examples. EXAMPLE 1: FERMAT'S LAST CONJECTURE: Some of the hardest unsolved problems in mathematics can be posed as problems of finding a global minimum in a smooth nonconvex NLP. Consider the Fermat's last conjecture, unresolved since 1637 A.D. It states that there exists no positive integer solution (x, y, z) to the equation 2

n n n x +y z when n is an integer 2 3 (here, x, y, z E R ). Eventhough this conjecture has been shown to be true for several individual values of n, in general, it remains open. Obviously, Fermat's last conjecture is true iff the global minimum objective value in the following NLP is > 0, where a is a positive penalty parameter, and H is the length of the circumference of the circle of diameter 1 in R2 minimize (xn + yn zn)2 + a (1 Cos(21Tx))2 + (1 -Cos(211)2 + (1 Cos(2z1) 2 + (1 - Cos(211n))2) subject to x, y, z > 1, n 2 3. EXAMPLE 2: SUBSET-SUM PROBLEM: To establish mathematically that the problem of computing a global minimum in a nonconvex NLP is a hard problem, we consider the subset-sum problem, a hard problem in discrete optimization, which is known to be NP-complete (see [2]): given positive integers do; dl,..., dn; is there a solution to n Zd.Yj = do j=1 JJ 0 d (2) y- = 0 or 1 for all j Now consider the following quadratic programming problem n - 2 n minimize ( djy-d)2 + E yj(1-yj) j=1JyJ J Sj J J (3) subject to 0 _ yj < 1, j = 1 to n. Because of the second term in the objective function, (3) is a nonconvex quadratic programming problem. Clearly (2) has a feasible solution iff the global minimum objective value in (3) is zero. Since the problem of checking whether (2) has a feasible solution is NP-complete, computing the global minimum in (3), a very special and simple case of a smooth nonconvex NLP, is an NP-hard problem. This shows that in general, the problem of computing a global minimum in a smooth nonconvex NLP may be a hard problem. 3

CAN WE AT LEAST COMPUTE A LOCAL MINIMUM FOR A SMOOTH NONCONVEX NLP, EFFICIENTLY? Since the problem of computing a global minimum in a nonconvex NLP is a hard problem, we will now study the question of whether it is at least possible to compute a local minimum, or check whether a given feasible solution for such a problem is not a local minimum, by efficient algorithms. We review the known optimality conditions for a given feasible solution x to (1) to be a local minimum. Let A = {i: gi(x) = 0}. Optimality conditions are derived under the assumption that some constraint qualifications (CQ, see [1, 3, 5]) are satisfied at x, which we assume. FIRST ORDER NECESSARY CONDITIONS FOR x TO BE A LOCAL MINIMUM FOR (1) There must exist a.A = (pi: i e A) such that VO(x) - Z PiVgi(x) = 0 isA (4) i > 0, for all i c A Here VO(x), Vgi(x) are the gradient vectors (row vectors) of these functions evaluated at x. Given the feasible solution x, it is possible to check whether (4) holds, efficiently, using Phase I of the simplex method for linear programming. SECOND ORDER NECESSARY CONDITIONS FOR x TO BE A LOCAL MINIMUM FOR (1) These conditions include (4). Given pA satisfying (4) together with x, let L(x, PA) = 0(x) iA 1igi(x). In addition to (4) these conditions require A icA 1_ yTHy. 0, for all y E {y: Vgi(x)y = 0 for each i E A} (5) where H is the Hessian matrix of L(x, PA) with respect to x at x = x. Condition (5) requires the solution of a quadratic program involving only equality constraints, which can be solved efficiently. It is equivalent to checking the positive semidefiniteness of a matrix which can be carried out efficiently using Gaussian pivot steps (see [51). 4

SUFFICIENT CONDITIONS FOR x TO BE A LOCAL MINIMUM FOR (1) Given the feasible solution x, and pA which together satisfy (4), the most general known sufficient optimality condition states that if yTHy > 0 for all y e T (1 where T1 = {y: y 4 0 and Vgi(x)y = 0 for each i e {i: i e A and Pi > 0}, and Vgi(x)y > 0 for each i e {i: i E A and ui = 0}}. Unfortunately, when H is not positive semidefinite, the problem of checking whether (6) holds leads to a nonconvex QP, which, as we will see later, may be hard to solve. Aside from the question of the difficulty of checking whether (6) holds, wE can verify that the gap between conditions (5) and (6) is very wide, particularly when the set {i: i c A and Ii = 0} + 0. In this case, condition (5) may hold, and even if we are able to check (6), if it is not satisfied, we are unable to determine whether x is a local minimum for (1) with present theory. Now we will use a simple indefinite QP, related to the problem of checking whether the sufficient optimality condition (6) holds, to study the following questions. 6) e i) Given a smooth nonconvex NLP and a feasible solution for it, can we check whether it is a local minimum or not efficiently? ii) At least in the simple case when the constraints are linear, can we check efficiently whether the objective function is bounded below or not on the set of feasible solutions? Let D be an integer square symmetric matrix of order n. D is said to be positive semidefinite (PSD) if xTDx > 0 for all x c Rn. So checking whether D is not PSD involves the question "is there an x e Rn satisfying xTDx < O". It is well known that this question can be settled by performing at most n Gaussian pivot steps along the main diagonal of D, requiring a computational effort of at most O(n3). (For example, see [5 or 6]). 5

The matrix D is said to be copositive if xTDx > 0 for all x > 0. All PSD matrices are copositive, but a matrix which is not PSD may be copositive. Testing whether the given matrix D is not copositive involves the question "is there an x > 0 satisfying xTDx < 0". If D is not PSD, no efficient algorithm for this question is known (some enumerative methods are available for this problem, see [5], but the computational effort required by these methods grows exponentially with n in the worst case). In fact we show later that this question is NP-complete. To study this question, we are naturally led to the NLP minimize Q(x) = xTDx ( subject to x > 0 We will show that this problem is an NP-hard problem. We assume that D is not PSD. So Q(x) is nonconvex and (7) is a nonconvex NLP. It can be considered the simplest nonconvex NLP. We consider the following decision problems. Problem 1: Is x = 0 not a local minimum for (7)? Problem 2: Is Q(x) not bounded below on the set 7) of feasible solutions of (7)? Clearly, the answer to problem 2 is in the affirmative iff the answer to problem 1 is. We will show that both these problems are NP-complete. To study problem 1, we can replace (7) by the NLP minimize Q(x) = xTDx subject to 0 < xj < 1, j = 1 to n = 3= (8) LEMMA 1: The decision problem "is there an x feasible to (8) which satisfies Q(x) < O", is in the class NP. PROOF: Given an x feasible to (8), to check whether Q(x) < 0, can be done by computing Q(x) which takes O(n2) time. Also, if the answer to the problem is in the affirmative, an optimum solution x of (8) satisfies Q(x) < O. There is a 6

linear complementarity problem (LCP) corresponding to (8) and an optimum solution for (8) must correspond to a basic feasible solution (BFS) for this LCP. Since there are only a finite number of BFSs for an LCP, and they are all rational vectors, a nondeterministic algorithm can find one of them satisfying Q(x) < O, if it exists, in polynomial time. Hence, this problem is in the class NP. LEMMA 2: The optimum objective value in (8) is either 0 or < -2L where L is the size of D. PROOF: Since the set of feasible solutions of (8) is a compact set and Q(x) is continuous, (8) has an optimum solution. By well known results, the necessary optimality conditions for (8) lead to the following linear complementarity problem (LCP), see [5 or 6]. \u /D ' I x 0. -....... =... (9) v -I: o o e ct, > of 419 > 0(10) (... ( ) =0 (11) v / v/y where y is the column vector of Lagrange multipliers associated with the constraints "xj < 1 for all j", and u, v are the column vectors in Rn of dual and primal slack variables. For every optimum solution x of (8), there exist vectors u, v, y such that (u, v, x, y) solves (9), (10) and (11). Also, it can be verified that whenever (u, v, x, y) satisfies (9), (10) and (11), xTDx = -eTy, a linear function, where e is the column vector of all l's in Rn. So, there exists an optimum solution of (8) which is a basic feasible solution (BFS) of (9), (10). By the results under the ellipsoid algorithm (see, for example [4, 5]), in every BFS of (9), (10), each yj is either 0 or > 2-L. If the optimum 7

objective value in (8) is not zero, it must be < 0, and this together with the above facts implies that an optimum solution x of (8) corresponds to a BFS (u, v, x, y) of (9), (10) in which -eTy < 0. All these facts clearly imply that the optimum objective value in (8) is either 0 or < -2L. We now make a list of several decision problems, some of which we have already seen, and some new ones which we need for establishing our results. Problem 3: Is there an x 2 0 satisfying Q(x) < O? Problem 4: For any positive integer ao, is there an x E Rn satisfying eTx = ao, x > 0 and Q(x) < O? Now consider a subset sum problem with data do; d1,.., dn, which are all positive integers. Let Y be a positive integer > 4(d (. ld))2n3. Let 9 be the size of this subset sum problem, that is, the total number of digits in all the 2 data for the problem. Let c be a positive rational number < 2nL2 The subset sum problem is: Problem 5: Subset sum problem: Is there a y = (yj) e Rn n satisfying jZ djyj = do, 0 i yj < 1, j 1 to n, and y integer vector. We now define several functions involving nonnegative variables y = (Y1,..., T and s = (si,... sn), related to the subset sum problem. n n n fl(y, s) = (j d. y d )2 Y ( (y. +j 1)2 + y -1 Jysj 1) + Y (y +ssj j=1 i j' "/j- 1 j-1 J n 2 n n 2 -1 ( j=1 0 -1 J 0 - J= n n ~2do( E djyj) -2Y~j (yj + sj) + nY + do j=1 jJ S j=1 (y J f2(y, s) = f (y, s) + 2do (. dyj(1 - yj)) n 2 n =(j1djyj) + Yj ( yj + s )+ yj s =j 1 J j =1 8

n 2 n n f3(Y' s) d- + Y (jyj) + S + ~ y -. s f4(y, s) = ( yj)2 + Y (yj + s )2 + ySj d2d y + (yj + S. f5(Y, s) = (jy, ) (Y + 2 j nJ1 Zj=1 3 j =1 j additional decision problems Problem 6: Is there a (y, s) e P satisfying fl(y, s) < O? Problem 7: Is there a (y, s) e P satisfying f2(Y, s) < O? n 2 Problem 8: Is there a (y, s) e P satisfying f4(y, s) 0O? Problem 9: Is there a (y, s) P s atisfying f(y, s) < O? THEOREM 1: Problem 4 is an NP-hard problem. PROOF: Since f1(y, s) is a sum of nonnegative terms whenever (y, s) e P, if (y, s) e P satisfies fi(y, s) < 0, then we must have f1(y, s) = 0, this clearly n implies from the definition of f{(y, s), that the following conditions must j1 djyj = do, yjsj = 0 and yj + s; = 1, for all j = 1 to n These conditions clearly imply that y is a solution of the subset sum problem and that the answer to problem 5 is in the affirmative. Conversely if y = (j) is a solution to the subset sum problem, define S = (Sj) where Sj = 1 - yj for each j = 1 to n, and it can be verified that f1(y, s) = 0. This verifies that problems 5 and 6 are equivalent. Whenever is a 0-1 vector, we have yj = for all j, and this implies that f1(y, s) = f2(y, s) for any s. So, from the above arguments, we see that if (y, s) ~ P satisfies f (Y, s) _ 0, then f1 (y, s) = f2(y, s) = 0. If 0 I yj 1, 9

we have 2dodjyj(1 - yj) > O. If (y, s) e P, and, yj > 1, then -(y + sj + 2dodjyj(1 - yj) > O, since Y is large (from the definition of Y). Using this and the definitions of f1(y, s), f2(y, s), it can be verified that for (y, s) E P, if f2(y, s) < 0 then f1(y, s) <0 too. These facts imply that problems 6 and 7 are equivalent. Clearly, problems 7 and 8 are equivalent. From the definition of e (since it is sufficiently small) and using Lemma 2, one can verify that problems 8 and 9 are equivalent. Problem 9 is a special case of problem 4. Since problem 5 is NP-complete, from the above chain of arguments we conclude that problem 4 is NP-hard. THEOREM 2: Problem 4 is NP-complete. PROOF: The answer to problem 4 is in the affirmative iff the answer to the decision problem in the statement of Lemma 1 is in the affirmative. So, from Lemma 1 we conclude that problem 4 is in NP. From Theorem 1, this shows that problem 4 is NP^complete. THEOREM 3: Problem 3 is NP-complete. PROOF: Problems 3 and 4 are clearly equivalent, this result follows from Theorem 2. THEOREM 4: Both problems 1 and 2 are NP-complete. PROOF: Problems 1 and 2 are both equivalent to problem 3, so this result follows from Theorem 3. U THEOREM 5: Given an integer square matrix D, the decision problem "is D not copositive?" is NP-complete. PROOF: The decision problem "is D not copositive?" is equivalent to problem 1, hence this result follows from Theorem 4. 10

CAN WE CHECK LOCAL MINIMALITY EFFICIENTLY IN UNCONSTRAINED MINIMIZATION PROBLEMS? Let O(x) be a real valued smooth function defined on Rn. Consider the unconstrained problem minimize O(x). (12) A necessary condition for a given point x e Rn to be a local minimum for (12) is VO(x) = 0, H(O(x)) is PSD (13) where H(O(x)) is the Hessian matrix (the matrix of second order partial derivatives) of O(x) at x. A sufficient condition for x to be a local minimum for (12) is VO(x) = 0, H(O(x)) is positive definite (14) Both conditions (13) and (14) can be checked very efficiently. If (13) is satisfied, but (14) is violated, there are no simple conditions known to check whether or not x is a local minimum for (12). Here, we investigate the complexity of checking whether or not a given point x is a local minimum for (12), and that of checking whether 0(x) is bounded below or not over Rn. As before, let D = (dij) be an integer square symmetric matrix of order n. Consider the unconstrained problem, minimize h(u) = (u..., u)D(u,..., u (15) Clearly, (15) is an instance of the general unconstrained minimization problem (12). Consider the following decision problems. Problem 10: Is u = 0 not a local minimum for (15)? Problem 11: Is h(u) not bounded below on Rn? 11

We have, for i, j = 1 to n h(u) = 4uj ((u,..., unD.j auj a2h(u)..... = 8uiujdi j, i t j aUi3Uj 2h( 2 h() = 4(u u2)D.. + 8ud. au2 1' i J where Dj is the jth column vector of D. So, u = 0 satisfies the necessary conditions for being a local minimum for (15),but not the sufficient condition given in (14). Using the transformation xj = uj j = 1 to n, we see that (15) is equivalent to (7). So problems 1 and 10 are equivalent. Likewise, problems 2 and 11 are equivalent. By Theorem 4, we conclude that both problems 10 and 11 are NP-hard. Thus, even in the unconstrained minimization problem, to check whether the objective function is not bounded below, and to check whether a given point is not a local minimum, may be hard problems in general. This also shows that the problem of checking whether a given smooth nonlinear function (even a polynomial) is or is not locally convex at a given point, may be a hard problem in general. 12

WHAT ARE SUITABLE GOALS FOR ALGORITHMS IN NONCONVEX NLP? Much of nonlinear programming literature stresses that the goal for algorithms in nonconvex NLPs should be to obtain a local minimum. Our results here show that in general, this may be hard to guarantee. Many nonlinear programming algorithms are iterative in nature, that is, beginning with an initial point x~, they obtain a sequence of points {xr: r = 0, 1,...}. For some of the algorithms, under certain conditions, it can be shown that the sequence converges to a KKT point for the original problem, (a KKT point is a feasible solution at which the first order necessary conditions for a local minimum, (4), hold). Unfortunately, there is no guarantee that a KKT point will be a local minimum, and our results point out that in general, checking whether or not it is a local minimum may be a hard problem. Some algorithms have the property that the sequence of points obtained is actually a descent sequence, that is, either the objective function, or a measure of the infeasibility of the current solution to the problem, or some merit function or criterion function which is a combination of both, strictly decreases along the sequence. Givef xr, these algorithms generate a yr $ such that the direction xr + Xyr, X 0, is a descent direction for the functions discussed above. The next point in the sequence xr+ is usually taken to be the point which minimizes the objective or criterion function on the halfline {xr + Xyr: X 2 0}, obtained by using a line minimization algorithm. On general nonconvex problems, these methods suffer from the same difficulties, they cannot theoretically guarantee that the point obtained at termination is even a local minimum. However, it seems reasonable to expect that a solution obtained through a descent process is more likely to be a local minimum, than a solution obtained purely based on necessary optimality conditions. Thus a suitable goal for algorithms for nonconvex NLPs seems to be a descent sequence 13

converging to a KKT point. Some recently developed algorithms, such as the sequential quadratic programming methods, reach this goal. 14

References 1. Fiacco, A. V. and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Technique, Wiley, New York, 1968. 2. Garey, M. R. and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-completeness, Freeman, New York, 1980. 3. Mangasarian, 0. L., Nonlinear Programming, McGraw-Hill, New York, 1965. 4. Murty, K. G., Linear Programming, Wiley, New York, 1983. 5. Murty, K. G., Linear Complementarity, Linear and Nonlinear Programming, Heldermann Verlag, West Berlin, 1986, to appear. 6. Murty, K. G. Linear and Combinatorial Programming, 1976, available from Krieger Publishing Company, Malabar, Florida. 15

UNIVERSITY OF MICHIGAN 3 9015 03994 8206