degeneracy

An L1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints

  • Zoumana Coulibaly
  • Dominique Orban
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , , ,

    We propose an interior-point algorithm based on an elastic formulation of the L1-penalty merit function for mathematical programs with complementarity constraints. The method generalizes that of Gould, Orban and Toint (2003) and naturally converges to a strongly stationary point or delivers a certificate of degeneracy without recourse to second-order intermediate solutions. Remarkably, the method allows … Read more

    Exact regularization of convex programs

  • Michael P. Friedlander
  • Paul Tseng
    • Categories Convex Optimization Tags , , , , , , , ,

    The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more

    Exact regularization of linear programs

  • Michael P. Friedlander
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    We show that linear programs (LPs) admit regularizations that either contract the original (primal) solution set or leave it unchanged. Any regularization function that is convex and has compact level sets is allowed–differentiability is not required. This is an extension of the result first described by Mangasarian and Meyer (SIAM J. Control Optim., 17(6), pp. … Read more

    An interior Newton-like method for nonnegative least-squares problems with degenerate solution

  • Stefania Bellavia
  • Benedetta Morini
  • Maria Macconi
    • Categories Nonlinear Optimization Tags , , , ,

    An interior point approach for medium and large nonnegative linear least-squares problems is proposed. Global and locally quadratic convergence is shown even if a degenerate solution is approached. Viable approaches for implementation are discussed and numerical results are provided. Citation Technical Report 1/2005, Dipartimento di Energetica ‘S. Stecco’, Universita di Firenze, Italia Article Download View … Read more

    Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

  • Zsolt Csizmadia
  • Tibor Illés
  • Bilen Filiz
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We define a variant of Anstreicher and Terlaky’s (1994) monotonic build-up (MBU) simplex algorithm for linear feasibility problems. Under a nondegeneracy assumption weaker than the normal one, the complexity of the algorithm can be given by $m\Delta$, where $\Delta$ is a constant determined by the input data of the problem and $m$ is the number … Read more

    Active Set Identification in Nonlinear Programming

  • Christina Oberlin
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , ,

    Techniques that identify the active constraints at a solution of a nonlinear programming problem from a point near the solution can be a useful adjunct to nonlinear programming algorithms. They have the potential to improve the local convergence behavior of these algorithms, and in the best case can reduce an inequality constrained problem to an … Read more

    An Algorithm for Degenerate Nonlinear Programming with Rapid Local Convergence

  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , ,

    The paper describes and analyzes an algorithmic framework for solving nonlinear programming problems in which strict complementarity conditions and constraint qualifications are not necessarily satisfied at a solution. The framework is constructed from three main algorithmic ingredients. The first is any conventional method for nonlinear programming that produces estimates of the Lagrange multipliers at each … Read more

    Constraint Identification and Algorithm Stabilization for Degenerate Nonlinear Programs

  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In the vicinity of a solution of a nonlinear programming problem at which both strict complementarity and linear independence of the active constraints may fail to hold, we describe a technique for distinguishing weakly active from strongly active constraints. We show that this information can be used to modify the sequential quadratic programming algorithm so … Read more