Search

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 consider the minimization of a convex objective function subject to the set of minima of another convex function, under the assumption that both functions are twice continuously differentiable. We approach this optimization problem from a continuous perspective by means of a second-order dynamical system with Hessian-driven damping and a penalty term corresponding to the constrained function. By constructing appropriate energy functionals, we prove weak convergence of the trajectories generated by this differential equation to a minimizer of the optimization problem as well as convergence for the objective function values along the trajectories. The performed investigations rely on Lyapunov analysis in combination with the continuous version of the Opial Lemma. In case the objective function is strongly convex, we can even show strong convergence of the trajectories.

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 propose an iterative scheme for solving variational inequalities with monotone operators over affine sets in an infinite dimensional Hilbert space setting. We show that several primal-dual algorithms in the literature as well as the classical ADMM algorithm for convex optimization problems, together with some of its variants, are encompassed by the proposed numerical scheme. Furthermore, we carry out a convergence analysis of the generated iterates and provide convergence rates by using suitable dynamical step sizes together with variable metric techniques.

We aim to solve a structured convex optimization problem, where a nonsmooth function is composed with a linear operator. When opting for full splitting schemes, usually, primal–dual type methods are employed as they are effective and also well studied. However, under the additional assumption of Lipschitz continuity of the nonsmooth function which is composed with the linear operator we can derive novel algorithms through regularization via the Moreau envelope. Furthermore, we tackle large scale problems by means of stochastic oracle calls, very similar to stochastic gradient techniques. Applications to total variational denoising and deblurring, and matrix factorization are provided.

The aim of this article is to present two different primal-dual methods for solving structured monotone inclusions involving parallel sums of compositions of maximally monotone operators with linear bounded operators. By employing some elaborated splitting techniques, all of the operators occurring in the problem formulation are processed individually via forward or backward steps. The treatment of parallel sums of linearly composed maximally monotone operators is motivated by applications in imaging which involve first- and second-order total variation functionals, to which a special attention is given., 25 pages

We investigate the asymptotic convergence of the trajectories generated by the second-order dynamical system , where are the convex and smooth functions defined on a real Hilbert space , and is a function of time which controls the penalty term. We show weak convergence of the trajectories to a minimizer of the function over the (nonempty) set of minima of as well as convergence for the objective function values along the trajectories, provided a condition expressed via the Fenchel conjugate of is fulfilled. When the function is assumed to be strongly convex, we can even show strong convergence of the trajectories. The results can be seen as the second-order counterparts of the ones given by Attouch and Czarnecki (Journal of Differential Equations 248(6), 1315–1344, 2010) for first-order dynamical systems associated to the constrained variational inequalities. At the same time we give a positive answer to an open problem posed by Attouch and Czarnecki in a recent preprint.

The Alternating Minimization Algorithm has been proposed by Paul Tseng to solve convex programming problems with two-block separable linear constraints and objectives, whereby (at least) one of the components of the latter is assumed to be strongly convex. The fact that one of the subproblems to be solved within the iteration process of this method does not usually correspond to the calculation of a proximal operator through a closed formula affects the implementability of the algorithm. In this paper, we allow in each block of the objective a further smooth convex function and propose a proximal version of the algorithm, which is achieved by equipping the algorithm with proximal terms induced by variable metrics. For suitable choices of the latter, the solving of the two subproblems in the iterative scheme can be reduced to the computation of proximal operators. We investigate the convergence of the proposed algorithm in a real Hilbert space setting and illustrate its numerical performances on two applications in image processing and machine learning. peerReviewed

We propose an inertial Douglas-Rachford splitting algorithm for finding the set of zeros of the sum of two maximally monotone operators in Hilbert spaces and investigate its convergence properties. To this end we formulate first the inertial version of the Krasnosel'skii?-Mann algorithm for approximating the set of fixed points of a nonexpansive operator, for which we also provide an exhaustive convergence analysis. By using a product space approach we employ these results to the solving of monotone inclusion problems involving linearly composed and parallel-sum type operators and provide in this way iterative schemes where each of the maximally monotone mappings is accessed separately via its resolvent. We consider also the special instance of solving a primal-dual pair of nonsmooth convex optimization problems and illustrate the theoretical results via some numerical experiments in clustering and location theory.

