Month: April 2018

Primal-Dual Interior-Point Methods for Domain-Driven Formulations: Algorithms

  • Mehdi Karimi
  • Levent Tunçel
    • Categories Convex Optimization Tags , , ,

    We study infeasible-start primal-dual interior-point methods for convex optimization problems given in a typically natural form we denote as Domain-Driven formulation. Our algorithms extend many advantages of primal-dual interior-point techniques available for conic formulations, such as the current best complexity bounds, and more robust certificates of approximate optimality, unboundedness, and infeasibility, to Domain-Driven formulations. The … Read more

    Complexity of gradient descent for multiobjective optimization

  • Jörg Fliege
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    A number of first-order methods have been proposed for smooth multiobjective optimization for which some form of convergence to first order criticality has been proved. Such convergence is global in the sense of being independent of the starting point. In this paper we analyze the rate of convergence of gradient descent for smooth unconstrained multiobjective … Read more

    On Integer and MPCC Representability of Affine Sparsity

  • Hongbo Dong
    • Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities Tags , ,

    In addition to sparsity, practitioners of statistics and machine learning often wish to promote additional structures in their variable selection process to incorporate prior knowledge. Borrowing the modeling power of linear systems with binary variables, many of such structures can be faithfully modeled as so-called affine sparsity constraints (ASC). In this note we study conditions … Read more

    New inertial factors of a splitting method for monotone inclusions

  • Fang Bingbing
  • Yunda Dong
  • Wang Xiangyang
    • Categories Convex and Nonsmooth Optimization

    In this article, we consider monotone inclusions of two operators in real Hilbert spaces, in which one is further assumed to be Lipschitz continuous, and we suggest adding an inertial term to a splitting method at each iteration. The associated weak convergence is analyzed under standard assumptions. The way of choosing steplength is self-adaptive via … Read more

    Dynamic Risked Equilibrium

  • Michael C. Ferris
  • Andrew B. Philpott
    • Categories Game Theory, Stochastic Programming Tags , , ,

    We revisit the correspondence of competitive partial equilibrium with a social optimum in markets where risk-averse agents solve multistage stochastic optimization problems formulated in scenario trees. The agents trade a commodity that is produced from an uncertain supply of resources which can be stored. The agents can also trade risk using Arrow-Debreu securities. In this … Read more

    Exact converging bounds for Stochastic Dual Dynamic Programming via Fenchel duality

  • Pierre Carpentier
  • Arnaud Lenoir
  • Jean-Philippe Chancelier
  • Vincent Leclère
  • François Pacaud
    • Categories Dynamic Programming, Stochastic Programming

    The Stochastic Dual Dynamic Programming (SDDP) algorithm has become one of the main tools to address convex multistage stochastic optimal control problem. Recently a large amount of work has been devoted to improve the convergence speed of the algorithm through cut-selection and regularization, or to extend the field of applications to non-linear, integer or risk-averse … Read more

    Block Coordinate Proximal Gradient Method for Nonconvex Optimization Problems: Convergence Analysis

  • Xiangfeng Wang
  • Xiao-Ming Yuan
  • Shangzhi Zeng
  • Jin Zhang
  • Jinchuan Zhou
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    We propose a block coordinate proximal gradient method for a composite minimization problem with two nonconvex function components in the objective while only one of them is assumed to be differentiable. Under some per-block Lipschitz-like conditions based on Bregman distance, but without the global Lipschitz continuity of the gradient of the differentiable function, we prove … Read more

    Tightening McCormick Relaxations Toward Global Solution of the ACOPF Problem

  • Michael Lee Bynum
  • Anya Castillo
  • Carl D. Laird
  • Jean-Paul Watson
    • Categories Global Optimization Applications Tags , ,

    We show that a strong upper bound on the objective of the alternating current optimal power flow (ACOPF) problem can significantly improve the effectiveness of optimization-based bounds tightening (OBBT) on a number of relaxations. We additionally compare the performance of relaxations of the ACOPF problem, including the rectangular form without reference bus constraints, the rectangular … Read more

    The Meal Delivery Routing Problem

  • Alan L. Erera
  • Damian Reyes
  • Martin Savelsbergh
  • Ryan J. O'Neil
  • Sagar Sahasrabudhe
    • Categories Applications - OR and Management Sciences Tags , , ,

    We introduce the Meal Delivery Routing Problem (MDRP) to formalize and study an important emerging class of dynamic delivery operations. We develop optimization-based algorithms tailored to solve the courier assignment (dynamic vehicle routing) and capacity management (offline shift scheduling) problems encountered in meal delivery operations. Extensive computational experiments using instances with realistic size, geography, urgency … Read more

    Distributionally Robust Linear and Discrete Optimization with Marginals

  • Louis Chen
  • Karthik Natarajan
  • David Simchi-Levi
  • Will Ma
  • Zhenzhen Yan
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Polyhedra Tags , ,

    In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to … Read more