Convexity and concavity properties of the optimal value function in parametric nonlinear programming

Convexity and concavity properties of the optimal value functionf* are considered for the general parametric optimization problemP() of the form min _x f(x, ), s.t.x R(). Such properties off* and the solution set mapS* form an important part of the theoretical basis for sensitivity, stability, and parametric analysis in mathematical optimization. Sufficient conditions are given for several standard types of convexity and concavity off*, in terms of respective convexity and concavity assumptions onf and the feasible region point-to-set mapR. Specializations of these results to the general parametric inequality-equality constrained nonlinear programming problem and its right-hand-side version are provided. To the authors' knowledge, this is the most comprehensive compendium of such results to date. Many new results are given.This paper is based on results presented in the PhD Thesis of the second author completed at The George Washington University under the direction of the first author.This work was partly supported by the Office of Naval Research, Program in Logistics, Contract No. N00014-75-C-0729 and by the National Science Foundation, Grant No. ECS-82-01370 to the Institute for Management Science and Engineering, The George Washington University, Washington, DC.     

Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective valuez ^*. These new methods combine the approach of Goldfarb and Mehrotra for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds forz ^* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402, and ONR Contract N0014-87-K0214.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

Directional differentiability of the optimal value function in convex semi-infinite programming

In this paper, directional differentiability properties of the optimal value function of a parameterized semi-infinite programming problem are studied. It is shown that if the unperturbed semi-infinite programming problem is convex, then the corresponding optimal value function is directionally differentiable under mild regularity assumptions. A max-min formula for the directional derivatives, well-known in the finite convex case, is given.     

Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization

In bi-parametric linear optimization (LO), perturbation occurs in both the right-hand-side and the objective function data with different parameters. In this paper, the bi-parametric LO problem is considered and we are interested in identifying the regions where the optimal partitions are invariant. These regions are referred to as invariancy regions. It is proved that invariancy regions are separated by vertical and horizontal lines and generate a mesh-like area. It is proved that the boundaries of these regions can be identified in polynomial time. The behavior of the optimal value function on these regions is investigated too.     

Geometry of optimal value functions with applications to redundancy in linear programming

In 1967, Wets and Witzgall (Ref. 1) made, in passing, a connection between frames of polyhedral cones and redundancy in linear programming. The present work elaborates and formalizes the theoretical details needed to establish this relation. We study the properties of optimal value functions in order to derive the correspondence between problems in redundancy and the frame of a polyhedral cone. The insights obtained lead to schemes to improve the efficiency of procedures to detect redundancy in the areas of linear programming, stochastic programming, and computational geometry.The author is indebted to G. Dewan for his review and discussions.     

Conditions for the uniqueness of the optimal solution in linear semi-infinite programming

In this paper, we establish different conditions for the uniqueness of the optimal solution of a semi-infinite programming problem. The approach here is based on the differentiability properties of the optimal value function and yields the corresponding extensions to the general linear semi-infinite case of many results provided by Mangasarian and others. In addition, detailed optimality conditions for the most general problem are supplied, and some features of the optimal set mapping are discussed. Finally, we obtain a dimensional characterization of the optimal set, provided that a usual closedness condition (Farkas-Minkowski condition) holds.     

Lipschitz continuity of the optimal value function and KKT solution set in indefinite quadratic programs

When all the involved data in indefinite quadratic programs change simultaneously,we show the locally Lipschtiz continuity of the KKT set of the quadratic programming problem firstly, then we establish the locally Lipschtiz continuity of the KKT solution set. Finally, the similar conclusion for the corresponding optimal value function is obtained.     

On the differentiability of optimal values for bounded nonlinear programs with equality constraints

We consider a parametrized family of nonlinear programs where the feasible region is defined by equality constraints in a ball. The global optimal value is shown to be twice continuously differentiable over an open and dense set in the perturbation parameter space.     

Parametric linear fractional programming for an unbounded feasible region

Parametric analysis in linear fractional programming is significantly more complicated in case of an unbounded feasible region. We propose procedures which are based on a modified version of Martos' algorithm or a modification of Charnes-Cooper's algorithm, applying each to problems where either the objective function or the right-hand side is parametrized.     

A property of certain multistage linear programs and some applications

In this paper, we present a property of certain linear multistage problems. To solve them, a method which takes this property into account is presented. It requires the resolution of 2N–1 subproblems, if there areN stages in the original problem. A sufficient condition is given on the matrix of the constraints for the property to be true. When only a submatrix has this property, we propose to use the Dantzig-Wolfe decomposition principle. We then can solve the subproblem with the proposed method. Applications to linear and nonlinear programming are presented.This work was done while the author was Visiting Scholar at the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California.     

Designing a majorization scheme for the recourse function in two-stage stochastic linear programming

We discuss issues pertaining to the domination from above of the second-stage recourse function of a stochastic linear program and we present a scheme to majorize this function using a simpler sublinear function. This majorization is constructed using special geometrical attributes of the recourse function. The result is a proper, simplicial function with a simple characterization which is well-suited for calculations of its expectation as required in the computation of stochastic programs. Experiments indicate that the majorizing function is well-behaved and stable.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

On characterizing the solution sets of pseudolinear programs

This paper provides several new and simple characterizations of the solution sets of pseudolinear programs. By means of the basic properties of pseudolinearity, the solution set of a pseudolinear program is characterized, for instance, by the equality that , for each feasible pointx, where is in the solution set. As a consequence, we give characterizations of both the solution set and the boundedness of the solution set of a linear fractional program.     

Continuity of the optimal value function and optimal solutions of parametric mixed-integer quadratic programs

To properly describe and solve complex decision problems, research on theoretical properties and solution of mixed-integer quadratic programs is becoming very important. We establish in this paper different Lipschitz-type continuity results about the optimal value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of the linear constraints. The obtained results extend some existing results for continuous quadratic programs, and, more importantly, lay the foundation for further theoretical study and corresponding algorithm analysis on mixed-integer quadratic programs.     

Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.     

On the lower semicontinuity of optimal solution sets

We study the lower semicontinuity of the optimal solution set of a parametric optimization problem. Our results sharpen the main results of Zhao (1997, The lower semicontinuity of optimal solution sets. Journal of Mathematical Analysis and Applications, 207, 240–254. Ref. ). Namely, it is shown that the conclusion of Theorem 1 of is still valid under weaker assumptions, and the conditions on “ε-nontriviality” and uniform continuity of the objective function in Theorems 2 and 3 of can be omitted.     

On singularities of value function for Bolza optimal control problem

We study the set of points of nondifferentiability, called the singular set, of the value function of a Bolza optimal control problem. The value function is a viscosity solution to an associated Hamilton-Jacobi equation. The method of characteristics associates to this equation a Hamiltonian system, that in turn can be used to study the propagation of singularities of the value function. In particular, we obtain an extension of the Rankine-Hugoniot type condition, which is well-known in the conservation law theory.     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

A penalty function approach for solving bi-level linear programs

The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems.