Nonalgorithmic sensitivity and tolerance bounds analysis for linear and nonlinear programs

In Chapter 1, we survey the work since the Fiacco-McCormick 1968 survey (65), that has been done in penalty function methodology and its extensions (exact penalty functions and augmented Lagrangians). We report on the existing software that implements penalty and augmented Lagrangian algorithms and some of the comparative studies that have been conducted.;In Chapter 2, we review the underlying theory for non-algorithmic sensitivity analysis (S.A.) formulas for the Karush-Kuhn-Tucker (K.K.T.) triple of general nonlinear programming (NLP) problems as developed in Fiacco (58) and a minor generalization of these formulas. We re-assess the formulas for bounds on the convex (concave) optimal objective function of NLP's when a single parameter is perturbed, along with the formulas for multiparameter perturbations. We describe the software SENS that we have developed to implement these non-algorithmic S.A. formulas and bounds for single parameter perturbations.;In Chapter 3, we present some new sensitivity results in linear programming and nonlinear programming with concave or convex optimal value functions. We first address the problem of finding upper and lower bounds on a parameter in the objective function of a linear programming problem such that the optimal objective function is within a prescribed tolerance of (1) the optimal objective function at a given value of the parameter and (2) the objective function evaluated at a given solution point. We then investigate finding the maximum deviation between a given value of the objective function and the optimal value function for the parameter restricted to a given interval. We relate our work to recent results due to Wendell (191) and indicate extensions to nonlinear programming. These results were developed jointly with A. V. Fiacco.;In Chapter 4, we report on the implementation of SENS on two test problems. The first one is a structural design problem from Bracken and McCormick (29) and the second one is an international intra-company transfer pricing problem as presented in Kassicieh (96). SENS results are compared to SENSUMT results as reported in Ghaemi (75) for the first test problem and Yacout (192) for the second, and to closed form solutions that we derived.;In Chapter 5, all the techniques developed in this thesis are applied to a diet problem. We first analyze a linear programming formulation of this problem then a convex quadratic extension. Solution, sensitivity analysis, bound analysis, and tolerance bounds results are presented.