Convex and Nonsmooth Optimization

Supermodularity, Curvature, and Convex Relaxations in a Class of Quadratic Binary Optimization Problems

  • Bismark Singh
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization Tags , , ,

    We study the combinatorial structure of a quadratic set function $F(S)$ arising from a class of binary optimization models within the family of undesirable facility location problems. Despite strong empirical evidence of nested optimal solutions in previously studied real-world instances, we show that $F(S)$ is, in general, neither submodular nor supermodular. To quantify deviation from … Read more

    Min-Max Optimization Is Strictly Easier Than Variational Inequalities

  • Henry Shugart
  • Jason M. Altschuler
    • Categories Convex Optimization

    Classically, a mainstream approach for solving a convex-concave min-max problem is to instead solve the variational inequality problem arising from its first-order optimality conditions. Is it possible to solve min-max problems faster by bypassing this reduction? This paper initiates this investigation. We show that the answer is yes in the textbook setting of unconstrained quadratic … Read more

    A One-Extra Player Reduction of GNEPs to NEPs

  • Henri Lefebvre
  • David Salas
  • Martin Schmidt
    • Categories Convex Optimization, Game Theory, Integer Programming Tags , , , ,

    It is common opinion that generalized Nash equilibrium problems are harder than Nash equilibrium problems. In this work, we show that by adding a new player, it is possible to reduce many generalized problems to standard equilibrium problems. The reduction holds for linear problems and smooth convex problems verifying a Slater-type condition. We also derive … Read more

    Preconditioned subgradient method for composite optimization: overparameterization and fast convergence

  • Liwei Jiang
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    Composite optimization problems involve minimizing the composition of a smooth map with a convex function. Such objectives arise in numerous data science and signal processing applications, including phase retrieval, blind deconvolution, and collaborative filtering. The subgradient method achieves local linear convergence when the composite loss is well-conditioned. However, if the smooth map is, in a … Read more

    Inexact subgradient algorithm with a non-asymptotic convergence guarantee for copositive programming problems

  • Mitsuhiro Nishijima
  • Pierre-Louis Poirion
  • Akiko Takeda
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper, we propose a subgradient algorithm with a non-asymptotic convergence guarantee to solve copositive programming problems. The subproblem to be solved at each iteration is a standard quadratic programming problem, which is NP-hard in general. However, the proposed algorithm allows this subproblem to be solved inexactly. For a prescribed accuracy $\epsilon > 0$ … Read more

    A Practical Adaptive Subgame Perfect Gradient Method

  • Alan Luner
  • Benjamin Grimmer
    • Categories Convex Optimization, Second-Order Cone Programming Tags , , , , , ,

    We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on … Read more

    Convexification of a Separable Function over a Polyhedral Ground Set

  • Santanu S. Dey
  • Burak Kocuk
    • Categories Cone Programming, Convex Optimization, Global Optimization Tags , , , , ,

    In this paper, we study the set \(\mathcal{S}^\kappa = \{ (x,y)\in\mathcal{G}\times\mathbb{R}^n : y_j = x_j^\kappa , j=1,\dots,n\}\), where \(\kappa > 1\) and the ground set \(\mathcal{G}\) is a nonempty polytope contained in \( [0,1]^n\). This nonconvex set is closely related to separable standard quadratic programming and appears as a substructure in potential-based network flow problems … Read more

    Optimization in Theory and Practice

  • Stephen Wright
    • Categories Convex Optimization, Linear Programming, Unconstrained Optimization Tags , ,

    Algorithms for continuous optimization problems have a rich history of design and innovation over the past several decades, in which mathematical analysis of their convergence and complexity properties plays a central role. Besides their theoretical properties, optimization algorithms are interesting also for their practical usefulness as computational tools for solving real-world problems. There are often … Read more