Abstract We introduce a new sequential algorithm for the Standard Quadratic Programming Problem (StQP), which exploits a formulation of StQP as a Linear Program with Linear Complementarity Constraints (LPLCC). The algorithm is finite and guarantees at least in theory a $$\delta $$ δ -approximate global minimum for an arbitrary small $$\delta $$ δ , which is a global minimum in practice. The sequential algorithm has two phases. In Phase 1, Stationary Points (SP) with strictly decreasing objective function values are computed. Phase 2 is designed for giving a certificate of global optimality for the last SP computed in Phase 1. Two different Nonlinear Programming Formulations for LPLCC are proposed for each one of these phases, which are solved by efficient enumerative algorithms. New procedures for computing a lower bound for StQP are also proposed, which are easy to implement and give tight bounds in general. Computational experiments with a number of test problems from known sources indicate that the two-phase sequential algorithm is, in general, efficient in practice. Furthermore, the algorithm seems to be an efficient way to study the copositivity of a matrix by exploiting an StQP with this matrix.

In this paper, we introduce the truncated primal-infeasible dual-feasible interior point algorithm for linear programming and describe an implementation of this algorithm for solving the minimum-cost network flow problem. In each iteration, the linear system that determines the search direction is computed inexactly, and the norm of the resulting residual vector is used in the stopping criteria of the iterative solver employed for the solution of the system. In the implementation, a preconditioned conjugate gradient method is used as the iterative solver. The details of the implementation are described and the code PDNET is tested on a large set of standard minimum-cost network flow test problems. Computational results indicate that the implementation is competitive with state-of-the-art network flow codes. © 2000 John Wiley & Sons, Inc.

We present a method for generating box-constrained nonlinear programming test problems. The technique allows the user to control some properties of the generated test problems that are know to influence the behavior of algorithms for their solution. A corresponding set of Fortran 77 routines is described in a companion algorithm (774).

We describe a set of Fortran routines for generatig box-constrained nonlinear programming test problems. The technique, as described by Facchinei et al. (this issue), allows the user to control relevant properties of the generated problems