large-scale optimization

A Matrix-free Algorithm for Equality Constrained Optimization Problems with Rank-deficient Jacobians

  • Frank E. Curtis
  • Jorge Nocedal
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization, Infinite Dimensional Optimization Tags , , , , ,

    We present a line search algorithm for large-scale constrained optimization that is robust and efficient even for problems with (nearly) rank-deficient Jacobian matrices. The method is matrix-free (i.e., it does not require explicit storage or factorizations of derivative matrices), allows for inexact step computations, and is applicable for nonconvex problems. The main components of the … Read more

    On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods

  • Marco D'Apuzzo
  • Valentina De Simone
  • Daniela di Serafino
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    The solution of KKT systems is ubiquitous in optimization methods and often dominates the computation time, especially when large-scale problems are considered. Thus, the effective implementation of such methods is highly dependent on the availability of effective linear algebra algorithms and software, that are able, in turn, to take into account specific needs of optimization. … Read more

    Primal interior point method for minimization of generalized minimax functions

  • Ladislav Lukšan
  • Ctirad Matonoha
  • Jan Vlček
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , , , ,

    In this report, we propose a primal interior-point method for large sparse generalized minimax optimization. After a short introduction, where the problem is stated, we introduce the basic equations of the Newton method applied to the KKT conditions and propose a primal interior-point method. Next we describe the basic algorithm and give more details concerning … Read more

    An Inexact Newton Method for Nonconvex Equality Constrained Optimization

  • Richard H. Byrd
  • Frank E. Curtis
  • Jorge Nocedal
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351–369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the … Read more

    Exploiting separability in large-scale linear support vector machine training

  • Jacek Gondzio
  • Kristian Woodsend
    • Categories Data-Mining, Quadratic Programming Tags , , ,

    Linear support vector machine training can be represented as a large quadratic program. We present an efficient and numerically stable algorithm for this problem using interior point methods, which requires only O(n) operations per iteration. Through exploiting the separability of the Hessian, we provide a unified approach, from an optimization perspective, to 1-norm classification, 2-norm … Read more

    A 2-BFGS updating in a trust region framework

  • Marianna S. Apostolopoulou
  • Panagiotis Pintelas
  • Dimitris G. Sotiropoulos
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    We present a new matrix-free method for the trust region subproblem, assuming that the approximate Hessian is updated by the limited memory BFGS formula with m = 2. The resulting updating scheme, called 2-BFGS, give us the ability to determine via simple formulas the eigenvalues of the resulting approximation. Thus, at each iteration, we can … Read more

    ASTRAL: An Active Set \inftyhBcTrust-Region Algorithm for Box Constrained Optimization

  • James V. Burke
  • Liang Xu
    • Categories Bound-constrained Optimization Tags , , ,

    An algorithm for solving large-scale nonlinear optimization problems with simple bounds is described. The algorithm is an $\ell_\infty$-norm trust-region method that uses both active set identification techniques as well as limited memory BFGS updating for the Hessian approximation. The trust-region subproblems are solved using primal-dual interior point techniques that exploit the structure of the limited … Read more

    New subroutines for large-scale optimization

  • Ladislav Lukšan
  • Ctirad Matonoha
  • Jan Vlček
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems Tags ,

    We present fourteen basic FORTRAN subroutines for large-scale unconstrained and box constrained optimization and large-scale systems of nonlinear equations. Subroutines {\tt PLIS} and {\tt PLIP}, intended for dense general optimization problems, are based on limited-memory variable metric methods. Subroutine {\tt PNET}, also intended for dense general optimization problems, is based on an inexact truncated Newton … Read more

    New class of limited-memory variationally-derived variable metric methods

  • Ladislav Lukšan
  • Jan Vlček
    • Categories Nonlinear Optimization Tags , ,

    A new family of limited-memory variationally-derived variable metric or quasi-Newton methods for unconstrained minimization is given. The methods have quadratic termination property and use updates, invariant under linear transformations. Some encouraging numerical experience is reported. Citation Technical Report V-973. Prague, ICS AS CR 2006. Article Download View New class of limited-memory variationally-derived variable metric methods

    A New Unblocking Technique to Warmstart Interior Point Methods based on Sensitivity Analysis

  • Jacek Gondzio
  • Andreas Grothey
    • Categories Quadratic Programming Tags , , ,

    One of the main drawbacks associated with Interior Point Methods (IPM) is the perceived lack of an efficient warmstarting scheme which would enable the use of information from a previous solution of a similar problem. Recently there has been renewed interest in the subject. A common problem with warmstarting for IPM is that an advanced … Read more