Adaptive Euler-Maruyama Method for SDEs with Nonglobally Lipschitz Drift I: Strong Convergence of Order 1/2 on a Finite Time IntervalResearch Paper
The explicit Euler–Maruyama scheme is the standard way to simulate a stochastic differential equation
254 missions · 180 completed
The explicit Euler–Maruyama scheme is the standard way to simulate a stochastic differential equation
Quasi-Newton methods replace the Hessian of an objective by a matrix that is updated from observed pairs of steps and gradient changes. The secant equation asks the new matrix to map the observed steps to the observed changes . The best-known update is BFGS, which for simultaneous pairs reads
Nonnegative matrix factorization (NMF) approximates a data matrix by a product of two nonnegative factors. Adding a cap on the number of nonzero entries of each factor gives sparse NMF, used in signal separation, text mining and image analysis because sparse nonnegative factors are easier to interpret. Bolte, Sabach and Teboulle…
Many problems in data analysis and signal processing are posed as minimizing a sum of three terms over two blocks of variables: a nonsmooth function of the first block, a nonsmooth function of the second block, and a smooth coupling term. Nonnegative and sparse matrix factorization, blind deconvolution and dictionary learning all have this form, with…
Many estimation problems in signal processing and statistics look for a vector with few nonzero entries that fits data well. Compressed sensing (Donoho 2006) recovers a sparse from linear measurements by minimizing over sparse vectors. Sub-wavelength optical imaging and phase retrieval (Shechtman, Eldar, Szameit, Segev 2011) lead to the same…
Many problems in signal processing, statistics and machine learning ask for a minimizer of a smooth loss among vectors with few nonzero entries: compressed sensing with a nonlinear measurement model, sparse regression with a non-quadratic loss, sparse phase retrieval. The common abstraction is the sparsity constrained problem
Many problems in signal processing, statistics and machine learning ask for a minimizer of a smooth loss among vectors with few nonzero entries: compressed sensing with a nonlinear measurement model, sparse regression with a non-quadratic loss, sparse phase retrieval. The common abstraction is the sparsity constrained problem
A differential variational inequality (DVI) couples an ordinary differential equation with a finite-dimensional variational inequality whose solution enters the dynamics as a control. Contact mechanics with friction, electrical circuits with diodes, dynamic traffic equilibria, hybrid engineering systems and the continuous-time limits of Nash games all have…
Random coordinate descent minimizes a smooth convex function by updating one coordinate at a time, chosen at random. Each iteration needs a single partial derivative instead of the full gradient, which is what makes the method usable on problems whose dimension is in the millions or billions ("huge-scale" problems). Nesterov's…
A differential variational inequality (DVI) couples an ordinary differential equation with a finite-dimensional variational inequality whose solution acts as an algebraic input to the dynamics. The class contains linear complementarity systems, mechanical systems with unilateral contact and friction, dynamic Nash games and many hybrid engineering models.…
Quasi-Newton methods such as BFGS were designed for smooth objectives, yet in practice they are routinely and successfully applied to nonsmooth functions. Lewis and Overton (Math. Program. 141 (2013) 135–163) study why. A quasi-Newton step needs a step length along each search direction, and on a nonsmooth function the usual line searches have to decide…
Stochastic differential equations (SDEs) are simulated almost always by time-stepping schemes, and the cheapest and most widely used is the explicit Euler (Euler–Maruyama) scheme. Its strong convergence with order is classical when the coefficients are globally Lipschitz. Many models in applications are not: Langevin dynamics with confining…
A backward stochastic differential equation (BSDE) prescribes the value of a process at a terminal time and asks for an adapted process that reaches it while following a given drift. In mathematical finance the price of a contingent claim, and its hedging strategy, solve such an equation; when the market has frictions (different borrowing and lending rates,…
Backward stochastic differential equations (BSDEs) describe the price and the hedge of a contingent claim in models with nonlinear pricing rules (differential interest rates, funding costs, reflected or constrained claims), and give probabilistic representations of semilinear parabolic PDEs (El Karoui, Peng and Quenez, 1997). Their numerical solution in…
Many objective functions in engineering and statistics are nonsmooth and nonconvex: the spectral abscissa of a parametrized matrix, the largest eigenvalue of a symmetric matrix function, the norm of a closed-loop system, or a maximum of finitely many smooth functions. Such functions are typically differentiable almost everywhere, yet their…
A backward stochastic differential equation (BSDE) prescribes the terminal value of a process instead of its initial value. Pardoux and Peng (1990) proved that a BSDE with Lipschitz driver has a unique adapted solution. Coupled with a forward diffusion it gives a forward–backward SDE (FBSDE), which represents the solution of a semilinear parabolic PDE…
Optimal control problems with pointwise bounds on the control, such as
Many problems in signal processing, statistics and decision theory have two blocks of variables coupled by a smooth term: matrix factorization, blind deconvolution, feasibility problems for two sets, and models of two agents adjusting their decisions in turn. Minimizing over one block at a time (alternating minimization, or Gauss–Seidel) is the natural…
The trust-region subproblem — minimizing a quadratic, possibly nonconvex, over a Euclidean ball — is the inner step of every trust-region method for nonlinear optimization, and it also appears in regularized least squares and in the analysis of quadratic constraints. It is one of the few nonconvex problems whose global minimizers are characterized exactly:…
Many problems in optimization and equilibrium modelling reduce to a system of nonsmooth equations with locally Lipschitz but not differentiable: reformulations of nonlinear complementarity problems, variational inequalities and Karush–Kuhn–Tucker systems through the function or piecewise smooth maps. Newton-type…
The Nelder–Mead simplex method (Nelder and Mead, 1965) is a derivative-free method for unconstrained minimization. It keeps a simplex of points in and replaces the worst vertex by a reflected, expanded or contracted trial point, using only comparisons of function values. It is one of the most widely used methods in practice, available in…
Solving a system of nonlinear equations , with continuously differentiable, is a basic task in numerical analysis and optimization: it is the inner step of interior-point and sequential quadratic programming methods, of implicit time-stepping for differential equations, and of equilibrium computations in operations…
Interior-point methods transformed linear programming in the 1980s and 1990s. A natural question was whether the same ideas carry over to nonlinear programming, where the objective and the constraints are general smooth functions. Sequential quadratic programming (SQP) methods were then the method of choice for small and medium nonlinear problems, but each…
Bound constrained minimization asks for a low value of a smooth objective while each variable stays between prescribed lower and upper limits. Such limits occur in nonlinear optimization models even when the objective itself has no special convexity. Coleman and Li's interior reflective method was designed to approach a solution from inside those limits…
Truncated-Newton methods minimize a smooth function by taking, at each iterate , a search direction obtained by solving the Newton equation only approximately, with the linear conjugate gradient (CG) method. Here is the gradient and the Hessian of . The approach was analysed by Dembo and Steihaug (Math.…