Showing 1–23 of 23 results for author: Ruszczyński, A

A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization

Authors: Andrzej Ruszczyński, Shangzhe Yang

Abstract: We consider stochastic optimization problems involving an expected value of a nonlinear function of a base random vector and a conditional expectation of another function depending on the base random vector, a dependent random vector, and the decision variables. We call such problems conditional stochastic optimization problems. They arise in many applications, such as uplift modeling, reinforceme… ▽ More We consider stochastic optimization problems involving an expected value of a nonlinear function of a base random vector and a conditional expectation of another function depending on the base random vector, a dependent random vector, and the decision variables. We call such problems conditional stochastic optimization problems. They arise in many applications, such as uplift modeling, reinforcement learning, and contextual optimization. We propose a specialized single time-scale stochastic method for nonconvex constrained conditional stochastic optimization problems with a Lipschitz smooth outer function and a generalized differentiable inner function. In the method, we approximate the inner conditional expectation with a rich parametric model whose mean squared error satisfies a stochastic version of a Łojasiewicz condition. The model is used by an inner learning algorithm. The main feature of our approach is that unbiased stochastic estimates of the directions used by the method can be generated with one observation from the joint distribution per iteration, which makes it applicable to real-time learning. The directions, however, are not gradients or subgradients of any overall objective function. We prove the convergence of the method with probability one, using the method of differential inclusions and a specially designed Lyapunov function, involving a stochastic generalization of the Bregman distance. Finally, a numerical illustration demonstrates the viability of our approach. △ Less

Submitted 17 May, 2024; originally announced May 2024.

MSC Class: 90C15; 49J52; 60-08

Fast Dual Subgradient Optimization of the Integrated Transportation Distance Between Stochastic Kernels

Authors: Zhengqi Lin, Andrzej Ruszczynski

Abstract: A generalization of the Wasserstein metric, the integrated transportation distance, establishes a novel distance between probability kernels of Markov systems. This metric serves as the foundation for an efficient approximation technique, enabling the replacement of the original system's kernel with a kernel with a discrete support of limited cardinality. To facilitate practical implementation, we… ▽ More A generalization of the Wasserstein metric, the integrated transportation distance, establishes a novel distance between probability kernels of Markov systems. This metric serves as the foundation for an efficient approximation technique, enabling the replacement of the original system's kernel with a kernel with a discrete support of limited cardinality. To facilitate practical implementation, we present a specialized dual algorithm capable of constructing these approximate kernels quickly and efficiently, without requiring computationally expensive matrix operations. Finally, we demonstrate the efficacy of our method through several illustrative examples, showcasing its utility in practical scenarios. This advancement offers new possibilities for the streamlined analysis and manipulation of stochastic systems represented by kernels. △ Less

Submitted 3 December, 2023; originally announced December 2023.

Comments: arXiv admin note: text overlap with arXiv:2311.06645

Risk-Averse Control of Markov Systems with Value Function Learning

Authors: Andrzej Ruszczynski, Shangzhe Yang

Abstract: We consider a control problem for a finite-state Markov system whose performance is evaluated by a coherent Markov risk measure. For each policy, the risk of a state is approximated by a function of its features, thus leading to a lower-dimensional policy evaluation problem, which involves non-differentiable stochastic operators. We introduce mini-batch transition risk mappings, which are particul… ▽ More We consider a control problem for a finite-state Markov system whose performance is evaluated by a coherent Markov risk measure. For each policy, the risk of a state is approximated by a function of its features, thus leading to a lower-dimensional policy evaluation problem, which involves non-differentiable stochastic operators. We introduce mini-batch transition risk mappings, which are particularly suited to our approach, and we use them to derive a robust learning algorithm for Markov policy evaluation. Finally, we discuss structured policy improvement in the feature-based risk-averse setting. The considerations are illustrated with an underwater robot navigation problem in which several waypoints must be visited and the observation results must be reported from selected transmission locations. We identify the relevant features, we test the simulation-based learning method, and we optimize a structured policy in a hyperspace containing all problems with the same number of relevant points. △ Less

Submitted 1 December, 2023; originally announced December 2023.

An Integrated Transportation Distance Between Kernels and Approximate Dynamic Risk Evaluation in Markov Systems

Authors: Zhengqi Lin, Andrzej Ruszczynski

