1,721,038 research outputs found
Variational Numerical Analysis
No full textThis monograph covers numerical analysis using the tools of variational analysis to handle nonsmooth and nonconvex problems in continuous optimizatio
Convergence in Distribution of Randomized Algorithms: The Case of Partially Separable Optimization
No full textWe present a Markov-chain analysis of blockwise-stochastic algorithms for solving partially block-separable optimization problems. Our main contributions to the extensive literature on these methods are statements about the Markov operators and distributions behind the iterates of stochastic algorithms, and in particular the regularity of Markov operators and rates of convergence of the distributions of the corresponding Markov chains. This provides a detailed characterization of the moments of the sequences beyond just the expected behavior. This also serves as a case study of how randomization restores favorable properties to algorithms that iterations of only partial information destroys. We demonstrate this on stochastic blockwise implementations of the forward-backward and Douglas-Rachford algorithms for nonconvex (and, as a special case, convex), nonsmooth optimization
Convergence in Distribution of Randomized Algorithms: The Case of Partially Separable Optimization
No full textWe present a Markov-chain analysis of blockwise-stochastic algorithms for solving partially
block-separable optimization problems. Our main contributions to the extensive literature on these methods are statements about the Markov operators and distributions behind the iterates of stochastic algorithms, and in particular the regularity of Markov operators and rates of convergence of the distributions
of the corresponding Markov chains. This provides a detailed characterization of the moments of the sequences beyond just the expected behavior. This also serves as a case study of how randomization restores
favorable properties to algorithms that iterations of only partial information destroys. We demonstrate
this on stochastic blockwise implementations of the forward-backward and Douglas-Rachford algorithms
for nonconvex (and, as a special case, convex), nonsmooth optimization
Variational Numerical Analysis
No full textThis monograph covers numerical analysis using the tools of variational analysis to handle nonsmooth and nonconvex problems in continuous optimizatio
Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
No full textWe study the convergence of an iterative projection/reflection algorithm originally proposed for solving what are known as phase retrieval problems in optics. There are two features that frustrate any analysis of iterative methods for solving the phase retrieval problem: nonconvexity and infeasibility. The algorithm that we developed, called relaxed averaged alternating reflections (RAAR), was designed primarily to address infeasibility, though our strategy has advantages for nonconvex problems as well. In the present work we investigate the asymptotic behavior of the RAAR algorithm for the general problem of finding points that achieve the minimum distance between two closed convex sets in a Hilbert space with empty intersection, and for the problem of finding points that achieve a local minimum distance between one closed convex set and a closed prox-regular set, also possibly nonintersecting. The nonconvex theory includes and expands prior results limited to convex sets with nonempty intersection. To place the RAAR algorithm in context, we develop parallel statements about the standard alternating projections algorithm and gradient descent. All of the various algorithms are unified as instances of iterated averaged alternating proximal reflectors applied to a sum of regularized maximal monotone mappings
The no response test - A sampling method for inverse scattering problems
No full textWe describe a novel technique, which we call the no response test, to locate the support of a scatterer from knowledge of a far field pattern of a scattered acoustic wave. The method uses a set of sampling surfaces and a special test response to detect the support of a scatterer without a priori knowledge of the physical properties of the scatterer. Specifically, the method does not depend on information about whether the scatterer is penetrable or impenetrable nor does it depend on any knowledge of the nature of the scatterer (absorbing, reflecting, etc.). In contrast to previous sampling algorithms, the techniques described here enable one to locate obstacles or inhomogeneities from the far field pattern of only one incident field-the no response test is a one-wave method. We investigate the theoretical basis for the no response test and derive a one-wave uniqueness proof for a region containing the scatterer. We show how to find the object within this region. We demonstrate the applicability of the method by reconstructing sound-soft, sound-hard, impedance, and inhomogeneous medium scatterers in two dimensions from one wave with full and limited aperture far-field data
Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
No full textWe present a unified treatment of the abstract problem of finding the best approximation between a cone and spheres in the image of affine transformations. Prominent instances of this problem are phase retrieval and source localization. The common geometry binding these problems permits a generic application of algorithmic ideas and abstract convergence results for nonconvex optimization. We organize variational models for this problem into three different classes and derive the main algorithmic approaches within these classes (13 in all). We identify the central ideas underlying these methods and provide thorough numerical benchmarks comparing their performance on synthetic and laboratory data. The software and data of our experiments are all publicly accessible. We also introduce one new algorithm, a cyclic relaxed Douglas--Rachford algorithm, which outperforms all other algorithms by every measure: speed, stability, and accuracy. The analysis of this algorithm remains open
Random Function Iterations for Stochastic Fixed Point Problems
No full textWe study the convergence of random function iterations for finding an invariant measure of the
corresponding Markov operator. We call the problem of finding such an invariant measure the
stochastic fixed point problem. This generalizes earlier work of the authors [Random function it-
erations for consistent stochastic feasibility, Numer. Funct. Analysis Opt. 40/4 (2019) 386–420]
studying the stochastic feasibility problem, namely, to find points that are, with probability 1,
fixed points of the random functions. When no such points exist, the stochastic feasibility problem
is called inconsistent, but still under certain assumptions, the more general stochastic fixed point
problem has a solution and the random function iteration converges to an invariant measure for
the corresponding Markov operator. We show how common structures in deterministic fixed point
theory can be exploited to establish existence of invariant measures and convergence in distribution
of the Markov chain. This framework specializes to many applications of current interest includ-
ing, for instance, stochastic algorithms for large-scale distributed computation, and deterministic
iterative procedures with computational error. The theory developed in this study provides a solid
basis for describing the convergence of simple computational methods without the assumption of
infinite precision arithmetic or vanishing computational errors
- …
