Search

Abdessamad Oussarhana and Tijani AmahroqbaLIMATI Laboratory, Poly-disciplinary Faculty, Sultan Moulay Slimane University, Beni Mellal, Morocco; bLAMAI Laboratory, Faculty of Sciences and Techniques, Cadi Ayyad University, Marrakech, Morocco We provide a counterexample to Proposition 2.3 in our paper [Optimization 20, 69(12), pp. 2611–2627] where we said that the convex set A and the element $ x_0 $ x 0 can be properly separated by a closed hyperplane if $ x_0\notin {\rm pri}(A) $ x 0 ∉ pri (A) , with $ {\rm pri}(A) $ pri (A) is the pseudo relative interior of A. In addition, we re-establish all results rely on this proposition, more precisely, [Amahroq and Oussarhan Infinite-dimensional vector optimization and a separation theorem. Optimization. 2020;69(12):2611–2627, Lemma 2.1 (ii)–(iv)], [Amahroq and Oussarhan Infinite-dimensional vector optimization and a separation theorem. Optimization. 2020;69(12):2611–2627, Theorem 3.1] and [Amahroq and Oussarhan Infinite-dimensional vector optimization and a separation theorem. Optimization. 2020;69(12):2611–2627, Corollary 5.1] (see Section 1). A revision to the proof of [Amahroq and Oussarhan Infinite-dimensional vector optimization and a separation theorem. Optimization. 2020;69(12):2611–2627, Theorem 4.1] is also done (see Section 2). We claim that, the rest of the paper (Amahroq and Oussarhan Infinite-dimensional vector optimization and a separation theorem. Optimization. 2020;69(12):2611–2627) is independent of the above incorrect statements. [ABSTRACT FROM AUTHOR]

This paper studies the forward–reflected–backward splitting algorithm with momentum terms for monotone inclusion problem of the sum of a maximal monotone and Lipschitz continuous monotone operators in Hilbert spaces. The forward–reflected–backward splitting algorithm is an interesting algorithm for inclusion problems with the sum of maximal monotone and Lipschitz continuous monotone operators due to the inherent feature of one forward evaluation and one backward evaluation per iteration it possesses. The results in this paper further explore the convergence behavior of the forward–reflected–backward splitting algorithm with momentum terms. We obtain weak, linear, and strong convergence results under the same inherent feature of one forward evaluation and one backward evaluation at each iteration. Numerical results show that forward–reflected–backward splitting algorithms with momentum terms are efficient and promising over some related splitting algorithms in the literature. [ABSTRACT FROM AUTHOR]

The growing use of optimization models to help decision making has created a demand for such tools that allow formulating and solving more models of real-world processes and systems related to human activity in which hypotheses are not verify in a way specific for classical optimization. One of the approaches for real-world extremum problems under uncertainty is interval-valued optimization. In this paper, a twice differentiable vector optimization problem with multiple interval-valued objective function and both inequality and equality constraints is considered. In this paper, the first order necessary optimality conditions of Karush-Kuhn-Tucker type are proved for differentiable interval-valued vector optimization problems under the first order constraint qualification. If the interval-valued objective function is assumed to be twice weakly differentiable and constraints functions are assumed to be twice differentiable, then two types of second order necessary optimality conditions under two various constraint qualifications are proved for such smooth interval-valued vector optimization problems. Finally, in order to illustrate the Karush-Kuhn-Tucker type necessary optimality conditions established in the paper, an example of an interval-valued optimization is given. [ABSTRACT FROM AUTHOR]

In this paper, by revisiting coderivative calculus rules for convex multifunctions in finite-dimensional spaces, we derive formulae for estimating/computing the basic subdifferential and the coderivative of the efficient point multifunction of parametric convex vector optimization problems. These results are then applied to a broad class of conventional convex vector optimization problems with the presence of operator constraints and equilibrium ones. Examples are also designed to analyze and illustrate the obtained results. [ABSTRACT FROM AUTHOR]

In this paper, we update the theory of deterministic linear semi-infinite programming, mainly with the dual characterizations of the constraint qualifications, which play a crucial role in optimality and duality. From this theory, we obtain new results on conic and two-stage stochastic linear optimization. Specifically, for conic linear optimization problems, we characterize the existence of feasible solutions and some geometric properties of the feasible set, and we also provide theorems on optimality and duality. Analogously, regarding stochastic optimization problems, we study the semi-infinite reformulation of a problem-based scenario reduction problem in two-stage stochastic linear programming, providing a sufficient condition for the existence of feasible solutions as well as optimality and duality theorems to its non-combinatorial part. [ABSTRACT FROM AUTHOR]