Abstract: We introduce a distance between kernels based on the Wasserstein distances between their values, study its properties, and prove that it is a metric on an appropriately defined space of kernels. We also relate it to various modes of convergence in the space of kernels. Then we consider the problem of approximating solutions to forward--backward systems, where the forward part is a Markov system de… ▽ More We introduce a distance between kernels based on the Wasserstein distances between their values, study its properties, and prove that it is a metric on an appropriately defined space of kernels. We also relate it to various modes of convergence in the space of kernels. Then we consider the problem of approximating solutions to forward--backward systems, where the forward part is a Markov system described by a sequence of kernels, and the backward part calculates the values of a risk measure by operators that may be nonlinear with respect to the system's kernels. We propose to recursively approximate the forward system with the use of the integrated transportation distance between kernels and we estimate the error of the risk evaluation by the errors of individual kernel approximations. We illustrate the results on stopping problems and several well-known risk measures. Then we develop a particle-based numerical procedure, in which the approximate kernels have finite support sets. Finally, we illustrate the efficacy of the approach on the financial problem of pricing an American basket option. △ Less

Submitted 11 November, 2023; originally announced November 2023.

Distributionally Robust Learning with Weakly Convex Losses: Convergence Rates and Finite-Sample Guarantees

Authors: Landi Zhu, Mert Gürbüzbalaban, Andrzej Ruszczyński

Abstract: We consider a distributionally robust stochastic optimization problem and formulate it as a stochastic two-level composition optimization problem with the use of the mean--semideviation risk measure. In this setting, we consider a single time-scale algorithm, involving two versions of the inner function value tracking: linearized tracking of a continuously differentiable loss function, and SPIDER… ▽ More We consider a distributionally robust stochastic optimization problem and formulate it as a stochastic two-level composition optimization problem with the use of the mean--semideviation risk measure. In this setting, we consider a single time-scale algorithm, involving two versions of the inner function value tracking: linearized tracking of a continuously differentiable loss function, and SPIDER tracking of a weakly convex loss function. We adopt the norm of the gradient of the Moreau envelope as our measure of stationarity and show that the sample complexity of $\mathcal{O}(\varepsilon^{-3})$ is possible in both cases, with only the constant larger in the second case. Finally, we demonstrate the performance of our algorithm with a robust learning example and a weakly convex, non-smooth regression example. △ Less

Submitted 9 June, 2023; v1 submitted 16 January, 2023; originally announced January 2023.

Risk Filtering and Risk-Averse Control of Markovian Systems Subject to Model Uncertainty

Authors: Tomasz R. Bielecki, Igor Cialenco, Andrzej Ruszczyński

Abstract: We consider a Markov decision process subject to model uncertainty in a Bayesian framework, where we assume that the state process is observed but its law is unknown to the observer. In addition, while the state process and the controls are observed at time $t$, the actual cost that may depend on the unknown parameter is not known at time $t$. The controller optimizes total cost by using a family… ▽ More We consider a Markov decision process subject to model uncertainty in a Bayesian framework, where we assume that the state process is observed but its law is unknown to the observer. In addition, while the state process and the controls are observed at time $t$, the actual cost that may depend on the unknown parameter is not known at time $t$. The controller optimizes total cost by using a family of special risk measures, that we call risk filters and that are appropriately defined to take into account the model uncertainty of the controlled system. These key features lead to non-standard and non-trivial risk-averse control problems, for which we derive the Bellman principle of optimality. We illustrate the general theory on two practical examples: optimal investment and clinical trials. △ Less

Submitted 18 June, 2022; originally announced June 2022.

A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning

Authors: Mert Gürbüzbalaban, Andrzej Ruszczyński, Landi Zhu

