Convex Optimization

On deterministic reformulations of distributionally robust joint chance constrained optimization problems

  • Shabbir Ahmed
  • Weijun Xie
    • Categories Convex Optimization, Robust Optimization, Stochastic Programming Tags , , ,

    A joint chance constrained optimization problem involves multiple uncertain constraints, i.e., constraints with stochastic parameters, that are jointly required to be satisfied with probability exceeding a prespecified threshold. In a distributionally robust joint chance constrained optimization problem (DRCCP), the joint chance constraint is required to hold for all probability distributions of the stochastic parameters from … Read more

    Positive-Indefinite Proximal Augmented Lagrangian Method and its Application to Full Jacobian Splitting for Multi-block Separable Convex Minimization Problems

  • Bingsheng He
  • Feng Ma
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , , ,

    The augmented Lagrangian method (ALM) is fundamental for solving convex programming problems with linear constraints. The proximal version of ALM, which regularizes ALM’s subproblem over the primal variable at each iteration by an additional positive-definite quadratic proximal term, has been well studied in the literature. In this paper, we show that it is not necessary … Read more

    Regularized nonlinear acceleration

  • Francis Bach
  • Alexandre d'Aspremont
  • Damien Scieur
    • Categories Convex Optimization, Unconstrained Optimization Tags

    We describe a convergence acceleration technique for generic optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates produced by any optimization method. The weights in this average are computed via a simple linear system, whose solution can be updated online. This acceleration scheme runs in parallel to the … Read more

    On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms

  • Robert Hannah
  • Wotao Yin
    • Categories Convex Optimization, Parallel Algorithms Tags , , , ,

    The need for scalable numerical solutions has motivated the development of asynchronous parallel algorithms, where a set of nodes run in parallel with little or no synchronization, thus computing with delayed information. This paper studies the convergence of the asynchronous parallel algorithm ARock under potentially unbounded delays. ARock is a general asynchronous algorithm that has … Read more

    On the identification of optimal partition for semidefinite optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    The concept of the optimal partition was originally introduced for linear optimization and linear complementarity problems and subsequently extended to semidefinite optimization. For linear optimization and sufficient linear complementarity problems, from a central solution sufficiently close to the optimal set, the optimal partition and a maximally complementary optimal solution can be identified in strongly polynomial … Read more

    On max-k-sums

  • Michael J. Todd
    • Categories Basic Sciences Applications, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The max-$k$-sum of a set of real scalars is the maximum sum of a subset of size $k$, or alternatively the sum of the $k$ largest elements. We study two extensions: First, we show how to obtain smooth approximations to functions that are pointwise max-$k$-sums of smooth functions. Second, we discuss how the max-$k$-sum can … Read more

    A first-order primal-dual algorithm with linesearch

  • Yura Malitsky
  • Thomas Pock
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    The paper proposes a linesearch for the primal-dual method. Each iteration of the linesearch requires to update only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under the standard assumptions. We also show … Read more

    Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more

    Improving an ADMM-like Splitting Method via Positive-Indefinite Proximal Regularization for Three-Block Separable Convex Minimization

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , ,

    The augmented Lagrangian method (ALM) is fundamental for solving convex minimization models with linear constraints. When the objective function is separable such that it can be represented as the sum of more than one function without coupled variables, various splitting versions of the ALM have been well studied in the literature such as the alternating … Read more

    A simple preprocessing algorithm for semidefinite programming

  • Preston Faulk
  • Gabor Pataki
  • Quoc Tran-Dinh
    • Categories Convex Optimization, Optimization Software Benchmark, Semi-definite Programming

    We propose a very simple preprocessing algorithm for semidefinite programming. Our algorithm inspects the constraints of the problem, deletes redundant rows and columns in the constraints, and reduces the size of the variable matrix. It often detects infeasibility. Our algorithm does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, … Read more