large-scale optimization

New interior-point approach for one- and two-class linear support vector machines using multiple variable splitting

  • Jordi Castro
    • Categories Data-Mining, Linear, Cone and Semidefinite Programming Tags , , , ,

    Multiple variable splitting is a general technique for decomposing problems by using copies of variables and additional linking constraints that equate their values. The resulting large optimization problem can be solved with a specialized interior-point method that exploits the problem structure and computes the Newton direction with a combination of direct and iterative solvers (i.e., … Read more

    An extended delayed weighted gradient algorithm for solving strongly convex optimization problems

  • Roberto Andreani
  • Harry Oviedo
  • Marcos Raydan
  • Leonardo D. Secchin
    • Categories Unconstrained Optimization Tags , , ,

    The recently developed delayed weighted gradient method (DWGM) is competitive with the well-known conjugate gradient (CG) method for the minimization of strictly convex quadratic functions. As well as the CG method, DWGM has some key optimality and orthogonality properties that justify its practical performance. The main difference with the CG method is that, instead of … Read more

    Minimization over the l1-ball using an active-set non-monotone projected gradient

  • Andrea Cristofari
  • Marianna De Santis
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    The l1-ball is a nicely structured feasible set that is widely used in many fields (e.g., machine learning, statistics and signal analysis) to enforce some sparsity in the model solutions. In this paper, we devise an active-set strategy for efficiently dealing with minimization problems over the l1-ball and embed it into a tailored algorithmic scheme … Read more

    An augmented Lagrangian method exploiting an active-set strategy and second-order information

  • Andrea Cristofari
  • Gianni Di Pillo
  • Giampaolo Liuzzi
  • Stefano Lucidi
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper, we consider nonlinear optimization problems with nonlinear equality constraints and bound constraints on the variables. For the solution of such problems, many augmented Lagrangian methods have been defined in the literature. Here, we propose to modify one of these algorithms, namely ALGENCAN by Andreani et al., in such a way to incorporate … Read more

    Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming

  • David Applegate
  • Mateo Díaz
  • Haihao Lu
  • Miles Lubin
    • Categories Convex Optimization, Linear Programming Tags , , ,

    We study the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient method (PDHG) of Chambolle and Pock (2011). The literature on PDHG has mostly focused on settings where the problem at hand is assumed to be feasible. When the problem is not feasible, the iterates of the algorithm do … Read more

    Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization

  • Coralia Cartis
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , ,

    We introduce a general framework for large-scale model-based derivative-free optimization based on iterative minimization within random subspaces. We present a probabilistic worst-case complexity analysis for our method, where in particular we prove high-probability bounds on the number of iterations before a given optimality is achieved. This framework is specialized to nonlinear least-squares problems, with a … Read more

    A Matrix-Free Trust-Region Newton Algorithm for Convex-Constrained Optimization

  • Drew P. Kouri
    • Categories Constrained Nonlinear Optimization, Infinite Dimensional Optimization, Nonlinear Optimization Tags , , , ,

    We describe a matrix-free trust-region algorithm for solving convex-constrained optimization problems that uses the spectral projected gradient method to compute trial steps. To project onto the intersection of the feasible set and the trust region, we reformulate and solve the dual projection problem as a one-dimensional root finding problem. We demonstrate our algorithm’s performance on … Read more

    Stochastic dual dynamic programming and its variants – a review

  • Christian Füllner
  • Steffen Rebennack
    • Categories Stochastic Programming Tags , , , , , , ,

    We provide a tutorial-type review on stochastic dual dynamic programming (SDDP), as one of the state-of-the-art solution methods for large-scale multistage stochastic programs. Since introduced about 30 years ago for solving large-scale multistage stochastic linear programming problems in energy planning, SDDP has been applied to practical problems from several fields and is enriched by various … Read more

    Secant acceleration of sequential residual methods for solving large-scale nonlinear systems of equations

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    Sequential Residual Methods try to solve nonlinear systems of equations $F(x)=0$ by iteratively updating the current approximate solution along a residual-related direction. Therefore, memory requirements are minimal and, consequently, these methods are attractive for solving large-scale nonlinear systems. However, the convergence of these algorithms may be slow in critical cases; therefore, acceleration procedures are welcome. … Read more

    A rolling-horizon approach for multi-period optimization

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel
    • Categories Airline Optimization, Applications - OR and Management Sciences, Production and Logistics Tags , , , ,

    Mathematical optimization problems including a time dimension abound. For example, logistics, process optimization and production planning tasks must often be optimized for a range of time periods. Usually, these problems incorporating time structure are very large and cannot be solved to global optimality by modern solvers within a reasonable period of time. Therefore, the so-called … Read more