Workshop Details

This introductory talk will outline the relationships between the key ideas covered in this workshop, including the ADMM, operator splitting, and progressive hedging, and discuss some key challenges in applying these methods to real-world optimization problems.  It is aimed at providing a common context the talks in the body of the workshop.

Proximal algorithms are ubiquitous tools in optimization, for they can decompose a complex minimization problem into simpler subproblems that scale gracefully with the problem size. This class of algorithms includes, yet is not limited to, the proximal gradient method, Douglas-Rachford splitting and ADMM, all extensively used for a plethora of applications in engineering and computer sciences such as control, signal processing, image analysis, machine learning, and many more. Splitting algorithms are also particularly suited for embedded applications, due to the simplicity of their operations and amenability to parallelization. The underlying mechanisms ensuring convergence of such methods are well understood when applied to convex problems, where the theory hinges on fixed-point and monotone operator theory, Fejér monotonicity, duality, and so on.

Recently, there has been an ever increasing interest in addressing large-scale, structured nonconvex problems. However, only partial convergence results for proximal algorithms  are available in the nonconvex setting and overall the theory lacks a unifying framework. Furthermore, despite the cheapness of each iteration, even in the simpler convex case the high sensitivity to ill-conditioning of the problem oftentimes results in prohibitively slow convergence rates.

In response to these issues we introduce the "proximal envelopes", a generalization of the Moreau envelope and of its connections with proximal point iterations. Proximal envelopes are continuous, exact, real-valued “Lyapunov" functions for the original problem with a two-fold value. One one hand, they serve as a theoretical tool for ensuring convergence of splitting algorithms. On the other hand, they can be used to robustify and greatly accelerate their convergence without any additional operation other than scalar products. The resulting method is globally convergent and preserves the simplicity of the original splitting algorithm. This is achieved by a suitable line-search strategy along (limited-memory) BFGS directions, for instance. 

For a symmetric positive semidefinite linear system of equations ${cal Q} x = b$, where $x = (x_1,ldots,x_s)$ is partitioned into $s$ blocks of sub-vectors $x_1,ldots,x_s$, with $s geq 2$, we show that each cycle of the classical block symmetric Gauss-Seidel (block sGS) method exactly solves the associated quadratic programming (QP) problem but  added with an extra proximal term of the form $frac{1}{2}

