Grobner bases were introduced by Bruno Buchberger in 1965. Since that time, they have been used with considerable success in several area of Mathematics, and are the subject of much current research. The most important aspect of Grobner bases is that they can be computed. Such computations bring a wealth of examples to theoretical research, and allow some important result to be applied. This thesis develops the algebraic concept needed to understand Grobner bases. The presentation focuses on the role of monomial ideals. Grobner bases are seen to provide an effective means of computing in the factor rings of multivariable polynomials. The theory is applied to rewriting of polynomial equations and to integer programming.

No description available.

In this thesis, we address three main subjects. Wefirst introducethe relation between linear inequality systems and linear programmingproblems, and continue by introducing the analyticcenter of a polyhedron and its calculation. Secondly, we study themultiple analytic center cutting plane method ACCPM and its proximalvariant. Finally, since ACCPM and proximal ACCPM are well knowntechniques for convexprogramming problems, we propose a sequential convex programming methodbased on ACCPM and convexification techniques to tackle unconstrainedproblems with a non-convex objective function in the last chapter. Wealso report a comparison of ourmethod with some existing algorithms: the steepest descent method andnonlinear conjugate gradient algorithms / Dans cette thèse, nous abordons trois thèmes principaux. Nous commençons par présenter la relation entre les systèmes d'inégalités linéaires et les problèmes de programmation linéaire. Nous poursuivons avec l'introduction de la notion de centre analytique d'un polyèdre et son calcul. Deuxièmement, nous étudions la méthode des coupes analytiques multiples ACCPM et sa variante proximale. En-fin, puisque ACCPM et sa variante proximale sont des techniques bien connues pour les problèmes de programmation convexe, nous proposons une méthode de programmation séquentielle convexe fondée sur ACCPM ainsi que des techniques de convexification destinées à traiter les problèmes dont la fonction objectif est non convexe dans le dernier chapitre. Nous présentons aussi une comparaison de nos méthode avec certains algorithmes existants tels que la méthode la plus forte pente et la méthode du gradient conjugué non linéaire.

Polyhedral cutting-plane algorithms for hard combinatorial problems have scored notable successes. However, computational research on the Maximum-Weight Cut Problem (MCP) on undirected graphs has been inconclusive. In 1988, Barahona suggested a new polyhedral algorithm that, given a good initial solution, attempts to prove optimality. If the initial cut is non-optimal, it is iteratively improved until optimal. The expected advantages are three-fold. If a good, fast heuristic is used, an optimal solution may be available. The algorithm can then prove optimality fast. Secondly, if time is a serious constraint, prematurely terminating the algorithm yields a cut at least as good as the original. Finally, since the algorithm nominally optimizes over the cut cone rather than the cut polytope, the underlying separation problem is very simple. This research explores Barahona's algorithm on a class of MCP instances arising in statistical mechanics. The graphs are toroidal grids, together with an additional universal vertex. By considering different integer programming formulations, it has been possible to design a fast algorithm that replaces optimization over the cut polytope by repeated optimization over the intersection of the cut cone and the unit cube. This latter polyhedron is shown to be equivalent to the multicut polytope, and its basic facet classes are identified. The final algorithm is successful in solving MCP instances over 70 x 70 grids, over 5 times bigger than previous algorithms. Substantial improvements in computation time have also been achieved.

A branch-and-cut IP solver is developed for a class of structured 0/1 integer programs arising from a truck dispatching scheduling problem. This problem is characterized by a group of set partitioning constraints and a group of knapsack equality constraints of a specific form. Families of facets for the polytopes associated with individual knapsack constraints are identified, and in some cases, a complete characterization of a polytope is obtained. In addition, a notion of "conflict graph" is introduced and utilized to obtain an approximating node-packing polytope for the convex hull of all 0/1 solutions. The branch-and-cut solver generates cuts based on both the knapsack constraints and the approximating node-packing polytope, and incorporates these cuts into a tree-search algorithm that uses problem reformulation and linear programming-based heuristics at each node in the search tree to assist in the solution process. Numerical experiments are performed on large-scale real instances supplied by Texaco Trading & Transportation, Inc. The optimal schedules obtained correspond to cost savings for the company and greater job satisfaction for drivers due to more balanced work schedules and income distribution. It is noteworthy that this is apparently the first time that branch-and-cut has been applied to an equality constrained problem in which the entries in the constraint matrix and right hand side are not purely 0/1.

