Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems

  • Jiang Hao
  • Cheng Lizhi
  • Sun Tao
    • Categories Nonlinear Optimization

    In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounters troubles in both mathematics and computations in solving the nonconvex and nonsmooth subproblem. In view of this, we propose a reweighted alternating direction method of … Read more

    Computation of exact bootstrap confidence intervals: complexity and deterministic algorithms

  • Dimitris Bertsimas
  • Bradley Sturt
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Statistics Tags , , , ,

    The bootstrap is a nonparametric approach for calculating quantities, such as confidence intervals, directly from data. Since calculating exact bootstrap quantities is believed to be intractable, randomized resampling algorithms are traditionally used. Motivated by the fact that the variability from randomization can lead to inaccurate outputs, we propose a deterministic approach. First, we establish several … Read more

    Same-Day Delivery with Drone Resupply

  • John-Paul Clarke
  • Iman Dayarian
  • Martin Savelsbergh
    • Categories Applications - OR and Management Sciences, Transportation

    Unmanned Aerial Vehicles (UAVs), commonly referred to as drones, have recently seen an increased level of interest as their potential use in same-day home delivery has been promoted and advocated by large retailers and courier delivery companies. We introduce a novel way to exploit drones in same-day home delivery settings: drone resupply. We consider a … Read more

    An incremental mirror descent subgradient algorithm with random sweeping and proximal step

  • Axel Böhm
  • Radu Ioan Bot
    • Categories Convex Optimization, Stochastic Programming

    We investigate the convergence properties of incremental mirror descent type subgradient algorithms for minimizing the sum of convex functions. In each step we only evaluate the subgradient of a single component function and mirror it back to the feasible domain, which makes iterations very cheap to compute. The analysis is made for a randomized selection … Read more

    Convergence Analysis of Processes with Valiant Projection Operators in Hilbert Space

  • Yair Censor
  • Rafiq Mansour
    • Categories Constrained Nonlinear Optimization, Convex Optimization

    Convex feasibility problems require to find a point in the intersection of a finite family of convex sets. We propose to solve such problems by performing set-enlargements and applying a new kind of projection operators called valiant projectors. A valiant projector onto a convex set implements a special relaxation strategy, proposed by Goffin in 1971, … Read more

    Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions

  • Ziran Yin
  • Liwei Zhang
    • Categories Linear, Cone and Semidefinite Programming, Second-Order Cone Programming, Semi-definite Programming

    We consider the stability of a class of parameterized conic programming problems which are more general than the C2-smooth parameterization. We show that when the Karush-Kuhn-Tucker (KKT) condition, the constraint nondegeneracy condition, the strict complementary condition and the second order sucient condition (named as Jacobian uniqueness conditions here) are satis ed at a feasible point of … Read more

    Modeling Time-dependent Randomness in Stochastic Dual Dynamic Programming

  • Nils Löhndorf
  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , ,

    We consider the multistage stochastic programming problem where uncertainty enters the right-hand sides of the problem. Stochastic Dual Dynamic Programming (SDDP) is a popular method to solve such problems under the assumption that the random data process is stagewise independent. There exist two approaches to incorporate dependence into SDDP. One approach is to model the … Read more

    Complementarity-Based Nonlinear Programming Techniques for Optimal Mixing in Gas Networks

  • Falk M. Hante
  • Martin Schmidt
    • Categories Applications - Science and Engineering, Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We consider nonlinear and nonsmooth mixing aspects in gas transport optimization problems. As mixed-integer reformulations of pooling-type mixing models already render small-size instances computationally intractable, we investigate the applicability of smooth nonlinear programming techniques for equivalent complementarity-based reformulations. Based on recent results for remodeling piecewise affine constraints using an inverse parametric quadratic programming approach, we … Read more

    Robust Combinatorial Optimization under Convex and Discrete Cost Uncertainty

  • Christoph Buchheim
  • Jannis Kurtz
    • Categories Combinatorial Optimization, Integer Programming, Robust Optimization Tags , , , , ,

    In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, … Read more

    Parsimonious formulations for low-diameter clusters

  • Austin Buchanan
  • Hosseinali Salemi
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization

    In the analysis of networks, one often searches for tightly knit clusters. One property of a “good” cluster is a small diameter (say, bounded by $k$), which leads to the concept of a $k$-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or … Read more