Search

In a Hilbert setting, we study the convergence properties of the second order in time dynamical system combining viscous and Hessian-driven damping with time scaling in relation to the minimization of a nonsmooth and convex function. The system is formulated in terms of the gradient of the Moreau envelope of the objective function with a time-dependent parameter. We show fast convergence rates for the Moreau envelope, its gradient along the trajectory, and also for the system velocity. From here, we derive fast convergence rates for the objective function along a path which is the image of the trajectory of the system through the proximal operator of the first. Moreover, we prove the weak convergence of the trajectory of the system to a global minimizer of the objective function. Finally, we provide multiple numerical examples illustrating the theoretical results.

This work aims to minimize a continuously differentiable convex function with Lipschitz continuous gradient under linear equality constraints. The proposed inertial algorithm results from the discretization of the second-order primal-dual dynamical system with asymptotically vanishing damping term addressed by Bot and Nguyen in [Bot, Nguyen, JDE, 2021], and it is formulated in terms of the Augmented Lagrangian associated with the minimization problem. The general setting we consider for the inertial parameters covers the three classical rules by Nesterov, Chambolle-Dossal and Attouch-Cabot used in the literature to formulate fast gradient methods. For these rules, we obtain in the convex regime convergence rates of order ${\cal O}(1/k^{2})$ for the primal-dual gap, the feasibility measure, and the objective function value. In addition, we prove that the generated sequence of primal-dual iterates converges to a primal-dual solution in a general setting that covers the two latter rules. This is the first result which provides the convergence of the sequence of iterates generated by a fast algorithm for linearly constrained convex optimization problems without additional assumptions such as strong convexity. We also emphasize that all convergence results of this paper are compatible with the ones obtained in [Bot, Nguyen, JDE, 2021] in the continuous setting., 37 pages

In this work we aim to solve a convex-concave saddle point problem, where the convex-concave coupling function is smooth in one variable and nonsmooth in the other and not assumed to be linear in either. The problem is augmented by a nonsmooth regulariser in the smooth component. We propose and investigate a novel algorithm under the name of OGAProx, consisting of an optimistic gradient ascent step in the smooth variable coupled with a proximal step of the regulariser, and which is alternated with a {proximal step} in the nonsmooth component of the coupling function. We consider the situations convex-concave, convex-strongly concave and strongly convex-strongly concave related to the saddle point problem under investigation. Regarding iterates we obtain (weak) convergence, a convergence rate of order $ \mathcal{O}(\frac{1}{K}) $ and linear convergence like $\mathcal{O}(\theta^{K})$ with $ \theta < 1 $, respectively. In terms of function values we obtain ergodic convergence rates of order $ \mathcal{O}(\frac{1}{K}) $, $ \mathcal{O}(\frac{1}{K^{2}}) $ and $ \mathcal{O}(\theta^{K}) $ with $ \theta < 1 $, respectively. We validate our theoretical considerations on a nonsmooth-linear saddle point problem, the training of multi kernel support vector machines and a classification problem incorporating minimax group fairness., Comment: A new numerical experiment on minimax group fairness has been added

We investigate a forward–backward splitting algorithm of penalty type with inertial effects for finding the zeros of the sum of a maximally monotone operator and a cocoercive one and the convex normal cone to the set of zeroes of an another cocoercive operator. Weak ergodic convergence is obtained for the iterates, provided that a condition expressed via the Fitzpatrick function of the operator describing the underlying set of the normal cone is verified. Under strong monotonicity assumptions, strong convergence for the sequence of generated iterates is proved. As a particular instance we consider a convex bilevel minimization problem including the sum of a non-smooth and a smooth function in the upper level and another smooth function in the lower level. We show that in this context weak non-ergodic and strong convergence can be also achieved under inf-compactness assumptions for the involved functions.

