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

    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

    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

    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

    On the convergence of the modified Levenberg-Marquardt method with a nonmonotone second order Armijo type line search

  • Weijun Zhou
    • Categories Nonlinear Systems and Least-Squares

    Recently, Fan [4, Math. Comput., 81 (2012), pp. 447-466] proposed a modified Levenberg-Marquardt (MLM) method for nonlinear equations. Using a trust region technique, global and cubic convergence of the MLM method is proved [4] under the local error bound condition, which is weaker than nonsingularity. The purpose of the paper is to investigate the convergence … Read more

    Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems

  • Thomas L. Magnanti
  • Dan Stratila
    • Categories Combinatorial Optimization, Supply Chain Management

    We introduce an algorithm design technique for a class of combinatorial optimization problems with concave costs. This technique yields a strongly polynomial primal-dual algorithm for a concave cost problem whenever such an algorithm exists for the fixed-charge counterpart of the problem. For many practical concave cost problems, the fixed-charge counterpart is a well-studied combinatorial optimization … Read more

    The Lagrangian Relaxation for the Combinatorial Integral Approximation Problem

  • Michael N. Jung
  • Sebastian Sager
  • Gerhard Reinelt
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming Tags , , , ,

    We are interested in methods to solve mixed-integer nonlinear optimal control problems (MIOCPs) constrained by ordinary di erential equations and combinatorial constraints on some of the control functions. To solve these problems we use a rst discretize, then opti- mize approach to get a specially structured mixed-integer nonlinear program (MINLP). We decompose this MINLP into an … Read more

    D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization

  • Pedro Aguiar
  • João Mota
  • Markus Püschel
  • João Xavier
    • Categories Convex Optimization, Network Optimization Tags , , , , ,

    We propose a distributed algorithm, named D-ADMM, for solving separable optimization problems in networks of interconnected nodes or agents. In a separable optimization problem, the cost function is the sum of all the agents’ private cost functions, and the constraint set is the intersection of all the agents’ private constraint sets. We require the private … Read more