Title 
Complexity of Minimization

Abstract

An important problem in numerical analysis is trying to minimize (or
maximize) a real function $F(x_1,x_2,..., 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 threshhold) is
in NP.  If the sum of the numerator and denominator degrees of a
(multivariate) rational function is $\le 4$, then finding all its
local minima is in $P$, {\em 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 {\em specified} point is a {\em local}
min 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 these
NP-completeness results, even {\em approximating} the value of the min
is NP-complete, and the problems remain NP-complete even if all
integers are input in {\em 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 $\vec{F}(\vec{x})=0$ is in P, if all the
nonlinear functions $F_j$ 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 {\em precisely} when
there are extremely long ``winding valleys.''

%Some of these results are extremely easy but have remained unnoticed;
%others are not so easy.

Keywords

rational functions,
minimization,
NP-completeness,
unimodal on lines