Primal-dual regularized SQP and SQCQP type methods for convex programming and their complexity analysis

  • M. Marques Alves
  • Renato D.C. Monteiro
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization

    This paper presents and studies the iteration-complexity of two new inexact variants of Rockafellar’s proximal method of multipliers (PMM) for solving convex programming (CP) problems with a fi nite number of functional inequality constraints. In contrast to the first variant which solves convex quadratic programming (QP) subproblems at every iteration, the second one solves convex constrained … Read more

    On the Complexity of the Traveling Umpire Problem

  • Lucas de Oliveira
  • Cid C. de Souza
  • Tallys H. Yunes
    • Categories Combinatorial Optimization, Other Topics, Scheduling Tags , ,

    The traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during a double round-robin tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too … Read more

    Coordinate shadows of semi-definite and Euclidean distance matrices

  • Dmitriy Drusvyatskiy
  • Gabor Pataki
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definite and Euclidean distance completion problems. We characterize when these sets are closed, and use the boundary structure of these two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. … Read more

    How Good Are Sparse Cutting-Planes?

  • Santanu S. Dey
  • Marco Molinaro
  • Qianyi Wang
    • Categories Integer Programming Tags ,

    Sparse cutting-planes are often the ones used in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-\&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope $P$ (e.g. the integer hull of … Read more

    Chance-Constrained Multi-Terminal Network Design Problems

  • Yongjia Song
  • Minjiao Zhang
    • Categories Integer Programming, Network Optimization, Stochastic Programming Tags , , ,

    We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum-cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose a scenario-based Steiner cut formulation, and a … Read more

    Distributionally Robust Discrete Optimization with Entropic Value-at-Risk

  • Qi Jin
  • Daniel Zhuoyu Long
    • Categories 0-1 Programming, Robust Optimization

    We study the discrete optimization problem under the distributionally robust framework. We optimize the Entropic Value-at-Risk, which is a coherent risk measure and is also known as Bernstein approximation for the chance constraint. We propose an efficient approximation algorithm to resolve the problem via solving a sequence of nominal problems. The computational results show that … Read more

    Dynamic vs. Static Optimization of Crossdocking Operations

  • Monique Guignard
  • Peter M. Hahn
  • Heng Zhang
    • Categories Applications - OR and Management Sciences

    To improve operations commonly found in today’s crossdocks, we offer a door assignment optimization tool that will reduce the distance travelled by goods across the crossdock, as well as workload and labor cost. The cross dock door assignment problem (CDAP) minimizes total distance traveled by the goods inside the crossdock where door capacities are limited … Read more

    Zero-Convex Functions, Perturbation Resilience, and Subgradient Projections for Feasibility-Seeking Methods

  • Yair Censor
  • Daniel Reem
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , , , ,

    The convex feasibility problem (CFP) is at the core of the modeling of many problems in various areas of science. Subgradient projection methods are important tools for solving the CFP because they enable the use of subgradient calculations instead of orthogonal projections onto the individual sets of the problem. Working in a real Hilbert space, … Read more

    Error Bounds and Metric Subregularity

  • Alexander Y. Kruger
    • Categories Nonsmooth Optimization

    Necessary and sufficient criteria for metric subregularity (or calmness) of set-valued mappings between general metric or Banach spaces are treated in the framework of the theory of error bounds for a special family of extended real-valued functions of two variables. A classification scheme for the general error bound and metric subregularity criteria is presented. The … Read more

    Relay Optimization Method

  • Xuyan Wang
    • Categories Finance and Economics, Global Optimization Applications

    Insurance-linked securities portfolio with the VaR constraint optimization problem have a kind of weak dominance or ordering property, which enables us to reduce the variables’ dimensions gradually through exercising a genetic algorithm with randomly selected initial populations. This property also enables us to add boundary attraction potential to GA-MPC’s repair operator, among other modifications such … Read more