This paper introduces a schematic approximation method for a solution to a variational inequality problem in the framework of Hadamard manifold. The method is a combination of the subgradient extragradient technique and Popov extragradient method. Using this method, some convergence algorithms were proved when the cost operators are pseudomonotone and strongly pseudomonotone, respectively. In the construction of this method, the dependence on Lipschitz constants of the operators is dispensed with by the use of a monotone decreasing step size. We give an application of our main result to the constrained convex minimization problem. Finally, we report some numerical examples to illustrate the efficiency and applicability of the method. [ABSTRACT FROM AUTHOR]

In this paper we present two Fenchel-type dual problems for a DC (difference of convex functions) optimization primal one. They have been built by means of the c-conjugation scheme, a pattern of conjugation which has been shown to be suitable for evenly convex functions. We study characterizations of weak, strong and stable strong duality for both pairs of primal–dual problems. We also give conditions which relate the existence of strong and stable strong duality for both pairs. [ABSTRACT FROM AUTHOR]

Discrete inverse problems correspond to solving a system of equations in a stable way with respect to noise in the data. A typical approach to select a meaningful solution is to introduce a regularizer. While for most applications the regularizer is convex, in many cases it is neither smooth nor strongly convex. In this paper, we propose and study two new iterative regularization methods, based on a primal-dual algorithm, to regularize inverse problems efficiently. Our analysis, in the noise free case, provides convergence rates for the Lagrangian and the feasibility gap. In the noisy case, it provides stability bounds and early stopping rules with theoretical guarantees. The main novelty of our work is the exploitation of some a priori knowledge about the solution set: we show that the linear equations determined by the data can be used more than once along the iterations. We discuss various approaches to reuse linear equations that are at the same time consistent with our assumptions and flexible in the implementation. Finally, we illustrate our theoretical findings with numerical simulations for robust sparse recovery and image reconstruction. We confirm the efficiency of the proposed regularization approaches, comparing the results with state-of-the-art methods. [ABSTRACT FROM AUTHOR]

This paper proposes and establishes the iteration complexity of an inexact proximal accelerated augmented Lagrangian (IPAAL) method for solving linearly constrained smooth nonconvex composite optimization problems. Each IPAAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite gradient (ACG) method followed by a suitable Lagrange multiplier update. For any given (possibly infeasible) initial point and tolerance ρ > 0 , it is shown that IPAAL generates an approximate stationary solution in O (ρ - 3 log (ρ - 1)) ACG iterations, which can be improved to O (ρ - 2.5 log (ρ - 1)) if it is further assumed that a certain Slater condition holds. [ABSTRACT FROM AUTHOR]

In this paper, we revisit some elements of the theory of self-concordant functions. We replace the notion of self-concordant barrier by a new notion of set-limited function, which forms a wider class. We show that the proper set-limited functions ensure polynomial time complexity of the corresponding path-following method (PFM). Our new PFM follows a deviated path, which connects an arbitrary feasible point with the solution of the problem. We present some applications of our approach to the problems of unconstrained optimization, for which it ensures a global linear rate of convergence even in for nonsmooth objective function. [ABSTRACT FROM AUTHOR]

This paper considers the relaxed proximal point algorithm for solving monotone variational inequality problems, and our main contribution is the establishment of a tight ergodic sublinear convergence rate. First, the tight or exact worst-case convergence rate is computed using the performance estimation framework. It is observed that this numerical bound asymptotically coincides with the best-known existing rate, whose tightness is not clear. This implies that, without further assumptions, sublinear convergence rate is likely the best achievable rate for the relaxed proximal point algorithm. Motivated by the numerical result, a concrete example is constructed, which provides a lower bound on the exact worst-case convergence rate. This lower bound coincides with the numerical bound computed via the performance estimation framework, leading us to conjecture that the lower bound provided by the example is exactly the tight worse-case rate, which is then verified theoretically. We thus have established an ergodic sublinear complexity rate that is tight in terms of both the sublinear order and the constants involved. [ABSTRACT FROM AUTHOR]