The centrality property satisfied by the analytic center of the solution set makes its computation very valuable for some linear programming applications. One such application coming from the economic and management sciences is Data Envelopment Analysis (DEA). In DEA one desires a solution of the underlying linear programming model that is in the relative interior of the solution set and one that is in some sense as far away as possible from the relative boundary. In this way the solution is robust and not affected by small changes in the data. In this work we study the effective computation of the analytic center solution by the use of primal-dual interior-point methods. We present a unified study of existing theoretical results for primal-dual interior-point algorithms as they concern the convergence of the iteration sequence and the convergence of the iteration sequence to the analytic center. These theoretical results are evaluated from the point of view of the practical computation of the analytic center. We propose a primal-dual interior-point algorithm for effectively computing the analytic center of the solution set. The algorithm proposed combines good theoretical and numerical properties and its ability to solve real world problems from the DEA application is demonstrated.

We study the choice of the Lagrange multipliers in the successive quadratic programming method (SQP) applied to the equality constrained optimization problem. It is known that the augmented Lagrangian SQP-Newton method depends on the penalty parameter only through the multiplier in the Hessian matrix of the Lagrangian function. This effectively reduces the augmented Lagrangian SQP-Newton method to the Lagrangian SQP Newton method where only the multiplier estimate depends on the penalty parameter. In this work, we construct a multiplier estimate that depends strongly on the penalty parameter and we derive a choice for the penalty parameter so that the Hessian matrix, restricted to the null space of the constraints, is positive definite and well conditioned. We demonstrate that the SQP-Newton method with this choice of Lagrange multipliers is locally and q-quadratically convergent.

Two new updates are presented, the UHU update and a modified Gurwitz update, for approximating the Hessian of the Lagrangian in nonlinear constrained optimization problems. Under the standard assumptions, the new UHU algorithm is shown to converge locally at a two-step q-superlinear rate. With the additional assumption that the update can be performed at every iteration, the UHU method converges locally at a one-step q-superlinear rate. Numerical experiments are performed on some full Hessian methods including Powell's modified BFGS and Tapia's ASSA and SALSA algorithms, and on reduced Hessian methods including the two new updates, the Coleman-Fenyes update, the Nocedal-Overton method, and the two-stage Gurwitz update. These experiments show that the new updates compare favorably with existing methods.

In a recent paper, Barzilai and Borwein presented a new choice of steplength for the gradient method. Their choice does not guarantee descent in the objective function and greatly speeds up the convergence of the method. We derive an interesting relationship between any gradient method and the shifted power method. This relationship allows us to establish the convergence of the Barzilai and Borwein method when applied to the problem of minimizing any strictly convex quadratic function (Barzilai and Borwein considered only 2-dimensional problems). Our point of view also allows us to explain the remarkable improvement obtained by using this new choice of steplength. For the two eigenvalues case we present some very interesting convergence rate results. We show that our Q and R-rate of convergence analysis is sharp and we compare it with the Barzilai and Borwein analysis. We derive the preconditioned Barzilai and Borwein method and present preliminary numerical results indicating that it is an effective method, as compared to the preconditioned Conjugate Gradient method, for the numerical solution of some special symmetric positive definite linear systems that arise in the numerical solution of Partial Differential Equations.

A new class of preconditioners for the iterative solution of the linear systems arising from interior point methods is proposed. For many of these methods, the linear systems come from applying Newton's method on the perturbed Karush-Kuhn-Tucker optimality conditions for the linear programming problem. This leads to a symmetric indefinite linear system called the augmented system. This system can be reduced to the Schur complement system which is positive definite. After the reduction, the solution for the linear system is usually computed via the Cholesky factorization. This factorization can be dense for some classes of problems. Therefore, the solution of these systems by iterative methods must be considered. Since these systems are very ill-conditioned near a solution of the linear programming problem, it is crucial to develop efficient preconditioners. We show that from the point of view of designing preconditioners, it is better to work with the augmented system. We show that all preconditioners for the Schur complement system have an equivalent for the augmented system while the opposite is not true. The theoretical properties of the new preconditioners are discussed. This class works better near a solution of the linear programming problem when the linear systems are highly ill-conditioned. Another important feature is the option to reduce the preconditioned indefinite system to a positive definite one of the size of the Schur complement. This class of preconditioners relies on the computation of an LU factorization of a subset of columns of the matrix of constraints. The techniques developed for a competitive implementation are rather sophisticated since the subset of columns is not known a priori. The new preconditioner applied to the conjugate gradient method compares favorably with the Cholesky factorization approach. The new approach performs better on large scale problems whose Cholesky factorization contains a large number of nonzero entries. Numerical experiments on several representative classes of linear programming problems are presented to indicate the promise of this new approach.