Andreas Fischer

On achieving strong necessary second-order properties in nonlinear programming

  • Gabriel Haeser
  • Andreas Fischer
  • Thiago P. Silveira
    • Categories Nonlinear Optimization

    Second-order necessary or sufficient optimality conditions for nonlinear programming are usually defined by means of the positive (semi-)definiteness of a quadratic form, or a maximum of quadratic forms, over the critical cone. However, algorithms for finding such second-order stationary points are currently unknown. Typically, an algorithm with a second-order property approximates a primal-dual point such … Read more

    Behavior of Newton-type methods near critical solutions of nonlinear equations with semismooth derivatives

  • Andreas Fischer
  • Alexey F. Izmailov
  • Mario Jelitte
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    Having in mind singular solutions of smooth reformulations of complementarity problems, arising unavoidably when the solution in question violates strict complementarity, we study the behavior of Newton-type methods near singular solutions of nonlinear equations, assuming that the operator of the equation possesses a strongly semismooth derivative, but is not necessarily twice differentiable. These smoothness restrictions … Read more

    Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

  • Muhammad Abid Dar
  • Andreas Fischer
  • John Martinovic
  • Guntram Scheithauer
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags , , , ,

    The minimum connectivity inference (MCI) problem represents an NP-hard generalization of the well-known minimum spanning tree problem. Given a set of vertices and a finite collection of subsets (of this vertex set), the MCI problem requires to find an edge set of minimal cardinality so that the vertices of each subset are connected. Although the … Read more

    An Improved Flow-based Formulation and Reduction Principles for the Minimum Connectivity Inference Problem

  • Muhammad Abid Dar
  • Andreas Fischer
  • John Martinovic
  • Guntram Scheithauer
    • Categories Applications - Science and Engineering, Combinatorial Optimization, Integer Programming Tags , , ,

    The Minimum Connectivity Inference (MCI) problem represents an NP-hard generalisation of the well-known minimum spanning tree problem and has been studied in different fields of research independently. Let an undirected complete graph and finitely many subsets (clusters) of its vertex set be given. Then, the MCI problem is to find a minimal subset of edges … Read more

    A Special Complementarity Function Revisited

  • Roger Behling
  • Andreas Fischer
  • Klaus Schönefeld
  • Nico Strasdat
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , ,

    Recently, a local framework of Newton-type methods for constrained systems of equations has been developed which, applied to the solution of Karush-KuhnTucker (KKT) systems, enables local quadratic convergence under conditions that allow nonisolated and degenerate KKT points. This result is based on a reformulation of the KKT conditions as a constrained piecewise smooth system of … Read more

    Local attractors of newton-type methods for constrained equations and complementarity problems with nonisolated solutions

  • Andreas Fischer
  • Alexey F. Izmailov
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Systems and Least-Squares

    For constrained equations with nonisolated solutions, we show that if the equation mapping is 2-regular at a given solution with respect to a direction in the null space of the Jacobian, and this direction is interior feasible, then there is an associated domain of starting points from which a family of Newton-type methods is well-de ned … Read more

    Convergence Conditions for Newton-type Methods Applied to Complementarity Systems with Nonisolated Solutions

  • Andreas Fischer
  • Alexey F. Izmailov
  • Markus Herrich
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , , , ,

    We consider a class of Newton-type methods for constrained systems of equations that involve complementarity conditions. In particular, at issue are the constrained Levenberg–Marquardt method and the recently introduced Linear Programming-Newton method, designed for the difficult case when solutions need not be isolated, and the equation mapping need not be differentiable at the solutions. We … Read more

    A New Error Bound Result for Generalized Nash Equilibrium Problems and its Algorithmic Application

  • Axel Dreves
  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Game Theory, Nonlinear Optimization Tags , , , , ,

    We present a new algorithm for the solution of Generalized Nash Equilibrium Problems. This hybrid method combines the robustness of a potential reduction algorithm and the local quadratic convergence rate of the LP-Newton method. We base our local convergence theory on an error bound and provide a new sufficient condition for it to hold that … Read more

    A Family of Newton Methods for Nonsmooth Constrained Systems with Nonisolated Solutions

  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We propose a new family of Newton-type methods for the solution of constrained systems of equations. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, local, quadratic convergence to a solution of the system of equations can be established. We show that as particular instances of the method we obtain inexact … Read more

    An LP-Newton Method: Nonsmooth Equations, KKT Systems, and Nonisolated Solutions

  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We define a new Newton-type method for the solution of constrained systems of equations and analyze in detail its properties. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, the method converges locally quadratically to a solution of the system of equations, thus filling an important gap in the existing theory. … Read more