In this paper, we consider finite sum composite optimization problems with many functional constraints. The objective function is expressed as a finite sum of two terms, one of which admits easy computation of (sub)gradients while the other is amenable to proximal evaluations. We assume a generalized bounded gradient condition on the objective which allows us to simultaneously tackle both smooth and nonsmooth problems. We also consider the cases of both with and without a quadratic functional growth property. Further, we assume that each constraint set is given as the level set of a convex but not necessarily a differentiable function. We reformulate the constrained finite sum problem into a stochastic optimization problem for which the stochastic subgradient projection method from Necoara and Singh [Stochastic subgradient projection methods for composite optimization with functional constraints; 2022 Journal of Machine Learning Research, 23, 1–35] specializes in a collection of mini-batch variants, with different mini-batch sizes for the objective function and functional constraints, respectively. More specifically, at each iteration, our algorithm takes a mini-batch stochastic proximal subgradient step aimed at minimizing the objective function and then a subsequent mini-batch subgradient projection step minimizing the feasibility violation. By specializing in different mini-batching strategies, we derive exact expressions for the stepsizes as a function of the mini-batch size and in some cases we also derive insightful stepsize-switching rules which describe when one should switch from a constant to a decreasing stepsize regime. We also prove sublinear convergence rates for the mini-batch subgradient projection algorithm which depend explicitly on the mini-batch sizes and on the properties of the objective function. Numerical results also show a better performance of our mini-batch scheme over its single-batch counterpart. [ABSTRACT FROM AUTHOR]

In this paper, we study split common fixed point problems with multiple output sets in Hilbert spaces. For solving this problem, we improve Reich and Tuyen's algorithms [10] and propose two new self-adaptive algorithms which do not need any priori information on the norms of the transfer operators. Then, we establish weak convergence theorems for them. It can be seen from our numerical experiments that the proposed methods depict a very significant improvement in terms of the number of iterations and execution time. [ABSTRACT FROM AUTHOR]

In this paper, we study the gradient descent–ascent method for convex–concave saddle-point problems. We derive a new non-asymptotic global convergence rate in terms of distance to the solution set by using the semidefinite programming performance estimation method. The given convergence rate incorporates most parameters of the problem and it is exact for a large class of strongly convex-strongly concave saddle-point problems for one iteration. We also investigate the algorithm without strong convexity and we provide some necessary and sufficient conditions under which the gradient descent–ascent enjoys linear convergence. [ABSTRACT FROM AUTHOR]

In this paper, we study the variational inequality over the solution set of the split common solution problem with multiple output sets for monotone operator equations in real Hilbert spaces. We propose a new approach for solving this problem without depending on the norm of the transfer mappings. Some of its applications for solving the variational inequality over the solution set of the split common fixed point problem with multiple output sets and related problems are also mentioned. Finally, we give numerical examples to illustrate the performance of the proposed algorithm and compare it with several existing previous algorithms. [ABSTRACT FROM AUTHOR]

First-order optimization algorithms can be considered as a discretization of ordinary differential equations (ODEs) (Su et al. in Adv Neural Inf Process Syst 27, 2014). In this perspective, studying the properties of the corresponding trajectories may lead to convergence results which can be transfered to the numerical scheme. In this paper we analyse the following ODE introduced by Attouch et al. (J Differ Equ 261(10):5734–5783, 2016): ∀ t ⩾ t 0 , x ¨ (t) + α t x ˙ (t) + β H F (x (t)) x ˙ (t) + ∇ F (x (t)) = 0 , where α > 0 , β > 0 and H F denotes the Hessian of F. This ODE can be derived to build numerical schemes which do not require F to be twice differentiable as shown in Attouch et al. (Math Program 1–43, 2020) and Attouch et al. (Optimization 72:1–40, 2021). We provide strong convergence results on the error F (x (t)) - F ∗ and integrability properties on ‖ ∇ F (x (t)) ‖ under some geometry assumptions on F such as quadratic growth around the set of minimizers. In particular, we show that the decay rate of the error for a strongly convex function is O (t - α - ε) for any ε > 0 . These results are briefly illustrated at the end of the paper. [ABSTRACT FROM AUTHOR]

This paper is devoted to reduce the conservativeness of distributionally robust optimization with moments information. Since the optimal solution of distributionally robust optimization is required to be feasible for all uncertain distributions in a given ambiguity distribution set and so the conservativeness of the optimal solution is inevitable. To address this issue, we introduce the globalized distributionally robust counterpart (GDRC) which allows constraint violations controlled by functional distance of the true distribution to the inner distribution set. We obtain the deterministic equivalent forms for several GDRCs under the moment-based framework. To be specific, we show the deterministic equivalent systems of inequalities for GDRCs under second order moment information with a separable convex distance function and a special jointly convex function, respectively. We also obtain the deterministic equivalent inequality for GDRC under first order moment and support information. The computationally tractable examples are presented for these GDRCs. Numerical tests of a portfolio optimization problem are given to show the effectiveness of our method and the results demonstrate that the globalized distributionally robust solution is non-conservative and flexible compared to the distributionally robust solution. [ABSTRACT FROM AUTHOR]

