Convex Optimization

Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper, we consider block-decomposition first-order methods for solving large-scale conic semidefinite programming problems. Several ingredients are introduced to speed-up the method in its pure form such as: an aggressive choice of stepsize for performing the extragradient step; use of scaled inner products in the primal and dual spaces; dynamic update of the scaled … Read more

    An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and its Implications to Second-Order Methods

  • Renato D.C. Monteiro
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , , ,

    This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) method. Iteration-complexity results are established for the A-HPE method, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE method are … Read more

    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

    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

    Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions

  • Oleg Burdakov
  • Ivan Kapyrin
  • Yuri Vassilevski
    • Categories Convex Optimization Tags , , , , ,

    We suggest here a least-change correction to available finite element (FE) solution. This postprocessing procedure is aimed at recovering the monotonicity and some other important properties that may not be exhibited by the FE solution. It is based on solving a monotonic regression problem with some extra constraints. One of them is a linear equality-type … Read more

    Interior-Point Algorithms for a Generalization of Linear Programming and Weighted Centering

  • Kurt M. Anstreicher
    • Categories Convex Optimization, Linear Programming Tags , , ,

    We consider an extension of ordinary linear programming (LP) that adds weighted logarithmic barrier terms for some variables. The resulting problem generalizes both LP and the problem of finding the weighted analytic center of a polytope. We show that the problem has a dual of the same form and give complexity results for several different … Read more

    There is no variational characterization of the cycles in the method of periodic projections

  • J.-B. Baillon
  • Patrick L. Combettes
  • Roberto Cominetti
    • Categories Convex Optimization, Infinite Dimensional Optimization Tags , , ,

    The method of periodic projections consists in iterating projections onto $m$ closed convex subsets of a Hilbert space according to a periodic sweeping strategy. In the presence of $m\geq 3$ sets, a long-standing question going back to the 1960s is whether the limit cycles obtained by such a process can be characterized as the minimizers … Read more

    A new, solvable, primal relaxation for convex nonlinear integer programming problems

  • Monique Guignard
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Convex Optimization Tags , , ,

    The paper describes a new primal relaxation (PR) for computing bounds on nonlinear integer programming (NLIP) problems. It is a natural extension to NLIP problems of the geometric interpretation of Lagrangean relaxation presented by Geoffrion (1974) for linear problems, and it is based on the same assumption that some constraints are complicating and are treated … Read more

    Convexity Conditions of Kantorovich Function and Related Semi-infinite Linear Matrix Inequalities

  • Yun-Bin Zhao
    • Categories Convex Optimization, Robust Optimization, Semi-infinite Programming Tags , , , ,

    The Kantorovich function $(x^TAx)( x^T A^{-1} x)$, where $A$ is a positive definite matrix, is not convex in general. From a matrix or convex analysis point of view, it is interesting to address the question: When is this function convex? In this paper, we prove that the 2-dimensional Kantorovich function is convex if and only … Read more