Month: September 2020

Naive constant rank-type constraint qualifications for multifold second-order cone programming and semidefinite programming

  • Roberto Andreani
  • Gabriel Haeser
  • Héctor Ramírez
  • Leonardo M. Mito
  • Daiana O. Santos
  • Thiago P. Siqueira
    • Categories Linear, Cone and Semidefinite Programming

    The constant rank constraint qualification, introduced by Janin in 1984 for nonlinear programming, has been extensively used for sensitivity analysis, global convergence of first- and second-order algorithms, and for computing the derivative of the value function. In this paper we discuss naive extensions of constant rank-type constraint qualifications to second-order cone programming and semidefinite programming, … Read more

    Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality

  • Rui Gao
    • Categories Robust Optimization, Statistics, Stochastic Programming Tags , , , ,

    Wasserstein distributionally robust optimization (DRO) aims to find robust and generalizable solutions by hedging against data perturbations in Wasserstein distance. Despite its recent empirical success in operations research and machine learning, existing performance guarantees for generic loss functions are either overly conservative due to the curse of dimensionality, or plausible only in large sample asymptotics. … Read more

    The Non-Stop Disjoint Trajectories Problem

  • Benno Hoch
  • Frauke Liers
  • Sarah Neumann
  • Francisco Javier Zaragoza Martínez
    • Categories Combinatorial Optimization, Network Optimization Tags , , , , ,

    Consider an undirected network with traversal times on its edges and a set of commodities with connection requests from sources to destinations and release dates. The non-stop disjoint trajectories problem is to find trajectories that fulfill all requests, such that the commodities never meet. In this extension to the \NP-complete disjoint paths problem, trajectories must … Read more

    Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Global Optimization, Semi-definite Programming Tags , , ,

    We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less … Read more

    Dual Randomized Coordinate Descent Method for Solving a Class of Nonconvex Problems

  • Amir Beck
  • Marc Teboulle
    • Categories Nonlinear Optimization

    We consider a nonconvex optimization problem consisting of maximizing the difference of two convex functions. We present a randomized method that requires low computational effort at each iteration. The described method is a randomized coordinate descent method employed on the so-called Toland-dual problem. We prove subsequence convergence to dual stationarity points, a new notion that … Read more

    SDP-based bounds for the Quadratic Cycle Cover Problem via cutting plane augmented Lagrangian methods and reinforcement learning

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    We study the Quadratic Cycle Cover Problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the … Read more

    An improved randomized algorithm with noise level tuning for large-scale noisy unconstrained DFO problems

  • Morteza Kimiaei
    • Categories Optimization Software Benchmark, Stochastic Programming, Unconstrained Optimization Tags , , , ,

    In this paper, a new randomized solver (called VRDFON) for noisy unconstrained derivative-free optimization (DFO) problems is discussed. Complexity result in the presence of noise for nonconvex functions is studied. Two effective ingredients of VRDFON are an improved derivative-free line search algorithm with many heuristic enhancements and quadratic models in adaptively determined subspaces. Numerical results … Read more

    Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates

  • Krishnakumar Balasubramanian
  • Saeed Ghadimi
  • Anthony Nguyen
    • Categories Nonlinear Optimization, Statistics, Stochastic Programming Tags , , ,

    In this paper, we study smooth stochastic multi-level composition optimization problems, where the objective function is a nested composition of $T$ functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle. For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze … Read more

    Dual optimal design and the Christoffel-Darboux polynomial

  • Yohann De Castro
  • Didier Henrion
  • Jean-Bernard Lasserre
  • Fabrice Gamboa
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    The purpose of this short note is to show that the Christoffel-Darboux polynomial, useful in approximation theory and data science, arises naturally when deriving the dual to the problem of semi-algebraic D-optimal experimental design in statistics. It uses only elementary notions of convex analysis. Article Download View Dual optimal design and the Christoffel-Darboux polynomial

    A Unified Approach to Solve Convex Hull Pricing and Average Incremental Cost Pricing

  • Yonghong Chen
  • Pete Whitman
  • Richard O'Neill
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    This paper introduces a unified approach to solving convex hull pricing (CHP) and average incremental cost (AIC) pricing problems. By developing a convex hull and convex envelope formulation for individual resources, a CHP model that minimizes uplift can be solved by linear programming (LP) using relaxation of the binary terms of the security constrained unit … Read more