Month: February 2012

Solving trajectory optimization problems via nonlinear programming: the brachistochrone case study

  • Jean-Pierre Dussault
    • Categories Nonlinear Optimization Tags

    This note discusses reformulations the brachistochrone problem suitable for solution via NLP. The availability of solvers and modeling languages such as AMPL makes it tempting to formulate discretized optimization problems and get solutions to the discretized versions of trajectory optimization problems. We use the famous brachistochrone problem to warn that the resulting solutions may be … Read more

    Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization

  • Pierre-Antoine Absil
  • Luke Winternitz
  • André L. Tits
    • Categories Linear Programming Tags , , ,

    In earlier work (Tits et al., SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints … Read more

    Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences

  • Christopher Re
  • Benjamin Recht
    • Categories Nonlinear Optimization

    Randomized algorithms that base iteration-level decisions on samples from some pool are ubiquitous in machine learning and optimization. Examples include stochastic gradient descent and randomized coordinate descent. This paper makes progress at theoretically evaluating the difference in performance between sampling with- and without-replacement in such algorithms. Focusing on least means squares optimization, we formulate a … Read more

    Asymptotic Analysis of Sample Average Approximation for Stochastic Optimization Problems with Joint Chance Constraints via CVaR/DC Approximations

  • Hailin Sun
  • Huifu Xu
  • Yong Wang
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , , , ,

    Conditional Value at Risk (CVaR) has been recently used to approximate a chance constraint. In this paper, we study the convergence of stationary points when sample average approximation (SAA) method is applied to a CVaR approximated joint chance constrained stochastic minimization problem. Specifically, we prove, under some moderate conditions, that optimal solutions and stationary points … Read more

    Sensitivity analysis for the outages of nuclear power plants

  • Kengy Barty
  • Joseph Frédéric Bonnans
  • Laurent Pfeiffer
    • Categories Control Applications Tags , , ,

    Nuclear power plants must be regularly shut down in order to perform refueling and maintenance operations. The scheduling of the outages is the first problem to be solved in electricity production management. It is a hard combinatorial problem for which an exact solving is impossible. Our approach consists in modelling the problem by a two-level … Read more

    A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

  • Frank Fischer
  • Christoph Helmberg
    • Categories Convex Optimization, Parallel Algorithms Tags , ,

    An algorithmic approach is proposed for exploiting parallelization possibilities in large scale optimization models of the following generic type. Objects change their state over time subject to a limited availability of common resources. These are modeled by linear coupling constraints and result in few objects competing for the same resource at each point in time. … Read more

    Interior-Point Methods for Nonconvex Nonlinear Programming: Cubic Regularization

  • Hande Benson
  • David F. Shanno
    • Categories Constrained Nonlinear Optimization Tags , ,

    In this paper, we present a barrier method for solving nonlinear programming problems. It employs a Levenberg-Marquardt perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the Levenberg-Marquardt perturbation is equivalent to replacing the Newton step by a cubic regularization … Read more

    An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables

  • Tomonari Kitahara
  • Shinji Mizuno
    • Categories Linear Programming

    Kitahara and Mizuno (2011a) obtained an upper bound for the number of different solutions generated by the primal simplex method with Dantzig’s (the most negative) pivoting rule. In this paper, we obtain an upper bound with any pivoting rule which chooses an entering variable whose reduced cost is negative at each iteration. The bound is … Read more

    Exact Penalization, Level Function Method and Modified Cutting-Plane Method for Stochastic Programs with Second Order Stochastic Dominance Constraints

  • Rudabeh Meskarian
  • Hailin Sun
  • Huifu Xu
  • Yong Wang
    • Categories Finance and Economics, Stochastic Programming Tags , , ,

    Level function methods and cutting plane methods have been recently proposed to solve stochastic programs with stochastic second order dominance (SSD) constraints. A level function method requires an exact penalization setup because it can only be applied to the objective function, not the constraints. Slater constraint qualification (SCQ) is often needed for deriving exact penalization. … Read more

    Branch-and-Price Guided Search for Integer Programs with an Application to the Multicommodity Fixed Charge Network Flow Problem

  • Mike Hewitt
  • George L. Nemhauser
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Network Optimization

    We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in … Read more