In this paper, we focus on solving the decentralized optimization problem of minimizing the sum of n objective functions over a multi-agent network. The agents are embedded in an undirected graph where they can only send/receive information directly to/from their immediate neighbors. Assuming smooth and strongly convex objective functions, we propose an Optimal Gradient Tracking (OGT) method that achieves the optimal gradient computation complexity O κ log 1 ϵ and the optimal communication complexity O κ θ log 1 ϵ simultaneously, where κ and 1 θ denote the condition numbers related to the objective functions and the communication graph, respectively. To our best knowledge, OGT is the first single-loop decentralized gradient-type method that is optimal in both gradient computation and communication complexities. The development of OGT involves two building blocks that are also of independent interest. The first one is another new decentralized gradient tracking method termed "Snapshot" Gradient Tracking (SS-GT), which achieves the gradient computation and communication complexities of O κ log 1 ϵ and O κ θ log 1 ϵ , respectively. SS - G T can be potentially extended to more general settings compared to OGT. The second one is a technique termed Loopless Chebyshev Acceleration (LCA), which can be implemented "looplessly" but achieves a similar effect by adding multiple inner loops of Chebyshev acceleration in the algorithm. In addition to SS - G T , this LCA technique can accelerate many other gradient tracking based methods with respect to the graph condition number 1 θ . [ABSTRACT FROM AUTHOR]

In the present paper, we propose a new approach to solving a class of generalized split problems. This approach will open some new directions for research to solve the other split problems, for instance, the split common zero point problem and the split common fixed point problem. More precisely, we study the split common solution problem for monotone operator equations in real Hilbert spaces. To find a solution to this problem, we propose and establish the strong convergence of the two new iterative methods by using the Tikhonov regularization method. Meantime, we also study the stability of the iterative methods. Finally, two numerical examples are also given to illustrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, a general formula concerning the multi-composition rule of convex subdifferential calculus is provided in the setting of Banach spaces under an appropriate regularity condition. As an application, this calculus rule is applied to obtain necessary and sufficient Karush–Kuhn–Tucker type optimality conditions for constrained convex minmax location problems with perturbed minimal time functions and set-up costs. [ABSTRACT FROM AUTHOR]

In this paper, we propose a reflected forward-backward splitting algorithm with two different inertial extrapolations to find a zero of the sum of three monotone operators consisting of the maximal monotone operator, Lipschitz continuous monotone operator, and a cocoercive operator in real Hilbert spaces. One of the interesting features of the proposed algorithm is that both the Lipschitz continuous monotone operator and the cocoercive operator are computed explicitly each with one evaluation per iteration. We then obtain weak and strong convergence results under some mild conditions. We finally give a numerical illustration to show that our proposed algorithm is effective and competitive with other related algorithms in the literature. [ABSTRACT FROM AUTHOR]

The class of convex–concave bilinear saddle point problems encompasses many important convex optimization models arising in a wide array of applications. The most of existing primal–dual dynamical systems for saddle point problems are based on first order ordinary differential equations (ODEs), which only own the O (1 / t) convergence rate in the convex case, and fast convergence rate analysis always requires some additional assumption such as strong convexity. In this paper, based on second order ODEs, we consider a general inertial primal–dual dynamical system, with damping, scaling and extrapolation coefficients, for a convex–concave bilinear saddle point problem. By the Lyapunov analysis approach, under appropriate assumptions, we investigate the convergence rates of the primal–dual gap and velocities, and the boundedness of the trajectories for the proposed dynamical system. With special parameters, our results can recover the Polyak's heavy ball acceleration scheme and Nesterov's acceleration scheme. We also provide numerical examples to support our theoretical claims. [ABSTRACT FROM AUTHOR]

The paper proposes and develops a novel inexact gradient method (IGD) for minimizing $ {\mathcal {C}}^1 $ C1-smooth functions with Lipschitzian gradients, i.e. for problems of $ {\mathcal {C}}^{1,1} $ C1,1 optimization. We show that the sequence of gradients generated by IGD converges to zero. The convergence of iterates to stationary points is guaranteed under the Kurdyka-Łojasiewicz (KL) property of the objective function with convergence rates depending on the KL exponent. The newly developed IGD is applied to designing two novel gradient-based methods of nonsmooth convex optimization such as the inexact proximal point methods (GIPPM) and the inexact augmented Lagrangian method (GIALM) for convex programs with linear equality constraints. These two methods inherit global convergence properties from IGD and are confirmed by numerical experiments to have practical advantages over some well-known algorithms of nonsmooth convex optimization. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of a batch of linearly correlated image alignment, where the observed images are deformed by some unknown domain transformations, and corrupted by additive Gaussian noise and sparse noise simultaneously. By stacking these images as the frontal slices of a third-order tensor, we propose to utilize the tensor factorization method via transformed tensor-tensor product to explore the low-rankness of the underlying tensor, which is factorized into the product of two smaller tensors via transformed tensor-tensor product under any unitary transformation. The main advantage of transformed tensor-tensor product is that its computational complexity is lower compared with the existing literature based on transformed tensor nuclear norm. Moreover, the tensor ℓ p (0 < p < 1) norm is employed to characterize the sparsity of sparse noise and the tensor Frobenius norm is adopted to model additive Gaussian noise. A generalized Gauss-Newton algorithm is designed to solve the resulting model by linearizing the domain transformations, and a proximal Gauss-Seidel algorithm is developed to solve the corresponding subproblem. Furthermore, the convergence of the proximal Gauss-Seidel algorithm is established according to Kurdyka-Łojasiewicz property, whose convergence rate is also analyzed. Extensive numerical examples on real-world image datasets are carried out to demonstrate the superior performance of the proposed method as compared to several state-of-the-art methods in both accuracy and computational time. [ABSTRACT FROM AUTHOR]

