An algorithmic approach is proposed for exploiting parallelization possibilities in large scale optimization models of the following generic type. Objects change their state over time subject to a limited availability of common resources. These are modeled by linear coupling constraints and result in few objects competing for the same resource at each point in time. In a kind of asynchronous parallel coordinate descent, each independent process iteratively picks a free subset of violated constraints together with their interacting objects, improves the corresponding Lagrange multipliers by a bundle method to a certain level, and stores observed presumable dependencies leading to increased violation of other constraints in a common dependency graph. These dependencies have to be respected in future subset selections. No synchronization is required between the processes, for each subproblem the number of evaluations may differ arbitrarily. Under the assumption of boundedness of the set of dual optimizers we prove convergence of appropriate subsequences of the iterates to primal and dual optimal solutions of the relaxation. Preliminary computational results indicate that this approach may develop into a viable alternative to classical bundle methods using parallel evaluations.
Citation
Preprint 2012-2, Fakultät für Mathematik, Technische Universität Chemnitz, D-09107 Chemnitz, February 2012