By leveraging on such a connection to optimization, we are able to extend the result (which we name as the  block sGS decomposition theorem) for solving convex composite QP (CCQP) with an additional possibly nonsmooth term in $x_1$, i.e., $min{ p(x_1) + frac{1}{2}langle x, {cal Q} xrangle -langle b, x rangle$, where $p(cdot)$ is a proper closed convex function.

Based on the block sGS decomposition theorem, we extend the classical block sGS method to solve   CCQP. In addition, our extended block sGS method has the flexibility of allowing for inexact computation in each step of the block sGS cycle. At the same time, we can also accelerate the inexact block sGS method to achieve an iteration complexity of $O(1/k^2)$ after performing $k$ cycles. As a fundamental building block, the block sGS decomposition theorem has played a key role in various recently developed algorithms such as the inexact semiproximal {ALM/ADMM} for linearly constrained multi-block convex composite conic programming (CCCP), and the accelerated block coordinate descent method for multi-block CCCP.

Day-ahead scheduling of electricity generation or unit commitment is an important and challenging operational activity of power system operators. Mixed integer programming (MIP) has been firmly established as an effective technology for this problem for moderate scale integrated systems. In this work, we consider decentralized unit commitment in a large-scale network of generation systems. We develop a decomposition-coordination approach by which independent unit commitment MIP models can be integrated to achieve high quality solutions to the network-wide problem. The approach is based on the alternating direction method of multipliers (ADMM) originally developed for decentralized convex optimization. We adapt ADMM to the highly nonconvex unit commitment problem and demonstrate its computational effectiveness.

This talk is based on joint works with Javad Feizollahi, Mitch Costley, Andy Sun and Santiago Grijalva.

In this work we focus on optimization of sums of squares of quadratic functions, which we refer to as second-order least-squares problems, subject to convex constraints. Our motivation arises from applications in risk parity portfolio selection. We generalize the setting further by considering a class of nonlinear, non convex functions which admit a (non separable) two-block representation with special structure. We then develop alternating direction and alternating linearization schemes for such functions and analyze their convergence and complexity. Due to the special structure of our functions, the steps of our methods reduce to solving convex optimization subproblems. We provide convergence rate results for the proposed methods. Furthermore, some global relaxation techniques are presented to find lower bounds and strengthen our local algorithms. We show the effectiveness of our techniques in application to risk parity optimization in portfolio management.

We propose a significant expansion of the scope of ADMM. Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain easily verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. Our analysis applies under assumptions that we have endeavored to make as weak as possible. It applies to problems that involve nonconvex and/or nonsmooth objective terms, in addition to the multiaffine constraints that can involve multiple (three or more) blocks of variables. To illustrate the applicability of our results, we describe examples including nonnegative matrix factorization, sparse learning, risk parity portfolio selection, nonconvex formulations of convex problems, and neural network training. In each case, our ADMM approach encounters only subproblems that have closed-form solutions.

This is joint work with Wenbo Gao and Frank E. Curtis.

The quadratic shortest path problem (QSPP) is the problem of finding a path between two vertices in a directed graph such that the sum of interaction costs over all pairs of arcs on the path is minimized. This problem is known to be NP-hard.

In this talk we present two approaches for solving the QSPP. Our first approach is based on splitting the quadratic objective into a linearizable and a non-linearizable part. Then, the linearizable part is used to compute  efficiently good lower bounds for the QSPP. Our second approach considers a semidefinite programming relaxation for the QSPP that is solved by using the ADMM. We also present numerical results on solving the problem to optimality by using the mentioned bounds within the branch and bound framework.

We discuss entropic proximal methods for convex optimization problems over the cone of nonnegative trigonometric polynomials. Problems of this type arise in signal processing and system identification. They can be handled by interior-point methods for semidefinite optimization, at a computational cost that it is at least cubic in the degree of the polynomial.

In the talk we will examine proximal methods with a lower complexity per iteration.  The methods use the Itakura-Saito distance measure as a Bregman divergence.  This choice is motivated by the possibility of computing the associated generalized projection at the cost of solving a small number of positive definite Toeplitz systems.

The complexity per iteration of the resulting proximal algorithms is therefore roughly quadratic in the degree of the polynomial.

Joint work with Hsiao-Han Chao.

Although Progressive Hedging (PH) is not guaranteed to converge in the case of non-convex and in particular mixed-integer problems, it has been effectively used as a heuristic in a remarkably wide range of applications. In this talk, we will consider the use of PH for solving stochastic mixed-integer and stochastic non-linear optimization problems, in domains ranging from power systems operations to natural resources management. We focus on key issues that occur in practice regarding non-convergence behaviors and how they are often mitigated in practice. Recent work related to computing lower bounds via PH will be introduced. We then discuss open source implementations of PH, available in the Pyomo (https://na01.safelinks.protection.outlook.com/?url=www.pyomo.org&data=02%7C01%7C%7C7e215235c2e44412fe0708d5b9a25fe2%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636619030308205535&sdata=JU3f86ks3h%2FekR1%2BkqhSZog9zm7K%2Bu%2FthN9Lwi7gcWw%3D&reserved=0) optimization library, and parallel deployment in cluster computing environments. We conclude by highlighting key recent application successes, including power systems operations and planning.

This talk represents joint work with Roger Wets, David Woodruff, Carl Laird, Francisco Munoz, among others.

We present a new progressive hedging/ADMM type algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. This dual is widely used in decomposition methods for the solution of SMIPs. A direct application of progressive hedging to this problem class is difficult because it requires solving a quadratic program over the convex hull of integer solutions, which is not given explicitly. We thus propose a variation that alternates between optimizing a linear objective over the true set of integer solutions and optimizing a quadratic objective over the convex hull of solutions collected to that point in the algorithm.  We demonstrate that the method converges to the optimal Lagrangian dual value. Numerical results demonstrate that our new algorithm empirically outperforms a previous implementation of progressive hedging for obtaining bounds in SMIP.

This is joint work with: Natashia Boland, Jeffrey Christiansen, Brian Dandurand, Andrew Eberhard, Jeff Linderoth, and Fabricio Oliveira

We derive differential equations that model the continuous limit of the iterate sequence generated by the alternating direction method of multipliers (ADMM), as well as an accelerated variant. The dynamical system associated with the accelerated variant corresponds to a nonlinear generalization of a damped harmonic oscillator. We employ the direct method of Lyapunov to analyze the stability of critical points and to obtain convergence rates. Our results strengthen the connection between commonly used optimization algorithms and continuous dynamical systems. 

To meet the challenges of large scale optimization, considerable effort has been devoted in recent years to the study of first-order splitting algorithms and their acceleration. In this lecture, based on recent works with  A. Cabot cite{AC1, AC2} and J. Peypouquet cite{AP1}, we address these issues for the resolution of general (structured) monotone inclusions. In doing so, we aim to provide a unified approach to solving, by rapid methods, convex optimization problems, convex-concave saddle value problems, and finding fixed points of nonexpansive mappings. Our approach is based on the link between dissipative dynamic systems and optimization algorithms.

Given $mathcal H$  a real Hilbert space, and $A: mathcal H rightarrow 2^{mathcal H}$, a  maximally monotone operator, we first study the asymptotic behavior, as time goes to $+infty$, of  the trajectories of the second-order differential equation $$

ddot{x}(t)   + frac{alpha}{t}  dot{x}(t) +A_{lambda(t)}(x(t)) = 0, qquad t>t_0>0,

$$ where $alpha $ is a positive damping parameter, and $A_lambda$ is the Yosida regularization of $A$ of index $lambda>0$. The Lipschitz continuity of the Yosida approximation makes the associated Cauchy problem well-posed. A proper tuning of the Yosida parameter $lambda(t)$ and of the damping parameter $alpha$ allows us to prove the weak convergence of the trajectories to zeroes of the operator $A$. By means of a convenient finite-difference time discretization of this differential equation, we introduce a new {it Relaxed Inertial Proximal Algorithm}  for which similar convergence properties hold.

When $A$ is the subdifferential of a closed convex function, we obtain fast convergence of the values, in line with the accelerated method of Nesterov.

Next, we extend this study to the Relaxed Inertial Proximal algorithm Algorithm with general inertial coefficient $alpha_k$, and  relaxation coefficient $rho_k$

{y_k=x_k+alpha_k(x_k-x_{k-1})

x_{k+1}=(1-rho_k)y_k + rho_k J_{mu_k A}(y_k),

where $J_{mu A} = left( I + mu A right)^{-1} $ is the {it resolvent} of $A$ with index $mu>0$.

We obtain convergence results under conditions involving only the coefficients $alpha_k$,  $rho_k$, $mu_k$ jointly.

Then, we  consider structured monotone problems governed by the sum of a prox-friendly maximally monotone operator and a cocoercive operator. We study a Relaxed Inertial Forward-Backward algorithm (RIFB) for which we obtain similar convergence results. Finally, we introduce an inertial proximal ADMM algorithm to solve convex structured minimization problems with linear constraint. Numerical experiments confirm the effectiveness of the algorithm.

In this talk, we propose a primal-dual algorithm with a momentum term, which can be viewed as a generalization of the method proposed by Chambolle and Pock in 2016, to solve saddle point problems defined by a convex-concave function L(x,y) = f(x) + Phi(x,y) - h(y) with a general coupling term Phi(x,y) that is not assumed to be bilinear. Given a saddle point (x*,y*), assuming the partial gradients of Phi satisfy certain Lipshitz continuity property, we derive error bounds in terms of L(x_k,x*)-L(y*,y_k) for the ergodic sequence {x_k, y_k}; in particular, we show O(1/k) rate that when the problem is merely convex in x. Furthermore, assuming Phi(x,y) is linear in y for each fixed x and f is strongly convex, we can obtain the ergodic convergence rate of O(1/k^2) – we are not aware of any other work in the related literature showing O(1/k^2) rate when Phi is not bilinear. We tested our method for solving kernel matrix learning problem, and compare it against the Mirror-prox algorithm and interior point methods.

We present two numerical algorithms for minimizing the sum of a smooth function and the composition of a nonsmooth function with a linear operator in the fully nonconvex setting. The iterative schemes are formulated in the spirit of the proximal and proximal linearized alternating direction method of multipliers, respectively. The proximal terms are introduced through variable metrics, which facilitates the derivation of proximal splitting algorithms for nonconvex complexly structured optimization problems as particular instances of the general schemes. Convergence of the iterates to a KKT point of the objective function is proved under mild conditions on the sequence of variable metrics and by assuming that a regularization of the associated augmented Lagrangian has the Kurdyka- Lojasiewicz property. If the augmented Lagrangian has the Lojasiewicz property, then convergence rates of both augmented Lagrangian and iterates are derived.

Multiplier methods based on augmented Lagrangians are attractive in convex and nonconvex programming for their stabilizing and even convexifying properties.  They have widely been seen, however, as incompatible with taking advantage of block-separable structure.

In fact, when articulated in the right way, they can produce decompostition algorithms in which low-dimensional subproblems can be solved in parallel.  Convergence in the nonconvex case is, of course, just local, but is available under a broad analog of the strong second-order sufficient condition for local optimality that dominates much of computational methodology outside of convex optimization. This carries over also to extended nonlinear programing with its greater flexibility to handle composite terms.

The alternating direction method of multipliers (ADMM) has been successfully used in solving problems arising from different fields such as machine learning, image processing, statistics and so on. In this talk, we discuss several recent results on convergence behavior of ADMM for solving nonconvex problems. We consider two nonconvex models. The first model allows the objective function to be nonconvex and nonsmooth, but the constraints are convex. The second model allows the constraints to be Riemannian manifolds. For both models, we propose ADMM variants for solving them and analyze their iteration complexities for obtaining an $epsilon$-stationary solution. Numerical results on tensor robust PCA, maximum bisection problem and community detection problem are reported to demonstrate the efficiency of the proposed methods.

Given the success of Douglas-Rachford splitting (DRS), it is natural to ask whether DRS can be generalized. Are there are other 2 operator splittings? Can DRS be generalized to 3 operators? This work presents the answers: no and no. In a certain sense, DRS is the unique 2 operator resolvent-splitting, and generalizing DRS to 3 operators is impossible without lifting, where lifting roughly corresponds to enlarging the problem size. The impossibility result further raises a question. How much lifting is necessary to generalize DRS to 3 operators? This work presents the answer by providing a novel 3 operator resolvent-splitting with provably minimal lifting that directly generalizes DRS.

Several local and global linear convergence rate results for the alternating direction method of multipliers (ADMM) have appeared in the literature over the last couple of years. Many of these are derived under strong monotonicity, Lipschitz continuity, and/or cocoercivity assumptions, and focus on the convex optimization setting. It is well known that ADMM is obtained by applying the Douglas-Rachford algorithm

to a Fenchel dual problem. In this talk, we show that the linear convergence results for ADMM follow from that the Douglas-Rachford operator is contractive under the stated assumptions. The benefits of our analysis are that 1) the contraction factors are sharp 2) the proofs are fairly simple, based on operator theoretic analysis.

This work is concerned with the classical problem of finding a zero of a sum of maximal monotone operators. For the projective splitting framework recently proposed by Combettes and Eckstein, we show how to replace the fundamental subproblem calculation using a backward step with one based on two forward steps. The resulting algorithms have the same kind of coordination procedure and can be implemented in the same block-iterative and potentially distributed and asynchronous manner, but may perform backward steps on some operators and forward steps on others. Prior algorithms in the projective splitting family have used only backward steps. Forward steps can be used for any Lipschitz-continuous operators provided the stepsize is bounded by the inverse of the Lipschitz constant. If the Lipschitz constant is unknown, a simple backtracking linesearch procedure may be used. Interestingly, this backtracking procedure also leads to a convergent algorithm even when the operator is only uniformly continuous, but not necessarily Lipschitz, provided it has full domain. For affine operators, the stepsize can be chosen adaptively without knowledge of the Lipschitz constant and without any additional forward steps. Convergence rates under various assumptions are also discussed along with preliminary experiments of several kinds of splitting algorithms on the lasso problem.

Recent work by Eckstein and Combettes resulted in development of an algorithm for multi-stage, convex stochastic optimization problems with uncertain input data expressed as a set of scenarios. The algorithm is called Asynchronous Projective Hedging (APH). In this talk we describe computational experience with this algorithm primarily based on two well-known problems from the stochastic programming literature: saphir and ssn. We explore various tradeoffs such as computational resources vs. wall-clock vs. solution quality as well primal versus dual solution quality.

Co-authors: Jonathan Eckstein, Rutgers and Jean-Paul Watson, Sandia

We propose and study the iteration complexity of a parallel version of the forward-backward (proximal gradient) splitting method for minimizing a (possibly) large sum of convex functions with many smooth and nonsmooth terms.  We obtain pointwise (nonergodic) as well as ergodic nonasymptotic convergence rates by embedding the  proposed method within the partial inverse framework of Spingarn.

We consider the problem of minimizing a sum of several convex non-smooth functions. In this talk, we introduce  the selective linearization method, which iteratively linearizes all but one of the functions and employs simple proximal steps. The algorithm is a form of multiple operator splitting in which the order of processing partial functions is not fixed, but rather determined in the course of calculations. It proposes one of the first operator-splitting type methods which are globally convergent for an arbitrary number of operators without artificial duplication of variables. Global convergence is proved and estimates of the convergence rate are derived. Specifically, under a strong convexity condition, the number of iterations needed to achieve solution accuracy ε is of order O(ln(1/ε)/ε). We also study the optimal tuning parameters in the improvement test of the algorithm. We report results of extensive comparison experiments in statistical learning problems such as large-scale fused lasso regularization problem, overlapping group lasso problem and regularized support vector machine problem. The numerical results demonstrate the efficacy and accuracy of the method.

In this talk, we consider some ADMM variants and discuss relative error criteria for solving approximately their subproblems. We present some  iteration-complexity bounds for these variants in order to compute approximate solutions of a linearly constrained optimization problem. Some numerical experiments are presented in order to show the advantage of considering inexact ADMM variants using relative error criteria.

Co-authors: Vando A. Adona  and  Max L.N. Gonçalves

First-order methods such as ADMM and Douglas-Rachford splitting are known for their easy implementations and low per-iteration costs. What is less known is their usefulness for “solving” infeasible problems and feasible-yet-unbounded problems. In this talk, we present a method for classifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting, or ADMM. When an optimization program is infeasible, unbounded, or pathological, the z^k iterates of Douglas-Rachford splitting diverge. Surprisingly, such divergent iterates still provide useful information, which our method uses for classification. They help us identify some of the cases where existing solvers cannot do reliably. When the problem is infeasible or weakly feasible, it is useful to know how to minimally modify the problem data to achieve strong feasibility, where “strong” makes it easier to find a solution. We also get this information via the divergent iterates.

This is joint work with Yanli Liu and Ernest Ryu.

The Douglas-Rachford algorithm is a popular method for finding zeros of sums of monotone operators. By its definition, the Douglas-Rachford operator is not symmetric with respect to the order of the two operators. In this talk we provide a systematic study of the two possible Douglas-Rachford operators. We show that the reflectors of the underlying operators act as bijections between the fixed points sets of the two Douglas-Rachford operators. Some elegant formulae arise under additional assumptions. Various examples illustrate our results.

Nonlinear programming is an effective technique to formulate and solve optimal control problems in many industries. These problems are often formulated as dynamic optimization problems, and in many cases, an optimal solution can be found using current off-the-shelf solvers. However, as the model rigor, system complexity increases, the size of these optimization problems often exceeds the computational capabilities of a serial algorithm on a single workstation. Efficient solution demands the development of algorithms that allow parallel solution.

In this presentation, we describe two decomposition strategies for time-discretized systems. In the first strategy, we focus on the parallelization of the interior-point (IP) algorithm and use a Schur-complement approach to decompose the solution of the KKT system in each iteration of the IP algorithm. We demonstrate the efficiency and scalability of this approach for solving nonlinear programming problems with millions of variables and constraints. In the second strategy, we partition the overall problem into N subproblems and investigate the use of the Alternating Direction Method of Multipliers (ADMM). We demonstrate the applicability of ADMM for decomposing challenging nonconvex optimal control problems.  To study the convergence of ADMM in the nonconvex setting, we present connections between the ADMM and the classical augmented Lagrangian (AL) and summarize our results in terms of a Lyapunov function and primal and dual feasibility metrics.

In this paper, we show that for a class of linearly constrained convex composite optimization problems, an (inexact) symmetric Gauss-Seidel based majorized multi-block proximal alternating direction method of multipliers (ADMM) is equivalent to an inexact proximal augmented Lagrangian method (ALM). This equivalence not only provides new perspectives for understanding some ADMM-type algorithms but also supplies meaningful guidelines on implementing them to achieve better computational efficiency. Even for the two-block case, a by-product of this equivalence is the convergence of the whole sequence generated by the classic ADMM with a step-length that exceeds the conventional upper bound of $(1+sqrt{5})/2$, if one part of the objective is linear. This is exactly the problem setting in which the very first convergence analysis of ADMM was conducted by Gabay and Mercier in 1976, but, even under notably stronger assumptions, only the convergence of the primal sequence was known. A collection of illustrative examples are provided to demonstrate the breadth of applications for which our results can be used. Numerical experiments on solving a large number of semidefinite programming problems are conducted to illustrate how the theoretical results established here can lead to improvements on the corresponding practical implementations.

This is a joint work with Liang Chen, Xudong Li, and Kim-Chuan Toh.

Modern astronomical images are collected with increasingly large telescopes and reach spectacular sensitivities. As an undesired consequence, images have become so densely populated with stars and galaxies that those sources routinely overlap, which interferes with the measurement process.

We employ a matrix factorization scheme to perform source separation across multiple images, observed in different optical filters. We use a combination of proximal gradient and ADMM approaches to enforce multiple simultaneous constraints on the spectral energy emission and/or morphology of the sources. I will present the methodology and show results of the source separation framework applied to state-of-the-art astronomical images from the HyperSuprimeCam Survey based in Hawaii.