primal-dual algorithms

Convergence Results for Primal-Dual Algorithms in the Presence of Adjoint Mismatch

  • Andres Contreras
  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Marion Savanier
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , ,

    Most optimization problems arising in imaging science involve high-dimensional linear operators and their adjoints. In the implementations of these operators, approximations may be introduced for various practical considerations (e.g., memory limitation, computational cost, convergence speed), leading to an adjoint mismatch. This occurs for the X-ray tomographic inverse problems found in Computed Tomography (CT), where the … Read more

    A nested primal–dual FISTA-like scheme for composite convex optimization problems

  • Silvia Bonettini
  • Marco Prato
  • Simone Rebegoldi
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We propose a nested primal–dual algorithm with extrapolation on the primal variable suited for minimizing the sum of two convex functions, one of which is continuously differentiable. The proposed algorithm can be interpreted as an inexact inertial forward–backward algorithm equipped with a prefixed number of inner primal–dual iterations for the proximal evaluation and a “warm–start” … Read more

    Bregman primal–dual first-order method and application to sparse semidefinite programming

  • Xin Jiang
  • Lieven Vandenberghe
    • Categories Semi-definite Programming Tags , , ,

    We present a new variant of the Chambolle–Pock primal–dual method with Bregman distances, analyze its convergence, and apply it to the centering problem in sparse semidefinite programming. The novelty in the method is a line search procedure for selecting suitable step sizes. The line search obviates the need for estimating the norm of the constraint … Read more

    A primal-dual modified log-barrier method for inequality constrained nonlinear optimization

  • Joshua D. Griffin
  • Riadh Omheni
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    We present a primal-dual modified log-barrier algorithm to solve inequality constrained nonlinear optimization problems. Basically, the algorithm is a Newton-like method applied to a perturbation of the optimality system that follows from a reformulation of the initial problem by introducing a modified log-barrier function to handle inequality constraints. The algorithm uses an outer/inner iteration scheme … Read more

    Status Determination by Interior-Point Methods for Convex Optimization Problems in Domain-Driven Form

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

    We study the geometry of convex optimization problems given in a Domain-Driven form and categorize possible statuses of these problems using duality theory. Our duality theory for the Domain-Driven form, which accepts both conic and non-conic constraints, lets us determine and certify statuses of a problem as rigorously as the best approaches for conic formulations … Read more

    The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems

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

    In this work, we show that for linearly constrained optimization problems the primal-dual hybrid gradient algorithm, analyzed by Chambolle and Pock [3], can be written as an entirely primal algorithm. This allows us to prove convergence of the iterates even in the degenerate cases when the linear system is inconsistent or when the strong duality … Read more

    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

    A Shifted Primal-Dual Interior Method for Nonlinear Optimization

  • Philip E. Gill
  • Vyacheslav Kungurtsev
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    Interior methods provide an effective approach for the treatment of inequality constraints in nonlinearly constrained optimization. A new primal-dual interior method is proposed based on minimizing a sequence of shifted primal-dual penalty-barrier functions. Certain global convergence properties are established. In particular, it is shown that every limit point is either an infeasible stationary point, or … Read more

    On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting

  • Daniel O'Connor
  • Lieven Vandenberghe
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    The primal-dual hybrid gradient (PDHG) algorithm proposed by Esser, Zhang, and Chan, and by Pock, Cremers, Bischof, and Chambolle is known to include as a special case the Douglas-Rachford splitting algorithm for minimizing the sum of two convex functions. We show that, conversely, the PDHG algorithm can be viewed as a special case of the … Read more

    An improved approximation algorithm for the covering 0-1 integer program

  • Tomonari Kitahara
  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms Tags , ,

    We present an improved approximation algorithm for the covering 0-1 integer program (CIP), a well-known problem as a natural generalization of the set cover problem. Our algorithm uses a primal-dual algorithm for CIP by Fujito (2004) as a subroutine and achieves an approximation ratio of (f- (f-1)/m) when m is greater than or equal to … Read more