The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs(SemiDefinite Programs). It is written in C++ with the help of {\it LAPACK} for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance … Read more
The affine-scaling algorithm was initially developed for linear programming problems. Its extension to problems with a nonlinear objective performs at each iteration a scaling followed by a line search along the steepest descent direction. In this paper we prove that any accumulation point generated by this algorithm when applied to a convex function is an … Read more
The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in trust region algorithms for function minimization. Trust region algorithms are popular for … Read more
We are interested in the solution of Horizontal Linear Complementarity Problems, HLCPs, that is complementarity problems with more variables than equations. Globally metrically regular HLCPs have nonempty solution sets that are stable with respect to “right-hand-side perturbations” of the data, hence are numerically attractive. The main purpose of the paper is to show how the … Read more
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
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
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
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
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
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