Abstract: We consider a distributionally robust formulation of stochastic optimization problems arising in statistical learning, where robustness is with respect to uncertainty in the underlying data distribution. Our formulation builds on risk-averse optimization techniques and the theory of coherent risk measures. It uses semi-deviation risk for quantifying uncertainty, allowing us to compute solutions th… ▽ More We consider a distributionally robust formulation of stochastic optimization problems arising in statistical learning, where robustness is with respect to uncertainty in the underlying data distribution. Our formulation builds on risk-averse optimization techniques and the theory of coherent risk measures. It uses semi-deviation risk for quantifying uncertainty, allowing us to compute solutions that are robust against perturbations in the population data distribution. We consider a large family of loss functions that can be non-convex and non-smooth and develop an efficient stochastic subgradient method. We prove that it converges to a point satisfying the optimality conditions. To our knowledge, this is the first method with rigorous convergence guarantees in the context of non-convex non-smooth distributionally robust stochastic optimization. Our method can achieve any desired level of robustness with little extra computational cost compared to population risk minimization. We also illustrate the performance of our algorithm on real datasets arising in convex and non-convex supervised learning problems. △ Less

Submitted 7 June, 2021; v1 submitted 8 June, 2020; originally announced June 2020.

Risk-Averse Learning by Temporal Difference Methods

Authors: Umit Kose, Andrzej Ruszczynski

Abstract: We consider reinforcement learning with performance evaluated by a dynamic risk measure. We construct a projected risk-averse dynamic programming equation and study its properties. Then we propose risk-averse counterparts of the methods of temporal differences and we prove their convergence with probability one. We also perform an empirical study on a complex transportation problem. We consider reinforcement learning with performance evaluated by a dynamic risk measure. We construct a projected risk-averse dynamic programming equation and study its properties. Then we propose risk-averse counterparts of the methods of temporal differences and we prove their convergence with probability one. We also perform an empirical study on a complex transportation problem. △ Less

Submitted 2 March, 2020; originally announced March 2020.

MSC Class: 49L20; 62L20; 90C39

A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization

Authors: Andrzej Ruszczynski

Abstract: We propose a single time-scale stochastic subgradient method for constrained optimization of a composition of several nonsmooth and nonconvex functions. The functions are assumed to be locally Lipschitz and differentiable in a generalized sense. Only stochastic estimates of the values and generalized derivatives of the functions are used. The method is parameter-free. We prove convergence with pro… ▽ More We propose a single time-scale stochastic subgradient method for constrained optimization of a composition of several nonsmooth and nonconvex functions. The functions are assumed to be locally Lipschitz and differentiable in a generalized sense. Only stochastic estimates of the values and generalized derivatives of the functions are used. The method is parameter-free. We prove convergence with probability one of the method, by associating with it a system of differential inclusions and devising a nondifferentiable Lyapunov function for this system. For problems with functions having Lipschitz continuous derivatives, the method finds a point satisfying an optimality measure with error of order $1/\sqrt{N}$, after executing $N$ iterations with constant stepsize. △ Less

Submitted 18 December, 2020; v1 submitted 28 January, 2020; originally announced January 2020.

MSC Class: 90C15; 49J52; 62L20

Subregular Recourse in Nonlinear Multistage Stochastic Optimization

Authors: Darinka Dentcheva, Andrzej Ruszczynski

Abstract: We consider nonlinear multistage stochastic optimization problems in the spaces of integrable functions. We allow for nonlinear dynamics and general objective functionals, including dynamic risk measures. We study causal operators describing the dynamics of the system and derive the Clarke subdifferential for a penalty function involving such operators. Then we introduce the concept of subregular… ▽ More We consider nonlinear multistage stochastic optimization problems in the spaces of integrable functions. We allow for nonlinear dynamics and general objective functionals, including dynamic risk measures. We study causal operators describing the dynamics of the system and derive the Clarke subdifferential for a penalty function involving such operators. Then we introduce the concept of subregular recourse in nonlinear multistage stochastic optimization and establish subregularity of the resulting systems in two formulations: with built-in nonanticipativity and with explicit nonanticipativity constraints. Finally, we derive optimality conditions for both formulations and study their relations. △ Less

Submitted 19 January, 2020; originally announced January 2020.

MSC Class: 49K27; 90C15

Convergence of a Stochastic Subgradient Method with Averaging for Nonsmooth Nonconvex Constrained Optimization

Authors: Andrzej Ruszczynski

Abstract: We prove convergence of a single time-scale stochastic subgradient method with subgradient averaging for constrained problems with a nonsmooth and nonconvex objective function having the property of generalized differentiability. As a tool of our analysis, we also prove a chain rule on a path for such functions. We prove convergence of a single time-scale stochastic subgradient method with subgradient averaging for constrained problems with a nonsmooth and nonconvex objective function having the property of generalized differentiability. As a tool of our analysis, we also prove a chain rule on a path for such functions. △ Less

