Search

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 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]

Robust convex constraints are difficult to handle, since finding the worst-case scenario is equivalent to maximizing a convex function. In this paper, we propose a new approach to deal with such constraints that unifies most approaches known in the literature and extends them in a significant way. The extension is either obtaining better solutions than the ones proposed in the literature, or obtaining solutions for classes of problems unaddressed by previous approaches. Our solution is based on an extension of the Reformulation-Linearization-Technique, and can be applied to general convex inequalities and general convex uncertainty sets. It generates a sequence of conservative approximations which can be used to obtain both upper- and lower- bounds for the optimal objective value. We illustrate the numerical benefit of our approach on a robust control and robust geometric optimization example. [ABSTRACT FROM AUTHOR]

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

In this paper, we present difference of convex algorithms for solving bilevel programs in which the upper level objective functions are difference of convex functions, and the lower level programs are fully convex. This nontrivial class of bilevel programs provides a powerful modelling framework for dealing with applications arising from hyperparameter selection in machine learning. Thanks to the full convexity of the lower level program, the value function of the lower level program turns out to be convex and hence the bilevel program can be reformulated as a difference of convex bilevel program. We propose two algorithms for solving the reformulated difference of convex program and show their convergence to stationary points under very mild assumptions. Finally we conduct numerical experiments to a bilevel model of support vector machine classification. [ABSTRACT FROM AUTHOR]

For two matroids M 1 and M 2 with the same ground set V and two cost functions w 1 and w 2 on 2 V , we consider the problem of finding bases X 1 of M 1 and X 2 of M 2 minimizing w 1 (X 1) + w 2 (X 2) subject to a certain cardinality constraint on their intersection X 1 ∩ X 2 . For this problem, Lendl et al. (Matroid bases with cardinality constraints on the intersection, arXiv:1907.04741v2, 2019) discussed modular cost functions: they reduced the problem to weighted matroid intersection for the case where the cardinality constraint is | X 1 ∩ X 2 | ≤ k or | X 1 ∩ X 2 | ≥ k ; and designed a new primal-dual algorithm for the case where the constraint is | X 1 ∩ X 2 | = k . The aim of this paper is to generalize the problems to have nonlinear convex cost functions, and to comprehend them from the viewpoint of discrete convex analysis. We prove that each generalized problem can be solved via valuated independent assignment, valuated matroid intersection, or M -convex submodular flow, to offer a comprehensive understanding of weighted matroid intersection with intersection constraints. We also show the NP-hardness of some variants of these problems, which clarifies the coverage of discrete convex analysis for those problems. Finally, we present applications of our generalized problems in the recoverable robust matroid basis problem, combinatorial optimization problems with interaction costs, and matroid congestion games. [ABSTRACT FROM AUTHOR]

This paper concerns the worst-case complexity of cyclic coordinate descent (C-CD) for minimizing a convex quadratic function, which is equivalent to Gauss–Seidel method, Kaczmarz method and projection onto convex sets (POCS) in this simple setting. We observe that the known provable complexity of C-CD can be O (n 2) times slower than randomized coordinate descent (R-CD), but no example was proven to exhibit such a large gap. In this paper we show that the gap indeed exists. We prove that there exists an example for which C-CD takes at least O (n 4 κ CD log 1 ϵ) operations, where κ CD is related to Demmel's condition number and it determines the convergence rate of R-CD. It implies that in the worst case C-CD can indeed be O (n 2) times slower than R-CD, which has complexity O (n 2 κ CD log 1 ϵ) . Note that for this example, the gap exists for any fixed update order, not just a particular order. An immediate consequence is that for Gauss–Seidel method, Kaczmarz method and POCS, there is also an O (n 2) gap between the cyclic versions and randomized versions (for solving linear systems). One difficulty with the analysis is that the spectral radius of a non-symmetric iteration matrix does not necessarily constitute a lower bound for the convergence rate. Finally, we design some numerical experiments to show that the size of the off-diagonal entries is an important indicator of the practical performance of C-CD. [ABSTRACT FROM AUTHOR]

Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a one-dimensional convex function and an affine function under arbitrary combinatorial constraints. As special cases of this result, we derive ideal convexifications for problems with hierarchy, multi-collinearity, and sparsity constraints. Moreover, we also give a short proof that for a separable objective function, the perspective reformulation is ideal independent from the constraints of the problem. Our computational experiments with sparse regression problems demonstrate the potential of the proposed approach in improving the relaxation quality without significant computational overhead. [ABSTRACT FROM AUTHOR]