In this paper, we provide an explicit expression for the proximity operator of a perspective of any proper lower semicontinuous convex function defined on a Hilbert space. Our computation enhances and generalizes known formulae for the case when the Fenchel conjugate of the convex function has an open domain or when it is radial. We show numerically that our approach is more efficient than previous approaches in the literature and we provide several examples of nonradial functions for which the domain of its conjugate is not open and we compute the proximity operators of their perspectives. [ABSTRACT FROM AUTHOR]

This paper presents a projection and contraction method with a double inertial extrapolation step and self-adaptive step sizes to solve variational inequalities with quasi-monotonicity in real Hilbert spaces. Weak and strong convergence results are obtained under some mild conditions. We also give linear convergence results under a special case of our proposed method. Preliminary numerical results show that our proposed method is competitive with other related methods in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we propose a first second-order scheme based on arbitrary non-Euclidean norms, incorporated by Bregman distances. They are introduced directly in the Newton iterate with regularization parameter proportional to the square root of the norm of the current gradient. For the basic scheme, as applied to the composite convex optimization problem, we establish the global convergence rate of the order O (k - 2) both in terms of the functional residual and in the norm of subgradients. Our main assumption on the smooth part of the objective is Lipschitz continuity of its Hessian. For uniformly convex functions of degree three, we justify global linear rate, and for strongly convex function we prove the local superlinear rate of convergence. Our approach can be seen as a relaxation of the Cubic Regularization of the Newton method (Nesterov and Polyak in Math Program 108(1):177–205, 2006) for convex minimization problems. This relaxation preserves the convergence properties and global complexities of the Cubic Newton in convex case, while the auxiliary subproblem at each iteration is simpler. We equip our method with adaptive search procedure for choosing the regularization parameter. We propose also an accelerated scheme with convergence rate O (k - 3) , where k is the iteration counter. [ABSTRACT FROM AUTHOR]

In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like "input", "size" and "complexity" in the context of general mathematical optimization, avoiding context dependent definitions which is one of the sources of difference in the treatment of complexity within continuous and discrete optimization. In the second part of the paper, we employ the language developed in the first part to study information theoretic and algorithmic complexity of mixed-integer convex optimization, which contains as a special case continuous convex optimization on the one hand and pure integer optimization on the other. We strive for the maximum possible generality in our exposition. We hope that this paper contains material that both continuous optimizers and discrete optimizers find new and interesting, even though almost all of the material presented is common knowledge in one or the other community. We see the main merit of this paper as bringing together all of this information under one unifying umbrella with the hope that this will act as yet another catalyst for more interaction across the continuous-discrete divide. In fact, our motivation behind Part I of the paper is to provide a common language for both communities. [ABSTRACT FROM AUTHOR]

In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon–Fletcher–Powell (DFP) method and the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite–time local convergence rate is not fully investigated. In this paper, we provide a finite–time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of (1 / k) k / 2 , where k is the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods. [ABSTRACT FROM AUTHOR]

The projected reflected gradient method has been shown to be a simple and elegant method for solving variational inequalities. The method involves one projection onto the feasible set and one evaluation of the cost operator per iteration and has been shown numerically to be more efficient than most available methods for solving variational inequalities. Convergence results for methods with similar elegant structures of projected reflected gradient method are still rare. In this paper, we present weak and linear convergence of a projected reflected gradient method with an inertial extrapolation step and give some applications arising from optimal control problems. We first obtain weak convergence result for the projected reflected gradient method with an inertial extrapolation step for solving variational inequalities under standard assumptions with self-adaptive step sizes. We further obtain a linear convergence rate when the cost operator is strongly monotone and Lipschitz continuous. Finally, we give some numerical applications arising from optimal control. Preliminary results show that our method is effective and efficient when compared to other related state-of-the-art methods in the literature and show the advantage gained by incorporating inertial terms into the projected reflected gradient methods. [ABSTRACT FROM AUTHOR]