In this paper, we analyse the convergence rate of the sequence of objective function values of a primal-dual proximal-point algorithm recently introduced in the literature for solving a primal convex optimization problem having as objective the sum of linearly composed infimal convolutions, nonsmooth and smooth convex functions and its Fenchel-type dual one. The theoretical part is illustrated by numerical experiments in image processing.

We propose a proximal-gradient algorithm with penalization terms and inertial and memory effects for minimizing the sum of a proper, convex, and lower semicontinuous and a convex differentiable function subject to the set of minimizers of another convex differentiable function. We show that, under suitable choices for the step sizes and the penalization parameters, the generated iterates weakly converge to an optimal solution of the addressed bilevel optimization problem, while the objective function values converge to its optimal objective value.

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.

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 for regression is investigated under a theoretical point of view that makes use of convex analysis and Fenchel duality. 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 optimal solutions of the dual problem. Corresponding dual problems are then derived for different loss functions. The theoretical results are applied by numerically solving the regression task for two data sets and the accuracy of the regression when choosing different loss functions is investigated.

We consider the problem of minimizing a smooth convex objective function subject to the set of minima of another differentiable convex function. In order to solve this problem, we propose an algorithm which combines the gradient method with a penalization technique. Moreover, we insert in our algorithm an inertial term, which is able to take advantage of the history of the iterates. We show weak convergence of the generated sequence of iterates to an optimal solution of the optimization problem, provided a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. We also prove convergence for the objective function values to the optimal objective value. The convergence analysis carried out in this paper relies on the celebrated Opial Lemma and generalized Fejer monotonicity techniques. We illustrate the functionality of the method via a numerical experiment addressing image classification via support vector machines.

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

We investigate the techniques and ideas used in the convergence analysis of two proximal ADMM algorithms for solving convex optimization problems involving compositions with linear operators. Besides this, we formulate a variant of the ADMM algorithm that is able to handle convex optimization problems involving an additional smooth function in its objective, and which is evaluated through its gradient. Moreover, in each iteration we allow the use of variable metrics, while the investigations are carried out in the setting of infinite dimensional Hilbert spaces. This algorithmic scheme is investigated from the point of view of its convergence properties., Comment: Updates in Section 2 concerning the derivation of the convergence rates + a unifying convergence theorem for the sequence of iterates

Regularization methods are techniques for learning functions from given data. We consider regularization problems the objective function of which consisting of a cost function and a regularization term with the aim of selecting a prediction function f with a finite representation f ( · ) = ∑ i = 1 n c i k ( · , X i ) which minimizes the error of prediction. Here the role of the regularizer is to avoid overfitting. In general these are convex optimization problems with not necessarily differentiable objective functions. Thus in order to provide optimality conditions for this class of problems one needs to appeal on some specific techniques from the convex analysis. In this paper we provide a general approach for deriving necessary and sufficient optimality conditions for the regularized problem via the so-called conjugate duality theory. Afterwards we employ the obtained results to the Support Vector Machines problem and Support Vector Regression problem formulated for different cost functions.

We give an answer to the Problem 11.6 posed by Stephen Simons in his book “From Hahn-Banach to Monotonicity”: Do there exist a nonzero finite dimensional Banach space and a pair of extended real-valued, proper and convex functions which is totally Fenchel unstable? The answer is negative.

We give two generalized Moreau–Rockafellar-type results for the sum of a convex function with a composition of convex functions in separated locally convex spaces. Then we equivalently characterize the stable strong duality for composed convex optimization problems through two new regularity conditions, which also guarantee two formulae of the subdifferential of the mentioned sum of functions. We also treat some special cases, rediscovering older results in the literature. A discussion on the topological assumptions for the vector function used in the composition closes this article.

The aim of this paper is to give dual representations for different convex risk measures by employing their conjugate functions. To establish the formulas for the conjugates, we use on the one hand some classical results from convex analysis and on the other hand some tools from the conjugate duality theory. Some characterizations of so-called deviation measures recently given in the literature turn out to be direct consequences of our results.

We give new regularity conditions expressed via epigraphs that assure strong duality between a given primal convex optimization problem and its Lagrange and Fenchel-Lagrange dual problems, respectively, in infinite dimensional spaces. Moreover we completely characterize through equivalent statements the so-called stable strong duality between the initial problem and the mentioned duals.