Submitted 16 December, 2019; originally announced December 2019.

MSC Class: 90C15; 90C48

A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization

Authors: Saeed Ghadimi, Andrzej Ruszczyński, Mengdi Wang

Abstract: We study constrained nested stochastic optimization problems in which the objective function is a composition of two smooth functions whose exact values and derivatives are not available. We propose a single time-scale stochastic approximation algorithm, which we call the Nested Averaged Stochastic Approximation (NASA), to find an approximate stationary point of the problem. The algorithm has two… ▽ More We study constrained nested stochastic optimization problems in which the objective function is a composition of two smooth functions whose exact values and derivatives are not available. We propose a single time-scale stochastic approximation algorithm, which we call the Nested Averaged Stochastic Approximation (NASA), to find an approximate stationary point of the problem. The algorithm has two auxiliary averaged sequences (filters) which estimate the gradient of the composite objective function and the inner function value. By using a special Lyapunov function, we show that NASA achieves the sample complexity of ${\cal O}(1/ε^{2})$ for finding an $ε$-approximate stationary point, thus outperforming all extant methods for nested stochastic approximation. Our method and its analysis are the same for both unconstrained and constrained problems, without any need of batch samples for constrained nonconvex stochastic optimization. We also present a simplified variant of the NASA method for solving constrained single level stochastic optimization problems, and we prove the same complexity result for both unconstrained and constrained problems. △ Less

Submitted 6 September, 2019; v1 submitted 3 December, 2018; originally announced December 2018.

Risk Forms: Representation, Disintegration, and Application to Partially Observable Two-Stage Systems

Authors: Darinka Dentcheva, Andrzej Ruszczynski

Abstract: We introduce the concept of a risk form, which is a real functional of two arguments: a measurable function on a Polish space and a measure on that space. We generalize the duality theory and the Kusuoka representation to this setting. For a risk form acting on a product of Polish spaces, we define marginal and conditional forms and we prove a disintegration formula, which represents a risk form a… ▽ More We introduce the concept of a risk form, which is a real functional of two arguments: a measurable function on a Polish space and a measure on that space. We generalize the duality theory and the Kusuoka representation to this setting. For a risk form acting on a product of Polish spaces, we define marginal and conditional forms and we prove a disintegration formula, which represents a risk form as a composition of its marginal and conditional forms. We apply the proposed approach to two-stage stochastic programming problems with partial information and decision-dependent observation distribution. △ Less

Submitted 17 November, 2018; v1 submitted 6 July, 2018; originally announced July 2018.

MSC Class: 90C15; 90C48

Time-Consistent Risk Measures for Continuous-Time Markov Chains

Authors: Darinka Dentcheva, Andrzej Ruszczynski

Abstract: We develop an approach to time-consistent risk evaluation of continuous-time processes in Markov systems. Our analysis is based on dual representation of coherent risk measures, differentiability concepts for multivalued mappings, and a refined concept of time consistency. We prove that the risk measures are defined by a family of risk evaluation functionals (transition risk mappings), which depen… ▽ More We develop an approach to time-consistent risk evaluation of continuous-time processes in Markov systems. Our analysis is based on dual representation of coherent risk measures, differentiability concepts for multivalued mappings, and a refined concept of time consistency. We prove that the risk measures are defined by a family of risk evaluation functionals (transition risk mappings), which depend on state, time, and the transition function. Their dual representations are risk multikernels of the Markov system. We introduce the concept of a semi-derivative of a risk multikernel and use it to generalize the concept of a generator of a Markov process. Using these semi-derivatives, we derive a system of ordinary differential equations that the risk evaluation must satisfy, which generalize the classical backward Kolmogorov equations for Markov processes. Additionally, we construct convergent discrete-time approximations to the continuous-time risk measures. △ Less

Submitted 29 January, 2017; originally announced January 2017.

A Dual Method For Backward Stochastic Differential Equations with Application to Risk Valuation

Authors: Andrzej Ruszczynski, Jianing Yao

