A Polynomial Arc-Search Interior-Point Algorithm for Convex Quadratic Programming

  • Yaguang Yang
    • Categories Linear Programming Tags , ,

    Arc-search is developed for linear programming in \cite{yang09, yang10}. The algorithms search for optimizers along an ellipse that are approximations of the central path. In this paper, the arc-search method is applied to primal-dual path-following interior-point method for convex quadratic programming. A simple algorithm with iteration complexity $O(\sqrt{n}\log(1/\epsilon))$ is devised. Several improvements on the simple … Read more

    A constraint sampling approach for multi-stage robust optimization

  • Daniel Kuhn
  • Berc Rustem
  • Phebe Vayanos
    • Categories Robust Optimization Tags , , ,

    We propose a tractable approximation scheme for convex (not necessarily linear) multi-stage robust optimization problems. We approximate the adaptive decisions by finite linear combinations of prescribed basis functions and demonstrate how one can optimize over these decision rules at low computational cost through constraint randomization. We obtain a-priori probabilistic guarantees on the feasibility properties of … Read more

    Cost-sharing mechanisms for scheduling under general demand settings

  • Sindhura Balireddi
  • Nelson A. Uhan
    • Categories Game Theory, Scheduling

    We investigate cost-sharing mechanisms for scheduling cost-sharing games. We assume that the demand is general—that is, each player can be allocated one of several levels of service. We show how to design mechanisms for these games that are weakly group strategyproof, approximately budget-balanced, and approximately efficient, using approximation algorithms for the underlying scheduling problems. We … Read more

    Generalizations of the limited-memory BFGS method based on quasi-product form of update

  • Ladislav Lukšan
  • Jan Vlček
    • Categories Nonlinear Optimization Tags , , , , ,

    Two families of limited-memory variable metric or quasi-Newton methods for unconstrained minimization based on quasi-product form of update are derived. As for the first family, four variants how to utilize the Strang recurrences for the Broyden class of variable metric updates are investigated; three of them use the same number of stored vectors as the … Read more

    Recursive formulation of limited memory variable metric methods

  • Ladislav Lukšan
  • Jan Vlček
    • Categories Nonlinear Optimization Tags , , , ,

    In this report we propose a new recursive matrix formulation of limited memory variable metric methods. This approach can be used for an arbitrary update from the Broyden class (and some other updates) and also for the approximation of both the Hessian matrix and its inverse. The new recursive formulation requires approximately $4 m n$ … Read more

    Band preconditioners for the matrix-free truncated Newton method

  • Ladislav Lukšan
  • Ctirad Matonoha
  • Jan Vlček
    • Categories Nonlinear Optimization Tags , , , ,

    This report is devoted to preconditioning techniques for the matrix-free truncated Newton method. After a review of basic known pproaches, we propose ew results concerning tridiagonal and pentadiagonal preconditioners based on the standard BFGS updates and on numerical differentiation. Furthermore, we present results of extensive numerical experiments serving for the careful comparison of suitable preconditioning … Read more

    Reliable solution of convex quadratic programs with parametric active set methods

  • Hans Georg Bock
  • Christian Kirches
  • Andreas Potschka
  • Johannes P. Schlöder
    • Categories Convex Optimization, Optimization Software Benchmark, Quadratic Programming Tags , , ,

    Parametric Active Set Methods (PASM) are a relatively new class of methods to solve convex Quadratic Programming (QP) problems. They are based on tracing the solution along a linear homotopy between a QP with known solution and the QP to be solved. We explicitly identify numerical challenges in PASM and develop strategies to meet these … Read more

    A quasi-Newton projection method for nonnegatively constrained image deblurring

  • Germana Landi
  • Elena Loli Piccolomini
    • Categories Basic Sciences Applications, Bound-constrained Optimization Tags , , , ,

    In this paper we present a quasi-Newton projection method for image deblurring. The mathematical problem is a constrained minimization problem, where the objective function is a regularization function and the constraint is the positivity of the solution. The regularization function is a sum of the Kullback-Leibler divergence, used to minimize the error in the presence … Read more

    DERIVATIVE-FREE METHODS FOR BOUND CONSTRAINED MIXED-INTEGER OPTIMIZATION

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization Tags , ,

    We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that the first order derivatives of the objective function can be neither calculated nor approximated explicitly. This class of mixed integer nonlinear optimization problems … Read more

    A Parallel Inertial Proximal Optimization Method

  • Jean-Christophe Pesquet
  • Nelly Pustelnik
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Parallel Algorithms Tags , , , , ,

    The Douglas-Rachford algorithm is a popular iterative method for finding a zero of a sum of two maximal monotone operators defined on a Hilbert space. In this paper, we propose an extension of this algorithm including inertia parameters and develop parallel versions to deal with the case of a sum of an arbitrary number of … Read more