It is well-known that the sum of two quasiconvex functions is not quasiconvex in general, and the same occurs with the minimum. Although apparently these two statements (for the sum or minimum) have nothing in common, they are related, as we show in this paper. To develop our study, the notion of quasiconvex family is introduced, and we establish various characterizations of such a concept: one of them being the quasiconvexity of the pointwise infimum of arbitrary translations of quasiconvex functions in the family; another is the convexity of the union of any two of their sublevel sets; a third one is the quasiconvexity of the sum of the quasiconvex functions, composed with arbitrary nondecreasing functions. As a by-product, any of the aforementioned characterizations, besides providing quasiconvexity of the sum, also implies the semistrict quasiconvexity of the sum if every function in the family has the same property. Three concrete applications in quasiconvex optimization are presented: First, we establish the convexity of the (Benson) proper efficient solution set to a quasiconvex vector optimization problem; second, we derive conditions that allow us to reduce a constrained optimization problem to one with a single inequality constraint, and finally, we show a class of quasiconvex minimization problems having zero duality gap. [ABSTRACT FROM AUTHOR]

In this paper, we present diverse new metric properties that prox-regular sets shared with convex ones. At the heart of our work lie the Legendre-Fenchel transform and complements of balls. First, we show that a connected prox-regular set is completely determined by the Legendre-Fenchel transform of a suitable perturbation of its indicator function. Then, we prove that such a function is also the right tool to extend, to the context of prox-regular sets, the famous connection between the distance function and the support function of a convex set. On the other hand, given a prox-regular set, we examine the intersection of complements of open balls containing the set. We establish that the distance of a point to a prox-regular set is the maximum of the distances of the point from boundaries of all such complements separating the set and the point. This is in the line of the known result expressing the distance from a convex set in terms of separating hyperplanes. To the best of our knowledge, these results are new in the literature and show that the class of prox-regular sets have good properties known in convex analysis. [ABSTRACT FROM AUTHOR]

In this paper we establish general formulas for the subdifferential of the pointwise supremum of convex functions, which cover and unify both the compact continuous and the non-compact non-continuous settings. From the non-continuous to the continuous setting, we proceed by a compactification-based approach which leads us to problems having compact index sets and upper semi-continuously indexed mappings, giving rise to new characterizations of the subdifferential of the supremum by means of upper semicontinuous regularized functions and an enlarged compact index set. In the opposite sense, we rewrite the subdifferential of these new regularized functions by using the original data, also leading us to new results on the subdifferential of the supremum. We give two applications in the last section, the first one concerning the nonconvex Fenchel duality, and the second one establishing Fritz-John and KKT conditions in convex semi-infinite programming. [ABSTRACT FROM AUTHOR]

In this paper we discuss the simple bilevel programming problem (SBP) and its extension, the simple mathematical programming problem under equilibrium constraints (SMPEC). Here we first define both these problems and study their interrelations. Next we study the various types of necessary and sufficient optimality conditions for the (SMPEC) problems, which occur under various reformulations. The optimality conditions for (SBP) are special cases of the results obtained for (SMPEC) when the lower level objective is the gradient of a convex function. Among the various optimality conditions presented in this article are the sequential optimality conditions, which do not need any constraint qualification. We also present a schematic algorithm for (SMPEC), where the sequential optimality conditions play a key role in the convergence analysis. [ABSTRACT FROM AUTHOR]

We analyze the convergence rate of the random reshuffling (RR) method, which is a randomized first-order incremental algorithm for minimizing a finite sum of convex component functions. RR proceeds in cycles, picking a uniformly random order (permutation) and processing the component functions one at a time according to this order, i.e., at each cycle, each component function is sampled without replacement from the collection. Though RR has been numerically observed to outperform its with-replacement counterpart stochastic gradient descent (SGD), characterization of its convergence rate has been a long standing open question. In this paper, we answer this question by providing various convergence rate results for RR and variants when the sum function is strongly convex. We first focus on quadratic component functions and show that the expected distance of the iterates generated by RR with stepsize α k = Θ (1 / k s) for s ∈ (0 , 1 ] converges to zero at rate O (1 / k s) (with s = 1 requiring adjusting the stepsize to the strong convexity constant). Our main result shows that when the component functions are quadratics or smooth (with a Lipschitz assumption on the Hessian matrices), RR with iterate averaging and a diminishing stepsize α k = Θ (1 / k s) for s ∈ (1 / 2 , 1) converges at rate Θ (1 / k 2 s) with probability one in the suboptimality of the objective value, thus improving upon the Ω (1 / k) rate of SGD. Our analysis draws on the theory of Polyak–Ruppert averaging and relies on decoupling the dependent cycle gradient error into an independent term over cycles and another term dominated by α k 2 . This allows us to apply law of large numbers to an appropriately weighted version of the cycle gradient errors, where the weights depend on the stepsize. We also provide high probability convergence rate estimates that shows decay rate of different terms and allows us to propose a modification of RR with convergence rate O (1 k 2) . [ABSTRACT FROM AUTHOR]

