On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.     

A differential equation approach to nonlinear programming

A new method is presented for finding a local optimum of the equality constrained nonlinear programming problem. A nonlinear autonomous system is introduced as the base of the theory instead of usual approaches. The relation between critical points and local optima of the original optimization problem is proved. Asymptotic stability of the critical points is also proved. A numerical algorithm which is capable of finding local optima systematically at the quadratic rate of convergence is developed from a detailed analysis of the nature of trajectories and critical points. Some numerical results are given to show the efficiency of the method.     

Global minimum test problem construction

A method is presented for the construction of test problems for which the global minimum point is known.Given a bounded convex polyhedron inR ⁿ , and a selected vertex, a concave quadratic function is constructed which attains its global minimum at the selected vertex. In general, this function will also have many other local minima.This research was supported in part by NSF Grant MCS 81-01214.     

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.     

Penalty for zero–one integer equivalent problem

The equivalence of zero–one integer programming and a concave quadratic penalty function problem has been shown by Raghavachari, for a sufficiently large value of the penalty. A lower bound for this penalty is obtained here, which in specific cases cannot be reduced.This research was supported in part by the Computer Science Section of the National Science Foundation under Research Grant MCS 8101214.     

AN OUTER APPROXIMATION ALGORITHM FOR SEMI-INFINITE NONDIFFERENTIABLE PROGRAMMINGS

This paper presents a conceptual outer approximation algorithm for dealing with the semi-infinite nondifferentiable programming in which functions are locally Lipschitzian. By weakening the restriction on the family of functions for a parametric programming, we answer a question proposed in [1].     

Stationarity and superlinear convergence of an algorithm for univariate locally lipschitz constrained minimization

This paper introduces an algorithm for minimizing a single-variable locally Lipschitz function subject to a like function being nonpositive. The method combines polyhedral and quadratic approximation, a new type of penalty technique and a safeguard in such a way as to give convergence to a stationary point. The convergence is shown to be superlinear under somewhat stronger assumptions that allow both nonsmooth and nonconvex cases. The algorithm can be an effective subroutine for solving line search subproblems called for by multivariable optimization algorithms. Research sponsored, in part, by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-83-0210. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Progressive global random search of continuous functions

A sequential random search method for the global minimization of a continuous function is proposed. The algorithm gradually concentrates the random search effort on areas neighboring the global minima. A modification is included for the case that the function cannot be exactly evaluated. The global convergence and the asymptotical optimality of the sequential sampling procedure are proved for both the stochastic and deterministic optimization problem.The research is sponsored in part by the Air Force under Grant AFOSR-72-2371.     

Optimum matching forests I: Special weights

We introduce the concept of matching forests as a generalization of branchings in a directed graph and matchings in an undirected graph. Given special weights on the edges of a mixed graph, we present an efficient algorithm for finding an optimum weight-sum matching forest. The algorithm is a careful application of known branching and matching algorithms. The maximum cardinality matching forest problem is solved as a special case.Research partially supported by a N.R.C. of Canada Postdoctorate Fellowship.     

Linear programming via a quadratic penalty function

We use quadratic penalty functions along with some recent ideas from linearl ₁ estimation to arrive at a new characterization of primal optimal solutions in linear programs. The algorithmic implications of this analysis are studied, and a new, finite penalty algorithm for linear programming is designed. Preliminary computational results are presented.Research supported by grant No. 11-0505 from the Danish Natural Science Research Council SNF.