Convex Optimization

A Partial PPa S-ADMM for Multi-Block for Separable Convex Optimization with Linear Constraints

  • Yuan Shen
  • Aolin Yu
  • Yannian Zuo
    • Categories Convex Optimization Tags , , , ,

    The symmetric alternating direction method of multipliers (S-ADMM) is a classical effective method for solving two-block separable convex optimization. However, its convergence may not be guaranteed for multi-block case providing there is no additional assumptions. In this paper, we propose a partial PPa S-ADMM (referred as P3SADMM), which updates the Lagrange multiplier twice with suitable … Read more

    Projection and rescaling algorithm for finding most interior solutions to polyhedral conic systems

  • Javier F. Peña
  • Negar Soheili
    • Categories Convex Optimization, Linear Programming Tags , , , ,

    We propose a simple projection and rescaling algorithm that finds {\em most interior} solutions to the pair of feasibility problems \[ \text{find} x\in L\cap \R^n_{+} \text{ and } \text{find} \; \hat x\in L^\perp\cap\R^n_{+}, \] where $L$ is a linear subspace of $\R^n$ and $L^\perp$ is its orthogonal complement. The algorithm complements a basic procedure that … Read more

    An explicit Tikhonov algorithm for nested variational inequalities

  • Lorenzo Lampariello
  • Christoph Neumann
  • Simone Sagratella
  • Oliver Stein
  • Jacopo Maria Ricci
    • Categories Complementarity and Variational Inequalities, Convex Optimization

    We consider nested variational inequalities consisting in a (upper-level) variational inequality whose feasible set is given by the solution set of another (lower-level) variational inequality. Purely hierarchical convex bilevel optimization problems and certain multi-follower games are particular instances of nested variational inequalities. We present an explicit and ready-to-implement Tikhonov-type solution method for such problems. We … Read more

    Effectively managing diagnostic tests to monitor the COVID-19 outbreak in Italy

  • Lorenzo Lampariello
  • Simone Sagratella
    • Categories Biomedical Applications, Convex Optimization

    Urged by the outbreak of the COVID-19 in Italy, this study aims at helping to tackle the spread of the disease by resorting to operations research techniques. In particular, we propose a mathematical program to model the problem of establishing how many diagnostic tests the Italian regions must perform in order to maximize the overall … Read more

    Geometry of First-Order Methods and Adaptive Acceleration

  • Jingwei Liang
  • Clarice Poon
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    First-order operator splitting methods are ubiquitous among many fields through science and engineering, such as inverse problems, signal/image processing, statistics, data science and machine learning, to name a few. In this paper, we study a geometric property of first-order methods when applying to solve non-smooth optimization problems. With the tool of “partial smoothness”, we design … Read more

    Orthogonal projection algorithm for projecting onto a fnitely generated cone

  • Chengjin Li
  • Shenggui Zhang
    • Categories Convex Optimization Tags , ,

    In this paper, an algorithm is proposed to find the nearest point of a convex cone to a given vector, which is composed of a series of orthogonal projections. Some properties of this algorithm, including the reasonability of implementation, the global convergence property and the finite termination, etc., are obtained. The proposed algorithm is more … Read more

    A Hybrid Gradient Method for Strictly Convex Quadratic Programming

  • Oscar S. Dalmau
  • Rafael Herrera
  • Harry Oviedo
    • Categories Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags ,

    In this paper, a reliable hybrid algorithm for solving convex quadratic minimization problems is presented. At each iteration, two points are computed: first, an auxiliary point $\dot{x}_k$ is generated by performing a gradient step equipped with an optimal steplength, then, the next iterate $x_{k+1}$ is obtained through a weighted sum of $\dot{x}_k$ with the penultimate … Read more

    Optimal Learning for Structured Bandits

  • Negin Golrezaei
  • Bart Paul Gerard Van Parys
    • Categories Convex Optimization, Semi-infinite Programming, Stochastic Programming Tags , ,

    We study structured multi-armed bandits, which is the problem of online decision-making under uncertainty in the presence of structural information. In this problem, the decision-maker needs to discover the best course of action despite observing only uncertain rewards over time. The decision- maker is aware of certain structural information regarding the reward distributions and would … Read more

    A parallel splitting ALM-based algorithm for separable convex programming

  • Bingsheng He
  • Shengjie Xu
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Parallel Algorithms Tags , , , ,

    The augmented Lagrangian method (ALM) provides a benchmark for tackling the canonical convex minimization problem with linear constraints. We consider a special case where the objective function is the sum of $m$ individual subfunctions without coupled variables. The recent study reveals that the direct extension of ALM for separable convex programming problems is not necessarily … Read more

    Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach

  • Mituhiro Fukuda
  • Masaru Ito
    • Categories Convex Optimization, Nonsmooth Optimization

    In the development of first-order methods for smooth (resp., composite) convex optimization problems minimizing smooth functions, the gradient (resp., gradient mapping) norm is a fundamental optimality measure for which a regularization technique of first-order methods is known to be nearly optimal. In this paper, we report an adaptive regularization approach attaining this iteration complexity without … Read more