Abstract: We propose a numerical recipe for risk evaluation defined by a backward stochastic differential equation. Using dual representation of the risk measure, we convert the risk valuation to a stochastic control problem where the control is a certain Radon-Nikodym derivative process. By exploring the maximum principle, we show that a piecewise-constant dual control provides a good approximation on a sh… ▽ More We propose a numerical recipe for risk evaluation defined by a backward stochastic differential equation. Using dual representation of the risk measure, we convert the risk valuation to a stochastic control problem where the control is a certain Radon-Nikodym derivative process. By exploring the maximum principle, we show that a piecewise-constant dual control provides a good approximation on a short interval. A dynamic programming algorithm extends the approximation to a finite time horizon. Finally, we illustrate the application of the procedure to financial risk management in conjunction with nested simulation and on an multidimensional portfolio valuation problem. △ Less

Submitted 20 August, 2020; v1 submitted 22 January, 2017; originally announced January 2017.

Journal ref: ESAIM: COCV, 2020

Rate of Convergence of the Bundle Method

Authors: Yu Du, Andrzej Ruszczynski

Abstract: We prove that the bundle method for nonsmooth optimization achieves solution accuracy $\varepsilon$ in at most $\mathcal{O}\big(\ln(1/\varepsilon)/\varepsilon\big)$ iterations, if the function is strongly convex. The result is true for the versions of the method with multiple cuts and with cut aggregation. We prove that the bundle method for nonsmooth optimization achieves solution accuracy $\varepsilon$ in at most $\mathcal{O}\big(\ln(1/\varepsilon)/\varepsilon\big)$ iterations, if the function is strongly convex. The result is true for the versions of the method with multiple cuts and with cut aggregation. △ Less

Submitted 3 September, 2016; originally announced September 2016.

Comments: arXiv admin note: text overlap with arXiv:1511.01716

Selective Linearization For Multi-Block Convex Optimization

Authors: Yu Du, Xiaodong Lin, Andrzej Ruszczynski

Abstract: We consider the problem of minimizing a sum of several convex non-smooth functions. We introduce a new algorithm called 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 co… ▽ More We consider the problem of minimizing a sum of several convex non-smooth functions. We introduce a new algorithm called 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. Global convergence is proved and estimates of the convergence rate are derived. Specifically, the number of iterations needed to achieve solution accuracy $\varepsilon$ is of order $\mathcal{O}\big(\ln(1/\varepsilon)/\varepsilon\big)$. We also illustrate the operation of the algorithm on structured regularization problems. △ Less

Submitted 12 August, 2016; v1 submitted 5 November, 2015; originally announced November 2015.

Discrete-Time Approximation of Risk-Averse Control Problems for Diffusion Processes

Authors: Andrzej Ruszczynski, Jianing Yao

Abstract: We consider optimal control problems for diffusion processes, where the objective functional is defined by a time-consistent dynamic risk measure. We focus on coherent risk measures defined by $g$-evaluations. For such problems, we construct a family of time and space perturbed systems with piecewise-constant control functions. We obtain a regularized optimal value function by a special mollificat… ▽ More We consider optimal control problems for diffusion processes, where the objective functional is defined by a time-consistent dynamic risk measure. We focus on coherent risk measures defined by $g$-evaluations. For such problems, we construct a family of time and space perturbed systems with piecewise-constant control functions. We obtain a regularized optimal value function by a special mollification procedure. This allows us to establish a bound on the difference between the optimal value functions of the original problem and of the problem with piecewise-constant controls. △ Less

Submitted 19 August, 2016; v1 submitted 21 August, 2015; originally announced August 2015.

Statistical Estimation of Composite Risk Functionals and Risk Optimization Problems

Authors: Darinka Dentcheva, Spiridon Penev, Andrzej Ruszczynski

Abstract: We address the statistical estimation of composite functionals which may be nonlinear in the probability measure. Our study is motivated by the need to estimate coherent measures of risk, which become increasingly popular in finance, insurance, and other areas associated with optimization under uncertainty and risk. We establish central limit formulae for composite risk functionals. Furthermore, w… ▽ More We address the statistical estimation of composite functionals which may be nonlinear in the probability measure. Our study is motivated by the need to estimate coherent measures of risk, which become increasingly popular in finance, insurance, and other areas associated with optimization under uncertainty and risk. We establish central limit formulae for composite risk functionals. Furthermore, we discuss the asymptotic behavior of optimization problems whose objectives are composite risk functionals and we establish a central limit formula of their optimal values when an estimator of the risk functional is used. While the mathematical structures accommodate commonly used coherent measures of risk, they have more general character, which may be of independent interest. △ Less