We consider optimization algorithms that successively minimize simple Taylor-like models of the objective function. Methods of Gauss–Newton type for minimizing the composition of a convex function and a smooth map are common examples. Our main result is an explicit relationship between the step-size of any such algorithm and the slope of the function at a nearby point. Consequently, we (1) show that the step-sizes can be reliably used to terminate the algorithm, (2) prove that as long as the step-sizes tend to zero, every limit point of the iterates is stationary, and (3) show that conditions, akin to classical quadratic growth, imply that the step-sizes linearly bound the distance of the iterates to the solution set. The latter so-called error bound property is typically used to establish linear (or faster) convergence guarantees. Analogous results hold when the step-size is replaced by the square root of the decrease in the model's value. We complete the paper with extensions to when the models are minimized only inexactly. [ABSTRACT FROM AUTHOR]

We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. Our major contribution is to present a new class of decentralized primal–dual type algorithms, namely the decentralized communication sliding (DCS) methods, which can skip the inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions. By employing DCS, agents can find an ϵ -solution both in terms of functional optimality gap and feasibility residual in O (1 / ϵ) (resp., O (1 / ϵ) ) communication rounds for general convex functions (resp., strongly convex functions), while maintaining the O (1 / ϵ 2) (resp., O (1 / ϵ) ) bound on the total number of intra-node subgradient evaluations. We also present a stochastic counterpart for these algorithms, denoted by SDCS, for solving stochastic optimization problems whose objective function cannot be evaluated exactly. In comparison with existing results for decentralized nonsmooth and stochastic optimization, we can reduce the total number of inter-node communication rounds by orders of magnitude while still maintaining the optimal complexity bounds on intra-node stochastic subgradient evaluations. The bounds on the (stochastic) subgradient evaluations are actually comparable to those required for centralized nonsmooth and stochastic optimization under certain conditions on the target accuracy. [ABSTRACT FROM AUTHOR]

The possibilities of exploiting the special structure of d.c. programs, which consist of optimising the difference of convex functions, are currently more or less limited to variants of the DCA proposed by Pham Dinh Tao and Le Thi Hoai An in 1997. These assume that either the convex or the concave part, or both, are evaluated by one of their subgradients. In this paper we propose an algorithm which allows the evaluation of both the concave and the convex part by their proximal points. Additionally, we allow a smooth part, which is evaluated via its gradient. In the spirit of primal-dual splitting algorithms, the concave part might be the composition of a concave function with a linear operator, which are, however, evaluated separately. For this algorithm we show that every cluster point is a solution of the optimisation problem. Furthermore, we show the connection to the Toland dual problem and prove a descent property for the objective function values of a primal-dual formulation of the problem. Convergence of the iterates is shown if this objective function satisfies the Kurdyka–Łojasiewicz property. In the last part, we apply the algorithm to an image processing model. [ABSTRACT FROM AUTHOR]

Representability results play a fundamental role in optimization since they provide characterizations of the feasible sets that arise from optimization problems. In this paper we study the sets that appear in the feasibility version of mixed binary convex quadratic optimization problems. We provide a complete characterization of the sets that can be obtained as the projection of such feasible regions. In order to obtain this result, we first provide a complete characterization of these sets in the special cases where (1) the feasible region is bounded, (2) only binary extended variables are present, and (3) only continuous variables are present. [ABSTRACT FROM AUTHOR]

This paper studies several classes of nonconvex optimization problems defined over convex cones, establishing connections between them and demonstrating that they can be equivalently formulated as convex completely positive programs. The problems being studied include: a conic quadratically constrained quadratic program (QCQP), a conic quadratic program with complementarity constraints (QPCC), and rank constrained semidefinite programs. Our results do not make any boundedness assumptions on the feasible regions of the various problems considered. The first stage in the reformulation is to cast the problem as a conic QCQP with just one nonconvex constraint $$q(x) \le 0$$ , where q( x) is nonnegative over the (convex) conic and linear constraints, so the problem fails the Slater constraint qualification. A conic QPCC has such a structure; we prove the converse, namely that any conic QCQP satisfying a constraint qualification can be expressed as an equivalent conic QPCC. The second stage of the reformulation lifts the problem to a completely positive program, and exploits and generalizes a result of Burer. We also show that a Frank-Wolfe type result holds for a subclass of this class of conic QCQPs. Further, we derive necessary and sufficient optimality conditions for nonlinear programs where the only nonconvex constraint is a quadratic constraint of the structure considered elsewhere in the paper. [ABSTRACT FROM AUTHOR]

