Data Structures and Algorithms

Complexity of Minimization

Authors: Warren D. Smith
Comments: 15 Pages. On internet since 2000; uploading to VIXRA for archival purposes.

An important problem in numerical analysis is trying to minimize (or maximize) a real function F(x₁,x₂,...,x_d) of d real variables. We investigate (and survey) its computational complexity borderlines.

Results include (precise theorem statements are in the text): Minimizing, e.g., functions specified by polynomial formulas involving both trigonometric and ordinary arguments, is undecidable. Hence consider plain rational functions; we'll show minimizing these (more precisely, deciding whether the minimum lies below some threshold) is in NP. If the sum of the numerator and denominator degrees of a (multivariate) rational function is ≤4, then finding all its local minima is in P, except for the 4+0 case of a quartic polynomial (or its reciprocal) in which case it is NP-complete. (There is a slight caveat for the case 3+1; the "polynomial" runtime unfortunately depends also on an additional parameter, but for practical purposes this does not matter.) Indeed, even deciding whether a specified point is a localmin is NP-complete for a quartic. Minimizing a linear function in a cube is polynomial, but minimizing a quadratic in a cube is NP-complete. Minimizing a quadratic in a ball is in P, but it is NP-complete for a quartic (cubics: unknown). In all theseNP-completeness results, even approximating the value of the min is NP-complete, and the problems remain NP-complete even if all integers are input in unary. The P minimization algorithms for low degree rational functions involve new techniques of "multi-stage minimization" and "dimension reduction."

Minimizing functions "unimodal on lines," is in P. Solving systems of nonlinear equations F&8407;(x⃗)=0 is in P, if all the nonlinear functions $F_k are monotonic on lines. We present evidence that minimizing strictly unimodal functions (with exactly one minimum, and no saddlepoints) is exponentially hard; but if additionally the function obeys certain derivative bounds, then hardness seems to occur precisely when there are extremely long "winding valleys."
Category: Data Structures and Algorithms