In this paper, we develop an exact reformulation and a deterministic approximation for distributionally robust joint chance-constrained programmings $ ({\rm DRCCPs}) $ (DRCCPs) with a general class of convex uncertain constraints under data-driven Wasserstein ambiguity sets. It is known that robust chance constraints can be conservatively approximated by worst-case conditional value-at-risk (CVaR) constraints. It is shown that the proposed worst-case CVaR approximation model can be reformulated as an optimization problem involving biconvex constraints for joint DRCCP. This approximation is essentially exact under certain conditions. We derive a convex relaxation of this approximation model by constructing new decision variables which allows us to eliminate biconvex terms. Specifically, when the constraint function is affine in both the decision variable and the uncertainty, the resulting approximation model is equivalent to a tractable mixed-integer convex reformulation for joint binary DRCCP. Numerical results illustrate the computational effectiveness and superiority of the proposed formulations. [ABSTRACT FROM AUTHOR]

Many problems in machine learning write as the minimization of a sum of individual loss functions over the training examples. These functions are usually differentiable but, in some cases, their gradients are not Lipschitz continuous, which compromises the use of (proximal) gradient algorithms. Fortunately, changing the geometry and using Bregman divergences can alleviate this issue in several applications, such as for Poisson linear inverse problems. However, the Bregman operation makes the aggregation of several points and gradients more involved, hindering the distribution of computations for such problems. In this paper, we propose an asynchronous variant of the Bregman proximal-gradient method, able to adapt to any centralized computing system. In particular, we prove that the algorithm copes with arbitrarily long delays and we illustrate its behaviour on distributed Poisson inverse problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider a data-driven distributionally robust two-stage stochastic linear optimization problem over 1-Wasserstein ball centered at a discrete empirical distribution. Differently from the traditional two-stage stochastic programming which involves the expected recourse function as the preference criterion and hence is risk-neutral, we take the conditional value-at-risk (CVaR) as the risk measure in order to model its effects on decision making problems. We mainly explore tractable reformulations for the proposed robust two-stage stochastic programming with mean-CVaR criterion by analyzing the first case where uncertainties are only in the objective function and then the second case where uncertainties are only in the constraints. We demonstrate that the first model can be exactly reformulated as a deterministic convex programming. Furthermore, it is shown that under several different support sets, the resulting convex optimization problems can be converted into computationally tractable conic programmings. Besides, the second model is generally NP-hard since checking constraint feasibility can be reduced to a norm maximization problem over a polytope. However, even with the case of uncertainty in constraints, tractable conic reformulations can be established when the extreme points of the polytope are known. Finally, we present numerical results to discuss how to control the risk for the best decisions and illustrate the computational effectiveness and superiority of the proposed models. [ABSTRACT FROM AUTHOR]

This paper presents a Mehrotra-type predictor–corrector algorithm for monotone nonlinear complementarity problems over symmetric cones. The proposed algorithm is a second-order predictor–corrector interior point algorithm. Based on a one-norm wide neighbourhood, the iteration complexity of the algorithm is estimated and some numerical results are provided. The numerical results show that the algorithm is efficient and reliable. [ABSTRACT FROM AUTHOR]

The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to introduce a new cyclic iterative algorithm for finding a solution to the system of split equality zero-point problems in Hilbert spaces. The strong convergence of the proposed algorithm is established under some mild conditions. Moreover, this algorithm does not depend on the norm of the transfer mappings. Some applications of the main theorem to the related problems are also presented. [ABSTRACT FROM AUTHOR]

In this paper, a joint study of the behavior of solutions of the Heavy Ball ODE and Heavy Ball type algorithms is given. Since the pioneering work of Polyak (USSR Comput Math Math Phys 4(5):1–17, 1964), it is well known that such a scheme is very efficient for C 2 strongly convex functions with Lipschitz gradient. But much less is known when only growth conditions are considered. Depending on the geometry of the function to minimize, convergence rates for convex functions, with some additional regularity such as quasi-strong convexity, or strong convexity, were recently obtained in Aujol et al. (Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization, 2020). Convergence results with much weaker assumptions are given in the present paper: namely, linear convergence rates when assuming a growth condition (which amounts to a Łojasiewicz property in the convex case). This analysis is firstly performed in continuous time for the ODE, and then transposed for discrete optimization schemes. In particular, a variant of the Heavy Ball algorithm is proposed, which converges geometrically whatever the parameters choice, and which has the best state of the art convergence rate for first order methods to minimize composite non smooth convex functions satisfying a Łojasiewicz property. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a speed restarting scheme for the inertial dynamics with Hessian-driven damping, introduced by Attouch et al. (J Differ Equ 261(10):5734–5783, 2016). We establish a linear convergence rate for the function values along the restarted trajectories. Numerical experiments suggest that the Hessian-driven damping and the restarting scheme together improve the performance of the dynamics and corresponding iterative algorithms in practice. [ABSTRACT FROM AUTHOR]