In this paper, we consider a class of nonsmooth sum-of-ratios fractional optimization problems with block structure. This model class is ubiquitous and encompasses several important nonsmooth optimization problems in the literature. We first propose an inertial proximal block coordinate method for solving this class of problems by exploiting the underlying structure. The global convergence of our method is guaranteed under the Kurdyka--Lojasiewicz (KL) property and some mild assumptions. We then identify the explicit exponents of the KL property for three important structured fractional optimization problems. In particular, for the sparse generalized eigenvalue problem with either cardinality regularization or sparsity constraint, we show that the KL exponents are 1/2, and so, the proposed method exhibits linear convergence rate. Finally, we illustrate our theoretical results with both analytic and simulated numerical examples.

Tseng’s forward–backward–forward algorithm is a valuable alternative for Korpelevich’s extragradient method when solving variational inequalities over a convex and closed set governed by monotone and Lipschitz continuous operators, as it requires in every step only one projection operation. However, it is well-known that Korpelevich’s method converges and can therefore be used also for solving variational inequalities governed by pseudo-monotone and Lipschitz continuous operators. In this paper, we first associate to a pseudo-monotone variational inequality a forward–backward–forward dynamical system and carry out an asymptotic analysis for the generated trajectories. The explicit time discretization of this system results into Tseng’s forward–backward–forward algorithm with relaxation parameters, which we prove to converge also when it is applied to pseudo-monotone variational inequalities. In addition, we show that linear convergence is guaranteed under strong pseudo-monotonicity. Numerical experiments are carried out for pseudo-monotone variational inequalities over polyhedral sets and fractional programming problems.

In a Hilbert space $H$, in order to develop fast optimization methods, we analyze the asymptotic behavior, as time $t$ tends to infinity, of inertial continuous dynamics where the damping acts as a closed-loop control. The function $f: H \to R$ to be minimized (not necessarily convex) enters the dynamic through it gradient, which is assumed to be Lipschitz continuous on the bounded subsets of $H$. This gives autonomous dynamical systems with nonlinear damping and nonlinear driving force. We first consider the case where the damping term $\partial \phi (\dot{x}(t))$ acts as a closed-loop control of the velocity. The damping potential $\phi : H \to [0,+\infty)$ is a convex continuous function which achieves its minimum at the origin. We show the existence and uniqueness of a global solution to the associated Cauchy problem. Then, we analyze the asymptotic convergence properties of the generated trajectories generated. We use techniques from optimization, control theory, and PDE's: Lyapunov analysis based on the decreasing property of an energy-like function, quasi-gradient and Kurdyka-Lojasiewicz theory, monotone operator theory for wave-like equations. Convergence rates are obtained based on the geometric properties of the data $f$ and $\phi$. When $f$ is strongly convex, we give general conditions which provide exponential convergence rates. Then, we extend the results to the case where an additional Hessian-driven damping enters the dynamic, which reduces the oscillations. Finally, we consider an inertial system involving jointly the velocity $\dot{x}(t)$ and the gradient $\nabla f(x(t))$. In addition to its original results, this work surveys the numerous works devoted in recent years to the interaction between continuous damped inertial dynamics and numerical algorithms for optimization, with the emphasis on autonomous systems, closed-loop adaptive procedures, and convergence rates., Comment: 63 pages, 6 figures, updated introduction, updated list of references

In this paper we aim to minimize the sum of two nonsmooth (possibly also nonconvex) functions in separate variables connected by a smooth coupling function. To tackle this problem we choose a continuous forward-backward approach and introduce a dynamical system which is formulated by means of the partial gradients of the smooth coupling function and the proximal point operator of the two nonsmooth functions. Moreover, we consider variable rates of implicity of the resulting system. We discuss the existence and uniqueness of a solution and carry out the asymptotic analysis of its convergence behaviour to a critical point of the optimization problem, when a regularization of the objective function fulfills the Kurdyka-Łojasiewicz property. We further provide convergence rates for the solution trajectory in terms of the Łojasiewicz exponent. We conclude this work with numerical simulations which confirm and validate the analytical results.

We investigate the asymptotic properties of the trajectories generated by a second-order dynamical system with Hessian driven damping and a Tikhonov regularization term in connection with the minimization of a smooth convex function in Hilbert spaces. We obtain fast convergence results for the function values along the trajectories. The Tikhonov regularization term enables the derivation of strong convergence results of the trajectory to the minimizer of the objective function of minimum norm.

