Understanding the Convergence of the Alternating Direction Method of Multipliers: Theoretical and Computational Perspectives

Categories Convex Optimization Tags ,

The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from “big data” and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. While it is … Read more

Generic properties for semialgebraic programs

Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

In this paper we study genericity for the following parameterized class of nonlinear programs: \begin{eqnarray*} \textrm{minimize } f_u(x) := f(x) – \langle u, x \rangle \quad \textrm{subject to } \quad x \in S, \end{eqnarray*} where $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ is a polynomial function and $S \subset \mathbb{R}^n$ is a closed semialgebraic set, which is … Read more

Stability and genericity for semi-algebraic compact programs

Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

In this paper we consider the class of polynomial optimization problems with inequality and equality constraints, in which every problem of the class is obtained by perturbations of the objective function, while the constraint functions are kept fixed. Under certain assumptions, we establish some stability properties (e.g., strong H\”older stability with explicitly determined exponents, semicontinuity, … Read more

ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

Categories Convex Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex … Read more

Solving the Probabilistic Traveling Salesman Problem by Linearising a Quadratic Approximation

Categories Integer Programming, Quadratic Programming, Transportation

The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The … Read more

Provably Near-Optimal Approximation Schemes for Implicit Stochastic and for Sample-Based Dynamic Programs

Categories Dynamic Programming Tags , , ,

In this paper we address two models of non-deterministic discrete-time finite-horizon dynamic programs (DPs): implicit stochastic DPs – the information about the random events is given by value oracles to their CDFs; and sample-based DPs – the information about the random events is deduced via samples. In both models the single period cost functions are … Read more

A semi-proximal-based strictly contractive Peaceman-Rachford splitting method

Categories Convex and Nonsmooth Optimization Tags , , , ,

The Peaceman-Rachford splitting method is very efficient for minimizing sum of two functions each depends on its variable, and the constraint is a linear equality. However, its convergence was not guaranteed without extra requirements. Very recently, He et al. (SIAM J. Optim. 24: 1011 – 1040, 2014) proved the convergence of a strictly contractive Peaceman-Rachford … Read more

Alternating Direction Method of Multipliers for Linear Programming

Categories Linear Programming Tags , ,

Recently the alternating direction method of multipliers (ADMM) has been widely used for various applications arising in scientific computing areas. Most of these application models are, or can be easily reformulated as, linearly constrained convex minimization models with separable nonlinear objective functions. In this note we show that ADMM can also be easily used for … Read more

Iterative Refinement for Linear Programming

Categories Linear Programming Tags , , ,

We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification … Read more

Existence Results for Particular Instances of the Vector Quasi-Equilibrium Problem on Hadamard Manifolds

Categories Generalized Convexity/Monoticity

We show the validity of select existence results for a vector optimization problem, and a variational inequality. More generally, we consider generalized vector quasi-variational inequalities, as well as, fixed point problems on genuine Hadamard manifolds. ArticleDownload View PDF