This paper considers a networked system with a finite number of users and supposes that each user tries to minimize its own private objective function over its own private constraint set. It is assumed that each user's constraint set can be expressed as a fixed point set of a certain quasi-nonexpansive mapping. This enables us to consider the case in which the projection onto the constraint set cannot be computed efficiently. This paper proposes two methods for solving the problem of minimizing the sum of their nondifferentiable, convex objective functions over the intersection of their fixed point sets of quasi-nonexpansive mappings in a real Hilbert space. One method is a parallel subgradient method that can be implemented under the assumption that each user can communicate with other users. The other is an incremental subgradient method that can be implemented under the assumption that each user can communicate with its neighbors. Investigation of the two methods' convergence properties for a constant step size reveals that, with a small constant step size, they approximate a solution to the problem. Consideration of the case in which the step-size sequence is diminishing demonstrates that the sequence generated by each of the two methods strongly converges to the solution to the problem under certain assumptions. Convergence rate analysis of the two methods under certain situations is provided to illustrate the two methods' efficiency. This paper also discusses nonsmooth convex optimization over sublevel sets of convex functions and provides numerical comparisons that demonstrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

This paper is concerned with the minimization of an objective that is the sum of a convex function f and an $$\ell _1$$ regularization term. Our interest is in active-set methods that incorporate second-order information about the function f to accelerate convergence. We describe a semismooth Newton framework that can be used to generate a variety of second-order methods, including block active set methods, orthant-based methods and a second-order iterative soft-thresholding method. The paper proposes a new active set method that performs multiple changes in the active manifold estimate at every iteration, and employs a mechanism for correcting these estimates, when needed. This corrective mechanism is also evaluated in an orthant-based method. Numerical tests comparing the performance of three active set methods are presented. [ABSTRACT FROM AUTHOR]

Computational methods are proposed for solving a convex quadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate a sequence of iterates that are feasible with respect to the equality constraints associated with the optimality conditions of the primal-dual form. The primal method maintains feasibility of the primal inequalities while driving the infeasibilities of the dual inequalities to zero. The dual method maintains feasibility of the dual inequalities while moving to satisfy the primal inequalities. In each of these methods, the search directions satisfy a KKT system of equations formed from Hessian and constraint components associated with an appropriate column basis. The composition of the basis is specified by an active-set strategy that guarantees the nonsingularity of each set of KKT equations. Each of the proposed methods is a conventional active-set method in the sense that an initial primal- or dual-feasible point is required. In the second part of the paper, it is shown how the quadratic program may be solved as a coupled pair of primal and dual quadratic programs created from the original by simultaneously shifting the simple-bound constraints and adding a penalty term to the objective function. Any conventional column basis may be made optimal for such a primal-dual pair of shifted-penalized problems. The shifts are then updated using the solution of either the primal or the dual shifted problem. An obvious application of this approach is to solve a shifted dual QP to define an initial feasible point for the primal (or vice versa). The computational performance of each of the proposed methods is evaluated on a set of convex problems from the CUTEst test collection. [ABSTRACT FROM AUTHOR]

We consider the classification problem when the input features are represented as matrices rather than vectors. To preserve the intrinsic structures for classification, a successful method is the support matrix machine (SMM) in Luo et al. (in: Proceedings of the 32nd international conference on machine learning, Lille, France, no 1, pp 938–947, 2015), which optimizes an objective function with a hinge loss plus a so-called spectral elastic net penalty. However, the issues of extending SMM to multicategory classification still remain. Moreover, in practice, it is common to see the training data contaminated by outlying observations, which can affect the robustness of existing matrix classification methods. In this paper, we address these issues by introducing a robust angle-based classifier, which boils down binary and multicategory problems to a unified framework. Benefitting from the use of truncated hinge loss functions, the proposed classifier achieves certain robustness to outliers. The underlying optimization model becomes nonconvex, but admits a natural DC (difference of two convex functions) representation. We develop a new and efficient algorithm by incorporating the DC algorithm and primal–dual first-order methods together. The proposed DC algorithm adaptively chooses the accuracy of the subproblem at each iteration while guaranteeing the overall convergence of the algorithm. The use of primal–dual methods removes a natural complexity of the linear operator in the subproblems and enables us to use the proximal operator of the objective functions, and matrix–vector operations. This advantage allows us to solve large-scale problems efficiently. Theoretical and numerical results indicate that for problems with potential outliers, our method can be highly competitive among existing methods. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of structured nonsmooth difference-of-convex (DC) minimization in which the first convex component is the sum of a smooth and nonsmooth functions while the second convex component is the supremum of possibly infinitely many convex smooth functions. We first propose an inexact enhanced DC algorithm for solving this problem in which the second convex component is the supremum of finitely many convex smooth functions, and show that every accumulation point of the generated sequence is an (α , η) -D-stationary point of the problem, which is generally stronger than an ordinary D-stationary point. In addition, inspired by the recent work (Pang et al. in Math Oper Res 42(1):95–118, 2017; Wen et al. in Comput Optim Appl 69(2):297–324, 2018), we propose two proximal DC algorithms with extrapolation for solving this problem. We show that every accumulation point of the solution sequence generated by them is an (α , η) -D-stationary point of the problem, and establish the convergence of the entire sequence under some suitable assumption. We also introduce a concept of approximate (α , η) -D-stationary point and derive iteration complexity of the proposed algorithms for finding an approximate (α , η) -D-stationary point. In contrast with the DC algorithm (Pang et al. 2017), our proximal DC algorithms have much simpler subproblems and also incorporate the extrapolation for possible acceleration. Moreover, one of our proximal DC algorithms is potentially applicable to the DC problem in which the second convex component is the supremum of infinitely many convex smooth functions. In addition, our algorithms have stronger convergence results than the proximal DC algorithm in Wen et al. (2018). [ABSTRACT FROM AUTHOR]

