Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper establishes the iteration-complexity of a Jacobi-type non-Euclidean proximal alternating direction method of multipliers (ADMM) for solving multi-block linearly constrained nonconvex programs. The subproblems of this ADMM variant can be solved in parallel and hence the method has great potential to solve large scale multi-block linearly constrained nonconvex programs. Moreover, our analysis allows the … Read more

    On the complexity of the Unit Commitment Problem

  • Pascale Bendotti
  • Pierre Fouilhoux
  • Cécile Rottner
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization

    This article analyzes how the Unit Commitment Problem (UCP) complexity evolves with respect to the number n of units and T of time periods.A classical reduction from the knapsack problem shows that the UCP is NP-hard in the ordinary sense even for T=1. The UCP is proved to be strongly NP-hard.When either a unitary cost … Read more

    Exact augmented Lagrangian functions for nonlinear semidefinite programming

  • Ellen H. Fukuda
  • Bruno F. Lourenço
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , ,

    In this paper, we study augmented Lagrangian functions for nonlinear semidefinite programming (NSDP) problems with exactness properties. The term exact is used in the sense that the penalty parameter can be taken appropriately, so a single minimization of the augmented Lagrangian recovers a solution of the original problem. This leads to reformulations of NSDP problems … Read more

    An Investigation of Newton-Sketch and Subsampled Newton Methods

  • Albert S. Berahas
  • Raghu Bollapragada
  • Jorge Nocedal
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton’s method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: … Read more

    Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints

  • Luís Gouveia
  • Martim Joyce-Moniz
  • Markus Leitner
    • Categories Cutting Plane Approaches, Network Optimization, Telecommunications

    The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable … Read more

    A Branch-and-Cut Algorithm for Discrete Bilevel Linear Programs

  • Osman Y. Ozaltin
  • Junlong Zhang
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms

    We present a branch-and-cut algorithm for solving discrete bilevel linear programs where the upper-level variables are binary and the lower-level variables are either pure integer or pure binary. This algorithm performs local search to find improved bilevel feasible solutions. We strengthen the relaxed node subproblems in the branch-and-cut search tree by generating cuts to eliminate … Read more

    Polynomial Norms

  • Amir Ali Ahmadi
  • Etienne de Klerk
  • Georgina Hall
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    In this paper, we study polynomial norms, i.e. norms that are the dth root of a degree-d homogeneous polynomial f. We first show that a necessary and sufficient condition for f^(1/d) to be a norm is for f to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from dth … Read more

    A Progressive Hedging Based Branch-and-Bound Algorithm for Stochastic Mixed-Integer Programs

  • Semih Atakan
  • Suvrajeet Sen
    • Categories Stochastic Programming

    Progressive Hedging (PH) is a well-known algorithm for solving multi-stage stochastic convex optimization problems. Most previous extensions of PH for stochastic mixed-integer programs have been implemented without convergence guarantees. In this paper, we present a new framework that shows how PH can be utilized while guaranteeing convergence to globally optimal solutions of stochastic mixed-integer convex … Read more

    Subdifferentiation and Smoothing of Nonsmooth Integral Functionals

  • James V. Burke
  • Xiaojun Chen
  • Hailin Sun
    • Categories Nonsmooth Optimization Tags , , ,

    The subdifferential calculus for the expectation of nonsmooth random integrands involves many fundamental and challenging problems in stochastic optimization. It is known that for Clarke regular integrands, the Clarke subdifferential equals the expectation of their Clarke subdifferential. In particular, this holds for convex integrands. However, little is known about calculation of Clarke subgradients for the … Read more