Optimization Software and Modeling Systems – Page 27

Efficient parallel coordinate descent algorithm for convex optimization problems with separable constraints: application to distributed MPC

Published: 2012/11/02, Updated: 2013/02/13

Control Applications, Convex Optimization, Parallel Algorithms (sub)linear convergence rate, coordinate descent optimization, distributed model predictive control, embedded control, parallel algorithm

In this paper we propose a parallel coordinate descent algorithm for solving smooth convex optimization problems with separable constraints that may arise e.g. in distributed model predictive control (MPC) for linear network systems. Our algorithm is based on block coordinate descent updates in parallel and has a very simple iteration. We prove (sub)linear rate of … Read more

On Defining Design Patterns to Generalize and Leverage Automated Constraint Solving

Published: 2012/10/11

Thiago Serra

Combinatorial Optimization, Integer Programming, Optimization Software Design Principles algorithm selection, autonomous search, hardness models

This position paper reflects on the generalization of adaptive methods for Constraint Programming (CP) solving mechanisms, and suggests the use of application-oriented descriptions as a means to broaden CP adoption in the industry. We regard as an adaptive method any procedure that modifies the behavior of the solving process according to previous experience gathered from … Read more

On parallelizing dual decomposition in stochastic integer programming

Published: 2012/10/09, Updated: 2013/02/10

Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming bundle method, column generation, dual decomposition, mixed-integer programming, parallel computing, stochastic programming

For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more

Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems

Published: 2012/10/03, Updated: 2013/02/12

Convex Optimization, Distributed Control, Parallel Algorithms distributed model predictive control, dual decomposition, estimates on suboptimality and infeasibility, inexact dual gradient algorithms, parallel coordinate descent algorithm, rate of convergence

In this paper we propose two dual decomposition methods based on inexact dual gradient information for solving large-scale smooth convex optimization problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first order methods based on approximate gradients and we prove sublinear rate of convergence … Read more

On Stable Piecewise Linearization and Generalized Algorithmic Differentiation

Published: 2012/09/05, Updated: 2012/12/30

Andreas Griewank

Nonlinear Optimization, Nonsmooth Optimization, Optimization Software Design Principles adol-c, automatic differentiation, bouligand derivative, bundle method, coherent orientation, computational graph, conical activity, directional derivative, generalized gradients and jacobians, lipschitz continuity, midpoint method, piecewise differentiability, piecewise newton, trapezoidal rule

It is shown how functions that are defined by evaluation programs involving the absolute value function (besides smooth elementals), can be approximated locally by piecewise-linear models in the style of algorithmic, or automatic, differentiation (AD). The model can be generated by a minor modification of standard AD tools and it is Lipschitz continuous with respect … Read more

Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method

Published: 2012/09/04, Updated: 2013/04/16

Optimization Software and Modeling Systems, Stochastic Programming cut consolidation, nested l-shaped method, sequencing protocols, stochastic programming

The Nested L-shaped method is used to solve two- and multi-stage linear stochastic programs with recourse, which can have integer variables on the first stage. In this paper we present and evaluate a cut consolidation technique and a dynamic sequencing protocol to accelerate the solution process. Furthermore, we present a parallelized implementation of the algorithm, … Read more

An Outer-Inner Approximation for separable MINLPs

Published: 2012/08/27

(Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems mixed-integer nonlinear programming, outer approximation, perspective cuts

A common structure in convex mixed-integer nonlinear programs is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. These … Read more

A first-order block-decomposition method for solving two-easy-block structured semidefinite programs

Published: 2012/07/28, Updated: 2013/10/14

Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark block-decomposition, complexity, conic optimization, convex optimization, extragradient, proximal, semidefinite programming

In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredients from a computational point of view, namely: an adaptive choice of stepsize for … Read more

Convergence and Perturbation Resilience of Dynamic String-Averaging Projection Methods

Published: 2012/06/01

Biomedical Applications, Convex Optimization, Parallel Algorithms dynamic string-averaging, fixed point, hilbert space, metric projection, nonexpansive operator, perturbation resilience, projection methods, superiorization method, variable strings, variable weights

We consider the convex feasibility problem (CFP) in Hilbert space and concentrate on the study of string-averaging projection (SAP) methods for the CFP, analyzing their convergence and their perturbation resilience. In the past, SAP methods were formulated with a single predetermined set of strings and a single predetermined set of weights. Here we extend the … Read more

Tolerances

Published: 2012/05/31

Harvey Greenberg

Optimization Software and Modeling Systems mathematical programming system, solution analysis, tolerance

Many different tolerances are used in mathematical programming systems. They are not used in the same way, and tolerances are related to each other. This Mathematical Programming Glossary Supplement presents the main concepts with specifics for some MPS’s and examples to illustrate caution. CitationAvailable as Mathematical Programming Glossary Supplement, 2003, at http://glossary.computing.society.informs.org/ArticleDownload View PDF