This paper presents a greedy randomized average block sampling Gauss–Seidel (GRABGS) method for solving sparse linear least-squares problems. The GRABGS method utilizes a novel probability criterion to collect the control index set of coordinates, and minimizes the quadratic convex objective by performing multiple accurate line searches on average per iteration. The probability criterion aims to capture subvectors whose norms are relatively large. Additionly, the GRABGS method is categorized as a member of randomized block Gauss–Seidel methods, which can be employed for parallel implementations. The convergence analysis encompasses two types of extrapolation stepsizes: constant and adaptive. It is proved that the GRABGS method converges to the unique solution of the sparse linear least-squares problem when the matrix has full column rank. Numerical examples demonstrate the superiority of this method over the greedy randomized coordinate descent method and several existing state-of-the-art block Gauss–Seidel methods. [ABSTRACT FROM AUTHOR]

In this paper we focus on solving the classical variational inequality (VI) problem. Most common methods for solving VIs use some kind of projection onto the associated feasible set. Thus, when the involved set is not simple to project onto, then the applicability and computational effort of the proposed method could be arguable. One such scenario is when the given set is represented as a finite intersection of sublevel sets of convex functions. In this work we develop an outer approximation method that replaces the projection onto the VI's feasible set by a simple, closed formula projection onto some "superset". The proposed method also combines several known ideas such as the inertial technique and self-adaptive step size. Under standard assumptions, a strong minimum-norm convergence is proved and several numerical experiments validate and exhibit the performance of our scheme. [ABSTRACT FROM AUTHOR]

In this paper, we propose an alternated inertial general splitting method with linearization for a split feasibility problem. Four rules of inertial parameters and relaxation parameters are discussed, where the adaptive inertial parameters are firstly investigated. The convergence of the proposed method is established under standard conditions. The numerical examples are presented to test four choices of the parameters and illustrate the advantage of our methods. An application in signal processing is presented to illustrate the recovery of the proposed algorithm for the sparse signal. [ABSTRACT FROM AUTHOR]

In this paper, we propose three kinds of inertial approximation methods based on the proximal gradient algorithm to accelerate the convergence of the algorithm for solving convex bilevel optimization problems. Under reasonable parameters, we prove that our algorithms converge strongly to some solution of the problem, which is the unique solution of a variational inequality problem. Firstly, two alternated inertial methods are presented. Secondly, a multi-step inertial method is proposed to accelerate the convergence of the algorithm. Thirdly, an alternated multi-step inertial method is further introduced. In addition, we also consider that the inertial parameters can be chosen as positive or negative parameters, and we get better results. Our numerical results illustrate the performances of our algorithms and present some comparisons with related algorithms. Our results improve and extend the corresponding results reported by some authors recently. [ABSTRACT FROM AUTHOR]

In a Hilbert framework, for general convex differentiable optimization, we consider accelerated gradient dynamics combining Tikhonov regularization with Hessian-driven damping. The temporal discretization of these dynamics leads to a new class of first-order optimization algorithms with favorable properties. The Tikhonov regularization parameter is assumed to tend to zero as time tends to infinity, which preserves equilibria. The presence of the Tikhonov regularization term induces a strong property of convexity which vanishes asymptotically. To take advantage of the fast convergence rates attached to the heavy ball method in the strongly convex case, we consider inertial dynamics where the viscous damping coefficient is proportional to the square root of the Tikhonov regularization parameter, and hence converges to zero. The geometric damping, controlled by the Hessian of the function to be minimized, induces attenuation of the oscillations. Under an appropriate setting of the parameters, based on Lyapunov's analysis, we show that the trajectories provide at the same time several remarkable properties: fast convergence of values, fast convergence of gradients towards zero, and strong convergence to the minimum norm minimizer. We show that the corresponding proximal algorithms share the same properties as continuous dynamics. The numerical illustrations confirm the results obtained. This study extends a previous paper by the authors regarding similar problems without the presence of Hessian driven damping. [ABSTRACT FROM AUTHOR]

