Nonlinear Systems and Least-Squares

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

    Steered sequential projections for the inconsistent convex feasibility problem

  • Yair Censor
  • Álvaro Rodolfo De Pierro
  • Maroun Zaknoon
    • Categories Convex Optimization, Nonlinear Systems and Least-Squares Tags , ,

    We study a steered sequential gradient algorithm which minimizes the sum of convex functions by proceeding cyclically in the directions of the negative gradients of the functions and using steered step-sizes. This algorithm is applied to the convex feasibility problem by minimizing a proximity function which measures the sum of the Bregman distances to the … Read more

    A filter-trust-region method for unconstrained optimization

  • Nicholas I. M. Gould
  • Caroline Sainvitu
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags ,

    A new filter-trust-region algorithm for solving unconstrained nonlinear optimization problems is introduced. Based on the filter technique introduced by Fletcher and Leyffer, it extends an existing technique of Gould, Leyffer and Toint (SIAM J. Optim., to appear 2004) for nonlinear equations and nonlinear least-squares to the fully general unconstrained optimization problem. The new algorithm is … Read more

    Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    The reliability of polyhedral homotopy continuation methods for solving a polynomial system becomes increasingly important as the dimension of the polynomial system increases. High powers of the homotopy continuation parameter $t$ and ill-conditioned Jacobian matrices encountered in tracing of homotopy paths affect the numerical stability. We present modified homotopy functions with a new homotopy continuation … Read more

    PHoM – a Polyhedral Homotopy Continuation Method for Polynomial Systems

  • Katsuki Fujisawa
  • Sunyoung Kim
  • Masakazu Kojima
  • Tomohiko Mizutani
  • Takayuki Gunji
  • Akiko Takeda
    • Categories Nonlinear Systems and Least-Squares Tags , , , ,

    PHoM is a software package in C++ for finding all isolated solutions of polynomial systems using a polyhedral homotopy continuation method. Among three modules constituting the package, the first module StartSystem constructs a family of polyhedral-linear homotopy functions, based on the polyhedral homotopy theory, from input data for a given system of polynomial equations $\f(\x) … Read more

    An (n-2)-dimensional Quadratic Surface Determining All Cliques and a Least Square Formulation for the Maximum Clique Problem

  • Stanislav Busygin
    • Categories Graphs and Matroids, Nonlinear Systems and Least-Squares, Polyhedra Tags , , ,

    Arranging an n-vertex graph as the standard simplex in R^n, we identify graph cliques with simplex faces formed by clique vertices. An unstrict quadratic inequality holds for all points of the simplex; it turns to equality if and only if the point is on a face corresponding to a clique. This way this equality determines … Read more

    The least-intensity feasible solution for aperture-based inverse planning in radiation therapy.

  • Yair Censor
  • James M. Galvin
  • Darek Michalski
  • Ying Xiao
    • Categories Biomedical Applications, Convex Optimization, Nonlinear Systems and Least-Squares Tags , , , , ,

    Aperture-based inverse planning (ABIP) for intensity modulated radiation therapy (IMRT) treatment planning starts with external radiation fields (beams) that fully conform to the target(s) and then superimposes sub-fields called segments to achieve complex shaping of 3D dose distributions. The segments’ intensities are determined by solving a feasibility problem. The least-intensity feasible (LIF) solution, proposed and … Read more

    Simple Efficient Solutions for Semidefinite Programming

  • Henry Wolkowicz
    • Categories Combinatorial Optimization, Nonlinear Systems and Least-Squares, Semi-definite Programming Tags , , , , ,

    This paper provides a simple approach for solving a semidefinite program, SDP\@. As is common with many other approaches, we apply a primal-dual method that uses the perturbed optimality equations for SDP, $F_\mu(X,y,Z)=0$, where $X,Z$ are $n \times n$ symmetric matrices and $y \in \Re^n$. However, we look at this as an overdetermined system of … Read more

    Componentwise fast convergence in the solution of full-rank systems of nonlinear equations

  • Nicholas I. M. Gould
  • Dominique Orban
  • Annick Sartenaer
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , ,

    The asymptotic convergence of parameterized variants of Newton’s method for the solution of nonlinear systems of equations is considered. The original system is perturbed by a term involving the variables and a scalar parameter which is driven to zero as the iteration proceeds. The exact local solutions to the perturbed systems then form a differentiable … 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