A Tractable Approximation of Stochastic Programming via Robust Optimization

  • Xin Chen
  • Peng Sun
  • Jiawei Zhang
  • Melvyn Sim
    • Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , , ,

    Stochastic programming, despite its immense modeling capabilities, is well known to be computationally excruciating. In this paper, we introduce a unified framework of approximating multiperiod stochastic programming from the perspective of robust optimization. Specifically, we propose a framework that integrates multistage modeling with safeguarding constraints. The framework is computationally tractable in the form of second … Read more

    A Feasibility Pump for Mixed Integer Nonlinear Programs

  • Pierre Bonami
  • Gérard Cornuéjols
  • Andrea Lodi
  • François Margot
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within … Read more

    A Robust Optimization Framework for Analyzing Distribution Systems with Transshipment

  • Mabel C. Chou
  • Melvyn Sim
  • Rick So
    • Categories Robust Optimization, Stochastic Programming, Supply Chain Management Tags , , ,

    This paper studies a distribution system consisting of multiple retail locations with transshipment operations among the retailers. Due to the difficulty in computing the optimal solution imposed by the transshipment operations and in estimating shortage cost from a practical perspective, we propose a robust optimization framework for analyzing the impact of transshipment operations on such … Read more

    A local convergence property of primal-dual methods for nonlinear programming

  • Paul Armand
  • Joël Benoist
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We prove a new local convergence property of a primal-dual method for solving nonlinear optimization problem. Following a standard interior point approach, the complementarity conditions of the original primal-dual system are perturbed by a parameter which is driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed … Read more

    Smooth minimization of two-stage stochastic linear programs

  • Shabbir Ahmed
    • Categories Nonsmooth Optimization, Stochastic Programming Tags ,

    This note presents an application of the smooth optimization technique of Nesterov for solving two-stage stochastic linear programs. It is shown that the original O(1/e) bound of Nesterov on the number of main iterations required to obtain an e-optimal solution is retained. CitationTechnical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology, 2006.ArticleDownload … Read more

    An extension of the standard polynomial-time primal-dual path-following algorithm to the weighted determinant maximization problem with semidefinite constraints

  • Takashi Tsuchiya
  • Yu Xia
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The problem of maximizing the sum of linear functional and several weighted logarithmic determinant (logdet) functions under semidefinite constraints is a generalization of the semidefinite programming (SDP) and has a number of applications in statistics and datamining, and other areas of informatics and mathematical sciences. In this paper, we extend the framework of standard primal-dual … Read more

    Central Paths in Semidefinite Programming, Generalized Proximal Point Method and Cauchy Trajectories in Riemannian Manifolds

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Paulo Roberto Oliveira
  • R. C. M. Silva
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The relationships among central path in the context of semidefinite programming, generalized proximal point method and Cauchy trajectory in Riemannian manifolds is studied in this paper. First it is proved that the central path associated to the general function is well defined. The convergence and characterization of its limit point is established for functions satisfying … Read more

    Second-order convergence properties of trust-region methods using incomplete curvature information, with an application to multigrid optimization

  • Serge Gratton
  • Annick Sartenaer
  • Philippe L. Toint
    • Categories Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization, Unconstrained Optimization Tags , ,

    Convergence properties of trust-region methods for unconstrained nonconvex optimization is considered in the case where information on the objective function’s local curvature is incomplete, in the sense that it may be restricted to a fixed set of “test directions” and may not be available at every iteration. It is shown that convergence to local “weak” … Read more

    Stochastic Programming Approach to Optimization under Uncertainty

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , ,

    In this paper we discuss computational complexity and risk averse approaches to two and multistage stochastic programming problems. We argue that two stage (say linear) stochastic programming problems can be solved with a reasonable accuracy by Monte Carlo sampling techniques while there are indications that complexity of multistage programs grows fast with increase of the … Read more