local convergence

Floorplanning with I/O assignment via feasibility-seeking and superiorization methods

  • ShanYu
  • Yair Censor
  • Guojie Luo
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, VLSI layout Tags , , , , , ,

    The feasibility-seeking approach offers a systematic framework for managing and resolving intricate constraints in continuous problems, making it a promising avenue to explore in the context of floorplanning problems with increasingly heterogeneous constraints. The classic legality constraints can be expressed as the union of convex sets. However, conventional projection-based algorithms for feasibility-seeking do not guarantee … Read more

    Riemannian Interior Point Methods for Constrained Optimization on Manifolds

  • Zhijian Lai
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    We extend the classical primal-dual interior point method from the Euclidean setting to the Riemannian one. Our method, named the Riemannian interior point method (RIPM), is for solving Riemannian  constrained optimization problems. We establish its local superlinear and quadratic convergence  under the standard assumptions. Moreover, we show its global convergence when it is combined with … Read more

    A Constraint-Reduced Algorithm for Semidefinite Optimization Problems with Superlinear Convergence

  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , ,

    Constraint reduction is an essential method because the computational cost of the interior point methods can be effectively saved. Park and O’Leary proposed a constraint-reduced predictor-corrector algorithm for semidefinite programming with polynomial global convergence, but they did not show its superlinear convergence. We first develop a constraint-reduced algorithm for semidefinite programming having both polynomial global … Read more

    A Trust Region Algorithm with a Worst-Case Iteration Complexity of ${\cal O}(\epsilon^{-3/2})$ for Nonconvex Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Mohammadreza Samadi
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , , , ,

    We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any $\bar\epsilon \in (0,\infty)$, the algorithm requires at most $\mathcal{O}(\epsilon^{-3/2})$ iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any $\epsilon \in (0,\bar\epsilon]$. This improves upon the $\mathcal{O}(\epsilon^{-2})$ bound known to hold for … Read more

    On local convergence of the method of alternating projections

  • Dominikus Noll
  • Aude Rondepierre
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    The method of alternating projections is a classical tool to solve feasibility problems. Here we prove local convergence of alternating projections between subanalytic sets A,B under a mild regularity hypothesis on one of the sets. We show that the speed of convergence is O$(k^{-\rho})$ for some $\rho\in(0,\infty)$. CitationUniversité de Toulouse, Institut de Mathématiques, december 19, … Read more

    Algebraic rules for quadratic regularization of Newton’s method

  • Elizabeth Wegner Karas
  • Sandra Augusta Santos
  • Benar Fux Svaiter
    • Categories Unconstrained Optimization Tags , , , ,

    In this work we propose a class of quasi-Newton methods to minimize a twice differentiable function with Lipschitz continuous Hessian. These methods are based on the quadratic regularization of Newton’s method, with algebraic explicit rules for computing the regularizing parameter. The convergence properties of this class of methods are analysed. We show that if the … Read more

    Abstract Newtonian Frameworks and Their Applications

  • Alexey F. Izmailov
  • A. S. Kurennoy
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , , ,

    We unify and extend some Newtonian iterative frameworks developed earlier in the literature, which results in a collection of convenient tools for local convergence analysis of various algorithms under various sets of assumptions including strong metric regularity, semistability, or upper-Lipschizt stability, the latter allowing for nonisolated solutions. These abstract schemes are further applied for deriving … Read more

    Nonmonotone Filter Method for Nonlinear Optimization

  • Shen Chungen
  • Roger Fletcher
  • Sven Leyffer
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we … Read more

    A Derivative-Free Algorithm for the Least-square minimization

  • Andrew R. Conn
  • Katya Scheinberg
  • Hongchao Zhang
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , , , , ,

    We develop a framework for a class of derivative-free algorithms for the least-squares minimization problem. These algorithms are based on polynomial interpolation models and are designed to take advantages of the problem structure. Under suitable conditions, we establish the global convergence and local quadratic convergence properties of these algorithms. Promising numerical results indicate the algorithm … Read more

    Convergence analysis of Riemannian trust-region methods

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
  • C. G. Baker
    • Categories Nonlinear Optimization Tags , , , , , , ,

    A general scheme for trust-region methods on Riemannian manifolds is proposed and analyzed. Among the various approaches available to (approximately) solve the trust-region subproblems, particular attention is paid to the truncated conjugate-gradient technique. The method is illustrated on problems from numerical linear algebra. Citation19 June 2006ArticleDownload View PDF