Convex and Nonsmooth Optimization

Optimality conditions of set-valued optimization problem involving relative algebraic interior in ordered linear spaces

  • Peng Jian-Wen
  • Xinmin Yang
  • Zhou Zhi-Ang
    • Categories Generalized Convexity/Monoticity, Multi-Criteria Optimization Tags

    In this paper, firstly, a generalized subconvexlike set-valued map involving the relative algebraic interior is introduced in ordered linear spaces. Secondly, some properties of a generalized subconvexlike set-valued map are investigated. Finally, the optimality conditions of set-valued optimization problem are established. Citation {\bf AMS 2010 Subject Classifications:} 90C26, 90C29, 90C30ArticleDownload View PDF

    Structured Sparsity via Alternating Direction Methods

  • Donald Goldfarb
  • Zhiwei (Tony) Qin
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus … Read more

    Hierarchical Classification via Orthogonal Transfer

  • Mingrui Wu
  • Lin Xiao
  • Dengyong Zhou
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , ,

    We consider multiclass classification problems where the set of labels are organized hierarchically as a category tree. We associate each node in the tree with a classifier and classify the examples recursively from the root to the leaves. We propose a hierarchical Support Vector Machine (SVM) that encourages the classifier at each node of the … Read more

    An Infeasible-Point Subgradient Method Using Adaptive Approximate Projections

  • Dirk A. Lorenz
  • Marc E. Pfetsch
  • Andreas M. Tillmann
    • Categories Convex Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , , , ,

    We propose a new subgradient method for the minimization of convex functions over a convex set. Common subgradient algorithms require an exact projection onto the feasible region in every iteration, which can be efficient only for problems that admit a fast projection. In our method we use inexact adaptive projections requiring to move within a … Read more

    A Sparsity Preserving Stochastic Gradient Method for Composite Optimization

  • Xi Chen
  • Qihang Lin
  • Javier F. Peña
    • Categories Convex Optimization Tags , ,

    We propose new stochastic gradient algorithms for solving convex composite optimization problems. In each iteration, our algorithms utilize a stochastic oracle of the gradient of the smooth component in the objective function. Our algorithms are based on a stochastic version of the estimate sequence technique introduced by Nesterov (Introductory Lectures on Convex Optimization: A Basic … Read more

    Explicit Solutions for Root Optimization of a Polynomial Family with One Affine Constraint

  • Vincent D. Blondel
  • Mert Gurbuzbalaban
  • Michael L. Overton
  • Alexander Megretski
    • Categories Control Applications, Global Optimization, Nonsmooth Optimization Tags , , , ,

    Given a family of real or complex monic polynomials of fixed degree with one affine constraint on their coefficients, consider the problem of minimizing the root radius (largest modulus of the roots) or root abscissa (largest real part of the roots). We give constructive methods for efficiently computing the globally optimal value as well as … Read more

    Group Sparse Optimization by Alternating Direction Method

  • Wei Deng
  • Wotao Yin
  • Yin Zhang
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper proposes efficient algorithms for group sparse optimization with mixed L21-regularization, which arises from the reconstruction of group sparse signals in compressive sensing, and the group Lasso problem in statistics and machine learning. It is known that encoding the group information in addition to sparsity will lead to better signal recovery/feature selection. The L21-regularization … Read more

    FAST FIRST-ORDER METHODS FOR COMPOSITE CONVEX OPTIMIZATION WITH BACKTRACKING

  • Xi Bai
  • Donald Goldfarb
  • Katya Scheinberg
    • Categories Nonsmooth Optimization Tags , , , , ,

    We propose new versions of accelerated first order methods for convex composite optimization, where the prox parameter is allowed to increase from one iteration to the next. In particular we show that a full backtracking strategy can be used within the FISTA \cite{Beck-Teboulle-2009} and FALM algorithms \cite{Goldfarb-Ma-Scheinberg-2010} while preserving their worst-case iteration complexities of $O(\sqrt{L(f)/\epsilon})$. … Read more

    Level methods uniformly optimal for composite and structured nonsmooth convex optimization

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization … Read more

    Level methods uniformly optimal for composite and structured nonsmooth convex optimization

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization … Read more