We propose dynamic sampled stochastic approximation (SA) methods for stochastic optimization with a heavy-tailed distribution (with finite 2nd moment). The objective is the sum of a smooth convex function with a convex regularizer. Typically, it is assumed an oracle with an upper bound σ 2 on its variance (OUBV). Differently, we assume an oracle with multiplicative noise. This rarely addressed setup is more aggressive but realistic, where the variance may not be uniformly bounded. Our methods achieve optimal iteration complexity and (near) optimal oracle complexity. For the smooth convex class, we use an accelerated SA method a la FISTA which achieves, given tolerance ε > 0 , the optimal iteration complexity of O (ε - 1 2 ) with a near-optimal oracle complexity of O (ε - 2) [ ln (ε - 1 2 ) ] 2 . This improves upon Ghadimi and Lan (Math Program 156:59–99, 2016) where it is assumed an OUBV. For the strongly convex class, our method achieves optimal iteration complexity of O (ln (ε - 1)) and optimal oracle complexity of O (ε - 1) . This improves upon Byrd et al. (Math Program 134:127–155, 2012) where it is assumed an OUBV. In terms of variance, our bounds are local: they depend on variances σ (x ∗) 2 at solutions x ∗ and the per unit distance multiplicative variance σ L 2 . For the smooth convex class, there exist policies such that our bounds resemble, up to absolute constants, those obtained in the mentioned papers if it was assumed an OUBV with σ 2 : = σ (x ∗) 2 . For the strongly convex class such property is obtained exactly if the condition number is estimated or in the limit for better conditioned problems or for larger initial batch sizes. In any case, if it is assumed an OUBV, our bounds are thus sharper since typically max { σ (x ∗) 2 , σ L 2 } ≪ σ 2 . [ABSTRACT FROM AUTHOR]

In this paper we study local error bound moduli for a locally Lipschitz and regular function via outer limiting subdifferential sets. We show that the distance from 0 to the outer limiting subdifferential of the support function of the subdifferential set, which is essentially the distance from 0 to the end set of the subdifferential set, is an upper estimate of the local error bound modulus. This upper estimate becomes tight for a convex function under some regularity conditions. We show that the distance from 0 to the outer limiting subdifferential set of a lower C1 function is equal to the local error bound modulus. [ABSTRACT FROM AUTHOR]

This paper is devoted to the design of an efficient and convergent semi-proximal alternating direction method of multipliers (ADMM) for finding a solution of low to medium accuracy to convex quadratic conic programming and related problems. For this class of problems, the convergent two block semi-proximal ADMM can be employed to solve their primal form in a straightforward way. However, it is known that it is more efficient to apply the directly extended multi-block semi-proximal ADMM, though its convergence is not guaranteed, to the dual form of these problems. Naturally, one may ask the following question: can one construct a convergent multi-block semi-proximal ADMM that is more efficient than the directly extended semi-proximal ADMM? Indeed, for linear conic programming with 4-block constraints this has been shown to be achievable in a recent paper by Sun et al. (, ). Inspired by the aforementioned work and with the convex quadratic conic programming in mind, we propose a Schur complement based convergent semi-proximal ADMM for solving convex programming problems, with a coupling linear equality constraint, whose objective function is the sum of two proper closed convex functions plus an arbitrary number of convex quadratic or linear functions. Our convergent semi-proximal ADMM is particularly suitable for solving convex quadratic semidefinite programming (QSDP) with constraints consisting of linear equalities, a positive semidefinite cone and a simple convex polyhedral set. The efficiency of our proposed algorithm is demonstrated by numerical experiments on various examples including QSDP. [ABSTRACT FROM AUTHOR]

