We analyze the properties that optimization algorithms must possess in order to prevent convergence to non-stationary points for the merit function. We show that demanding the exact satisfaction of constraint linearizations results in difficulties in a wide range of optimization algorithms. Feasibility control is a mechanism that prevents convergence to spurious solutions by ensuring that … Read more
A primal-dual active set method for convex quadratic problems with bound constraints is presented. Based on a guess on the active set, a primal-dual pair $(x,s)$ is computed that satisfies the first order optimality condition and the complementarity condition. If $(x,s)$ is not feasible, a new active set is determined, and the process is iterated. … Read more
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. Citation NA\195, Department of Mathematics, University of Dundee, UK, December, 1999 Article Download View A bundle filter method for nonsmooth nonlinear optimization
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. Citation Draft, Department of Industrial Engineering andManagement Sciences, Northwestern University, 1994. Article Download View Notes … 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
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
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
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