Piecewise-Linear Approximation Methods for Nonseparable Convex Optimization

B. Feijoo and R. R. Meyer
Additional contact information
B. Feijoo: Department of Mathematics and Computer Sciences, Universidad Simon Bolivar, Caracas, Venezuela
R. R. Meyer: Mathematics Research Center, University of Wisconsin, Madison, Wisconsin 53706

Management Science, 1988, vol. 34, issue 3, 411-419

Abstract: An algorithm is described for the solution of nonseparable convex optimization problems. This method utilizes iterative piecewise-linear approximation of the nonseparable objective function, but requires function values only along a translated set of axes, thereby avoiding the curse of dimensionality commonly associated with grid methods for multi-dimensional problems. A global convergence proof is given under the assumptions that the objective function is Lipschitz continuous and differentiable and that the feasible set is convex and compact. The method is well-suited to linearly constrained large-scale optimization, since the direction-finding problems reduce to linear programs of manageable size. It is particularly appropriate for nonlinear networks, since it preserves the network structure of the constraints. In addition, because the resulting objective function approximation is separable, this approach permits for certain problem classes a decomposition that may be exploited for parallel computation. Some numerical results on the CRYSTAL multicomputer are presented to illustrate this decomposition feature.

Keywords: convex optimization; parallel computation; nonlinear networks (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.3.411 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:3:p:411-419

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().