Approximate methods for convex minimization problems with series-parallel structure

Adi Ben-Israel, Genrikh Levin, Yuri Levin, Boris Rozin

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Consider a problem of minimizing a separable, strictly convex, monotone and differentiable function on a convex polyhedron generated by a system of m linear inequalities. The problem has a series-parallel structure, with the variables divided serially into n disjoint subsets, whose elements are considered in parallel. This special structure is exploited in two algorithms proposed here for the approximate solution of the problem. The first algorithm solves at most min{m, ν - n + 1} subproblems; each subproblem has exactly one equality constraint and at most n variables. The second algorithm solves a dynamically generated sequence of subproblems; each subproblem has at most ν - n + 1 equality constraints, where ν is the total number of variables. To solve these subproblems both algorithms use the authors' Projected Newton Bracketing method for linearly constrained convex minimization, in conjunction with the steepest descent method. We report the results of numerical experiments for both algorithms.

Original languageEnglish (US)
Pages (from-to)841-855
Number of pages15
JournalEuropean Journal of Operational Research
Volume189
Issue number3
DOIs
StatePublished - Sep 16 2008

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Convex programming
  • Decomposition
  • Large-scale optimization

Fingerprint Dive into the research topics of 'Approximate methods for convex minimization problems with series-parallel structure'. Together they form a unique fingerprint.

Cite this