A quadratic programming algorithm using conjugate search directions

A quadratic programming algorithm is presented, resembling Beale's 1955 quadratic programming algorithm and Wolfe's Reduced Gradient method. It uses conjugate search directions. The algorithm is conceived as being particularly appropriate for problems with a large Hessian matrix. An experimental computer program has been written to validate the concepts, and has performed adequately, although it has not been used on very large problems. An outline of the solution to the quadratic capacity-constrained transportation problem using the above method is also presented.While engaged in this research the author had a part-time post with the Manpower Services Commission.     

A unified approach to one-parametric general quadratic programming

A method is proposed for finding local minima to the parametric general quadratic programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The local minimum vector and the local minimum value are determined explicitly as rational functions of the parameter. A numerical example is given.     

Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.The author wishes to thank two anonymous referees for their helpful comments and suggestions for revising the paper.     

A class of methods for linear programming

A class of methods is presented for solving standard linear programming problems. Like the simplex method, these methods move from one feasible solution to another at each iteration, improving the objective function as they go. Each such feasible solution is also associated with a basis. However, this feasible solution need not be an extreme point and the basic solution corresponding to the associated basis need not be feasible. Nevertheless, an optimal solution, if one exists, is found in a finite number of iterations (under nondegeneracy). An important example of a method in the class is the reduced gradient method with a slight modification regarding selection of the entering variable.     

Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem

We investigate new bounding strategies based on different relaxations of the quadratic assignment problem. In particular, we improve the lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part. The improvement is accomplished by applying a steepest ascent algorithm to the sum of the two bounds.Both authors would like to thank the Natural Sciences and Engineering Research Council Canada and the Austrian Government for their support.This author would like to acknowledge partial support from the Department of Combinatorics and Optimization at the University of Waterloo.Research partially supported by Natural Sciences and Engineering Research Council Canada.     

Remarks on a difficult test problem for quadratic boolean programming

We show that a “difficult” example is only difficult for special kinds of algorithms     

Equivalence of some quadratic programming algorithms

We formulate a general algorithm for the solution of a convex (but not strictly convex) quadratic programming problem. Conditions are given under which the iterates of the algorithm are uniquely determined. The quadratic programming algorithms of Fletcher, Gill and Murray, Best and Ritter, and van de Panne and Whinston/Dantzig are shown to be special cases and consequently are equivalent in the sense that they construct identical sequences of points. The various methods are shown to differ only in the manner in which they solve the linear equations expressing the Kuhn-Tucker system for the associated equality constrained subproblems. Equivalence results have been established by Goldfarb and Djang for the positive definite Hessian case. Our analysis extends these results to the positive semi-definite case. This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189.     

A decomposition algorithm for quadratic programming

A decomposition algorithm using Lemke's method is proposed for the solution of quadratic programming problems having possibly unbounded feasible regions. The feasible region for each master program is a generalized simplex of minimal size. This property is maintained by a dropping procedure which does not affect the finiteness of the convergence. The details of the matrix transformations associated with an efficient implementation of the algorithm are given. Encouraging preliminary computational experience is presented.     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

On solving convex quadratic semi-infinite programming probelms

In this paper we study a from of convex quadratic semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. An entropic path-following algorithum is introduced with a convergence proof. Some practical implementations and numerical experiments are also included     

Evaluating computational efficiency: A stochastic approach

This paper introduces the use of stochastic models for the evaluation of relative computational efficiency of algorithms. Such an approach is used for the comparison of computational efficiency of three algorithms for quadratic programming.     

Numerically stable methods for quadratic programming

Numerically stable algorithms for quadratic programming are discussed. A new algorithm is described for indefinite quadratic programming which utilizes methods for updating positivedefinite factorizations only. Consequently all the updating procedures required are common to algorithms for linearly-constrained optimization. The new algorithm can be used for the positive-definite case without loss of efficiency.     

Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

Quadratic geometric programming with application to machining economics

Geometric Programming is extended to include convex quadratic functions. Generalized Geometric Programming is applied to this class of programs to obtain a convex dual program. Machining economics problems fall into this class. Such problems are studied by applying this duality to a nested set of three problems. One problem is zero degree of difficulty and the solution is obtained by solving a simple system of equations. The inclusion of a constraint restricting the force on the tool to be less than or equal to the breaking force provides a more realistic solution. This model is solved as a program with one degree of difficulty. Finally the behavior of the machining cost per part is studied parametrically as a function of axial depth. This research was supported by the Air Force Office of Scientific Research Grant AFOSR-83-0234     

A practicable way for computing the directional derivative of the optimal value function in convex programming

Formulas for computing the directional derivative of the optimal value function or of lower or upper bounds of it are well-known from literature. Because they have as a rule a minmax structure, methods from nondifferentiable optimization are required.

Considering a fully parametrized convex problem, in the paper the mentioned minmax formulas are transformed into usual programming problems. Although they are nonconvex in general, the computational effort is much lower than that for minmax problems. In several special cases, for instance, for linear least squares problems, linear programming problems arise.     

Global minimization of large-scale constrained concave quadratic problems by separable programming

The global minimization of a large-scale linearly constrained concave quadratic problem is considered. The concave quadratic part of the objective function is given in terms of the nonlinear variablesx R ⁿ , while the linear part is in terms ofy R ^k. For large-scale problems we may havek much larger thann. The original problem is reduced to an equivalent separable problem by solving a multiple-cost-row linear program with 2n cost rows. The solution of one additional linear program gives an incumbent vertex which is a candidate for the global minimum, and also gives a bound on the relative error in the function value of this incumbent. Ana priori bound on this relative error is obtained, which is shown to be 0.25, in important cases. If the incumbent is not a satisfactory approximation to the global minimum, a guaranteed-approximate solution is obtained by solving a single liner zero–one mixed integer programming problem. This integer problem is formulated by a simple piecewise-linear underestimation of the separable problem.This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.Dedicated to Professor George Dantzig in honor of his 70th Birthday.     

Optimal electric power scheduling: A large nonlinear programming test problem solved by recursive quadratic programming

This paper discusses a nonlinear programming problem which arises when the optimum scheduling of an electric power system is being considered. A realistic, moderately large text example is described in detail; and the solution of this example by a recent method based on quadratic programming is also reported.     

Least-index resolution of degeneracy in quadratic programming

In this study, we combine least-index pivot selection rules with Keller's algorithm for quadratic programming to obtain a finite method for processing degenerate problems.Research and reproduction of this report were partially supported by National Science Foundation Grant MCS76-81259; and the Office of Naval Research Contract N00014-75-C-0267.     

A parameterized hessian quadratic programming problem

We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432.