Search

In this paper, we consider a broad class of nonsmooth and nonconvex fractional programs, where the numerator can be written as the sum of a continuously differentiable convex function whose gradient is Lipschitz continuous and a proper lower semicontinuous (possibly nonconvex) function, and the denominator is weakly convex over the constraint set. This model problem includes the composite optimization problems studied extensively lately, and encompasses many important modern fractional optimization problems arising from diverse areas such as the recently proposed scale invariant sparse signal reconstruction problem in signal processing. We propose a proximal subgradient algorithm with extrapolations for solving this optimization model and show that the iterated sequence generated by the algorithm is bounded and any of its limit points is a stationary point of the model problem. The choice of our extrapolation parameter is flexible and includes the popular extrapolation parameter adopted in the restarted Fast Iterative Shrinking-Threshold Algorithm (FISTA). By providing a unified analysis framework of descent methods, we establish the convergence of the full sequence under the assumption that a suitable merit function satisfies the Kurdyka--{\L}ojasiewicz (KL) property. In particular, our algorithm exhibits linear convergence for the scale invariant sparse signal reconstruction problem and the Rayleigh quotient problem over spherical constraint. In the case where the denominator is the maximum of finitely many continuously differentiable weakly convex functions, we also propose an enhanced extrapolated proximal subgradient algorithm with guaranteed convergence to a stronger notion of stationary points of the model problem. Finally, we illustrate the proposed methods by both analytical and simulated numerical examples., Comment: Revised version: Oct. 16, 2020

In this work, we approach the minimization of a continuously differentiable convex function under linear equality constraints by a second-order dynamical system with asymptotically vanishing damping term. The system is formulated in terms of the augmented Lagrangian associated to the minimization problem. We show fast convergence of the primal-dual gap, the feasibility measure, and the objective function value along the generated trajectories. In case the objective function has Lipschitz continuous gradient, we show that the primal-dual trajectory asymptotically weakly converges to a primal-dual optimal solution of the underlying minimization problem. To the best of our knowledge, this is the first result which guarantees the convergence of the trajectory generated by a primal-dual dynamical system with asymptotic vanishing damping. Moreover, we will rediscover in case of the unconstrained minimization of a convex differentiable function with Lipschitz continuous gradient all convergence statements obtained in the literature for Nesterov's accelerated gradient method.

We propose two numerical algorithms in the fully nonconvex setting for the minimization of the sum of a smooth function and the composition of a nonsmooth function with a linear operator. The iterative schemes are formulated in the spirit of the proximal alternating direction method of multipliers and its linearized variant, respectively. The proximal terms are introduced via variable metrics, a fact that allows us to derive new proximal splitting algorithms for nonconvex structured optimization problems, as particular instances of the general schemes. Under mild conditions on the sequence of variable metrics and by assuming that a regularization of the associated augmented Lagrangian has the Kurdyka–Łojasiewicz property, we prove that the iterates converge to a Karush–Kuhn–Tucker point of the objective function. By assuming that the augmented Lagrangian has the Łojasiewicz property, we also derive convergence rates for both the augmented Lagrangian and the iterates.

