Logarithmic-Barrier Decomposition Interior-Point Methods for Stochastic Linear Optimization in a Hilbert Space

  • Baha Alzalg
    • Categories Infinite Dimensional Optimization, Linear Programming, Stochastic Programming

    Several logarithmic-barrier interior-point methods are now available for solving two-stage stochastic optimization problems with recourse in the finite-dimensional setting. However, despite the genuine need for studying such methods in general spaces, there are no infinite-dimensional analogs of these methods. Inspired by this evident gap in the literature, in this paper, we propose logarithmic-barrier decomposition-based interior-point … Read more

    Identifying Effective Scenarios for Sample Average Approximation

  • Lijian Chen
    • Categories Stochastic Programming Tags

    We introduce a method to improve the tractability of the well-known Sample Average Approximation (SAA) without compromising important theoretical properties, such as convergence in probability and the consistency of an independent and identically distributed (iid) sample. We consider each scenario as a polyhedron of the mix of first-stage and second-stage decision variables. According to John’s … Read more

    Tractable semi-algebraic approximation using Christoffel-Darboux kernel

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Swann Marx
  • Edouard Pauwels
  • Tillmann Weisser
    • Categories Semi-definite Programming Tags , , , ,

    We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy … Read more

    Error estimates for iterative algorithms for minimizing regularized quadratic subproblems

  • Nicholas I. M. Gould
  • Valeria Simoncini
    • Categories Nonlinear Optimization Tags , , ,

    We derive bounds for the objective errors and gradient residuals when finding approximations to the solution of common regularized quadratic optimization problems within evolving Krylov spaces. These provide upper bounds on the number of iterations required to achieve a given stated accuracy. We illustrate the quality of our bounds on given test examples. Citation Technical … Read more

    Planning Out-of-Hours Services for Pharmacies

  • Christina Büsing
  • Arie M.C.A. Koster
  • Timo Gersing
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Scheduling Tags , , , , ,

    The supply of pharmaceuticals is one important factor in a functioning health care system. In the German health care system, the chambers of pharmacists are legally obliged to ensure that every resident can find an open pharmacy at any day and night time within an appropriate distance. To that end, the chambers of pharmacists create … Read more

    A Delayed Weighted Gradient Method for Strictly Convex Quadratic Minimization

  • Harry Oviedo
    • Categories Nonlinear Optimization, Quadratic Programming, Unconstrained Optimization Tags , ,

    This paper develops an accelerated version of the steepest descent method by a two-step iteration. The new algorithm uses information with delay to define the iterations. Specifically, in the first step, a prediction of the new test point is calculated by using the gradient method with the exact minimal gradient steplength and then, a correction … Read more

    Partially observable multistage stochastic programming

  • Oscar Dowson
  • David P. Morton
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming

    We propose a class of partially observable multistage stochastic programs and describe an algorithm for solving this class of problems. We provide a Bayesian update of a belief-state vector, extend the stochastic programming formulation to incorporate the belief state, and characterize saddle-function properties of the corresponding cost-to-go function. Our algorithm is a derivative of the … Read more

    Exact Multiple Sequence Alignment by Synchronized Decision Diagrams

  • Amin Hosseininasab
  • Willem-Jan van Hoeve
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Integer Programming

    This paper develops an exact solution algorithm for the Multiple Sequence Alignment (MSA) problem. In the first step, we design a dynamic programming model and use it to construct a novel Multi-valued Decision Diagrams (MDD) representation of all pairwise sequence alignments (PSA). PSA MDDs are then synchronized using side constraints to model the MSA problem … Read more

    Multi-objective optimization models for many-to-one matching problems

  • Natsumi Shimada
  • Yuichi Takano
  • Natsuki Yamazaki
    • Categories (Mixed) Integer Linear Programming, Finance and Economics Tags , , , ,

    This paper is concerned with many-to-one matching problems for assigning residents to hospitals according to their preferences. The stable matching model aims at finding a stable matching, and the assignment game model involves maximizing the total utility; however, these two objectives are incompatible in general. We also focus on a situation where there are predetermined … Read more

    Line search and convergence in bound-constrained optimization

  • Behzad Azmi
  • Arnold Neumaier
    • Categories Bound-constrained Optimization Tags , , , ,

    The first part of this paper discusses convergence properties of a new line search method for the optimization of continuously differentiable functions with Lipschitz continuous gradient. The line search uses (apart from the gradient at the current best point) function values only. After deriving properties of the new, in general curved, line search, global convergence … Read more