In this paper, we consider the maximum and minimum versions of degree-concentrated fault-tolerant spanning subgraph problem which has many applications in network communications. We prove that both this two problems are NP-hard. For the maximum version, we use DC programming relaxation to propose a heuristic algorithm. Numerical tests indicate that the proposed algorithm is efficient and effective. For the minimum version, we also formulate it as a DC program, and show that the DC algorithm does not perform well for this problem. [ABSTRACT FROM AUTHOR]

This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach. [ABSTRACT FROM AUTHOR]

The aim of this paper is to show that every representative function of a maximally monotone operator is the Fitzpatrick transform of a bifunction corresponding to the operator. In fact, for each representative function φ of the operator, there is a family of equivalent saddle functions (i.e., bifunctions which are concave in the first and convex in the second argument) each of which has φ as Fitzpatrick transform. In the special case where φ is the Fitzpatrick function of the operator, the family of equivalent saddle functions is explicitly constructed. In this way we exhibit the relation between the recent theory of representative functions, and the much older theory of saddle functions initiated by Rockafellar. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of non-Lipschitz and non-convex minimization problems which generalize the $$L_2$$ - $$L_p$$ minimization problem. We propose an iterative algorithm that decides the next iteration based on the local convexity/concavity/sparsity of its current position. We show that our algorithm finds an $$\epsilon $$ -KKT point within $$O(\log {\epsilon ^{-1}})$$ iterations from certain initial points. The same result is also applied to the problem with general linear constraints under mild conditions. [ABSTRACT FROM AUTHOR]

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems. [ABSTRACT FROM AUTHOR]

Recently, Bandeira (C R Math, 2015) introduced a new type of algorithm (the so-called probably certifiably correct algorithm) that combines fast solvers with the optimality certificates provided by convex relaxations. In this paper, we devise such an algorithm for the problem of k-means clustering. First, we prove that Peng and Wei's semidefinite relaxation of k-means Peng and Wei (SIAM J Optim 18(1):186-205, 2007) is tight with high probability under a distribution of planted clusters called the stochastic ball model. Our proof follows from a new dual certificate for integral solutions of this semidefinite program. Next, we show how to test the optimality of a proposed k-means solution using this dual certificate in quasilinear time. Finally, we analyze a version of spectral clustering from Peng and Wei (SIAM J Optim 18(1):186-205, 2007) that is designed to solve k-means in the case of two clusters. In particular, we show that this quasilinear-time method typically recovers planted clusters under the stochastic ball model. [ABSTRACT FROM AUTHOR]

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

In this paper we study the t-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to ( n−1)-branch split cuts. It was shown earlier by Cook et al. (Math Program 47:155–174, 1990) that this conjecture is true when n = 2, and Li and Richard proved the conjecture when n = 3. In this paper we show that this conjecture is also true for all n > 3. [ABSTRACT FROM AUTHOR]

We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $${O(1/\epsilon)}$$ iterations to obtain an $${\epsilon}$$ -optimal solution, while our accelerated (i.e., fast) versions of them require at most $${O(1/\sqrt{\epsilon})}$$ iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in (Fast multiple splitting algorithms for convex optimization, Columbia University, 2009 ) where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to characterize the weak efficient solutions, the efficient solutions, and the isolated efficient solutions of a given vector optimization problem with finitely many convex objective functions and infinitely many convex constraints. To do this, we introduce new and already known data qualifications (conditions involving the constraints and/or the objectives) in order to get optimality conditions which are expressed in terms of either Karusk-Kuhn-Tucker multipliers or a new gap function associated with the given problem. [ABSTRACT FROM AUTHOR]

In this paper we consider an aggregation technique introduced by Yıldıran (J Math Control Inf 26:417-450, 2009) to study the convex hull of regions defined by two quadratic inequalities or by a conic quadratic and a quadratic inequality. Yıldıran (2009) shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities. We show how this aggregation technique can be easily extended to yield valid conic quadratic inequalities for the convex hull of open sets defined by two strict quadratic inequalities or by a strict conic quadratic and a strict quadratic inequality. We also show that for sets defined by a strict conic quadratic and a strict quadratic inequality, under one additional containment assumption, these valid inequalities characterize the convex hull exactly. We also show that under certain topological assumptions, the results from the open setting can be extended to characterize the closed convex hull of sets defined with non-strict conic and quadratic inequalities. [ABSTRACT FROM AUTHOR]

