Stochastic first-order methods for convex and nonconvex functional constrained optimization

Mathematical Programming - Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in...     

From error bounds to the complexity of first-order descent methods for convex functions

This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-?ojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Hölderian growth). A counterexample shows that the equivalence is no longer true for extremely flat functions. This fact reveals the relevance of an approach based on KL inequality. In a second stage, we show how KL inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence in the spirit of the famous majorant method of Kantorovich. Our result applies to a very simple abstract scheme that covers a wide class of descent methods. As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple method: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form \(O(q^{k})\) where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with \(\ell ^1\) regularization.     

Iteration-complexity of first-order penalty methods for convex programming

This paper considers a special but broad class of convex programming problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. It studies the computational complexity of quadratic penalty based methods for solving the above class of problems. An iteration of these methods, which is simply an iteration of Nesterov’s optimal method (or one of its variants) for approximately solving a smooth penalization subproblem, consists of one or two projections onto the simple convex set. Iteration-complexity bounds expressed in terms of the latter type of iterations are derived for two quadratic penalty based variants, namely: one which applies the quadratic penalty method directly to the original problem and another one which applies the latter method to a perturbation of the original problem obtained by adding a small quadratic term to its objective function.     

Linear stability of stiff differential equation solvers

When a linear multistep method is used to solve a stiff differential equationy(x)=f(y(x)), producing an approximationy _n toy(x _n ), it is preferable to approximate the valuey(x _n ) in subsequent formulae by a value which exactly satisfies the corrector equation used, rather than by the valuef(y _n ). We prove that the resulting method is stable if the underlying corrector equation is absolutely stable, provided that the residuals obtained in solving successive nonlinear equations remain uniformly bounded.     

Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates

A general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed by Scheinberg and Tang (Math Program 160:495–529, 2016) and a sublinear global convergence rate has been established. In this paper, we analyze the global convergence rate of this method, in the both exact and inexact settings, in the case when the objective function is strongly convex. We also investigate a practical variant of this method by establishing a simple stopping criterion for the subproblem optimization. Furthermore, we consider an accelerated variant, based on FISTA of Beck and Teboulle (SIAM 2:183–202, 2009), to the proximal quasi-Newton algorithm. Jiang et al. (SIAM 22:1042–1064, 2012) considered a similar accelerated method, where the convergence rate analysis relies on very strong impractical assumptions on Hessian estimates. We present a modified analysis while relaxing these assumptions and perform a numerical comparison of the accelerated proximal quasi-Newton algorithm and the regular one. Our analysis and computational results show that acceleration may not bring any benefit in the quasi-Newton setting.     

Multiple periodic solutions for system of first-order differential equation

Sufficient conditions have been obtained for the existence of at least two non-negative periodic solutions to a system of first-order nonlinear functional differential equations. Applications to some ecological models are given.     

A nonlocal problem for a first-order partial differential equation

In this paper we study a nonlocal problem for a first-order partial differential equation with an integral condition instead of the standard boundary one. We prove that the problem under consideration is uniquely solvable.     

A numerical evaluation of solvers for the periodic Riccati differential equation

Efficient and accurate structure exploiting numerical methods for solving the periodic Riccati differential equation (PRDE) are addressed. Such methods are essential, for example, to design periodic feedback controllers for periodic control systems. Three recently proposed methods for solving the PRDE are presented and evaluated on challenging periodic linear artificial systems with known solutions and applied to the stabilization of periodic motions of mechanical systems. The first two methods are of the type multiple shooting and rely on computing the stable invariant subspace of an associated Hamiltonian system. The stable subspace is determined using either algorithms for computing an ordered periodic real Schur form of a cyclic matrix sequence, or a recently proposed method which implicitly constructs a stable deflating subspace from an associated lifted pencil. The third method reformulates the PRDE as a convex optimization problem where the stabilizing solution is approximated by its truncated Fourier series. As known, this reformulation leads to a semidefinite programming problem with linear matrix inequality constraints admitting an effective numerical realization. The numerical evaluation of the PRDE methods, with focus on the number of states (n) and the length of the period (T) of the periodic systems considered, includes both quantitative and qualitative results.     

Towards adaptive finite element schemes for partial differential Volterra equation solvers

We give a brief indication of how elliptic, parabolic and hyperbolic partial differential equations with memory arise when modelling viscoelastic materials. We then point out the urgent need for adaptive solvers for these problems and, employing the methodology of Eriksson, Johnson et al. (e.g., SIAM J. Numer. Anal. 28 (1991)), we given ana posteriori error estimate for a model two-point hereditary boundary value problem. The strengths and weaknesses of the analysis and estimate are discussed.Dedicated to Professor J. Crank on the occasion of his 80th birthday     

梯度Q-线性收敛的光滑凸极小化的一阶算法

受性能估计问题(PEP)方法的启发,通过考察最坏函数误差的收敛边界(即效率),优化了迭代点对应的梯度满足Q-线性收敛的光滑凸极小化的一阶方法的步长系数.介绍新的有效的一阶方法,称为QGM,具有与优化梯度法(OGM)类似的计算有效形式.     

Regularized optimization methods for convex MINLP problems

We propose regularized cutting-plane methods for solving mixed-integer nonlinear programming problems with nonsmooth convex objective and constraint functions. The given methods iteratively search for trial points in certain localizer sets, constructed by employing linearizations of the involved functions. New trial points can be chosen in several ways; for instance, by minimizing a regularized cutting-plane model if functions are costly. When dealing with hard-to-evaluate functions, the goal is to solve the optimization problem by performing as few function evaluations as possible. Numerical experiments comparing the proposed algorithms with classical methods in this area show the effectiveness of our approach.     

Performance of first-order methods for smooth convex minimization: a novel approach

We introduce a novel approach for analyzing the worst-case performance of first-order black-box optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space. Our approach relies on the observation that by definition, the worst-case behavior of a black-box optimization method is by itself an optimization problem, which we call the performance estimation problem (PEP). We formulate and analyze the PEP for two classes of first-order algorithms. We first apply this approach on the classical gradient method and derive a new and tight analytical bound on its performance. We then consider a broader class of first-order black-box methods, which among others, include the so-called heavy-ball method and the fast gradient schemes. We show that for this broader class, it is possible to derive new bounds on the performance of these methods by solving an adequately relaxed convex semidefinite PEP. Finally, we show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best worst-case performance.     

Exact multiplicity for periodic solutions of a first-order differential equation

Consider the differential equation

(1)