Month: June 2013

Sample Average Approximation Method for Compound Stochastic Optimization Problems

  • Yuri M. Ermoliev
  • Vladimir I. Norkin
    • Categories Statistics, Stochastic Programming

    The paper studies stochastic optimization (programming) problems with compound functions containing expectations and extreme values of other random functions as arguments. Compound functions arise in various applications. A typical example is a variance function of nonlinear outcomes. Other examples include stochastic minimax problems, econometric models with latent variables, and multilevel and multicriteria stochastic optimization problems. … Read more

    Extended Linear Formulation for Binary Quadratic Problems

  • Fabio Furini
  • Emiliano Traversi
    • Categories 0-1 Programming, Quadratic Programming

    In this work we propose and test a new linearisation technique for Binary Quadratic Problems (BQP). We computationally prove that the new formulation, called Extended Linear Formulation, performs much better than the standard one in practice, despite not being stronger in terms of Linear Programming relaxation (LP). We empirically prove that this behaviour is due … Read more

    Finitely Convergent Decomposition Algorithms for Two-Stage Stochastic Pure Integer Programs

  • Simge Küçükyavuz
  • Minjiao Zhang
    • Categories Integer Programming, Stochastic Programming Tags , ,

    We study a class of two-stage stochastic integer programs with general integer variables in both stages and finitely many realizations of the uncertain parameters. Based on Benders’ method, we propose a decomposition algorithm that utilizes Gomory cuts in both stages. The Gomory cuts for the second-stage scenario subproblems are parameterized by the first-stage decision variables, … Read more

    On Minimal Valid Inequalities for Mixed Integer Conic Programs

  • Fatma Kılınç-Karzan
    • Categories (Mixed) Integer Nonlinear Programming

    We study mixed integer conic sets involving a general regular (closed, convex, full dimensional, and pointed) cone K such as the nonnegative orthant, the Lorentz cone or the positive semidefinite cone. In a unified framework, we introduce K-minimal inequalities and show that under mild assumptions, these inequalities together with the trivial cone-implied inequalities are sufficient … Read more

    Family Constraining of Iterative Algorithms

  • Yair Censor
  • Ioana Pantelimon
  • Constantin Popa
    • Categories Applications - Science and Engineering, Nonlinear Systems and Least-Squares Tags , ,

    In constraining iterative processes, the algorithmic operator of the iterative process is pre-multiplied by a constraining operator at each iterative step. This enables the constrained algorithm, besides solving the original problem, also to find a solution that incorporates some prior knowledge about the solution. This approach has been useful in image restoration and other image … Read more

    Mixed Integer Second-Order Cone Programming Formulations for Variable Selection

  • Ryuhei Miyashiro
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming, Statistics Tags , , , , ,

    This paper concerns the method of selecting the best subset of explanatory variables in a multiple linear regression model. To evaluate a subset regression model, some goodness-of-fit measures, e.g., adjusted R^2, AIC and BIC, are generally employed. Although variable selection is usually handled via a stepwise regression method, the method does not always provide the … Read more

    Randomized Block Coordinate Non-Monotone Gradient Method for a Class of Nonlinear Programming

  • Zhaosong Lu
  • Lin Xiao
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    In this paper we propose a randomized block coordinate non-monotone gradient (RBCNMG) method for minimizing the sum of a smooth (possibly nonconvex) function and a block-separable (possibly nonconvex nonsmooth) function. At each iteration, this method randomly picks a block according to any prescribed probability distribution and typically solves several associated proximal subproblems that usually have … Read more

    An MILP approach to Multi-location, Multi-Period Equipment Selection for Surface Mining with Case Studies

  • Christina Burt
  • Louis Caccetta
  • Leon Fouche
  • Palitha Welgama
    • Categories Applications - OR and Management Sciences Tags , ,

    In the surface mining industry, the Equipment Selection Problem involves choosing an appropriate fleet of trucks and loaders such that the long-term mine plan can be satisfied. An important characteristic for multi-location (multi-location and multi-dumpsite) mines is that the underlying problem is a multi-commodity flow problem. The problem is therefore at least as difficult as … Read more

    A Second-Order Method for Strongly Convex L1-Regularization Problems

  • Kimon Fountoulakis
  • Jacek Gondzio
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In this paper a robust second-order method is developed for the solution of strongly convex l1-regularized problems. The main aim is to make the proposed method as inexpensive as possible, while even difficult problems can be efficiently solved. The proposed method is a primal-dual Newton Conjugate Gradients (pdNCG) method. Convergence properties of pdNCG are studied … Read more

    Some preconditioners for systems of linear inequalities

  • Javier F. Peña
  • Vera Roshchina
  • Negar Soheili
    • Categories Convex Optimization, Linear Programming

    We show that a combination of two simple preprocessing steps would generally improve the conditioning of a homogeneous system of linear inequalities. Our approach is based on a comparison among three different but related notions of conditioning for linear inequalities. Article Download View Some preconditioners for systems of linear inequalities