Month: February 2024

Using Filter Methods to Guide Convergence for ADMM, with Applications to Nonnegative Matrix Factorization Problems

  • Robert Baraldi
  • Stefan M. Wild
  • Sven Leyffer
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , ,

    Nonconvex, nonlinear cost functions arise naturally in physical inverse problems and machine learning. The alternating direction method of multipliers (ADMM) has seen extensive use in these applications, despite exhibiting uncertain convergence behavior in many practical nonconvex settings, and struggling with general nonlinear constraints. In contrast, filter methods have proved effective in enforcing convergence for sequential … Read more

    Riemannian Bilevel Optimization

  • Jiaxiang Li
  • Shiqian Ma
    • Categories Nonlinear Optimization Tags ,

    In this work, we consider the bilevel optimization problem on Riemannian manifolds. We inspect the calculation of the hypergradient of such problems on general manifolds and thus enable the utilization of gradient-based algorithms to solve such problems. The calculation of the hypergradient requires utilizing the notion of Riemannian cross-derivative and we inspect the properties and … Read more

    Store Fulfillment with Autonomous Mobile Robots and In-Store Customers

  • Joyjit Bhowmick
  • Jennifer Pazour
  • Iman Dayarian
    • Categories Production and Logistics, Supply Chain Management, Transportation

    Omnichannel services, such as buy-online-pickup-in-store, curbside pickup, and ship-from-store, have shifted the order-picking tasks previously completed by in-store customers doing their own shopping to the retailer’s responsibility. To fulfill these orders, many retailers have deployed a store fulfillment strategy, where online orders are picked from brick-and-mortar retail store shelves. We focus on the design of … Read more

    Non-facial exposedness of copositive cones over symmetric cones

  • Mitsuhiro Nishijima
  • Bruno F. Lourenço
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In this paper, we consider copositive cones over symmetric cones and show that they are never facially exposed when the underlying cone has dimension at least 2. We do so by explicitly exhibiting a non-exposed extreme ray. Our result extends the known fact that the cone of copositive matrices over the nonnegative orthant is not … Read more

    Distributionally Fair Stochastic Optimization using Wasserstein Distance

  • Ye Qing
  • Grani A. Hanasusanto
  • Weijun Xie
    • Categories Stochastic Programming Tags , ,

    A traditional stochastic program under a finite population typically seeks to optimize efficiency by maximizing the expected profits or minimizing the expected costs, subject to a set of constraints. However, implementing such optimization-based decisions can have varying impacts on individuals, and when assessed using the individuals’ utility functions, these impacts may differ substantially across demographic … Read more

    On the power of linear programming for K-means clustering

  • Aida Khajavirad
    • Categories Combinatorial Optimization, Integer Programming, Polyhedra Tags , , , ,

    In a previous work, we introduced a new linear programming (LP) relaxation for K-means clustering. In this paper, we further investigate the theoretical properties of this relaxation. We focus on K-means clustering with two clusters, which is an NP-hard problem. As evident from our numerical experiments with both synthetic and real-world data sets, the proposed … Read more

    Branch and Price for the Length-Constrained Cycle Partition Problem

  • Mohammed Ghannam
  • Ambros Gleixner
  • Gioni Mexi
  • Edward Lam
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , , ,

    The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is associated with a critical time and the length of every cycle must not exceed the critical time of any node in the cycle. We formulate LCCP … Read more

    Robust support vector machines via conic optimization

  • Shaoning Han
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Optimization in Data Science Tags , , , ,

    We consider the problem of learning support vector machines robust to uncertainty. It has been established in the literature that typical loss functions, including the hinge loss, are sensible to data perturbations and outliers, thus performing poorly in the setting considered. In contrast, using the 0-1 loss or a suitable non-convex approximation results in robust … Read more

    On Tractability, Complexity, and Mixed-Integer Convex Programming Representability of Distributionally Favorable Optimization

  • Nan Jiang
  • Weijun Xie
    • Categories Stochastic Programming Tags , ,

    Distributionally Favorable Optimization (DFO) is an important framework for decision-making under uncertainty, with applications across fields such as reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without relatively complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge– the application of the inner infimum … Read more

    Bounds and Heuristic Algorithms for the Bin Packing Problem with Minimum Color Fragmentation

  • Barkel Mathijs
  • Maxence Delorme
  • Enrico Malaguti
  • Michele Monaci
    • Categories Combinatorial Optimization

    In this paper, we consider a recently introduced packing problem in which a given set of weighted items with colors has to be packed into a set of identical bins, while respecting capacity constraints and minimizing the total number of times that colors appear in the bins. We review exact methods from the literature and … Read more