Convex and Nonsmooth Optimization

Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization

  • Saeed Ghadimi
  • Guanghui Lan
  • Hongchao Zhang
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are … Read more

    Composite Self-concordant Minimization

  • Volkan Cevher
  • Quoc Tran-Dinh
  • Anastasios Kyrillidis
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Statistics Tags , , , ,

    We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function endowed with a computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth part. An important highlight of our work is a new … Read more

    Inverse Parametric Optimization with an Application to Hybrid System Control

  • Paul J. Goulart
  • Andreas B. Hempel
  • John Lygeros
    • Categories Complementarity and Variational Inequalities, Control Applications, Convex Optimization Tags ,

    We present a number of results on inverse parametric optimization and its application to hybrid system control. We show that any function that can be written as the difference of two convex functions can also be written as a linear mapping of the solution to a convex parametric optimization problem. We exploit these results in … Read more

    A direct splitting method for nonsmooth variational inequalities

  • Yunier Bello-Cruz
  • R. Diaz Millan
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonsmooth Optimization

    We propose a direct splitting method for solving nonsmooth variational inequality problems in Hilbert spaces. The weak convergence is established, when the operator is the sum of two point-to-set and monotone operators. The proposed method is a natural extension of the incremental subgradient method for nondifferentiable optimization, which explores strongly the structure of the operator … Read more

    Nonsmooth Algorithms and Nesterov’s Smoothing Techniques for Generalized Fermat-Torricelli Problems

  • Nguyen Thai An
  • Jie Sun
  • Nguyen Mau Nam
  • R. Blake Rector
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    In this paper we present some algorithms for solving a number of new models of facility location involving sets which generalize the classical Fermat-Torricelli problem. Our approach uses subgradient-type algorithms to cope with nondi erentiabilty of the distance functions therein. Another approach involves approximating nonsmooth optimization problems by smooth optimizations problems using Nesterov’s smoothing techniques. Convergence … Read more

    On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization

  • Cristobal Guzman
  • Arkadi Nemirovski
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    In this note we present tight lower bounds on the information-based complexity of large-scale smooth convex minimization problems. We demonstrate, in particular, that the k-step Conditional Gradient (a.k.a. Frank-Wolfe) algorithm as applied to minimizing smooth convex functions over the n-dimensional box with n ≥ k is optimal, up to an O(ln n)-factor, in terms of … Read more

    Multiperiod Portfolio Optimization with General Transaction Costs

  • Victor DeMiguel
  • Xiaoling Mei
  • Francisco Javier Nogales
    • Categories Convex Optimization, Finance and Economics

    We analyze the properties of the optimal portfolio policy for a multiperiod mean-variance investor facing multiple risky assets in the presence of general transaction costs such as proportional, market impact, and quadratic transaction costs. For proportional transaction costs, we find that a buy-and-hold policy is optimal: if the starting portfolio is outside a parallelogram-shaped no-trade … Read more

    Second-order Characterizations of Tilt Stability with Applications to Nonlinear Programming

  • Boris S. Mordukhovich
  • Nghia Tran
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    The paper is devoted to the study of tilt-stable local minimizers of general optimization problems in finite-dimensional spaces and its applications to classical nonlinear programs with twice continuously differentiable data. The importance of tilt stability has been well recognized from both theoretical and numerical aspects of optimization, and this notion has been extensively studied in … Read more

    Convex relaxation for finding planted influential nodes in a social network

  • Lisa Elkin
  • Ting Kei Pong
  • Stephen A. Vavasis
    • Categories Convex Optimization, Data-Mining Tags , ,

    We consider the problem of maximizing influence in a social network. We focus on the case that the social network is a directed bipartite graph whose arcs join senders to receivers. We consider both the case of deterministic networks and probabilistic graphical models, that is, the so-called “cascade” model. The problem is to find the … Read more