Equality and inequality constrained optimization algorithms with convergent stepsizes

In this paper, we consider two algorithms for nonlinear equality and inequality constrained optimization. Both algorithms utilize stepsize strategies based on differentiable penalty functions and quadratic programming subproblems. The essential difference between the algorithms is in the stepsize strategies used. The objective function in the quadratic subproblem includes a linear term that is dependent on the penalty functions. The quadratic objective function utilizes an approximate Hessian of the Lagrangian augmented by the penalty functions. In this approximation, it is possible to ignore the second-derivative terms arising from the constraints in the penalty functions.The penalty parameter is determined using a strategy, slightly different for each algorithm, that ensures boundedness as well as a descent property. In particular, the boundedness follows as the strategy is always satisfied for finite values of the parameter.These properties are utilized to establish global convergence and the condition under which unit stepsizes are achieved. There is also a compatibility between the quadratic objective function and the stepsize strategy to ensure the consistency of the properties for unit steps and subsequent convergence rates.This research was funded by SERC and ESRC research contracts. The author is grateful to Professors Laurence Dixon and David Mayne for their comments. The numerical results in the paper were obtained using a program written by Mr. Robin Becker.     

On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs.     

Degeneracy in NLP and the development of results motivated by its presence

We study notions of nondegeneracy and several levels of increasing degeneracy from the perspective of the local behavior of a local solution of a nonlinear program when problem parameters are slightly perturbed. Ideal nondegeneracy at a local minimizer is taken to mean satisfaction of second order sufficient conditions, linear independence and strict complimentary slackness. Following a brief exploration of the relationship of these conditions with the classical definition of nondegeneracy in linear programming, we recall a number of optimality and regularity conditions used to attempt to resolve degeneracy and survey results of Fiacco, McCormick, Robinson, Kojima, Gauvin and Janin, Shapiro, Kyparisis and Liu. This overview may be viewed as a structured survey of sensitivity and stability results: the focus is on progressive levels of degeneracy. We note connections of nondegeneracy with the convergence of algorithms and observe the striking parallel between the effects of nondegeneracy and degeneracy on optimality conditions, stability analysis and algorithmic convergence behavior. Although our orientation here is primarily interpretive and noncritical, we conclude that more effort is needed to unify optimality, stability and convergence theory and more results are needed in all three areas for radically degenerate problems.Research supported by National Science Foundation Grant ECS 90-00560 and Grant N00014-89-J-1537 Office of Naval Research     

Solving multiple-objective problems in the objective space

Projection and relaxation techniques are employed to decompose a multiobjective problem into a two-level structure. The basic manipulation consists in projecting the decision variables onto the space of the implicit tradeoffs, allowing the definition of a relaxed multiobjective master problem directly in the objective space. An additional subproblem tests the feasibility of the solution encountered by the relaxed problem. Some properties of the relaxed problem (linearity, small number of variables, etc.) render its solution efficient by a number of methods. Representatives of two different classes of multiobjective methods [the Geoffrion, Dyer, Feinberg (GDF) method and the fuzzy method of Baptistella and Ollero] are implemented and applied within this context to a water resources allocation problem. The results attest the computational viability of the overall procedure and its usefulness for the solution of multiobjective problems.This work was partially sponsored by grants from CNP_q and FAPESP, Brazil. The authors are indebted to the anonymous reviewers for their valuable comments.     

Generating well-behaved utility functions for compromise programming

The purpose of this paper is to seek utility functions satisfying a weak condition which guarantees that the utility optimum always belongs to the compromise set. This set is a special subset of the attainable or feasible set, which is generated through the application of the well-known operational research approach called compromise programming. It is shown that there are large families of utility functions satisfying this condition, thus reinforcing the value of compromise programming as a good surrogate of the traditional utility optimum.Thanks are due to the reviewers for their helpful suggestions. The English editing by Ms. Christine Méndez is appreciated. The authors have been supported by the Comisión Interministerial de Ciencia y Tecnología (CICYT), Madrid, Spain.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

Some proximity and sensitivity results in quadratic integer programming

We show that for any optimal solution for a given separable quadratic integer programming problem there exist an optimal solution for its continuous relaxation such that wheren is the number of variables and(A) is the largest absolute subdeterminant of the integer constraint matrixA. Also for any feasible solutionz, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution having greater objective function value and with . We further prove, under some additional assumptions, that the distance between a pair of optimal solutions to an integer quadratic programming problem with right hand side vectorsb andb, respectively, depends linearly on b–b₁. Finally the validity of all the results for nonseparable mixed-integer quadratic programs is established. The proximity results obtained in this paper are extensions of some of the results described in Cook et al. (1986) for linear integer programming.This research was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998.     

A trajectory-following method for unconstrained optimization

A trajectory-following method with interesting properties is considered for solving unconstrained nonlinear programming problems. The trajectory is defined by a special system of ordinary differential equations. This system uses only the gradient of the objective function. Numerical examples are given.The work of the second author was supported by the DFG Schwerpunkt Anwendungs-bezogene Optimierung and Steuerung.     

Quadratically constrained minimum cross-entropy analysis

Quadratically constrained minimum cross-entropy problem has recently been studied by Zhang and Brockett through an elaborately constructed dual. In this paper, we take a geometric programming approach to analyze this problem. Unlike Zhang and Brockett, we separate the probability constraint from general quadratic constraints and use two simple geometric inequalities to derive its dual problem. Furthermore, by using the dual perturbation method, we directly prove the strong duality theorem and derive a dual-to-primal conversion formula. As a by-product, the perturbation proof gives us insights to develop a computation procedure that avoids dual non-differentiability and allows us to use a general purpose optimizer to find an-optimal solution for the quadratically constrained minimum cross-entropy analysis.     

Convergence of interval-type algorithms for generalized fractional programming

The purpose of this paper is to analyze the convergence of interval-type algorithms for solving the generalized fractional program. They are characterized by an interval [LB _k , UB _k ] including*, and the length of the interval is reduced at each iteration. A closer analysis of the bounds LB _k and UB _k allows to modify slightly the best known interval-type algorithm NEWMODM accordingly to prove its convergence and derive convergence rates similar to those for a Dinkelbach-type algorithm MAXMODM under the same conditions. Numerical results in the linear case indicate that the modifications to get convergence results are not obtained at the expense of the numerical efficiency since the modified version BFII is as efficient as NEWMODM and more efficient than MAXMODM.This research was supported by NSERC (Grant A8312) and FCAR (Grant 0899).