Convex and Nonsmooth Optimization

A New Perspective on Boosting in Linear Regression via Subgradient Optimization and Relatives

  • Robert M. Freund
  • Rahul Mazumder
  • Paul Grigas
    • Categories Data-Mining, Nonsmooth Optimization, Statistics Tags , , , ,

    In this paper we analyze boosting algorithms in linear regression from a new perspective: that of modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FS-epsilon) and least squares boosting (LS-Boost-epsilon), can be viewed as subgradient descent to minimize the loss function defined … Read more

    First-Order Algorithms for Convex Optimization with Nonseparate Objective and Coupled Constraints

  • Xiang Gao
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more

    Solving nonsmooth convex optimization with complexity (\eps^{-1/2})$

  • Masoud Ahookhosh
  • Arnold Neumaier
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization

    This paper describes an algorithm for solving structured nonsmooth convex optimization problems using OSGA, a first-order method with the complexity $O(\eps^{-2})$ for Lipschitz continuous nonsmooth problems and $O(\eps^{-1/2})$ for smooth problems with Lipschitz continuous gradient. If the nonsmoothness of the problem is manifested in a structured way, we reformulate the problem in a form that … Read more

    Distributionally robust expectation inequalities for structured distributions

  • Paul J. Goulart
  • Bart Paul Gerard van Parys
  • Manfred Morari
    • Categories Convex Optimization, Semi-definite Programming, Stochastic Programming Tags , , ,

    Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification, notwithstanding distributional ambiguity. In this work we discuss worst-case probability and conditional … Read more

    First order optimality conditions for mathematical programs with second-order cone complementarity constraints

  • Jane J. Ye
  • Jinchuan Zhou
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Second-Order Cone Programming Tags , , , , ,

    In this paper we consider a mathematical program with second-order cone complementarity constraints (SOCMPCC). The SOCMPCC generalizes the mathematical program with complementarity constraints (MPCC) in replacing the set of nonnegative reals by a second-order cone. We show that if the SOCMPCC is considered as an optimization problem with convex cone constraints, then Robinson’s constraint qualification … Read more

    An O(1/k) Convergence Rate for the Variable Stepsize Bregman Operator Splitting Algorithm

  • William W. Hager
  • Maryam Yashtini
  • Hongchao Zhang
    • Categories Nonsmooth Optimization Tags , , , , ,

    An earlier paper proved the convergence of a variable stepsize Bregman operator splitting algorithm (BOSVS) for minimizing $\phi(Bu)+H(u)$ where $H$ and $\phi$ are convex functions, and $\phi$ is possibly nonsmooth. The algorithm was shown to be relatively efficient when applied to partially parallel magnetic resonance image reconstruction problems. In this paper, the convergence rate of … Read more

    Decomposition algorithm for large-scale two-stage unit-commitment

  • Jérôme Malick
  • Wim van Ackooij
    • Categories Applications - OR and Management Sciences, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    Everyday, electricity generation companies submit a generation schedule to the grid operator for the coming day; computing an optimal schedule is called the unit-commitment problem. Generation companies can also occasionally submit changes to the schedule, that can be seen as intra-daily incomplete recourse actions. In this paper, we propose a two-stage formulation of unit-commitment, wherein … Read more

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more

    Preconditioning of a Generalized Forward-Backward Splitting and Application to Optimization on Graphs

  • Loïc Landrieu
  • Hugo Raguet
    • Categories Convex and Nonsmooth Optimization, Generalized Convexity/Monoticity

    We present a preconditioning of a generalized forward-backward splitting algorithm for finding a zero of a sum of maximally monotone operators \sum_{i=1}^n A_i + B with B cocoercive, involving only the computation of B and of the resolvent of each A_i separately. This allows in particular to minimize functionals of the form \sum_{i=1}^n g_i + … Read more

    Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions

  • Amir Beck
  • Shimrit Shtern
    • Categories Convex Optimization

    We consider the problem of minimizing a function, which is the sum of a linear function and a composition of a strongly convex function with a linear transformation, over a compact polyhedral set. Jaggi and Lacoste-Julien [14] showed that the conditional gradient method with away steps employed on the aforementioned problem without the additional linear … Read more