The exclusive lasso (also known as elitist lasso) regularizer has become popular recently due to its superior performance on intra-group feature selection. Its complex nature poses difficulties for the computation of high-dimensional machine learning models involving such a regularizer. In this paper, we propose a highly efficient dual Newton method based proximal point algorithm (PPDNA) for solving large-scale exclusive lasso models. As important ingredients, we systematically study the proximal mapping of the weighted exclusive lasso regularizer and the corresponding generalized Jacobian. These results also make popular first-order algorithms for solving exclusive lasso models more practical. Extensive numerical results are presented to demonstrate the superior performance of the PPDNA against other popular numerical algorithms for solving the exclusive lasso problems. [ABSTRACT FROM AUTHOR]

In this paper, a class of directionally differentiable multiobjective programming problems with inequality, equality and vanishing constraints is considered. Under both the Abadie constraint qualification and the modified Abadie constraint qualification, the Karush–Kuhn–Tucker type necessary optimality conditions are established for such nondifferentiable vector optimization problems by using the nonlinear version Gordan theorem of the alternative for convex functions. Further, the sufficient optimality conditions for such directionally differentiable multiobjective programming problems with vanishing constraints are proved under convexity hypotheses. Furthermore, vector Wolfe dual problem is defined for the considered directionally differentiable multiobjective programming problem vanishing constraints and several duality theorems are established also under appropriate convexity hypotheses. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze an inexact version of the symmetric proximal alternating direction method of multipliers (ADMM) for solving linearly constrained optimization problems. Basically, the method allows its first subproblem to be solved inexactly in such way that a relative approximate criterion is satisfied. In terms of the iteration number k, we establish global O (1 / k) pointwise and O (1 / k) ergodic convergence rates of the method for a domain of the acceleration parameters, which is consistent with the largest known one in the exact case. Since the symmetric proximal ADMM can be seen as a class of ADMM variants, the new algorithm as well as its convergence rates generalize, in particular, many others in the literature. Numerical experiments illustrating the practical advantages of the method are reported. To the best of our knowledge, this work is the first one to study an inexact version of the symmetric proximal ADMM. [ABSTRACT FROM AUTHOR]

The aim of this paper is to provide a general description of the Pareto subdifferential (weak and proper) of the sum of two cone-convex set-valued mappings in terms of sequences without any constraint qualifications. As an application, we derive sequential Lagrange multipliers optimality conditions for general set-valued optimization problem in terms of sequential Lagrange multipliers at nearby points for the Pareto efficient solutions, where no constraint qualification is assumed. [ABSTRACT FROM AUTHOR]

Mehrotra and Özevin (SIAM J Optim 19:1846–1880, 2009) computationally found that a weighted barrier decomposition algorithm for two-stage stochastic conic programs achieves significantly superior performance when compared to standard barrier decomposition algorithms existing in the literature. Inspired by this motivation, Mehrotra and Özevin (SIAM J Optim 20:2474–2486, 2010) theoretically analyzed the iteration complexity for a decomposition algorithm based on the weighted logarithmic barrier function for two-stage stochastic linear optimization with discrete support. In this paper, we extend the aforementioned theoretical paper and its self-concordance analysis from the polyhedral case to the semidefinite case and analyze the iteration complexity for a weighted logarithmic barrier decomposition algorithm for two-stage stochastic convex quadratic SDP with discrete support. [ABSTRACT FROM AUTHOR]

The inertial projection and contraction method and the inertial forward-backward-forward method have been studied for solving variational inequality problems due to the ability of these methods to work well with only one projection per iteration during computations. The inertial factor in these methods is chosen to be less than 1 in most of the papers that studied these methods. It is known from a computational point of view that the efficiency of these methods improves as the inertial factor approaches 1. In this paper, we modify both the inertial projection and contraction method and the inertial forward-backward-forward method with the possibility of inertial factor taken as 1. Our proposed methods also involve a step-size rule which does not depend on the Lipschitz constant of the cost function and without any line search rule. We analyse the weak convergence of the methods under appropriate conditions. We also modify the proposed methods so that strong convergence is obtained. Preliminary computational results show that our proposed methods are promising and show better performance than some variants of inertial projection and contraction methods and inertial forward-backward-forward methods where the inertial factor is assumed to be less than 1. [ABSTRACT FROM AUTHOR]

In this paper we show that simple projections can improve the algorithmic performance of cutting plane-based optimization methods. Projected cutting planes can, for example, be used as alternatives to standard cutting planes or supporting hyperplanes in the extended cutting plane (ECP) method. In the paper we analyse the properties of such an algorithm and prove that it will converge to a global optimum for smooth and nonsmooth convex mixed integer nonlinear programming problems. Additionally, we show that we are able to solve two old but very difficult facility layout problems (FLP), with previously unknown optimal solutions, to verified global optimum by using projected cutting planes in the algorithm. These solution results are also given in the paper. [ABSTRACT FROM AUTHOR]