The Douglas-Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the algorithm remains mysterious in the general inconsistent case, i.e., when the sum problem has no zeros. However, more than a decade ago, it was shown that in the (possibly inconsistent) convex feasibility setting, the shadow sequence remains bounded and its weak cluster points solve a best approximation problem. In this paper, we advance the understanding of the inconsistent case significantly by providing a complete proof of the full weak convergence in the convex feasibility setting. In fact, a more general sufficient condition for the weak convergence in the general case is presented. Our proof relies on a new convergence principle for Fejér monotone sequences. Numerous examples illustrate our results. [ABSTRACT FROM AUTHOR]

Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is that there exist no theoretically guaranteed bounds on the quality of the configuration. The other is that they are slow in computation when the data points are beyond moderate size. In this paper, we propose a convex optimization model of Euclidean distance matrices. We establish a non-asymptotic error bound for the random graph model with sub-Gaussian noise, and prove that our model produces a matrix estimator of high accuracy when the order of the uniform sample size is roughly the degree of freedom of a low-rank matrix up to a logarithmic factor. Our results partially explain why MVU and MVE often work well. Moreover, the convex optimization model can be efficiently solved by a recently proposed 3-block alternating direction method of multipliers. Numerical experiments show that the model can produce configurations of high quality on large data points that the SDP approach would struggle to cope with. [ABSTRACT FROM AUTHOR]

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth $$\ell _1$$ regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function. [ABSTRACT FROM AUTHOR]

We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle (Math Program 145(1-2):451-482, 2014. doi:) recently described a numerical method for computing the N-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods (Polyak in USSR Comput Math Math Phys 4(5):1-17, 1964. doi:), and Nesterov's fast gradient methods (Nesterov in Sov Math Dokl 27(2):372-376, 1983; Math Program 103(1):127-152, 2005. doi:). However, the numerical method in Drori and Teboulle (2014) is computationally expensive for large N, and the corresponding numerically optimized first-order algorithm in Drori and Teboulle (2014) requires impractical memory and computation for large-scale optimization problems. In this paper, we propose optimized first-order algorithms that achieve a convergence bound that is two times smaller than for Nesterov's fast gradient methods; our bound is found analytically and refines the numerical bound in Drori and Teboulle (2014). Furthermore, the proposed optimized first-order methods have efficient forms that are remarkably similar to Nesterov's fast gradient methods. [ABSTRACT FROM AUTHOR]

This paper studies $$\mathcal {K}$$ -sublinear inequalities, a class of inequalities with strong relations to $$\mathcal {K}$$ -minimal inequalities for disjunctive conic sets. We establish a stronger result on the sufficiency of $$\mathcal {K}$$ -sublinear inequalities. That is, we show that when $$\mathcal {K}$$ is the nonnegative orthant or the second-order cone, $$\mathcal {K}$$ -sublinear inequalities together with the original conic constraint are always sufficient for the closed convex hull description of the associated disjunctive conic set. When $$\mathcal {K}$$ is the nonnegative orthant, $$\mathcal {K}$$ -sublinear inequalities are tightly connected to functions that generate cuts-so called cut-generating functions. In particular, we introduce the concept of relaxed cut-generating functions and show that each $${\mathbb {R}}^n_+$$ -sublinear inequality is generated by one of these. We then relate the relaxed cut-generating functions to the usual ones studied in the literature. Recently, under a structural assumption, Cornuéjols, Wolsey and Yıldız established the sufficiency of cut-generating functions in terms of generating all nontrivial valid inequalities of disjunctive sets where the underlying cone is nonnegative orthant. We provide an alternate and straightforward proof of this result under the same assumption as a consequence of the sufficiency of $$\mathbb {R}^n_+$$ -sublinear inequalities and their connection with relaxed cut-generating functions. [ABSTRACT FROM AUTHOR]

The paper concerns the study of new classes of parametric optimization problems of the so-called infinite programming that are generally defined on infinite-dimensional spaces of decision variables and contain, among other constraints, infinitely many inequality constraints. These problems reduce to semi-infinite programs in the case of finite-dimensional spaces of decision variables. We focus on DC infinite programs with objectives given as the difference of convex functions subject to convex inequality constraints. The main results establish efficient upper estimates of certain subdifferentials of (intrinsically nonsmooth) value functions in DC infinite programs based on advanced tools of variational analysis and generalized differentiation. The value/marginal functions and their subdifferential estimates play a crucial role in many aspects of parametric optimization including well-posedness and sensitivity. In this paper we apply the obtained subdifferential estimates to establishing verifiable conditions for the local Lipschitz continuity of the value functions and deriving necessary optimality conditions in parametric DC infinite programs and their remarkable specifications. Finally, we employ the value function approach and the established subdifferential estimates to the study of bilevel finite and infinite programs with convex data on both lower and upper level of hierarchical optimization. The results obtained in the paper are new not only for the classes of infinite programs under consideration but also for their semi-infinite counterparts. [ABSTRACT FROM AUTHOR]

