Nonlinear Optimization

The Design and Implementation of a Generic Sparse Bundle Adjustment Software Package Based on the Levenberg-Marquardt Algorithm

  • Antonis Argyros
  • Manolis Lourakis
    • Categories Basic Sciences Applications, Nonlinear Systems and Least-Squares, Optimization Software and Modeling Systems Tags , , , , ,

    Bundle adjustment using the Levenberg-Marquardt minimization algorithm is almost invariably used as the last step of every feature-based structure and motion estimation computer vision algorithm to obtain optimal 3D structure and viewing parameter estimates. However, due to the large number of unknowns contributing to the minimized reprojection error, a general purpose implementation of the Levenberg-Marquardt … Read more

    Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Constrained Nonlinear Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more

    Best approximation to common fixed points of a semigroup of nonexpansive operators

  • Arkady Aleyner
  • Yair Censor
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization Tags , , , ,

    We study a sequential algorithm for finding the projection of a given point onto the common fixed points set of a semigroup of nonexpansive operators in Hilbert space. The convergence of such an algorithm was previously established only for finitely many nonexpansive operators. Algorithms of this kind have been applied to the best approximation and … Read more

    On the Convergence of Successive Linear-Quadratic Programming Algorithms

  • Richard H. Byrd
  • Nicholas I. M. Gould
  • Jorge Nocedal
  • Richard A. Waltz
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    The global convergence properties of a class of penalty methods for nonlinear programming are analyzed. These methods include successive linear programming approaches, and more specifically, the successive linear-quadratic programming approach presented by Byrd, Gould, Nocedal and Waltz (Math. Programming 100(1):27–48, 2004). Every iteration requires the solution of two trust-region subproblems involving piecewise linear and quadratic … Read more

    The Q Method for Second-order Cone Programming

  • Farid Alizadeh
  • Yu Xia
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    Based on the Q method for SDP, we develop the Q method for SOCP. A modified Q method is also introduced. Properties of the algorithms are discussed. Convergence proofs are given. Finally, we present numerical results. CitationAdvOl-Report#2004/15 McMaster University, Advanced Optimization LaboratoryArticleDownload View PDF

    A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

  • Renato D.C. Monteiro
  • Arkadi Nemirovski
  • Jerome W. O'Neal
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , , ,

    The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the … Read more

    A survey of the S-lemma

  • Imre Pólik
  • Tamás Terlaky
    • Categories Control Applications, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , , ,

    In this survey we review the many faces of the S-lemma, a result about the correctness of the S-procedure. The basic idea of this widely used method came from control theory but it has important consequences in quadratic and semidefinite optimization, convex geometry and linear algebra as well. These were active research areas, but as … Read more

    Newton-KKT Interior-Point Methods for Indefinite Quadratic Programming

  • Pierre-Antoine Absil
  • André L. Tits
    • Categories Constrained Nonlinear Optimization, Quadratic Programming Tags , , ,

    Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the `primal´ variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) … Read more

    A shifted Steihaug-Toint method for computing a trust-region step.

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

    Trust-region methods are very convenient in connection with the Newton method for unconstrained optimization. The More-Sorensen direct method and the Steihaug-Toint iterative method are most commonly used for solving trust-region subproblems. We propose a method which combines both of these approaches. Using the small-size Lanczos matrix, we apply the More-Sorensen method to a small-size trust-region … Read more

    Nonlinear-Programming Reformulation of the Order-Value Optimization problem

  • Roberto Andreani
  • José Mario Martínez
  • Cibele Dunder
    • Categories Nonlinear Optimization Tags , , , ,

    Order-value optimization (OVO) is a generalization of the minimax problem motivated by decision-making problems under uncertainty and by robust estimation. New optimality conditions for this nonsmooth optimization problem are derived. An equivalent mathematical programming problem with equilibrium constraints is deduced. The relation between OVO and this nonlinear-programming reformulation is studied. Particular attention is given to … Read more