Nonlinear Optimization

Quadratic regularizations in an interior-point method for primal block-angular problems

  • Jordi Castro
  • Jordi Cuesta
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming

    One of the most efficient interior-point methods for some classes of primal block-angular problems solves the normal equations by a combination of Cholesky factorizations and preconditioned conjugate gradient for, respectively, the block and linking constraints. Its efficiency depends on the spectral radius—in [0,1)—of a certain matrix in the definition of the preconditioner. Spectral radius close … Read more

    Descent heuristics for unconstrained minimization

  • Florian Jarre
  • Ania Lopez
    • Categories Global Optimization, Unconstrained Optimization Tags , ,

    Semidefinite relaxations often provide excellent starting points for nonconvex problems with multiple local minimizers. This work aims to find a local minimizer within a certain neighborhood of the starting point and with a small objective value. Several approaches are motivated and compared with each other. CitationReport, Mathematisches Institut, Universitaet Duesseldorf, August 2008.ArticleDownload View PDF

    Optimal steepest descent algorithms for unconstrained convex problems: fine tuning Nesterov’s method

  • Clóvis Caesar Gonzaga
  • Elizabeth Wegner Karas
    • Categories Convex Optimization, Unconstrained Optimization Tags ,

    We modify the first order algorithm for convex programming proposed by Nesterov. The resulting algorithm keeps the optimal complexity obtained by Nesterov with no need of a known Lipschitz constant for the gradient, and performs better in practically all examples in a set of test problems. CitationTechnical Report, Federal University of Santa Catarina, 2008.ArticleDownload View … Read more

    Group sparsity via linear-time projection

  • Michael P. Friedlander
  • Kevin Murphy
  • Mark Schmidt
  • Ewout van den Berg
    • Categories Constrained Nonlinear Optimization

    We present an efficient spectral projected-gradient algorithm for optimization subject to a group one-norm constraint. Our approach is based on a novel linear-time algorithm for Euclidean projection onto the one- and group one-norm constraints. Numerical experiments on large data sets suggest that the proposed method is substantially more efficient and scalable than existing methods. CitationTechnical … Read more

    Iteration-complexity of first-order penalty methods

  • Guanghui Lan
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    This paper considers a special but broad class of convex programing (CP) problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. We study two first-order penalty methods for solving the above class of problems, namely: the quadratic penalty method and … Read more

    Nonlinear optimization for matroid intersection and extensions

  • Yael Berstein
  • Jon Lee
  • Shmuel Onn
  • Robert Weismantel
    • Categories Combinatorial Optimization, Nonlinear Optimization Tags , ,

    We address optimization of nonlinear functions of the form $f(Wx)$~, where $f:\R^d\rightarrow \R$ is a nonlinear function, $W$ is a $d\times n$ matrix, and feasible $x$ are in some large finite set $\calF$ of integer points in $\R^n$~. Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes … Read more

    On fast integration to steady state and earlier times

  • Uri Ascher
  • Hui Huang
  • Benar Fux Svaiter
  • Kees van den Doel
    • Categories Basic Sciences Applications, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , , , ,

    The integration to steady state of many initial value ODEs and PDEs using the forward Euler method can alternatively be considered as gradient descent for an associated minimization problem. Greedy algorithms such as steepest descent for determining the step size are as slow to reach steady state as is forward Euler integration with the best … Read more

    A stochastic algorithm for function minimization

  • Su Dongcai
  • Dong Junwei
  • Zheng Zuduo
    • Categories Constrained Nonlinear Optimization, Stochastic Approaches, Unconstrained Optimization Tags , ,

    Focusing on what an optimization problem may comply with, the so-called convergence conditions have been proposed and sequentially a stochastic optimization algorithm named as DSZ algorithm is presented in order to deal with both unconstrained and constrained optimizations. Its principle is discussed in the theoretical model of DSZ algorithm, from which we present a practical … Read more

    Numerical Experience with a Recursive Trust-Region Method for Multilevel Nonlinear Optimization

  • Serge Gratton
  • Annick Sartenaer
  • Philippe L. Toint
  • Mélodie Mouffe
  • Dimitri Tomanos
    • Categories Bound-constrained Optimization, Distributed Control, Optimization of Systems modeled by PDEs Tags , , , , ,

    We consider an implementation of the recursive multilevel trust-region algorithm proposed by Gratton, Mouffe, Toint, Weber (2008) for bound-constrained nonlinear problems, and provide numerical experience on multilevel test problems. A suitable choice of the algorithm’s parameters is identified on these problems, yielding a satisfactory compromise between reliability and efficiency. The resulting default algorithm is then … Read more