We give new regularity conditions for convex optimization problems in separated locally convex spaces. We completely characterize the stable strong and strong Fenchel–Lagrange duality. Then we give similar statements for the case when a solution of the primal problem is assumed as known, obtaining complete characterizations for the so-called total and stable totalFenchel–Lagrange duality, respectively. For particular settings the conditions that we consider turn into some constraint qualifications already used by different authors, like Farkas–Minkowski CQ , locally Farkas–Minkowski CQ and basic CQ , and we rediscover and improve some recent results from the literature.

In this paper, we deal with regularity conditions formulated by making use of the quasirelative interior and/or of the quasi-interior of the sets involved, guaranteeing strong duality for a convex optimization problem with cone (and equality) constraints and its Lagrange dual. We discuss also some recent results on this topic, which are proved to have either superfluous or contradictory assumptions. Several examples illustrate the theoretical considerations.

We deal with duality for almost convex finite dimensional optimization problems by means of the classical perturbation approach. To this aim some standard results from the convex analysis are extended to the case of almost convex sets and functions. The duality for some classes of primal-dual problems is derived as a special case of the general approach. The sufficient regularity conditions we need for guaranteeing strong duality are proved to be similar to the ones in the convex case.

We give some necessary and sufficient conditions which completely characterize the strong and total Lagrange duality, respectively, for convex optimization problems in separated locally convex spaces. We also prove similar statements for the problems obtained by perturbing the objective functions of the primal problems by arbitrary linear functionals. In the particular case when we deal with convex optimization problems having infinitely many convex inequalities as constraints the conditions we work with turn into the so-called Farkas–Minkowski and locally Farkas–Minkowski conditions for systems of convex inequalities, recently used in the literature. Moreover, we show that our new results extend some existing ones in the literature.

When characterizing optimal solutions of both scalar and vector optimization problems usually constraint qualifications have to be satisfied. By considering sequential characterizations, given for the first time in vector optimization in this paper, this drawback is eliminated. In order to establish them we give first of all sequential characterizations for a convex composed optimization problem with geometric and cone constraints. Then, by means of scalarization, we extend them to the vector case. For exemplification we particularize the characterization in the case of linear and set scalarization.

Considering a constrained fractional programming problem, within the present paper we present some necessary and sufficient conditions, which ensure that the optimal objective value of the considered problem is greater than or equal to a given real constant. The desired results are obtained using the Fenchel–Lagrange duality approach applied to an optimization problem with convex or difference of convex (DC) objective functions and finitely many convex constraints. These are obtained from the initial fractional programming problem using an idea due to Dinkelbach. We also show that our general results encompass as special cases some recently obtained Farkas-type results.

The present paper is a continuation of [2] where we deal with the duality for a multiobjective fractional optimization problem. The basic idea in [2] consists in attaching an intermediate multiobjective convex optimization problem to the primal fractional problem, using an approach due to Dinkelbach ([6]), for which we construct then a dual problem expressed in terms of the conjugates of the functions involved. The weak, strong and converse duality statements for the intermediate problems allow us to give dual characterizations for the efficient solutions of the initial fractional problem. The aim of this paper is to compare the intermediate dual problem with other similar dual problems known from the literature. We completely establish the inclusion relations between the image sets of the duals as well as between the sets of maximal elements of the image sets.

We present a new constraint qualification which guarantees strong duality between a cone-constrained convex optimization problem and its Fenchel-Lagrange dual. This result is applied to a convex optimization problem having, for a given nonempty convex cone K, as objective function a K-convex function postcomposed with a K-increasing convex function. For this so-called composed convex optimization problem, we present a strong duality assertion, too, under weaker conditions than the ones considered so far. As an application, we rediscover the formula of the conjugate of a postcomposition with a K-increasing convex function as valid under weaker conditions than usually used in the literature.

We present an extension of Fenchel's duality theorem by weakening the convexity assumptions to near convexity. These weak hypotheses are automatically fulfilled in the convex case. Moreover, we show by a counterexample that a further extension to closely convex functions is not possible under these hypotheses.

A general duality framework in convex multiobjective optimization is established using the scalarization with K-strongly increasing functions and the conjugate duality for composed convex cone-constrained optimization problems. Other scalarizations used in the literature arise as particular cases and the general duality is specialized for some of them, namely linear scalarization, maximum (-linear) scalarization, set scalarization, (semi)norm scalarization and quadratic scalarization.

