Nonlinear Optimization

Subspace accelerated matrix splitting algorithms for bound-constrained quadratic programming and linear complementarity problems

  • Liming Feng
  • Jorge Nocedal
  • Daniel P. Robinson
  • Jong-Shi Pang
    • Categories Bound-constrained Optimization, Finance and Economics Tags , , , , , , ,

    This paper studies the solution of two problems—bound-constrained quadratic programs and linear complementarity problems—by two-phase methods that consist of an active set prediction phase and a subspace phase. The algorithms enjoy favorable convergence properties under weaker assumptions than those assumed for other methods in the literature. The active set prediction phase employs matrix splitting iterations … Read more

    A short note on the global convergence of the unmodified PRP method

  • Weijun Zhou
    • Categories Unconstrained Optimization Tags , ,

    It is well-known that the search direction generated by the standard (unmodified) PRP nonlinear conjugate gradient method is not necessarily a descent direction of the objective function, which brings difficulty for its global convergence for general functions. However, to our surprise, it is easily proved in this short note that the unmodified PRP method still … Read more

    COIN-OR METSlib: a Metaheuristics Framework in Modern C++.

  • Mirko Maischberger
    • Categories Meta Heuristics, Nonlinear Optimization, Problem Solving Environments Tags , , , , ,

    The document describes COIN-OR METSlib, a C++ framework for local search based metaheuristics. METSlib has been used to implement a massively parallel VRP algorithm, a state of the art Vertex Coloring Problem solver, a Timetabling software, and in many other projects. ArticleDownload View PDF

    An LP-Newton Method: Nonsmooth Equations, KKT Systems, and Nonisolated Solutions

  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We define a new Newton-type method for the solution of constrained systems of equations and analyze in detail its properties. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, the method converges locally quadratically to a solution of the system of equations, thus filling an important gap in the existing theory. … Read more

    Unbounded Convex Sets for Non-Convex Mixed-Integer Quadratic Programming

  • Samuel Burer
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra, Quadratic Programming Tags , , ,

    This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a set in the family. Some fundamental properties of the convex sets are … Read more

    Decomposition methods based on projected gradient for network equilibrium problems

  • Andrea Cassioli
  • David Di Lorenzo
  • Marco Sciandrone
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Transportation Tags , , , ,

    In this work we consider the symmetric network equilibrium problem formulated as convex minimization problem whose variables are the path flows. In order to take into account the difficulties related to the large dimension of real network problems we adopt a column generation strategy and we employ a gradient projection method within an inexact decomposition … Read more

    An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Global Optimization Theory Tags , ,

    We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of nonlinear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme … Read more

    Trajectory-following methods for large-scale degenerate convex quadratic programming

  • Nicholas I. M. Gould
  • Dominique Orban
  • Daniel P. Robinson
    • Categories Optimization Software and Modeling Systems, Quadratic Programming Tags , ,

    We consider a class of infeasible, path-following methods for convex quadratric programming. Our methods are designed to be effective for solving both nondegerate and degenerate problems, where degeneracy is understood to mean the failure of strict complementarity at a solution. Global convergence and a polynomial bound on the number of iterations required is given. An … Read more

    Adjoint Sensitivity Analysis for Numerical Weather Prediction: Applications to Power Grid Optimization

  • Alexandru Cioaca
  • Emil M. Constantinescu
  • Victor M. Zavala
    • Categories Constrained Nonlinear Optimization, Control Applications, Stochastic Programming Tags ,

    We present an approach to estimate adjoint sensitivities of economic metrics of relevance in the power grid with respect to physical weather variables using numerical weather prediction models. We demonstrate that this capability can significantly enhance planning and operations. We illustrate the method using a large-scale computational study where we compute sensitivities of the regional … Read more

    Weak and Strong Convergence of Algorithms for the Split Common Null Point Problem

  • Charles Byrne
  • Yair Censor
  • Aviv Gibali
  • Simeon Reich
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Nonlinear Optimization

    We introduce and study the Split Common Null Point Problem (SCNPP) for set-valued maximal monotone mappings in Hilbert space. This problem generalizes our Split Variational Inequality Problem (SVIP) [Y. Censor, A. Gibali and S. Reich, Algorithms for the split variational inequality problem, Numerical Algorithms, accepted for publication, DOI 10.1007/s11075-011-9490-5]. The SCNPP with only two set-valued … Read more