The empirical performance of a polynomial algorithm for constrained nonlinear optimization

Dorit S. Hochbaum, Sridhar Seshadri

Research output: Contribution to journalArticlepeer-review

Abstract

In [6], a polynomial algorithm based on successive piecewise linear approximation was described. The algorithm is polynomial for constrained nonlinear (convex or concave) optimization, when the constraint matrix has a polynomial size subdeterminant. We propose here a practical adaptation of that algorithm with the idea of successive piecewise linear approximation of the objective on refined grids, and the testing of the gap between lower and upper bounds. The implementation uses the primal affine interior point method at each approximation step. We develop special features to speed up each step and to evaluate the gap. Empirical study of problems of size up to 198 variables and 99 constraints indicates that the procedure is very efficient and all problems tested were terminated after 171 interior point iterations. The procedure used in the implementation is proved to converge when the objective is strongly convex.

Original languageEnglish (US)
Pages (from-to)229-248
Number of pages20
JournalAnnals of Operations Research
Volume43
Issue number4
DOIs
StatePublished - Apr 1993
Externally publishedYes

ASJC Scopus subject areas

  • General Decision Sciences
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'The empirical performance of a polynomial algorithm for constrained nonlinear optimization'. Together they form a unique fingerprint.

Cite this