Asymptotic equivalence and Kobayashi-type estimates for nonautonomous monotone operators in Banach spaces

  • Felipe Álvarez
  • Juan Peypouquet
    • Categories Basic Sciences Applications Tags , ,

    We provide a sharp generalization to the nonautonomous case of the well-known Ko\-ba\-yashi estimate for proximal iterates associated with maximal monotone operators. We then derive a bound for the distance between a continuous-in-time trajectory, namely the solution to the differential inclusion $\dot{x} + A(t)x\ni 0$, and the corresponding proximal iterations. We also establish continuity properties … Read more

    Algorithms for stochastic lot-sizing problems with backlogging

  • Yongpei Guan
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    As a traditional model in the operations research and management science domain, lot-sizing problem is embedded in many application problems such as production and inventory planning and has been consistently drawing attentions from researchers. There is significant research progress on polynomial time algorithm developments for deterministic uncapacitated lot-sizing problems based on Wagner-and-Whitin property. However, in … Read more

    Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

  • Dimitris Bertsimas
  • Xuan Vinh Doan
  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories Semi-definite Programming, Stochastic Programming

    In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with … Read more

    New Turnpike Theorems for the Unbounded Knapsack Problem

  • Ping H. Huang
  • Thomas L. Morin
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bang-for-buck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce … Read more

    Nonlinear Optimization over a Weighted Independence System

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , ,

    We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual … Read more

    On the computation of $C^*$ certificates

  • Florian Jarre
  • Katrin Schmallowsky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags

    The cone of completely positive matrices $C^*$ is the convex hull of all symmetric rank-1-matrices $xx^T$ with nonnegative entries. Determining whether a given matrix $B$ is completely positive is an $\cal NP$-complete problem. We examine a simple algorithm which — for a given input $B$ — either determines a certificate proving that $B\in C^*$ or … Read more

    Automatically Assessing the Performance of an Optimization-Based Multigrid Method

  • Robert Michael Lewis
  • Stephen G. Nash
    • Categories Systems governed by Differential Equations Optimization Tags , ,

    Many large nonlinear optimization problems are based upon discretizations of underlying function spaces. Optimization-based multigrid methods—that is, multigrid methods based on solving coarser versions of an optimization problem—are designed to solve such discretized problems efficiently by taking explicit advantage of the family of discretizations. The methods are generalizations of more traditional multigrid methods for solving … Read more

    A Primal-Dual Augmented Lagrangian

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

    Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we discuss the formulation of subproblems in which the objective is a primal-dual generalization of the Hestenes-Powell augmented Lagrangian function. This generalization has the crucial feature that it is minimized with respect to both … Read more

    SHOWCASE SCHEDULING AT FRED ASTAIRE EAST SIDE DANCE STUDIO

  • Miguel A. Lejeune
  • Nevena Yakova
    • Categories Applications - OR and Management Sciences, Scheduling

    The ballroom dancing showcases at Fred Astaire East Side Dance Studio in Manhattan are held at least twice a year and provide the students with an environment for socializing, practice, and improvement. The most important part of a showcase organization is the construction of the dance presentations timetable, and, with the number of participants increasing … Read more