We investigate the use of interior point methods for solving quadratic programming problems with a small number of linear constraints where the quadratic term consists of a low-rank update to a positive semi-definite matrix. Several formulations of the support vector machine fit into this category. An interesting feature of these particular problems is the volume … Read more
The term Planning is not used in Operations Research in the sense that is most common in Artificial Intelligence. AI Planning does have many features in common with OR scheduling, sequencing, routing, and assignment problems, however. Current approaches to solving such problems can be broadly classified into four areas: Combinatorial Optimization, Integer Programming, Constraint Programming, … Read more
We consider minimizing a nonsmooth objective subject to nonsmooth constraints. The nonsmooth functions are approximated by a bundle of subgradients. The novel idea of a filter is used to promote global convergence. CitationNA\195, Department of Mathematics, University of Dundee, UK, December, 1999ArticleDownload View PDF
A mechanism for proving global convergence infilter-type methods for nonlinear programming is described. Such methods are characterized by their use of the dominance concept of multi objective optimization, instead of a penalty parameter whose adjustment can be problematic. The main point of interest is to demonstrate how convergence for NLP can be induced without forcing … Read more
In this paper we discuss duality theory of optimization problems with a linear objective function and subject to linear constraints with cone inclusions, referred to as conic linear problems. We formulate the Lagrangian dual of a conic linear problem and survey some results based on the conjugate duality approach where the questions of “no duality … Read more
We describe a parallel, linear programming and implication based heuristic for solving set partitioning problems on distributed memory computer architectures. Our implementation is carefully designed to exploit parallelism to greatest advantage in advanced techniques like preprocessing and probing, primal heuristics, and cut generation. A primal-dual subproblem simplex method is used for solving the linear programming … Read more
0. The standard dual simplex method. 1. A more general and practical dual simplex method. 2. Phase I for the dual simplex method. 3. Degeneracy in the dual simplex method. 4. A generalized ratio test for the dual simplex method. CitationDraft, Department of Industrial Engineering andManagement Sciences, Northwestern University, 1994.ArticleDownload View PDF
This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems. In … Read more
Techniques for transforming convex quadratic programs (QPs) into monotone linear complementarity problems (LCPs) and vice versa are well known. We describe a class of LCPs for which a reduced QP formulation—one that has fewer constraints than the “standard” QP formulation—is available. We mention several instances of this class, including the known case in which the … Read more
We study the situation in which, having solved a linear program with an interior-point method, we are presented with a new problem instance whose data is slightly perturbed from the original. We describe strategies for recovering a “warm-start” point for the perturbed problem instance from the iterates of the original problem instance. We obtain worst-case … Read more