We present some Farkas-type results for inequality systems involving finitely many functions. Therefore we use a conjugate duality approach applied to an optimization problem with a composed convex objective function and convex inequality constraints. Some recently obtained results are rediscovered as special cases of our main result.

We give an alternative formulation for the so-called closed cone constraint qualification (CCCQ) related to a convex optimization problem in Banach spaces recently introduced in the literature. This new formulation allows to prove in a simple way that (CCCQ) is weaker than some generalized interior-point constraint qualifications given in the past. By means of some insights from the theory of conjugate duality we also show that strong duality still holds under some weaker hypotheses than the ones considered so far in the literature.

We consider a convex optimization problem whose objective function consists of an entropy-like sum of functions. We calculate the Lagrange dual of this problem. Weak and strong duality assertions a...

This chapter presents a survey on primal–dual splitting methods for solving monotone inclusion problems involving maximally monotone operators, linear compositions of parallel sums of maximally monotone operators, and single-valued Lipschitzian or cocoercive monotone operators. The primal–dual algorithms have the remarkable property that the operators involved are evaluated separately in each iteration, either by forward steps in the case of the single-valued ones or by backward steps for the set-valued ones, by using the corresponding resolvents. In the hypothesis that strong monotonicity assumptions for some of the involved operators are fulfilled, accelerated algorithmic schemes are presented and analyzed from the point of view of their convergence. Finally, we discuss the employment of the primal–dual methods in the context of solving convex optimization problems arising in the fields of image denoising and deblurring, support vector machine learning, location theory, portfolio optimization and clustering.

We introduce and investigate the convergence properties of an inertial forward-backward-forward splitting algorithm for approaching the set of zeros of the sum of a maximally monotone operator and a single-valued monotone and Lipschitzian operator. By making use of the product space approach, we expand it to the solving of inclusion problems involving mixtures of linearly composed and parallel-sum type monotone operators. We obtain in this way an inertial forward-backward-forward primal-dual splitting algorithm having as main characteristic the fact that in the iterative scheme all operators are accessed separately either via forward or via backward evaluations. We present also the variational case when one is interested in the solving of a primal-dual pair of convex optimization problems with intricate objective functions., Comment: arXiv admin note: text overlap with arXiv:1303.2875

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.

In this paper we propose two different primal-dual splitting algorithms for solving inclusions involving mixtures of composite and parallel-sum type monotone operators which rely on an inexact Douglas-Rachford splitting method, however applied in different underlying Hilbert spaces. Most importantly, the algorithms allow to process the bounded linear operators and the set-valued operators occurring in the formulation of the monotone inclusion problem separately at each iteration, the latter being individually accessed via their resolvents. The performances of the primal-dual algorithms are emphasized via some numerical experiments on location and image deblurring problems.

This article provides an overview on regularity conditions for Fenchel duality in convex optimization. Our attention is focused, on the one hand, on three generalized interior-point regularity conditions expressed by means of the quasi interior and of the quasi-relative interior and, on the other hand, on two closedness-type conditions that have been recently introduced in the literature. We discuss how they do relate to each other, but also to several other classical ones and illustrate these investigations by numerous examples.

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

Throughout this chapter, we assume that all topological dual spaces of the separated locally convex spaces considered are endowed with the corresponding weak* topologies. In this section, we give generalized Moreau–Rockafellar formulae expressed via the perturbation function Φ considered in Section 1 as well as closedness-type regularity conditions for the general optimization problem (PG). These will be particularized in the following sections to the different classes of convex functions and corresponding convex optimization problems, respectively, introduced in the previous chapter (see also [27]).

In this chapter we introduce some basic notions and results in convex analysis and vector optimization in order to make the book as self-contained as possible. The reader is supposed to have basic notions of functional analysis.

We prove that the formulae of the conjugates of the precomposition with a linear operator, of the sum of finitely many functions and of the sum between a function and the precomposition of another one with a linear operator hold even when the convexity assumptions are replaced by almost convexity or nearly convexity. We also show that the duality statements due to Fenchel hold when the functions involved are taken only almost convex, respectively nearly convex.

In this paper we consider, in a general normed space, the optimization problem with the objective function being a composite of a convex and componentwise increasing function with a vector convex function. Perturbing the primal problem, we obtain, by means of the Fenchel-Rockafellar approach, a dual problem for it. The existence of strong duality is proved and the optimality conditions are derived.

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.