Sufficient optimality criterion for linearly constrained, separable concave minimization problems

T. Illes, Á.B. Nagy

Research output: Contribution to journalArticle

Abstract

A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimality criterion is based on the sensitivity analysis of the relaxed linear programming problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive. In the Phillips and Rosen paper (Ref. 1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimality of the current basic solution. The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithms developed for linearly-constrained concave minimization problems.
Original languageEnglish
Pages (from-to)559-575
Number of pages16
JournalJournal of Optimization Theory and Applications
Volume125
Issue number3
DOIs
Publication statusPublished - Jun 2005

Keywords

  • separable concave minimization problems
  • linear relaxation
  • sensitivity analysis

Fingerprint Dive into the research topics of 'Sufficient optimality criterion for linearly constrained, separable concave minimization problems'. Together they form a unique fingerprint.

  • Cite this