On bilevel programming,Part I: General nonlinear cases

This paper is concerned with general nonlinear nonconvex bilevel programming problems (BLPP). We derive necessary and sufficient conditions at a local solution and investigate the stability and sensitivity analysis at a local solution in the BLPP. We then explore an approach in which a bundle method is used in the upper-level problem with subgradient information from the lower-level problem. Two algorithms are proposed to solve the general nonlinear BLPP and are shown to converge to regular points of the BLPP under appropriate conditions. The theoretical analysis conducted in this paper seems to indicate that a sensitivity-based approach is rather promising for solving general nonlinear BLPP.This research is sponsored by the Office of Naval Research under contract N00014-89-J-1537.     

Postoptimal analysis in multicriteria linear programming

The aim of the paper is to present the postoptimal analysis of a chosen extreme efficient point in multicriteria linear programming. There are three cases considered: one objective function coefficient change, objective function addition and objective function removal. The proven theorems allow us to create methods based on the analysis of a simplex tableau.     

A dual-active-set algorithm for positive semi-definite quadratic programming

Because of the many important applications of quadratic programming, fast and efficient methods for solving quadratic programming problems are valued. Goldfarb and Idnani (1983) describe one such method. Well known to be efficient and numerically stable, the Goldfarb and Idnani method suffers only from the restriction that in its original form it cannot be applied to problems which are positive semi-definite rather than positive definite. In this paper, we present a generalization of the Goldfarb and Idnani method to the positive semi-definite case and prove finite termination of the generalized algorithm. In our generalization, we preserve the spirit of the Goldfarb and Idnani method, and extend their numerically stable implementation in a natural way. Supported in part by ATERB, NSERC and the ARC. Much of this work was done in the Department of Mathematics at the University of Western Australia and in the Department of Combinatorics and Optimization at the University of Waterloo.     

A convex analysis approach for convex multiplicative programming

Global optimization problems involving the minimization of a product of convex functions on a convex set are addressed in this paper. Elements of convex analysis are used to obtain a suitable representation of the convex multiplicative problem in the outcome space, where its global solution is reduced to the solution of a sequence of quasiconcave minimizations on polytopes. Computational experiments illustrate the performance of the global optimization algorithm proposed.      

Finding all maximal efficient faces in multiobjective linear programming

An algorithm for finding the whole efficient set of a multiobjective linear program is proposed. From the set of efficient edges incident to a vertex, a characterization of maximal efficient faces containing the vertex is given. By means of the lexicographic selection rule of Dantzig, Orden and Wolfe, a connectedness property of the set of dual optimal bases associated to a degenerate vertex is proved. An application of this to the problem of enumerating all the efficient edges incident to a degenerate vertex is proposed. Our method is illustrated with numerical examples and comparisons with Armand—Malivert's algorithm show that this new algorithm uses less computer time.     

Fitting piecewise linear continuous functions

We consider the problem of fitting a continuous piecewise linear function to a finite set of data points, modeled as a mathematical program with convex objective. We review some fitting problems that can be modeled as convex programs, and then introduce mixed-binary generalizations that allow variability in the regions defining the best-fit function’s domain. We also study the additional constraints required to impose convexity on the best-fit function.     

Lipschitz properties of solutions in mathematical programming

This paper deals with the dependence of the solutions and the associated multipliers of a nonlinear programming problem when the data of the problem are subjected to small perturbations. Sufficient conditions are given which imply that the solutions and the multipliers of a perturbed nonlinear programming problem are Lipschitzian with respect to the perturbations.The authors wish to thank J. Drèze and J. P. Vial for many helpful discussions and J. B. Hiriart-Urruty for comments on a previous version of the paper.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Some perturbation theory for linear programming

Mathematical Programming -     

Constructing efficient solutions structure of multiobjective linear programming

It is not a difficult task to find a weak Pareto or Pareto solution in a multiobjective linear programming (MOLP) problem. The difficulty lies in finding all these solutions and representing their structure. This paper develops an algorithm for solving this problem. We investigate the solutions and their relationships in the objective space. The algorithm determines finite number of weights, each of which corresponds to a weighted sum problems. By solving these problems, we further obtain all weak Pareto and Pareto solutions of the MOLP and their structure in the constraint space. The algorithm avoids the degeneration problem, which is a major hurdle of previous works, and presents an easy and clear solution structure.     