Proximal splitting algorithms for monotone inclusions (and convex optimization problems) in Hilbert spaces share the common feature to guarantee for the generated sequences in general weak convergence to a solution. In order to achieve strong convergence, one usually needs to impose more restrictive properties for the involved operators, like strong monotonicity (respectively, strong convexity for optimization problems). In this paper, we propose a modified Krasnosel'skiĭ-Mann algorithm in connection with the determination of a fixed point of a nonexpansive mapping and show strong convergence of the iteratively generated sequence to the minimal norm solution of the problem. Relying on this, we derive a forward-backward and a Douglas-Rachford algorithm, both endowed with Tikhonov regularization terms, which generate iterates that strongly converge to the minimal norm solution of the set of zeros of the sum of two maximally monotone operators. Furthermore, we formulate strong convergent primal-dual algorithms of forward-backward and Douglas-Rachford-type for highly structured monotone inclusion problems involving parallel-sums and compositions with linear operators. The resulting iterative schemes are particularized to the solving of convex minimization problems. The theoretical results are illustrated by numerical experiments on the split feasibility problem in infinite dimensional spaces.

We propose two forward–backward proximal point type algorithms with inertial/memory effects for determining weakly efficient solutions to a vector optimization problem consisting in vector-minimizing with respect to a given closed convex pointed cone the sum of a proper cone-convex vector function with a cone-convex differentiable one, both mapping from a Hilbert space to a Banach one. Inexact versions of the algorithms, more suitable for implementation, are provided as well, while as a byproduct one can also derive a forward–backward method for solving the mentioned problem. Numerical experiments with the proposed methods are carried out in the context of solving a portfolio optimization problem.

In this paper we propose a primal-dual dynamical approach to the minimization of a structured convex function consisting of a smooth term, a nonsmooth term, and the composition of another nonsmooth term with a linear continuous operator. In this scope we introduce a dynamical system for which we prove that its trajectories asymptotically converge to a saddle point of the Lagrangian of the underlying convex minimization problem as time tends to infinity. In addition, we provide rates for both the violation of the feasibility condition by the ergodic trajectories and the convergence of the objective function along these ergodic trajectories to its minimal value. Explicit time discretization of the dynamical system results in a numerical algorithm which is a combination of the linearized proximal method of multipliers and the proximal ADMM algorithm.

We investigate the asymptotic properties of the trajectories generated by a second-order dynamical system of proximal-gradient type stated in connection with the minimization of the sum of a nonsmooth convex and a (possibly nonconvex) smooth function. The convergence of the generated trajectory to a critical point of the objective is ensured provided a regularization of the objective function satisfies the Kurdyka–Łojasiewicz property. We also provide convergence rates for the trajectory formulated in terms of the Łojasiewicz exponent.

Supervised learning methods are powerful techniques to learn a function from a given set of labeled data, the so-called training data. In this paper the support vector machines approach is applied to an image classification task. Starting with the corresponding Tikhonov regularization problem, reformulated as a convex optimization problem, we introduce a conjugate dual problem to it and prove that, whenever strong duality holds, the function to be learned can be expressed via the dual optimal solutions. Corresponding dual problems are then derived for different loss functions. The theoretical results are applied by numerically solving a classification task using high dimensional real-world data in order to obtain optimal classifiers. The results demonstrate the excellent performance of support vector classification for this particular problem.

