Approximate methods for convex minimization problems with series-parallel structure

doi:10.1016/j.ejor.2006.04.052

Approximate methods for convex minimization problems with series-parallel structure

2008-09-01

2

PRE

AI

DOI：10.1016/j.ejor.2006.04.052

Original

Original request for help

Save

Abstract

En 中文

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, v - 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 v - n + 1 equality constraints, where v 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. (C) 2007 Published by Elsevier B.V.

Keywords:

convex programming

decomposition

large-scale optimization

Approximate methods for convex minimization problems with series-parallel structure

Abstract

AI Summary

Journal

Organization