Convex and Nonsmooth Optimization

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

    Complexity of gradient descent for multiobjective optimization

  • Jörg Fliege
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    A number of first-order methods have been proposed for smooth multiobjective optimization for which some form of convergence to first order criticality has been proved. Such convergence is global in the sense of being independent of the starting point. In this paper we analyze the rate of convergence of gradient descent for smooth unconstrained multiobjective … Read more

    New inertial factors of a splitting method for monotone inclusions

  • Fang Bingbing
  • Yunda Dong
  • Wang Xiangyang
    • Categories Convex and Nonsmooth Optimization

    In this article, we consider monotone inclusions of two operators in real Hilbert spaces, in which one is further assumed to be Lipschitz continuous, and we suggest adding an inertial term to a splitting method at each iteration. The associated weak convergence is analyzed under standard assumptions. The way of choosing steplength is self-adaptive via … Read more

    Block Coordinate Proximal Gradient Method for Nonconvex Optimization Problems: Convergence Analysis

  • Xiangfeng Wang
  • Xiao-Ming Yuan
  • Shangzhi Zeng
  • Jin Zhang
  • Jinchuan Zhou
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    We propose a block coordinate proximal gradient method for a composite minimization problem with two nonconvex function components in the objective while only one of them is assumed to be differentiable. Under some per-block Lipschitz-like conditions based on Bregman distance, but without the global Lipschitz continuity of the gradient of the differentiable function, we prove … Read more

    An algorithm for solving infinite horizon Markov dynamic programmes

  • Regan Baucke
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming Tags , , , ,

    We consider a general class of infinite horizon dynamic programmes where state and control sets are convex and compact subsets of Euclidean spaces and (convex) costs are discounted geometrically. The aim of this work is to provide a convergence result for these problems under as few restrictions as possible. Under certain assumptions on the cost … Read more

    BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a … Read more

    User Manual for BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    BBCPOP proposed in [4] is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity constraints. Given a POP in the class and a relaxation order (or a hierarchy level), BBCPOP constructs a simple conic optimization problem (COP), which … Read more

    Derivative-Free Superiorization With Component-Wise Perturbations

  • Yair Censor
  • Howard Heaton
  • Reinhard W. Schulte
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    Superiorization reduces, not necessarily minimizes, the value of a target function while seeking constraints-compatibility. This is done by taking a solely feasibility-seeking algorithm, analyzing its perturbations resilience, and proactively perturbing its iterates accordingly to steer them toward a feasible point with reduced value of the target function. When the perturbation steps are computationally efficient, this … Read more

    Stochastic model-based minimization of weakly convex functions

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    We consider an algorithm that successively samples and minimizes stochastic models of the objective function. We show that under weak-convexity and Lipschitz conditions, the algorithm drives the expected norm of the gradient of the Moreau envelope to zero at the rate $O(k^{-1/4})$. Our result yields the first complexity guarantees for the stochastic proximal point algorithm … Read more

    Entropic proximal operators for nonnegative trigonometric polynomials

  • Hsiao-Han Chao
  • Lieven Vandenberghe
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

    Signal processing applications of semidefinite optimization are often rooted in sum-of-squares representations of nonnegative trigonometric polynomials. Interior-point solvers for semidefinite optimization can handle constraints of this form with a per-iteration-complexity that is cubic in the degree of the trigonometric polynomial. The purpose of this paper is to discuss first-order methods with a lower complexity per … Read more