In connection with the optimization problem $$\inf_{x\in argmin \Psi}\{\Phi(x)+\Theta(x)\},$$ where $\Phi$ is a proper, convex and lower semicontinuous function and $\Theta$ and $\Psi$ are convex and smooth functions defined on a real Hilbert space, we investigate the asymptotic behavior of the trajectories of the nonautonomous Levenberg-Marquardt dynamical system \begin{equation*}\left\{ \begin{array}{ll} v(t)\in\partial\Phi(x(t))\\ \lambda(t)\dot x(t) + \dot v(t) + v(t) + \nabla \Theta(x(t))+\beta(t)\nabla \Psi(x(t))=0, \end{array}\right.\end{equation*} where $\lambda$ and $\beta$ are functions of time controlling the velocity and the penalty term, respectively. We show weak convergence of the generated trajectory to an optimal solution as well as convergence of the objective function values along the trajectories, provided $\lambda$ is monotonically decreasing, $\beta$ satisfies a growth condition and a relation expressed via the Fenchel conjugate of $\Psi$ is fulfilled. When the objective function is assumed to be strongly convex, we can even show strong convergence of the trajectories., Comment: arXiv admin note: text overlap with arXiv:1512.04702

In this note we provide regularity conditions of closedness type which guarantee some surjectivity results concerning the sum of two maximal monotone operators by using representative functions. The first regularity condition we give guarantees the surjectivity of the monotone operator $S(\cdot + p)+T(\cdot)$, where $p\in X$ and $S$ and $T$ are maximal monotone operators on the reflexive Banach space $X$. Then, this is used to obtain sufficient conditions for the surjectivity of $S+T$ and for the situation when $0$ belongs to the range of $S+T$. Several special cases are discussed, some of them delivering interesting byproducts., Comment: 11 pages, no figures

We investigate the existence and uniqueness of (locally) absolutely continuous trajectories of a penalty term-based dynamical system associated to a constrained variational inequality expressed as a monotone inclusion problem. Relying on Lyapunov analysis and on the ergodic continuous version of the celebrated Opial Lemma we prove weak ergodic convergence of the orbits to a solution of the constrained variational inequality under investigation. If one of the operators involved satisfies stronger monotonicity properties, then strong convergence of the trajectories can be shown., arXiv admin note: text overlap with arXiv:1306.0352

We study the existence and uniqueness of (locally) absolutely continuous trajectories of a dynamical system governed by a nonexpansive operator. The weak convergence of the orbits to a fixed point of the operator is investigated by relying on Lyapunov analysis. We show also an order of convergence of $$o\left( \frac{1}{\sqrt{t}}\right) $$ for the fixed point residual of the trajectory of the dynamical system. We apply the results to dynamical systems associated with the problem of finding the zeros of the sum of a maximally monotone operator and a cocoercive one. Several dynamical systems from the literature turn out to be particular instances of this general approach.

In this paper we are concerned with solving monotone inclusion problems expressed by the sum of a set-valued maximally monotone operator with a single-valued maximally monotone one and the normal cone to the nonempty set of zeros of another set-valued maximally monotone operator. Depending on the nature of the single-valued operator, we will propose two iterative penalty schemes, both addressing the set-valued operators via backward steps. The single-valued operator will be evaluated via a single forward step if it is cocoercive, and via two forward steps if it is monotone and Lipschitz continuous. The latter situation represents the starting point for dealing with complexly structured monotone inclusion problems from algorithmic point of view., arXiv admin note: text overlap with arXiv:1306.0352

In this paper we investigate the applicability of a recently introduced primal-dual splitting method in the context of solving portfolio optimization problems which assume the minimization of risk measures associated to different convex utility functions. We show that, due to the splitting characteristic of the used primal-dual method, the main effort in implementing it constitutes in the calculation of the proximal points of the utility functions, which assume explicit expressions in a number of cases. When quantifying risk via the meanwhile classical Conditional Value-at-Risk, an alternative approach relying on the use of its dual representation is presented as well. The theoretical results are finally illustrated via some numerical experiments on real and synthetic data sets., 16 pages

In this paper we propose an algorithm for solving systems of coupled monotone inclusions in Hilbert spaces. The operators arising in each of the inclusions of the system are processed in each iteration separately, namely, the single-valued are evaluated explicitly (forward steps), while the set-valued ones via their resolvents (backward steps). In addition, most of the steps in the iterative scheme can be executed simultaneously, this making the method applicable to a variety of convex minimization problems. The numerical performances of the proposed splitting algorithm are emphasized through applications in average consensus on colored networks and image classification via support vector machines.

In this paper we investigate the convergence behavior of a primal-dual splitting method for solving monotone inclusions involving mixtures of composite, Lipschitzian and parallel sum type operators proposed by Combettes and Pesquet (in Set-Valued Var. Anal. 20(2):307---330, 2012). Firstly, in the particular case of convex minimization problems, we derive convergence rates for the partial primal-dual gap function associated to a primal-dual pair of optimization problems by making use of conjugate duality techniques. Secondly, we propose for the general monotone inclusion problem two new schemes which accelerate the sequences of primal and/or dual iterates, provided strong monotonicity assumptions for some of the involved operators are fulfilled. Finally, we apply the theoretical achievements in the context of different types of image restoration problems solved via total variation regularization.

In this article we investigate the possibilities of accelerating the double smoothing technique when solving unconstrained nondifferentiable convex optimization problems. This approach relies on the regularization in two steps of the Fenchel dual problem associated to the problem to be solved into an optimization problem having a differentiable strongly convex objective function with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method. The aim of this paper is to show how do the properties of the functions in the objective of the primal problem influence the implementation of the double smoothing approach and its rate of convergence. The theoretical results are applied to linear inverse problems by making use of different regularization functionals., 22 pages. arXiv admin note: text overlap with arXiv:1203.2070

The aim of this paper is to develop an efficient algorithm for solving a class of unconstrained nondifferentiable convex optimization problems in finite dimensional spaces. To this end we formulate first its Fenchel dual problem and regularize it in two steps into a differentiable strongly convex one with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method with the aim of accelerating the resulting convergence scheme. The theoretical results are finally applied to an l 1 regularization problem arising in image processing.

The regularization of linear ill-posed problems is based on their conditional well-posedness when restricting the problem to certain classes of solutions. Given such class one may consider several related real-valued functions, which measure the wellposedness of the problem on such class. Among those functions the modulus of continuity is best studied. For solution classes which enjoy the additional feature of being star-shaped at zero, the authors develop a series of results with focus on continuity properties of the modulus of continuity. In particular it is highlighted that the problem is conditionally well-posed if and only if the modulus of continuity is right-continuous at zero. Those results are then applied to smoothness classes in Hilbert space. This study concludes with a new perspective on a concavity problem for the modulus of continuity, recently addressed by two of the authors in "Some note on the modulus of continuity for ill-posed problems in Hilbert space", 2011.

Convergence rates results for Tikhonov regularization of nonlinear ill-posed operator equations in abstract function spaces require the handling of both smoothness conditions imposed on the solution and structural conditions expressing the character of nonlinearity. Recently, the distinguished role of variational inequalities holding on some level sets was outlined for obtaining convergence rates results. When lower rates are expected such inequalities combine the smoothness properties of solution and forward operator in a sophisticated manner. In this paper, using a Banach space setting we are going to extend the variational inequality approach from Holder rates to more general rates including the case of logarithmic convergence rates.

A fruitful idea, when providing subdifferential formulae and dual representations for convex risk measures, is to make use of the conjugate duality theory in convex optimization. In this paper we underline the outstanding role played by the qualification conditions in the context of different problem formulations in this area. We show that not only the meanwhile classical generalized interiority point ones come here to bear, but also a recently introduced one formulated by means of the quasi-relative interior., 20 pages

In this paper we derive by means of the duality theory necessary and sufficient optimality conditions for convex optimization problems having as objective function the composition of a convex function with a linear mapping defined on a finite-dimensional space with values in a Hausdorff locally convex space. We use the general results for deriving optimality conditions for two portfolio optimization problems having as objective functions different convex deviation measures.

In this paper we provide a duality theory for multiobjective optimization problems with convex objective functions and finitely many D.C. constraints. In order to do this, we study first the duality for a scalar convex optimization problem with inequality constraints defined by extended real-valued convex functions. For a family of multiobjective problems associated to the initial one we determine then, by means of the scalar duality results, their multiobjective dual problems. Finally, we consider as a special case the duality for the convex multiobjective optimization problem with convex constraints.

The aim of the present paper is to provide a formula for the @?-subdifferential of [email protected]?h different from the ones which can be found in the existent literature. Further we equivalently characterize this formula by using a so-called closedness type regularity condition expressed by means of the epigraphs of the conjugates of the functions involved. Even more, using the @?-subdifferential formula we are able to derive necessary and sufficient conditions for the @?-optimal solutions of composed convex optimization problems.