In this paper two simple examples of a twice continuously differentiable strictly convex function $$f$$ are presented for which Newton's method with line search converges to a point where the gradient of $$f$$ is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex function $$f$$ is defined as well as a sequence of descent directions for which exact line searches do not converge to the minimizer of $$f$$ . Then $$f$$ is perturbed such that these search directions coincide with the Newton directions for the perturbed function while leaving the exact line search invariant. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex, finite-dimensional domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst case number of iterations needed to achieve a given accuracy is independent of the dimension and-apart from a constant factor-best possible under a variety of smoothness assumptions on the objective function. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend the ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of more than two separable convex functions. However, the convergence of this extension has been missing for a long time-neither an affirmative convergence proof nor an example showing its divergence is known in the literature. In this paper we give a negative answer to this long-standing open question: The direct extension of ADMM is not necessarily convergent. We present a sufficient condition to ensure the convergence of the direct extension of ADMM, and give an example to show its divergence. [ABSTRACT FROM AUTHOR]

In this paper we prove that the broad class of direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, exhibits the same worst case complexity bound and global rate of the gradient method for the unconstrained minimization of a convex and smooth function. More precisely, it will be shown that the number of iterations needed to reduce the norm of the gradient of the objective function below a certain threshold is at most proportional to the inverse of the threshold. It will be also shown that the absolute error in the function values decay at a sublinear rate proportional to the inverse of the iteration counter. In addition, we prove that the sequence of absolute errors of function values and iterates converges r-linearly in the strongly convex case. [ABSTRACT FROM AUTHOR]

A $$0$$ -extension of graph $$\varGamma $$ is a metric $$d$$ on a set $$V$$ containing the vertex set $$V_{\varGamma }$$ of $$\varGamma $$ such that $$d$$ extends the shortest path metric of $$\varGamma $$ and for all $$x \in V$$ there exists a vertex $$s$$ in $$\varGamma $$ with $$d(x,s) = 0$$ . The minimum $$0$$ -extension problem 0-Ext $$[\varGamma ]$$ on $$\varGamma $$ is: given a set $$V \supseteq V_{\varGamma }$$ and a nonnegative cost function $$c$$ defined on the set of all pairs of $$V$$ , find a $$0$$ -extension $$d$$ of $$\varGamma $$ with $$\sum _{xy}c(xy) d(x,y)$$ minimum. The $$0$$ -extension problem generalizes a number of basic combinatorial optimization problems, such as minimum $$(s,t)$$ -cut problem and multiway cut problem. Karzanov proved the polynomial solvability of 0-Ext $$[\varGamma ]$$ for a certain large class of modular graphs $$\varGamma $$ , and raised the question: What are the graphs $$\varGamma $$ for which 0-Ext $$[\varGamma ]$$ can be solved in polynomial time? He also proved that 0-Ext $$[\varGamma ]$$ is NP-hard if $$\varGamma $$ is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if $$\varGamma $$ is orientable and modular, then 0-Ext $$[\varGamma ]$$ can be solved in polynomial time. This completes the classification of graphs $$\varGamma $$ for which 0-Ext $$[\varGamma ]$$ is tractable. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Živný on valued CSP. [ABSTRACT FROM AUTHOR]

In this paper, we present new methods for black-box convex minimization. They do not need to know in advance the actual level of smoothness of the objective function. Their only essential input parameter is the required accuracy of the solution. At the same time, for each particular problem class they automatically ensure the best possible rate of convergence. We confirm our theoretical results by encouraging numerical experiments, which demonstrate that the fast rate of convergence, typical for the smooth optimization problems, sometimes can be achieved even on nonsmooth problem instances. [ABSTRACT FROM AUTHOR]

In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341-362, ), Richtárik and Takáč (Math Program 144(1-2):1-38, ) for minimizing the sum of a smooth convex function and a block-separable convex function, and derive improved bounds on their convergence rates. In particular, we extend Nesterov's technique developed in Nesterov (SIAM J Optim 22(2):341-362, ) for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general problem and obtain a sharper expected-value type of convergence rate than the one implied in Richtárik and Takáč (Math Program 144(1-2):1-38, ). As a result, we also obtain a better high-probability type of iteration complexity. In addition, for unconstrained smooth convex minimization, we develop a new technique called randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov (SIAM J Optim 22(2):341-362, ) and establish a sharper expected-value type of convergence rate than the one given in Nesterov (SIAM J Optim 22(2):341-362, ). [ABSTRACT FROM AUTHOR]