Submitted 10 April, 2015; originally announced April 2015.

Process-Based Risk Measures and Risk-Averse Control of Discrete-Time Systems

Authors: Jingnan Fan, Andrzej Ruszczynski

Abstract: For controlled discrete-time stochastic processes we introduce a new class of dynamic risk measures, which we call process-based. Their main features are that they measure risk of processes that are functions of the history of a base process. We introduce a new concept of conditional stochastic time consistency and we derive the structure of process-based risk measures enjoying this property. We s… ▽ More For controlled discrete-time stochastic processes we introduce a new class of dynamic risk measures, which we call process-based. Their main features are that they measure risk of processes that are functions of the history of a base process. We introduce a new concept of conditional stochastic time consistency and we derive the structure of process-based risk measures enjoying this property. We show that they can be equivalently represented by a collection of static law-invariant risk measures on the space of functions of the state of the base process. We apply this result to controlled Markov processes and we derive dynamic programming equations. △ Less

Submitted 29 November, 2016; v1 submitted 10 November, 2014; originally announced November 2014.

MSC Class: 90C40; 49L20

Common Mathematical Foundations of Expected Utility and Dual Utility Theories

Authors: Darinka Dentcheva, Andrzej Ruszczynski

Abstract: We show that the main results of the expected utility and dual utility theories can be derived in a unified way from two fundamental mathematical ideas: the separation principle of convex analysis, and integral representations of continuous linear functionals from functional analysis. Our analysis reveals the dual character of utility functions. We also derive new integral representations of dual… ▽ More We show that the main results of the expected utility and dual utility theories can be derived in a unified way from two fundamental mathematical ideas: the separation principle of convex analysis, and integral representations of continuous linear functionals from functional analysis. Our analysis reveals the dual character of utility functions. We also derive new integral representations of dual utility models. △ Less

Submitted 19 November, 2012; originally announced November 2012.

Risk-Averse Control of Undiscounted Transient Markov Models

Authors: Ozlem Cavus, Andrzej Ruszczynski

Abstract: We use Markov risk measures to formulate a risk-averse version of the undiscounted total cost problem for a transient controlled Markov process. We derive risk-averse dynamic programming equations and we show that a randomized policy may be strictly better than deterministic policies, when risk measures are employed. We illustrate the results on an optimal stopping problem and an organ transplant… ▽ More We use Markov risk measures to formulate a risk-averse version of the undiscounted total cost problem for a transient controlled Markov process. We derive risk-averse dynamic programming equations and we show that a randomized policy may be strictly better than deterministic policies, when risk measures are employed. We illustrate the results on an optimal stopping problem and an organ transplant problem. △ Less

Submitted 22 March, 2014; v1 submitted 24 March, 2012; originally announced March 2012.

MSC Class: 90C39; 90C40 (Primary) 91B30 (Secondary)

Alternating Linearization for Structured Regularization Problems

Authors: Xiaodong Lin, Minh Pham, Andrzej Ruszczynski

Abstract: We adapt the alternating linearization method for proximal decomposition to structured regularization problems, in particular, to the generalized lasso problems. The method is related to two well-known operator splitting methods, the Douglas--Rachford and the Peaceman--Rachford method, but it has descent properties with respect to the objective function. This is achieved by employing a special upd… ▽ More We adapt the alternating linearization method for proximal decomposition to structured regularization problems, in particular, to the generalized lasso problems. The method is related to two well-known operator splitting methods, the Douglas--Rachford and the Peaceman--Rachford method, but it has descent properties with respect to the objective function. This is achieved by employing a special update test, which decides whether it is beneficial to make a Peaceman--Rachford step, any of the two possible Douglas--Rachford steps, or none. The convergence mechanism of the method is related to that of bundle methods of nonsmooth optimization. We also discuss implementation for very large problems, with the use of specialized algorithms and sparse data structures. Finally, we present numerical results for several synthetic and real-world examples, including a three-dimensional fused lasso problem, which illustrate the scalability, efficacy, and accuracy of the method. △ Less

Submitted 24 March, 2014; v1 submitted 31 December, 2011; originally announced January 2012.