TY - JOUR

T1 - Approximate methods for convex minimization problems with series-parallel structure

AU - Ben-Israel, Adi

AU - Levin, Genrikh

AU - Levin, Yuri

AU - Rozin, Boris

N1 - Funding Information:
We thank the referees for their constructive suggestions, and A. Suvorov for the implementation of the proposed algorithms. The research of the second and fourth authors was partly supported by the International Science and Technology Center (Project B-986). The research of the third author was supported by Natural Sciences and Engineering Research Council of Canada (Grant Number 261512–04).

PY - 2008/9/16

Y1 - 2008/9/16

N2 - 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.

AB - 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.

KW - Convex programming

KW - Decomposition

KW - Large-scale optimization

UR - http://www.scopus.com/inward/record.url?scp=40849114583&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40849114583&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2006.04.052

DO - 10.1016/j.ejor.2006.04.052

M3 - Article

AN - SCOPUS:40849114583

VL - 189

SP - 841

EP - 855

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -