Complexity and algorithms for nonlinear optimization problems |
| |
Authors: | Dorit S Hochbaum |
| |
Institution: | (1) Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, Berkeley, USA |
| |
Abstract: | Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear
problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing
algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space.
We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity,
constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices,
and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms
which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the
complexity of the respective problems.
In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare
the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear
optimization.
An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005. |
| |
Keywords: | Nonlinear optimization Convex network flow Strongly polynomial algorithms Lower bounds on complexity |
本文献已被 SpringerLink 等数据库收录! |
|