Linear, Cone and Semidefinite Programming

A Quadratically Convergent Sequential Programming Method for Second-Order Cone Programs Capable of Warm Starts

  • Xinyi Luo
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming Tags , ,

    We propose a new method for linear second-order cone programs. It is based on the sequential quadratic programming framework for nonlinear programming. In contrast to interior point methods, it can capitalize on the warm-start capabilities of active-set quadratic programming subproblem solvers and achieve a local quadratic rate of convergence. In order to overcome the non-differentiability … Read more

    A Sparse Interior Point Method for Linear Programs arising in Discrete Optimal Transport

  • Filippo Zanetti
  • Jacek Gondzio
    • Categories Convex Optimization, Linear Programming, Transportation Tags , , , ,

    Discrete Optimal Transport problems give rise to very large linear programs (LP) with a particular structure of the constraint matrix. In this paper we present an interior point method (IPM) specialized for the LP originating from the Kantorovich Optimal Transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we … Read more

    Decision Rule Approaches for Pessimistic Bilevel Linear Programs under Moment Ambiguity with Facility Location Applications

  • Akshit Goyal
  • Yiling Zhang
  • Chuan He
    • Categories Robust Optimization, Semi-definite Programming Tags , , , ,

    We study a pessimistic stochastic bilevel program in the context of sequential two-player games, where the leader makes a binary here-and-now decision, and the follower responds a continuous wait-and-see decision after observing the leader’s action and revelation of uncertainty. Only the information of the mean, covariance, and support is known. We formulate the problem as … Read more

    Lexicographic Branch-and-Bound Column Search

  • Andreas Bärmann
  • Alexander Müller
  • Dieter Weninger
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Scheduling Tags , , , , ,

    We present an exact generic method for solving the pricing problem in a column generation approach, which we call branch-and-bound column search. It searches the space of all feasible columns via a branch-and-bound tree search and returns all columns with a reduced-cost value below a certainthreshold. The approach is based on an idea from Krumke … Read more

    Accelerated first-order methods for a class of semidefinite programs

  • Alex L. Wang
  • Fatma Kılınç-Karzan
    • Categories Convex and Nonsmooth Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    This paper introduces a new storage-optimal first-order method (FOM), CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs , is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard … Read more

    Wasserstein Logistic Regression with Mixed Features

  • Aras Selvi
  • Mohammad Reza Belbasi
  • Martin Haugh
  • Wolfram Wiesemann
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , ,

    Recent work has leveraged the popular distributionally robust optimization paradigm to combat overfitting in classical logistic regression. While the resulting classification scheme displays a promising performance in numerical experiments, it is inherently limited to numerical features. In this paper, we show that distributionally robust logistic regression with mixed (i.e., numerical and categorical) features, despite amounting … Read more

    A Reduced Jacobian Scheme with Full Convergence for Multicriteria Optimization

  • Mounir El Maghri
  • Youssef Elboulqe
    • Categories Constrained Nonlinear Optimization, Linear Programming, Multi-Criteria Optimization Tags , , , , ,

    In this paper, we propose a variant of the reduced Jacobian method (RJM) introduced by El Maghri and Elboulqe in [JOTA, 179 (2018) 917–943] for multicriteria optimization under linear constraints. Motivation is that, contrarily to RJM which has only global convergence to Pareto KKT-stationary points in the classical sense of accumulation points, this new variant … Read more

    Partitioning through projections: strong SDP bounds for large graph partition problems

  • Frank de Meijer
  • Renata Sotirov
  • Angelika Wiegele
  • Shudian Zhao
    • Categories Semi-definite Programming Tags , , , ,

    The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more

    Robust Actionable Prescriptive Analytics

  • Li Chen
  • Melvyn Sim
  • Xun Zhang
  • Minglong Zhou
  • Long Zhao
    • Categories Linear Programming, Robust Optimization, Stochastic Programming Tags , , , , ,

    We propose a new robust actionable prescriptive analytics framework that leverages past data and side information to minimize a risk-based objective function under distributional ambiguity. Our framework aims to find a policy that directly transforms the side information into implementable decisions. Specifically, we focus on developing actionable response policies that offer the benefits of interpretability … Read more

    Distributionally Robust Inventory Management with Advance Purchase Contracts

  • Yilin Xue
  • Yongzhen Li
  • Napat Rujeerapaiboon
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Supply Chain Management Tags , ,

    Motivated by the worldwide Covid-19 vaccine procurement, we study an inventory problem with an advance purchase contract which requires all ordering decisions to be committed at once. In reality, not only the demand is uncertain, but its distribution can also be ambiguous. Hence, we assume that only the mean and the variance are known and … Read more