Convex Optimization

FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients

  • Mathieu Besançon
  • Alejandro Carderera
  • Sebastian Pokutta
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Optimization Software and Modeling Systems Tags , ,

    We present FrankWolfe.jl, an open-source implementation of several popular Frank-Wolfe and Conditional Gradients variants for first-order constrained optimization. The package is designed with flexibility and high-performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia’s unique multiple dispatch feature, and interfaces smoothly with generic linear optimization … Read more

    Long-run market equilibria in coupled energy sectors: A study of uniqueness

  • Jonas Egerer
  • Veronika Grimm
  • Julia Grübel
  • Gregor Zöttl
    • Categories Applications - OR and Management Sciences, Convex Optimization, Finance and Economics Tags , , , ,

    We propose an equilibrium model for coupled markets of multiple energy sectors. The agents in our model are operators of sector-specific production and sector-coupling technologies, as well as price-sensitive consumers with varying demand. We analyze long-run investment in production capacity in each sector and investment in coupling capacity between sectors, as well as production decisions … Read more

    Universal Conditional Gradient Sliding for Convex Optimization

  • Yuyuan Ouyang
  • Trevor Squires
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

    In this paper, we present a first-order projection-free method, namely, the universal conditional gradient sliding (UCGS) method, for solving ε-approximate solutions to convex differentiable optimization problems. For objective functions with Hölder continuous gradients, we show that UCGS is able to terminate with ε-solutions with at most O((1/ε)^(2/(1+3v))) gradient evaluations and O((1/ε)^(4/(1+3v))) linear objective optimizations, where … Read more

    String-Averaging Methods for Best Approximation to Common Fixed Point Sets of Operators: The Finite and Infinite Cases

  • Yair Censor
  • Ariel Nisenbaum
    • Categories Convex Optimization, Nonlinear Optimization, Parallel Algorithms

    Abstract String-averaging is an algorithmic structure used when handling a family of operators in situations where the algorithm at hand requires to employ the operators in a specific order. Sequential orderings are well-known and a simultaneous order means that all operators are used simultaneously (in parallel). String-averaging allows to use strings of indices, constructed by … Read more

    Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming

  • David Applegate
  • Mateo Díaz
  • Haihao Lu
  • Miles Lubin
    • Categories Convex Optimization, Linear Programming Tags , , ,

    We study the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient method (PDHG) of Chambolle and Pock (2011). The literature on PDHG has mostly focused on settings where the problem at hand is assumed to be feasible. When the problem is not feasible, the iterates of the algorithm do … Read more

    How do exponential size solutions arise in semidefinite programming?

  • Gabor Pataki
  • Aleksandr Touzov
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming

    Semidefinite programs (SDPs) are some of the most popular and broadly applicable optimization problems to emerge in the last thirty years. A curious pathology of SDPs, illustrated by a classical example of Khachiyan, is that their solutions may need exponential space to even write down. Exponential size solutions are the main obstacle to solve a … Read more

    First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation

  • Krzysztof Postek
  • Shimrit Shtern
    • Categories Convex Optimization, Robust Optimization

    Robust optimization (RO) is one of the key paradigms for solving optimization problems affected by uncertainty. Two principal approaches for RO, the robust counterpart method and the adversarial approach, potentially lead to excessively large optimization problems. For that reason, first order approaches, based on online-convex-optimization, have been proposed (Ben-Tal et al. (2015), Kilinc-Karzan and Ho-Nguyen … Read more

    An (s^r)hBcResolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems

  • Haihao Lu
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization Tags , ,

    There has been a long history of using ordinary differential equations (ODEs) to understand the dynamic of discrete-time algorithms (DTAs). Surprisingly, there are still two fundamental and unanswered questions: (i) it is unclear how to obtain a \emph{suitable} ODE from a given DTA, and (ii) it is unclear the connection between the convergence of a … Read more

    Moreau envelope of supremum functions with applications to infinite and stochastic programming

  • Pedro Pérez-Aros
  • Emilio Vilches
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we investigate the Moreau envelope of the supremum of a family of convex, proper, and lower semicontinuous functions. Under mild assumptions, we prove that the Moreau envelope of a supremum is the supremum of Moreau envelopes, which allows us to approximate possibly nonsmooth supremum functions by smooth functions that are also the … Read more

    Algorithms for Block Tridiagonal Systems: Foundations and New Results for Generalized Kalman Smoothing

  • Aleksandr Y. Aravkin
  • James V. Burke
  • Bradley Bell
  • Gianluigi Pillonetto
    • Categories Control Applications, Convex Optimization

    Block tridiagonal systems appear in classic Kalman smoothing problems, as well in generalized Kalman smoothing, where problems may have nonsmooth terms, singular covariance, constraints, nonlinear models, and unknown parameters. In this paper, first we interpret all the classic smoothing algorithms as different approaches to solve positive definite block tridiagonal linear systems. Then, we obtain new … Read more