Month: June 2006

An Accelerated Newton Method for Equations with Semismooth Jacobians and Nonlinear Complementarity Problems: Extended Version

  • Christina Oberlin
  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Nonlinear Systems and Least-Squares Tags , ,

    We discuss local convergence of Newton’s method to a singular solution $x^*$ of the nonlinear equations $F(x) = 0$, for $F:\R^n \rightarrow \R^n$. It is shown that an existing proof of Griewank, concerning linear convergence to a singular solution $x^*$ from a starlike domain around $x^*$ for $F$ twice Lipschitz continuously differentiable and $x^*$ satisfying … Read more

    On the divergence of line search methods

  • Walter F. Mascarenhas
    • Categories Unconstrained Optimization Tags

    We discuss the convergence of line search methods for minimization. We explain how Newton’s method and the BFGS method can fail even if the restrictions of the objective function to the search lines are strictly convex functions, the level sets of the objective functions are compact, the line searches are exact and the Wolfe conditions … Read more

    Identifying Redundant Linear Constraints in Systems of Linear Matrix Inequality Constraints

  • Shafiu Jibrin
  • Daniel Stover
    • Categories Semi-definite Programming Tags , , ,

    Semidefinite programming has been an interesting and active area of research for several years. In semidefinite programming one optimizes a convex (often linear) objective function subject to a system of linear matrix inequality constraints. Despite its numerous applications, algorithms for solving semidefinite programming problems are restricted to problems of moderate size because the computation time … Read more

    The extreme points of QSTAB(G) and its implications

  • Arie M.C.A. Koster
  • Annegret K. Wagler
    • Categories 0-1 Programming, Graphs and Matroids, Polyhedra Tags , ,

    Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs G where the stable set polytope STAB(G) coincides with the clique constraint stable set polytope QSTAB(G). For all imperfect graphs STAB(G) \subset QSTAB(G) holds and, therefore, it is … Read more

    A Proximal Cutting Plane Method Using Chebychev Center for Nonsmooth Convex Optimization

  • Adam Ouorou
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    An algorithm is developed for minimizing nonsmooth convex functions. This algorithm extends Elzinga-Moore cutting plane algorithm by enforcing the search of the next test point not too far from the previous ones, thus removing compactness assumption. Our method is to Elzinga-Moore’s algorithm what a proximal bundle method is to Kelley’s algorithm. Instead of lower approximations … Read more