Additive and multiplicative tolerance in multiobjective linear programming

We consider a multiobjective linear program. We propose a procedure for computing an additive and multiplicative (percentage) tolerance in which all the objective function coefficients may simultaneously and independently vary while preserving the efficiency of a given solution. For a nondegenerate basic solution, the procedure runs in polynomial time.     

Maximal and supremal tolerances in multiobjective linear programming

Let a multiobjective linear programming problem and any efficient solution be given. Tolerance analysis aims to compute interval tolerances for (possibly all) objective function coefficients such that the efficient solution remains efficient for any perturbation of the coefficients within the computed intervals. The known methods either yield tolerances that are not the maximal possible ones, or they consider perturbations of weights of the weighted sum scalarization only. We focus directly on perturbations of the objective function coefficients, which makes the approach independent on a scalarization technique used. In this paper, we propose a method for calculating the supremal tolerance (the maximal one need not exist). The main disadvantage of the method is the exponential running time in the worst case. Nevertheless, we show that the problem of determining the maximal/supremal tolerance is NP-hard, so an efficient (polynomial time) procedure is not likely to exist. We illustrate our approach on examples and present an application in transportation problems. Since the maximal tolerance may be small, we extend the notion to individual lower and upper tolerances for each objective function coefficient. An algorithm for computing maximal individual tolerances is proposed.     

A Fast MPC Algorithm Using Nonfeasible Active Set Methods

Model predictive control (MPC) is an optimization-based control framework which is attractive to industry both because it can be practically implemented and it can deal with constraints directly. One of the main drawbacks of MPC is that large MPC horizon times can cause requirements of excessive computational time to solve the quadratic programming (QP) minimization which occurs in the calculation of the controller at each sampling interval. This motivates the study of finding faster ways for computing the QP problem associated with MPC. In this paper, a new nonfeasible active set method is proposed for solving the QP optimization problem that occurs in MPC. This method has the feature that it is typically an order of magnitude faster than traditional methods. This work has been supported by the Canadian NSERC under Grant A4396.     

An unconstrained convex programming view of linear programming

The major interest of this paper is to show that, at least in theory, a pair of primal and dual -optimal solutions to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.     

A Rigorous Lower Bound for the Optimal Value of Convex Optimization Problems

In this paper, we consider the computation of a rigorous lower error bound for the optimal value of convex optimization problems. A discussion of large-scale problems, degenerate problems, and quadratic programming problems is included. It is allowed that parameters, whichdefine the convex constraints and the convex objective functions, may be uncertain and may vary between given lower and upper bounds. The error bound is verified for the family of convex optimization problems which correspond to these uncertainties. It can be used to perform a rigorous sensitivity analysis in convex programming, provided the width of the uncertainties is not too large. Branch and bound algorithms can be made reliable by using such rigorous lower bounds.     

The relationship between integer and real solutions of constrained convex programming

We prove the following theorem which gives a bound on the proximity of the real and the integer solutions to certain constrained optimization programs.     

Presolving in linear programming

Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and Tomlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible.In this paper we present a comprehensive survey of presolve methods. Moreover, we discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve.Computational results on the NETLIB problems (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.This author was supported by a Danish SNF Research studentship.     

Weak linear bilevel programming problems: existence of solutions via a penalty method

We are concerned with a class of weak linear bilevel programs with nonunique lower level solutions. For such problems, we give via an exact penalty method an existence theorem of solutions. Then, we propose an algorithm.     

Intelligent gradient search in linear programming

The simplex algorithm is still the best known and most frequently used way to solve LP problems. Khachian has suggested a method to solve these problems in polynomial time. The average behaviour of his method, however, is still inferior to the modern simplex based LP codes. A new gradient based approach which also has polynomial worst-case behaviour has been suggested by Karmarkar. This method was modified, programmed and compared with other available LP codes. It is shown that the numerical efficiency of Karmarkar's method compares favourably with other LP codes, particularly for problems with high numbers of variables and few constraints.