Extension of Quasi-Newton Methods to Mathematical Programs with Complementarity Constraints

  • Houyuan Jiang
  • Daniel Ralph
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , , ,

    Quasi-Newton methods in conjunction with the piecewise sequential quadratic programming are investigated for solving mathematical programming with equilibrium constraints, in particular for problems with complementarity constraints. Local convergence as well as superlinear convergence of these quasi-Newton methods can be established under suitable assumptions. In particular, several well-known quasi-Newton methods such as BFGS and DFP are … Read more

    Convergence of a Penalty Method for Mathematical Programmingwith ComplementarityConstraints

  • Xinmin Hu
  • Daniel Ralph
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , ,

    We adapt the convergence analysis of smoothing (Fukushima and Pang) and regularization (Scholtes) methods to a penalty framework for mathematical programs with complementarity constraints (MPCCs), and show that the penalty framework shares similar convergence properties to these methods. Moreover, we give sufficient conditions for a sequence generated by the penalty framework to be attracted to … 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

    A new path-following algorithm for nonlinear P_* complementarity problems

  • Duan Li
  • Yun-Bin Zhao
    • Categories Complementarity and Variational Inequalities

    Inspired by the recent theoretical results of Zhao and Li [{\em Math. Oper. Res.,} 26 (2001), pp. 119-146], we present in this paper a new path-following method for nonlinear P$_*$ complementarity problems. Different from most existing interior-point algorithms that are based on the central path, this algorithm is to track the newly defined “regularized central … Read more

    A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions

  • Sven de Vries
  • Oktay Gunluk
  • Lazslo Ladanyi
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , , ,

    When combinatorial bidding is permitted in Spectrum Auctions, such as the upcoming FCC auction #31, the resulting winner-determination problem can be computationally challenging. We present a branch-and-price algorithm based on a set-packing formulation originally proposed by Dietrich and Forrest (2002). This formulation has a variable for every possible combination of winning bids for each bidder. … Read more

    Global and Convex Optimization in Modeling Environments: Compiler-Based, Excel, and Mathematica Implementations

  • János Pintér
    • Categories Applications - Science and Engineering, Global Optimization, Optimization Software and Modeling Systems

    We present a review of several software products that serve to analyze and solve nonlinear (specifically including global) optimization problems across different hardware and software platforms. The implementations discussed are LGO, as a stand-alone, but compiler-dependent modeling and solver environment; its Excel platform implementation; and MathOptimizer, a native solver package for Mathematica users. The discussion … Read more

    Numerical experience with solving MPECs as NLPs

  • Roger Fletcher
  • Sven Leyffer
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Optimization Software Benchmark Tags , , , ,

    This paper describes numerical experience with solving MPECs as NLPs on a large collection of test problems. The key idea is to use off-the-shelf NLP solvers to tackle large instances of MPECs. It is shown that SQP methods are very well suited to solving MPECs and at present outperform Interior Point solvers both in terms … Read more

    A Feasible Trust-Region Sequential Quadratic Programming Algorithm

  • M. J. Tenny
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , ,

    An algorithm for smooth nonlinear constrained optimization problems is described, in which a sequence of feasible iterates is generated by solving a trust-region sequential quadratic programming (SQP) subproblem at each iteration, and perturbing the resulting step to retain feasibility of each iterate. By retaining feasibility, the algorithm avoids several complications of other trust-region SQP approaches: … Read more

    Nonlinear Model Predictive Control via Feasibility-Perturbed Sequential Quadratic Programming

  • J B Rawlings
  • M. J. Tenny
  • Stephen Wright
    • Categories Chemical Engineering, Constrained Nonlinear Optimization, Control Applications Tags , ,

    Model predictive control requires the solution of a sequence of continuous optimization problems that are nonlinear if a nonlinear model is used for the plant. We describe briefly a trust-region feasibility-perturbed sequential quadratic programming algorithm (developed in a companion report), then discuss its adaptation to the problems arising in nonlinear model predictive control. Computational experience … Read more

    A Simplified/Improved HKM Direction for Certain Classes of Semidefinite Programming

  • Franz Rendl
  • Renata Sotirov
  • Henry Wolkowicz
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the … Read more