Quantitative convergence analysis of iterated expansive, set-valued mappings D. R. Luke, M.K. Tam and N.H. Thao, Mathematics of Operations Research (to appear). Abstract: We develop a framework for quantitative convergence analysis of Picard iterations of expansive set-valued fixed point mappings. There are two key components of the analysis. The first is a natural generalization of single-valued averaged mappings to expansive, set-valued mappings that characterizes a type of strong calmness of the fixed point mapping. The second component to this analysis is an extension of the well-established notion of metric subregularity – or inverse calmness – of the mapping at fixed points. Convergence of expansive fixed point iterations is proved using these two properties, and quantitative estimates are a natural byproduct of the framework. To demonstrate the application of the theory, we prove for the first time a number of results showing local linear convergence of nonconvex cyclic projections for inconsistent (and consistent) feasibility problems, local linear convergence of the forward-backward algorithm for structured optimization without convexity, strong or otherwise, and local linear convergence of the Douglas–Rachford algorithm for structured nonconvex minimization. This theory includes earlier approaches for known results, convex and nonconvex, as special cases. [arXiv] |
Algorithms Based on Unions of Nonexpansive Maps M.K. Tam Optimization Letters, (2018). Abstract: In this note, we consider a framework for the analysis of iterative algorithms which can described in terms of a structured set-valued operator. More precisely, at each point in the ambient space, we assume that the value of operator can be expressed as a finite union of values of single-valued paracontracting operators. Our main result, which shows that the associated fixed point iteration is locally convergent around strong fixed points, generalises a theorem due to Bauschke and Noll (2014). [article] [arXiv] |
Block-coordinate primal-dual method for
nonsmooth minimization over linear constraints D. R. Luke and Y. Malitsky. In Distributed and Large-Scale Optimization edited by P. Giselsson and A. Rantzer. Springer Verlag, 2018. Abstract: We consider the problem of minimizing a convex, separable, nonsmooth function subject to linear constraints. The numerical method we propose is a block-coordinate extension of the Chambolle-Pock primal-dual algorithm. We prove convergence of the method without resorting to assumptions like smoothness or strong convexity of the objective, full-rank condition on the matrix, strong duality or even consistency of the linear system. Freedom from imposing the latter assumption permits convergence guarantees for misspecified or noisy systems. [arXiv] |
Implicit Error Bounds for Picard Iterations on Hilbert
Spaces D. R. Luke, M.K. Tam and N.H. Thao, Vietnam J. Mathematics 46(2), 243-258 (2018). DOI: 10.1007/s10013-018-0279-x. Abstract: We investigate the role of error bounds, or metric subregularity, in the convergence of Picard iterations of nonexpansive maps in Hilbert spaces. Our main results show, on one hand, that the existence of an error bound is sufficient for strong convergence and, on the other hand, that an error bound exists on bounded sets for nonexpansive mappings possessing a fixed point whenever the space is finite dimensional. In a Hilbert space setting, we show that a monotonicity property of the distances of the Picard iterations is all that is needed to guarantee the existence of an error bound. The same monotonicity assumption turns out also to guarantee that the distance of Picard iterates to the fixed point set converges to zero. Our results provide a quantitative characterization of strong convergence as well as new criteria for when strong, as opposed to just weak, convergence holds. [article] |
A feasibility approach for constructing combinatorial designs of circulant type F.J. Aragón Artacho, R. Campoy, I. Kotsireas, M. K. Tam, Journal of Combinatorial Optimization, 35(4):1061--1085, (2018). Abstract: In this work, we propose an optimization approach for constructing various classes of circulant combinatorial designs that can be defined in terms of autocorrelations. The problem is formulated as a so-called feasibility problem having three sets, to which the Douglas-Rachford projection algorithm is applied. The approach is illustrated on three different classes of circulant combinatorial designs: circulant weighing matrices, D-optimal matrices, and Hadamard matrices with two circulant cores. Furthermore, we explicitly construct two new circulant weighing matrices, a CW(126,64) and a CW(198,100), whose existence was previously marked as unresolved in the most recent version of Strassler's table. [article] [arXiv] |
Symbolic computation with monotone operators F. Lauster, D. R. Luke and M.K. Tam, J. Set-Valued and Variational Analysis (2018) 26:353--368, DOI 10.1007/s11228-017-0418-7 (arXiv:1703.05946) Abstract: We consider a class of monotone operators which are appropriate for symbolic representation and manipulation within a computer algebra system. Various structural properties of the class (e.g., closure under taking inverses, resolvents) are investigated as well as the role played by maximal monotonicity within the class. In particular, we show that there is a natural correspondence between our class of monotone operators and the subdifferentials of convex functions belonging to a class of convex functions deemed suitable for symbolic computation of Fenchel conjugates which were previously studied by Bauschke & von Mohrenschildt and by Borwein & Hamilton. A number of illustrative examples utilizing the introduced class of operators are provided including computation of proximity operators, recovery of a convex penalty function associated with the hard thresholding operator, and computation of superexpectations, superdistributions and superquantiles with specialization to risk measures. [arXiv] [article] [Code] |
A Globally Linearly Convergent Method for Pointwise Quadratically Supportable Convex-Concave Saddle Point Problems D. R. Luke and R. Shefi J. Math. Anal. Appl. 457(2), 1568--1590 (2018). Abstract: We study the Proximal Alternating Predictor-Corrector (PAPC) algorithm introduced recently by Drori, Sabach and Teboulle to solve nonsmooth structured convex-concave saddle point problems consisting of the sum of a smooth convex function, a finite collection of nonsmooth convex functions and bilinear terms. We introduce the notion of pointwise quadratic supportability, which is a relaxation of a standard strong convexity assumption and allows us to show that the primal sequence is R-linearly convergent to an optimal solution and the primal-dual sequence is globally Q-linearly convergent. We illustrate the proposed method on total variation denoising problems and on locally adaptive estimation in signal/image deconvolution and denoising with multiresolution statistical constraints. [arXiv] |
Set Regularities and Feasibility Problems A. Y. Kruger, D. R. Luke, and N. H. Thao, Mathematical Programming B, (2018) 168: 279--311. Abstract: We synthesize and unify notions of regularity, both of individual sets and of collections of sets, as they appear in the convergence theory of projection methods for consistent feasibility problems. Several new characterizations of regularities are presented which shed light on the relations between seemingly different ideas and point to possible necessary conditions for local linear convergence of fundamental algorithms. [Link] [arXiv] |
Tangent and normal cones for low-rank matrices S. Hosseini, D. R. Luke, A. Uschmajew Institute for Numerical Simmulation Preprint No. 1715, October 2017. Abstract: In [D. R. Luke,J. Math. Imaging Vision, 47(3):231-238, 2013] the structure of the Mordukhovich normal cone to varieties of low rank matrices at rank-deficient points has been determined. A simplified proof of that result is presented here. As a corollary we obtain the corresponding Clarke normal cone. The results are put into context of first-order optimality conditions for low-rank matrix optimization problems. [preprint] |
About subtransversality of collections of sets A. Y. Kruger, D. R. Luke, and N.H. Thao, Set-Valued and Variational Analysis, 25(4), 701-729 (2017). Abstract: We provide dual sufficient conditions for subtransversality of collections of sets in an Asplund space setting. For the convex case, we formulate a necessary and sufficient dual criterion of subtransversality in general Banach spaces. Our more general results suggest an intermediate notion of subtransversality, what we call {\em weak intrinsic subtransversality}, which lies between intrinsic transversality and subtransversality in Asplund spaces. [article] [arXiv] |
A Simple Globally Convergent Algorithm for the Nonsmooth Nonconvex Single Source Localization Problem D. R. Luke, S. Sabach and M. Teboulle, J. Global Optimization (2017) 69: 889--909. https://doi.org/10.1007/s10898-017-0545-6. Abstract: We study the single source localization problem which consists of minimizing the squared sum of the errors, also known as the maximum likelihood formulation of the problem. The resulting optimization model is not only nonconvex but is also nonsmooth. We first derive a novel equivalent reformulation as a smooth constrained nonconvex minimization problem. The resulting reformulation allows for deriving a delightfully simple algorithm that does not rely on smoothing or convex relaxations. The proposed algorithm is proven to generate bounded iterates which globally converge to critical points of the original objective function of the source localization problem. Numerical examples are presented to demonstrate the performance of our algorithm. [article] |
Phase Retrieval, What's New? D. R. Luke, SIAG/OPT Views and News, 25(1):1--5 (2017) Abstract: Ask an engineer to solve a problem and she will come back in a day or so with something that seems to work well enough most of the time. Ask a mathematician to solve the same problem and he will return many months later with an exact but unimplementable solution to a different problem. I'm sure most readers of this newsletter have heard some variation of that joke. But a true story lies somewhere in there, a story that is writ large with the phase retrieval problem. [Link] |
Regularity Properties of Non-Negative Sparsity Sets M. K. Tam, Journal of Mathematical Analysis and Applications, 447(2):758-777, 2017. Abstract: This paper investigates regularity properties of two non-negative sparsity sets: non-negative sparse vectors, and low-rank positive semi-definite matrices. Novel formulae for their Mordukhovich normal cones are given and used to formulate sufficient conditions for non-convex notions of regularity to hold. Our results provide a useful tool for justifying the application of projection methods to certain rank constrained feasibility problems. [Link] [arXiv] |
Lagrange multipliers, (exact) regularization and error bounds for monotone variational inequalities C. Charitha, J. Dutta, and D. R. Luke, Mathematical Programming A, 161(1):519-549, 2017. Abstract: We examine two central regularization strategies for monotone variational inequalities, the first a direct regularization of the operative monotone mapping, and the second via regularization of the associated dual gap function. A key link in the relationship between the solution sets to these various regularized problems is the idea of exact regularization, which, in turn, is fundamentally associated with the existence of Lagrange multipliers for the regularized variational inequality. A regularization is said to be exact if a solution to the regularized problem is a solution to the unregularized problem for all parameters beyond a certain value. The Lagrange multipliers corresponding to a particular regularization of a variational inequality, on the other hand, are defined via the dual gap function. Our analysis suggests various conceptual, iteratively regularized numerical schemes, for which we provide error bounds, and hence stopping criteria, under the additional assumption that the solution set to the unregularized problem is what we call weakly sharp of order greater than one. [Link] [arXiv] |
Regularity of collections of sets and convergence of inexact alternating projections. A. Y. Kruger and N. H. Thao, J. Convex Anal, 23 (2016), no. 3, 823–847. Abstract: In this paper the authors compare the uniform regularity property of collections of sets by A. S. Lewis, D. R. Luke and J. Malick in [Found. Comput. Math. 9(2009),no. 4, 485–513] and relaxed regularity properties given by H. H. Bauschke, Luke, H. M. Phan and X. Wang (BLPW) in [Set-Valued Var. Anal.21 (2013), no. 3,431–473 and 475-501] D. Drusvyatskiy, A. D. Ioffe and Lewis (DIL) in [Found. Comput. Math. 15 (2015),no. 6, 1637–1651], and D. Noll and A. Rondepierre (NR) in [Found. Comput. Math.16(2016), no. 2, 425–455]. Equivalent characterizations of these regularity properties in terms of metric, dual normal cone, and angle are provided. Two examples are provided to show that BLPW-DIL-restricted regularity and DIL-restricted regularity are different. They study inexact alternating projections for two possibly nonconvex sets. Under the assumptions of DIL-restricted regularity and uniform regularity together with the super-regularity of one set, respectively, the authors establish R-linear convergence rates. [Link] [arXiv] |
Local Linear Convergence of the ADMM/Douglas-Rachford Algorithms without Strong Convexity and Application to Statistical Imaging T. Aspelmeier, C. Charitha, and D. R. Luke, SIAM J. Imaging Sci., 9(2):842-868, 2016. Abstract: We consider the problem of minimizing the sum of a convex function and a convex function composed with an injective linear mapping. For such problems, subject to a coercivity condition at fixed points of the corresponding Picard iteration, iterates of the alternating directions method of multipliers converge locally linearly to points from which the solution to the original problem can be computed. Our proof strategy uses duality and strong metric subregularity of the Douglas-Rachford fixed point mapping. Our analysis does not require strong convexity and yields error bounds to the set of model solutions. We show in particular that convex piecewise linear-quadratic functions naturally satisfy the requirements of the theory, guaranteeing eventual linear convergence of both the Douglas--Rachford algorithm and the alternating directions method of multipliers for this class of objectives under mild assumptions on the set of fixed points. We demonstrate this result on quantitative image deconvolution and denoising with multiresolution statistical constraints. [Link] [Preprint] |
Proximal Heterogeneous Block Implicit-Explicit Method and Application to Blind Ptychographic Diffraction Imaging R. Hesse, D. R. Luke, S. Sabach, and M. K. Tam, SIAM J. Imaging Sci., 8(1):426-457, 2015. Abstract: We propose a general alternating minimization algorithm for nonconvex optimization problems with separable structure and nonconvex coupling between blocks of variables. To fix our ideas, we apply the methodology to the problem of blind ptychographic imaging. Compared to other schemes in the literature, our approach differs in two ways: (i) it is posed within a clear mathematical framework with practical verifiable assumptions, and (ii) under the given assumptions, it is provably convergent to critical points. A numerical comparison of our proposed algorithm with the current state of the art on simulated and experimental data validates our approach and points toward directions for further improvement. [Link] [arXiv] |
Quantitative characterizations of regularity properties of collections of sets A. Y. Kruger and Nguyen Thao, J. Optim. Theory Appl, 164 (2015), no. 1, 41-67. Abstract: Several primal and dual quantitative characterizations of regularity properties of collections of sets in normed linear spaces are discussed. Relationships between regularity properties of collections of sets and those of set-valued mappings are provided. [Link] |
Quantitative characterizations of regularity properties of collections of sets Khanh, Phan Q, A. Y. Kruger and Nguyen Thao, SIAM J. Optim. 25 (2015), no. 4, 2561–2588. Abstract: A general nonlinear regularity model for a set-valued mapping $F:X\times\mathbb{R}_+\rightrightarrows Y$, where $X$ and $Y$ are metric spaces, is studied using special iteration procedures, going back to Banach, Schauder, Lyusternik, and Graves. Namely, we revise the induction theorem from Khanh [J. Math. Anal. Appl., 118 (1986), pp. 519--534] and employ it to obtain basic estimates for exploring regularity/openness properties. We also show that it can serve as a substitution for the Ekeland variational principle when establishing other regularity criteria. Then, we apply the induction theorem and the mentioned estimates to establish criteria for both global and local versions of regularity/openness properties for our model and demonstrate how the definitions and criteria translate into the conventional setting of a set-valued mapping $F:X\rightrightarrows Y$. An application to second-order necessary optimality conditions for a nonsmooth set-valued optimization problem with mixed constraints is provided. [Link] |
Duality and Convex Programming J. M. Borwein and D. R. Luke, pp 229--270 in Handbook of Mathematical Methods in Imaging, 2nd Edition, Otmar Scherzer, ed. Springer Verlag (2015). Abstract: This chapter surveys key concepts in convex duality theory and their application to the analysis and numerical solution of problem archetypes in imaging. [Link] [Preprint] |
Activity Identification and Local Linear Convergence of Douglas-Rachford/ADMM under Partial Smoothness J. Liang, J. Fadili, G. Peyre and D. R. Luke Conference on Scale Space and Variational Methods in Computer Vision (2015) Abstract: Convex optimization has become ubiquitous in most quantitative disciplines of science, including variational image processing. Proximal splitting algorithms are becoming popular to solve such structured convex optimization problems. Within this class of algorithms, Douglas- Rachford (DR) and ADMM are designed to minimize the sum of two proper lower semi-continuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local convergence behaviour of DR (resp. ADMM) when the involved functions (resp. their Legendre-Fenchel conjugates) are moreover partly smooth. More precisely, when both of the two functions (resp. their conjugates) are partly smooth relative to their respective manifolds, we show that DR (resp. ADMM) identi es these manifolds in nite time. Moreover, when these manifolds are ane or linear, we prove that DR/ADMM is locally linearly convergent with a rate in terms of the cosine of the Friedrichs angle between the tangent spaces of the identi ed manifolds. This is illustrated by several concrete examples and supported by numerical experiments. [arXiv Preprint] |
Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility R. Hesse, D. R. Luke, and P. Neumann, IEEE Transactions on Signal Processing, 62(18):4868-4881, 2014 Abstract: The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved nonconvex relaxations. In this work we consider elementary methods based on projections for solving a sparse feasibility problem without employing convex heuristics. It has been shown recently that, locally, the fundamental method of alternating projections must converge linearly to a solution to the sparse feasibility problem with an affine constraint. In this paper we apply different analytical tools that allow us to show global linear convergence of alternating projections under familiar constraint qualifications. These analytical tools can also be applied to other algorithms. This is demonstrated with the prominent Douglas-Rachford algorithm where we establish local linear convergence of this method applied to the sparse affine feasibility problem. [Link] [Preprint] |
Restricted normal cones and sparsity optimization with affine constraints H. H. Bauschke, D. R. Luke, H. M. Phan, and X. Wang, Foundations of Computational Mathematics 14(1):63--83 (2014). Abstract: The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved non convex relaxations. In this paper we consider the elementary method of alternating projections (MAP) for solving the sparsity optimization problem without employing convex heuristics. In a parallel paper we recently introduced the restricted normal cone which generalizes the classical Mordukhovich normal cone and reconciles some fundamental gaps in the theory of sufficient conditions for local linear convergence of the MAP algorithm. We use the restricted normal cone together with the notion of superregularity, which is naturally satisfied for the affine sparse optimization problem, to obtain local linear convergence results with estimates for the radius of convergence of the MAP algorithm applied to sparsity optimization with an affine constraint. [Link] [arXiv] |
Reconstruction of wave front and object for inline holography from a set of detection planes J. Hagemann, A.-L. Robisch, D. R. Luke, C. Homann, T. Hohage, P. Cloetens, H. Suhonen and T. Salditt, Optics Express 22(2014): 11552-11569. Abstract: We illustrate the errors inherent in the conventional empty beam correction of full field X-ray propagation imaging, i.e. the division of intensities in the detection plane measured with an object in the beam by the intensity pattern measured without the object, i.e. the empty beam intensity pattern. The error of this conventional approximation is controlled by the ratio of the source size to the smallest feature in the object, as is shown by numerical simulation. In a second step, we investigate how to overcome the flawed empty beam division by simultaneous reconstruction of the probing wavefront (probe) and of the object, based on measurements in several detection planes (multi-projection approach). The algorithmic scheme is demonstrated numerically and experimentally, using the defocus wavefront of the hard X-ray nanoprobe setup at the European Synchrotron Radiation Facility. [Link] |
Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems R. Hesse, and D. R. Luke, SIAM J. Optim., 23(4):2397-2419, 2013. Abstract: We consider projection algorithms for solving (nonconvex) feasibility problems in Euclidean spaces. Of special interest are the method of alternating projections (AP) and the Douglas--Rachford algorithm (DR). In the case of convex feasibility, firm nonexpansiveness of projection mappings is a global property that yields global convergence of AP and for consistent problems DR. A notion of local subfirm nonexpansiveness with respect to the intersection is introduced for consistent feasibility problems. This, together with a coercivity condition that relates to the regularity of the collection of sets at points in the intersection, yields local linear convergence of AP for a wide class of nonconvex problems and even local linear convergence of nonconvex instances of the DR algorithm. [Link] [arXiv] |
Restricted normal cones and the method of alternating projections: applications H. H. Bauschke, D. R. Luke, H. M. Phan, and X. Wang, J. Set-Valued and Variational Analysis 21:475--501 (2013) Abstract: The method of alternating projections (MAP) is a common method for solving feasibility prob- lems. While employed traditionally to subspaces or to convex sets, little was known about the behavior of the MAP in the nonconvex case until 2009, when Lewis, Luke, and Malick de- rived local linear convergence results provided that a condition involving normal cones holds and at least one of the sets is superregular (a property less restrictive than convexity). How- ever, their results failed to capture very simple classical convex instances such as two lines in a three-dimensional space. In this paper, we extend and develop the Lewis-Luke-Malick framework so that not only any two linear subspaces but also any two closed convex sets whose relative interiors meet are covered. We also allow for sets that are more structured such as unions of convex sets. The key tool required is the restricted normal cone, which is a generalization of the classical Mordukhovich normal cone. Numerous examples are provided to illustrate the theory. [Link] [Preprint] |
Restricted normal cones and the method of alternating projections: theory H. H. Bauschke, D. R. Luke, H. M. Phan, and X. Wang, J. Set-Valued and Variational Analysis 21:431--473 (2013) Abstract: n this paper, we introduce and develop the theory of restricted normal cones which generalize the classical Mordukhovich normal cone. We thoroughly study these objects from the viewpoint of constraint qualifications and regularity. Numerous examples are provided to illustrate the theory. This work provides the theoretical underpinning for a subsequent article in which these tools are applied to obtain a convergence analysis of the method of alternating projections for nonconvex sets. [Link] [Preprint] |
Institute for Numerical and
Applied Mathematics
University of Göttingen
Lotzestr. 16-18
37083 Göttingen, Germany
Directions