Convex and Nonsmooth Optimization

A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms

  • Laurent Condat
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    We propose a new first-order splitting algorithm for solving jointly the primal and dual formulations of large-scale convex minimization problems involving the sum of a smooth function with Lipschitzian gradient, a nonsmooth proximable function, and linear composite functions. This is a full splitting approach in the sense that the gradient and the linear operators involved … Read more

    Continuous convex sets and zero duality gap for convex programs

  • Emil Ernst
  • Michel Volle
    • Categories Convex Optimization Tags , , , ,

    This article uses classical notions of convex analysis over euclidean spaces, like Gale & Klee’s boundary rays and asymptotes of a convex set, or the inner aperture directions defined by Larman and Brøndsted for the same class of sets, to provide a new zero duality gap criterion for ordinary convex programs. On this ground, we … Read more

    Zero duality gap for convex programs: a general result

  • Emil Ernst
  • Michel Volle
    • Categories Convex Optimization Tags , ,

    This article addresses a general criterion providing a zero duality gap for convex programs in the setting of the real locally convex spaces. The main theorem of our work is formulated only in terms of the constraints of the program, hence it holds true for any objective function fulfilling a very general qualification condition, implied … Read more

    Closed means continuous iff polyhedral: a converse of the GKR theorem

  • Emil Ernst
    • Categories Convex Optimization Tags , , , , ,

    Given x, a point of a convex subset C of an Euclidean space, the two following statements are proven to be equivalent: (i) any convex function f : C → R is upper semi-continuous at x, and (ii) C is polyhedral at x. In the particular setting of closed convex mappings and Fσ domains, we … Read more

    Strong formulations for convex functions over nonconvex sets

  • Daniel Bienstock
  • Alexander Michalka
    • Categories Global Optimization, Nonsmooth Optimization, Second-Order Cone Programming Tags , ,

    In this paper we derive strong linear inequalities for sets of the form {(x, q) ∈ R^d × R : q ≥ Q(x), x ∈ R^d − int(P ) }, where Q(x) : R^d → R is a quadratic function, P ⊂ R^d and “int” denotes interior. Of particular but not exclusive interest is the … Read more

    DC approach to regularity of convex multifunctions with applications to infinite systems

  • Boris S. Mordukhovich
  • Nghia Tran
    • Categories Convex and Nonsmooth Optimization, Semi-infinite Programming Tags , , ,

    The paper develops a new approach to the study of metric regularity and related well-posedness properties of convex set-valued mappings between general Banach spaces by reducing them to unconstrained minimization problems with objectives given as the difference of convex (DC) functions. In this way we establish new formulas for calculating the exact regularity bound of … Read more

    Hedge algorithm and Dual Averaging schemes

  • Michel Baes
  • Michael Bürgisser
    • Categories Convex Optimization Tags , , ,

    We show that the Hedge algorithm, a method that is widely used in Machine Learning, can be interpreted as a particular instance of Dual Averaging schemes, which have recently been introduced by Nesterov for regret minimization. Based on this interpretation, we establish three alternative methods of the Hedge algorithm: one in the form of the … Read more

    A randomized Mirror-Prox method for solving structured large-scale matrix saddle-point problems

  • Michel Baes
  • Arkadi Nemirovski
  • Michael Bürgisser
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    In this paper, we derive a randomized version of the Mirror-Prox method for solving some structured matrix saddle-point problems, such as the maximal eigenvalue minimization problem. Deterministic first-order schemes, such as Nesterov’s Smoothing Techniques or standard Mirror-Prox methods, require the exact computation of a matrix exponential at every iteration, limiting the size of the problems … Read more

    Subdifferentials of nonconvex supremum functions and their applications to semi-infinite and infinite programs with Lipschitzian data

  • Boris S. Mordukhovich
  • Nghia Tran
    • Categories Nonsmooth Optimization, Semi-infinite Programming Tags , , ,

    The paper is devoted to the subdifferential study and applications of the supremum of uniformly Lipschitzian functions over arbitrary index sets with no topology. Based on advanced techniques of variational analysis, we evaluate major subdifferentials of the supremum functions in the general framework of Asplund (in particular, reflexive) spaces with no convexity or relaxation assumptions. … Read more