Nonlinear Optimization

A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDPs

  • Samuel Burer
  • Renato D.C. Monteiro
  • Yin Zhang
    • Categories Combinatorial Optimization, Semi-definite Programming, Unconstrained Optimization Tags , , , ,

    The authors of this paper recently introduced a transformation \cite{BuMoZh99-1} that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based … Read more

    Automatic Differentiation Tools in Optimization Software

  • Jorge Moré
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , ,

    We discuss the role of automatic differentiation tools in optimization software. We emphasize issues that are important to large-scale optimization and that have proved useful in the installation of nonlinear solvers in the NEOS Server. Our discussion centers on the computation of the gradient and Hessian matrix for partially separable functions and shows that the … Read more

    Properties of the Log-Barrier Function on Degenerate Nonlinear Programs

  • Dominique Orban
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We examine the sequence of local minimizers of the log-barrier function for a nonlinear program near a solution at which second-order sufficient conditions and the Mangasarian-Fromovitz constraint qualifications are satisfied, but the active constraint gradients are not necessarily linearly independent. When a strict complementarity condition is satisfied, we show uniqueness of the local minimizer of … Read more

    New Results on Quadratic Minimization

  • Yinyu Ye
  • Shuzhong Zhang
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    In this paper we present several new results on minimizing an indefinite quadratic function under quadratic/linear constraints. The emphasis is placed on the case where the constraints are two quadratic inequalities. This formulation is known as {\em the extended trust region subproblem}\/ and the computational complexity of this problem is still unknown. We consider several … Read more

    Examples of ill-behaved central paths in convex optimization

  • Jean Charles Gilbert
  • Clóvis Caesar Gonzaga
  • Elizabeth Wegner Karas
    • Categories Convex Optimization, Nonlinear Optimization

    This paper presents some examples of ill-behaved central paths in convex optimization. Some contain infinitely many fixed length central segments; others manifest oscillations with infinite variation. These central paths can be encountered even for infinitely differentiable data. Citation Rapport de recherche 4179, INRIA, France, 2001 Article Download View Examples of ill-behaved central paths in convex … Read more

    On the Convergence of Newton Iterations to Non-Stationary Points

  • Richard H. Byrd
  • Marcelo Marazzi
  • Jorge Nocedal
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

    We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, … Read more

    Extra-Updates Criterion for the Limited Memory BFGS Algorithm for Large Scale Nonlinear Optimization

  • Mehiddin Al-Baali
    • Categories Unconstrained Optimization Tags , ,

    This paper studies recent modifications of the limited memory BFGS (L-BFGS) method for solving large scale unconstrained optimization problems. Each modification technique attempts to improve the quality of the L-BFGS Hessian by employing (extra) updates in certain sense. Because at some iterations these updates might be redundant or worsen the quality of this Hessian, this … Read more

    Fast iterative solution of saddle point problems in optimal control based on wavelets

  • Angela Kunoth
    • Categories Systems governed by Differential Equations Optimization Tags , , , , , , , , , , ,

    In this paper, wavelet techniques are employed for the fast numerical solution of a control problem governed by an elliptic boundary value problem with boundary control. A quadratic cost functional involving natural norms of the state and the control is to be minimized. Firstly the constraint, the elliptic boundary value problem, is formulated in an … Read more

    A Pattern Search Filter Method for Nonlinear Programming without Derivatives

  • Charles Audet
  • John E. Dennis, Jr.
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    This paper presents and analyzes a pattern search method for general constrained optimization based on filter methods for step acceptance. Roughly, a filter method accepts a step that either improves the objective function value or the value of some function that measures the constraint violation. The new algorithm does not compute or approximate any derivatives, … Read more

    Pattern search algorithms for mixed variable programming

  • Charles Audet
  • John E. Dennis, Jr.
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization Tags , , , ,

    Many engineering optimization problems involve a special kind of discrete variable that {\em can} be represented by a number, but this representation has no significance. Such variables arise when a decision involves some situation like a choice from an unordered list of categories. This has two implications: The standard approach of solving problems with continuous … Read more