In this paper, we investigate in a Hilbert space setting a second-order dynamical system of the form [Formula: see text] where [Formula: see text]image[Formula: see text] is a maximal monotone operator, [Formula: see text] is the resolvent operator of [Formula: see text] and [Formula: see text] are cocoercive operators, and [Formula: see text], and [Formula: see text] are step size, penalization and, respectively, damping functions, all depending on time. We show the existence and uniqueness of strong global solutions in the framework of the Cauchy–Lipschitz–Picard Theorem and prove ergodic asymptotic convergence for the generated trajectories to a zero of the operator [Formula: see text] where [Formula: see text] and [Formula: see text] denotes the normal cone operator of [Formula: see text]. To this end, we use Lyapunov analysis combined with the celebrated Opial Lemma in its ergodic continuous version. Furthermore, we show strong convergence for trajectories to the unique zero of [Formula: see text], provided that [Formula: see text] is a strongly monotone operator.

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 carry out an asymptotic analysis of the proximal-gradient dynamical system \begin{equation*}\left\{ \begin{array}{ll} \dot x(t) +x(t) = \prox_{\gamma f}\big[x(t)-\gamma\nabla\Phi(x(t))-ax(t)-by(t)\big],\\ \dot y(t)+ax(t)+by(t)=0 \end{array}\right.\end{equation*} where $f$ is a proper, convex and lower semicontinuous function, $\Phi$ a possibly nonconvex smooth function and $\gamma, a$ and $b$ are positive real numbers. We show that the generated trajectories approach the set of critical points of $f+\Phi$, here understood as zeros of its limiting subdifferential, under the premise that a regularization of this sum function satisfies the Kurdyka-\L{}ojasiewicz property. We also establish convergence rates for the trajectories, formulated in terms of the \L{}ojasiewicz exponent of the considered regularization function., Comment: arXiv admin note: substantial text overlap with arXiv:1507.01416

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 consider the dynamical system $$\displaystyle \begin {cases} v(t)\in \partial \phi (x(t))\\ \lambda \dot x(t) + \dot v(t) + v(t) + \nabla \psi (x(t))=0, \end {cases} $$ where \(\phi :\mathbb {R}^n\to \mathbb {R}\cup \{+\infty \}\) is a proper, convex, and lower semicontinuous function, \(\psi :\mathbb {R}^n\to \mathbb {R}\) is a (possibly nonconvex) smooth function, and λ > 0 is a parameter which controls the velocity. We show that the set of limit points of the trajectory x is contained in the set of critical points of the objective function ϕ + ψ, which is here seen as the set of the zeros of its limiting subdifferential. If the objective function is smooth and satisfies the Kurdyka-Łojasiewicz property, then we can prove convergence of the whole trajectory x to a critical point. Furthermore, convergence rates for the orbits are obtained in terms of the Łojasiewicz exponent of the objective function, provided the latter satisfies the Łojasiewicz property.

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.

In this note, using a technique of Verona and Verona, we show that a result announced in “All maximal monotone operators in a Banach space are of type FPV” by A. Eberhard and R. Wenczel, Set-Valued Var. Anal. 22, 597–615, (2014), implies the truth of the Rockafellar conjecture. We then show that there is a gap in the logic of the Eberhard–Wenczel result, which we tried unsuccessfully to close. We also discuss briefly the connection with maximally monotone multifunctions of type (FPV).

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 introduce a penalty term-based splitting algorithm with inertial effects designed for solving monotone inclusion problems involving the sum of maximally monotone operators and the convex normal cone to the (nonempty) set of zeros of a monotone and Lipschitz continuous operator. We show weak ergodic convergence of the generated sequence of iterates to a solution of the monotone inclusion problem, provided a condition expressed via the Fitzpatrick function of the operator describing the underlying set of the normal cone is verified. Under strong monotonicity assumptions we can even show strong nonergodic convergence of the iterates. This approach constitutes the starting point for investigating from a similar perspective monotone inclusion problems involving linear compositions of parallel-sum operators and, further, for the minimization of a complexly structured convex objective function subject to the set of minima of another convex and differentiable function., arXiv admin note: text overlap with arXiv:1306.0352

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 investigate a second-order dynamical system with variable damping in connection with the minimization of a nonconvex differentiable function. The dynamical system is formulated in the spirit of the differential equation which models Nesterov's accelerated convex gradient method. We show that the generated trajectory converges to a critical point, if a regularization of the objective function satisfies the Kurdyka- Lojasiewicz property. We also provide convergence rates for the trajectory formulated in terms of the Lojasiewicz exponent.

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.

In this paper we consider the inclusion problem involving a maximally monotone operator, a monotone and Lipschitz continuous operator, linear compositions of parallel-sum type monotone operators as well as the normal cone to the set of zeros of another monotone and Lipschitz continuous operator. We propose a forward–backward–forward type algorithm for solving it that assumes an individual evaluation of each operator. Weak ergodic convergence of the sequence of iterates generated by the algorithmic scheme is guaranteed under a condition formulated in terms of the Fitzpatrick function associated to one of the monotone and Lipschitz continuous operators. We also discuss how the proposed penalty scheme can be applied to convex minimization problems and present some numerical experiments in TV-based image inpainting.

In this paper we deal with the minimization of a convex function over the solution set of a range inclusion problem determined by a multivalued operator with convex graph. We attach a dual problem to it, provide regularity conditions guaranteeing strong duality and derive for the resulting primal–dual pair necessary and sufficient optimality conditions. We also discuss the existence of optimal solutions for the primal and dual problems by using duality arguments. The theoretical results are applied in the context of the control of linear discrete systems.

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 primal problem of finding the zeros of the sum of a maximal monotone operator and the composition of another maximal monotone operator with a linear continuous operator. By formulat...

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 this paper, we propose two proximal-gradient algorithms for fractional programming problems in real Hilbert spaces, where the numerator is a proper, convex and lower semicontinuous function and the denominator is a smooth function, either concave or convex. In the iterative schemes, we perform a proximal step with respect to the nonsmooth numerator and a gradient step with respect to the smooth denominator. The algorithm in case of a concave denominator has the particularity that it generates sequences which approach both the (global) optimal solutions set and the optimal objective value of the underlying fractional programming problem. In case of a convex denominator the numerical scheme approaches the set of critical points of the objective function, provided the latter satisfies the Kurdyka-ᴌojasiewicz property.

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

Modelling of convex optimization in the face of data uncertainty often gives rise to families of parametric convex optimization problems. This motivates us to present, in this paper, a duality framework for a family of parametric convex optimization problems. By employing conjugate analysis, we present robust duality for the family of parametric problems by establishing strong duality between associated dual pair. We first show that robust duality holds whenever a constraint qualification holds. We then show that this constraint qualification is also necessary for robust duality in the sense that the constraint qualification holds if and only if robust duality holds for every linear perturbation of the objective function. As an application, we obtain a robust duality theorem for the best approximation problems with constraint data uncertainty under a strict feasibility condition.

The aim of this note is to give an alternative proof for a recent result due to Dorsch et al., which provides an upper estimate for the Clarke subdifferential of an infimal value function. We show the validity of this result under a weaker condition than the one assumed in the aforementioned paper, while the use of the Mordukhovich subdifferential, as an intermediate step, will considerably shorten its proof.

In this note we show that the main result of the paper (J. Optim. Theory Appl., published online on 10 September 2011) due to A. Capata and, consequently, all its particular cases are false.

Considering a vector optimization problem to which properly efficient solutions are defined by using convex cone-monotone scalarization functions, we attach to it, by means of perturbation theory, new vector duals. When the primal problem, the scalarization function and the perturbation function are particularized, different dual vector problems are obtained, some of them are already known in the literature. Weak and strong duality statements are delivered in each case.

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.

The aim of this paper is to implement some new techniques, based on conjugate duality in convex optimization, for proving the existence of global error bounds for convex inequality systems. We deal first of all with systems described via one convex inequality and extend the achieved results, by making use of a celebrated scalarization function, to convex inequality systems expressed by means of a general vector function. We also propose a second approach for guaranteeing the existence of global error bounds of the latter, which meanwhile sharpens the classical result of Robinson., 12 pages

In this paper we extend to infinite-dimensional spaces a vector duality concept recently considered in the literature in connection to the classical vector minimization linear optimization problem in a finite-dimensional framework. Weak, strong and converse duality for the vector dual problem introduced with this respect are proven and we also investigate its connections to some classical vector duals considered in the same framework in the literature.

In this paper we provide some extension results for n-cyclically monotone operators in reflexive Banach spaces by making use of the Fenchel duality. In this way we give a positive answer to a question posed by Bauschke and Wang (2007) [4] .

Considering a general optimization problem, we attach to it by means of perturbation theory two dual problems having in the constraints a subdifferential inclusion relation. When the primal problem and the perturbation function are particularized different new dual problems are obtained. In the special case of a constrained optimization problem, the classical Wolfe and Mond–Weir duals, respectively, follow as particularizations of the general duals by using the Lagrange perturbation. Examples to show the differences between the new duals are given and a gate towards other generalized convexities is opened.

We give a lower semicontinuous type regularity condition and a closedness type one which turn out to be necessary and sufficient for the fulfilment of two different formulae involving the e-subdifferential of a perturbation function, respectively. These regularity conditions prove to be sufficient also for having formulae for the classical subdifferential of a perturbation function. Some recently published results concerning e-subdifferentials are rediscovered as special cases.

In this paper we provide first existence results for solutions of the generalized equilibrium problem with composed functions ( G E P C ) under generalized convexity assumptions. Then we construct by employing some tools specific to the theory of conjugate duality two gap functions for ( G E P C ) . The importance of these gap functions is to be seen in the fact that they equivalently characterize the solutions of an equilibrium problem. We also prove that for some particular instances of ( G E P C ) the gap functions we introduce here become among others the celebrated Auslender’s and Giannessi’s gap 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 an answer to Problem 11.5 posed in Stephen Simons’s book From Hahn-Banach to Monotonicity.

In this paper we work in separated locally convex spaces where we give equivalent statements for the formulae of the conjugate function of the sum of a convex lower-semicontinuous function and the precomposition of another convex lower-semicontinuous function which is also K -increasing with a K -convex K -epi-closed function, where K is a nonempty closed convex cone. These statements prove to be the weakest constraint qualifications given so far under which the formulae for the subdifferential of the mentioned sum of functions are valid. Then we deliver constraint qualifications inspired from them that guarantee some conjugate duality assertions. Two interesting special cases taken from the literature conclude the paper. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

Motivated by a classical result concerning the e-subdifferential of the sum of two proper, convex and lower semicontinuous functions, we give in this paper a similar result for the enlargement of the sum of two maximal monotone operators defined on a Banach space. This is done by establishing a necessary and sufficient condition for a bivariate inf-convolution formula.

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.

In this paper we use the tools of the convex analysis in order to give a suitable characterization for the epigraph of the conjugate of the pointwise maximum of two proper, convex and lower semicontinuous functions in a normed space. By using this characterization we obtain, as a natural consequence, the formula for the biconjugate of the pointwise maximum of two functions, provided the so-called Attouch---Brezis regularity condition holds.

We introduce some abstract convexity notions in a real linear space and investigate which of the results from the convex analysis in topological vector spaces still work in a linear space. The differences between these abstract convexity notions and those established in spaces endowed with a topology are underlined by some examples. Mathematics subject classification (2000): 15A03, 52A01, 52A41.

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.