Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Linearly constrained minimax optimization

We present an algorithm for nonlinear minimax optimization subject to linear equality and inequality constraints which requires first order partial derivatives. The algorithm is based on successive linear approximations to the functions defining the problem. The resulting linear subproblems are solved in the minimax sense subject to the linear constraints. This ensures a feasible-point algorithm. Further, we introduce local bounds on the solutions of the linear subproblems, the bounds being adjusted automatically, depending on the quality of the linear approximations. It is proved that the algorithm will always converge to the set of stationary points of the problem, a stationary point being defined in terms of the generalized gradients of the minimax objective function. It is further proved that, under mild regularity conditions, the algorithm is identical to a quadratically convergent Newton iteration in its final stages. We demonstrate the performance of the algorithm by solving a number of numerical examples with up to 50 variables, 163 functions, and 25 constraints. We have also implemented a version of the algorithm which is particularly suited for the solution of restricted approximation problems.This work has been supported by the Danish Natural Science Research Council, Grant No. 511-6874.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

A parallel algorithm for partially separable non-convex global minimization: Linear constraints

The global minimization of large-scale partially separable non-convex problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of a separable concave part, an unseparated convex part, and a strictly linear part, which are all coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. An important special class of problems which can be reduced to this form are the synomial global minimization problems. Such problems often arise in engineering design, and previous computational methods for such problems have been limited to the convex posynomial case. In the current work, a convex underestimating function to the objective function is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and convex underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results obtained on the four processor Cray 2, both sequentially and in parallel on all four processors, are also presented.     

A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique

This paper is concerned with the development of an algorithm to solve continuous polynomial programming problems for which the objective function and the constraints are specified polynomials. A linear programming relaxation is derived for the problem based on a Reformulation Linearization Technique (RLT), which generates nonlinear (polynomial) implied constraints to be included in the original problem, and subsequently linearizes the resulting problem by defining new variables, one for each distinct polynomial term. This construct is then used to obtain lower bounds in the context of a proposed branch and bound scheme, which is proven to converge to a global optimal solution. A numerical example is presented to illustrate the proposed algorithm.     

Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization

The subject of this article is a class of global optimization problems, in which the variables can be divided into two groups such that, in each group, the functions involved have the same structure (e.g. linear, convex or concave, etc.). Based on the decomposition idea of Benders (Ref. 1), a corresponding master problem is defined on the space of one of the two groups of variables. The objective function of this master problem is in fact the optimal value function of a nonlinear parametric optimization problem. To solve the resulting master problem, a branch-and-bound scheme is proposed, in which the estimation of the lower bounds is performed by applying the well-known weak duality theorem in Lagrange duality. The results of this article concentrate on two subjects: investigating the convergence of the general algorithm and solving dual problems of some special classes of nonconvex optimization problems. Based on results in sensitivity and stability theory and in parametric optimization, conditions for the convergence are established by investigating the so-called dual properness property and the upper semicontinuity of the objective function of the master problem. The general algorithm is then discussed in detail for some nonconvex problems including concave minimization problems with a special structure, general quadratic problems, optimization problems on the efficient set, and linear multiplicative programming problems.     

A parallel algorithm for constrained concave quadratic global minimization

The global minimization of large-scale concave quadratic problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of both a concave part (nonlinear variables) and a strictly linear part, which are coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. A linear underestimating function to the concave part of the objective is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and linear underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results are presented for problems with 25 and 50 nonlinear variables and up to 400 linear variables. These results were obtained on a four processor CRAY2 using both sequential and parallel implementations of the algorithm. The average parallel solution time was approximately 15 seconds for problems with 400 linear variables and a relative tolerance of 0.001. For a relative tolerance of 0.1, the average computation time appears to increase only linearly with the number of linear variables.     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

The empirical performance of a polynomial algorithm for constrained nonlinear optimization

In [6], a polynomial algorithm based on successive piecewise linear approximation was described. The algorithm is polynomial for constrained nonlinear (convex or concave) optimization, when the constraint matrix has a polynomial size subdeterminant. We propose here a practical adaptation of that algorithm with the idea of successive piecewise linear approximation of the objective on refined grids, and the testing of the gap between lower and upper bounds. The implementation uses the primal affine interior point method at each approximation step. We develop special features to speed up each step and to evaluate the gap. Empirical study of problems of size up to 198 variables and 99 constraints indicates that the procedure is very efficient and all problems tested were terminated after 171 interior point iterations. The procedure used in the implementation is proved to converge when the objective is strongly convex.Supported in part by the Office of Naval Research under Grant No. N00014-88-K-0377 and Grant No. ONR N00014-91-J-1241.     

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration

In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.     

Alternating direction augmented Lagrangian methods for semidefinite programming

We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixed-point argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our algorithms are robust and very efficient due to their ability or exploit special structures, such as sparsity and constraint orthogonality in these problems.     

Bibliographic zur vektoroptimierung (theorie und anwendungen)

An algorithm is developed which yields the straight lines that bound a set of points from below and from above and which minimizes the sum of the vertical distances from the points to the lines. The algorithm can also be used to construct bounds so that some specified fraction of the points lies between them. The minimization can be expressed as a linear programming problem whose dual contains only two constraints. The two basic variables that result can be obtained and the objective function is easily evaluated. Two examples are given.     

Semidefinite relaxations for non-convex quadratic mixed-integer programming

We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this approach as a bounding routine in an SDP-based branch-and-bound framework. In case of a convex objective function, the new SDP bound improves the bound given by the continuous relaxation of the problem. Numerical experiments show that our algorithm performs well on various types of non-convex instances.     

Airport noise modelling and aircraft scheduling so as to minimize community annoyance

A mathematical model of the annoyance created at an airport by aircraft operations is developed. The model incorporates population distribution considerations around an airport and the annoyance caused by aircraft noise. The objective function of this model corresponds to seeking to minimize total population annoyance created by all aircraft operations in a 24-hour period. Several factors are included in this model as constraint relationships. Aircraft operations by type and time period are upper bounded. Demand for flight services is incorporated by including lower bounds on the number of operations by type of aircraft, runway used and time period. Also upper bounds on the number of operations for each runway are included. The mathematical model as formulated is recognized as corresponding to a nonlinear integer mathematical programming problem.The solution technique selected makes use of a successive linear approximation optimization algorithm. An especially attractive feature of this solution algorithm is that it is capable of obtaining solutions to large problems. For example, it would be feasible to attempt the solution of problems involving several thousand variables and over 500 linear constraints. This suggested solution algorithm was implemented on a computer and computational results obtained for example problems.     

Reducibility of minimax to minisum 0–1 programming problems

We consider 0–1 programming problems with a minimax objective function and any set of constraints. Upon appropriate transformations of its cost coefficients, such a minimax problem can be reduced to a linear minisum problem with the same set of feasible solutions such that an optimal solution to the latter will also solve the original minimax problem.Although this reducibility applies for any 0–1 programming problem, it is of particular interest for certain locational decision models. Among the obvious implications are that an algorithm for solving a p-median (minisum) problem in a network will also solve a corresponding p-center (minimax) problem.It should be emphasized that the results presented will in general only hold for 0–1 problems due to intrinsic properties of the minimax criterion.     

Solving discrete linear bilevel optimization problems using the optimal value reformulation

In this article, we consider two classes of discrete bilevel optimization problems which have the peculiarity that the lower level variables do not affect the upper level constraints. In the first case, the objective functions are linear and the variables are discrete at both levels, and in the second case only the lower level variables are discrete and the objective function of the lower level is linear while the one of the upper level can be nonlinear. Algorithms for computing global optimal solutions using Branch and Cut and approximation of the optimal value function of the lower level are suggested. Their convergence is shown and we illustrate each algorithm via an example.     

Solving the minimal least squares problem subject to bounds on the variables

A computational procedure is developed for determining the solution of minimal length to a linear least squares problem subject to bounds on the variables. In the first stage, a solution to the least squares problem is computed and then in the second stage, the solution of minimal length is determined. The objective function in each step is minimized by an active set method adapted to the special structure of the problem.The systems of linear equations satisfied by the descent direction and the Lagrange multipliers in the minimization algorithm are solved by direct methods based on QR decompositions or iterative preconditioned conjugate gradient methods. The direct and the iterative methods are compared in numerical experiments, where the solutions are sought to a sequence of related, minimal least squares problems subject to bounds on the variables. The application of the iterative methods to large, sparse problems is discussed briefly.This work was supported by The National Swedish Board for Technical Development under contract dnr 80-3341.     

The equal flow problem

This paper presents a new algorithm for the solution of a network problem with equal flow side constraints. The solution technique is motivated by the desire to exploit the special structure of the side constraints and to maintain as much of the characteristics of pure network problems as possible. The proposed algorithm makes use of Lagrangean relaxation to obtain a lower bound and decomposition by right-hand-side allocation to obtain upper bounds. The lagrangean dual serves not only to provide a lower bound used to assist in termination criteria for the upper bound, but also allows an initial allocation of equal flows for the upper bound. The algorithm has been tested on problems with up to 1500 nodes and 6000 arcs. Computational experience indicates that solutions whose objective function value is well within 1% of the optimum can be obtained in 1%–65% of the MPSX time depending on the amount of imbalance inherent in the problem. Incumbent integer solutions which are within 99.99% feasible and well within 1% of the proven lower bound are obtained in a straightforward manner requiring, on the average, 30% of the MPSX time required to obtain a linear optimum.     

Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds

Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that the objective function is continuously differentiable and that the points of the level set have at least one component strictly between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model.     

An algorithm for separable non-linear minimax problems

We consider a minimax resource allocation problem in which each term of the objective function is a strictly decreasing, invertible function of a single decision variable. The objective is to minimize the maximum term subject to non-negativity constraints and a set of linear constraints with only non-negative parameters. We develop an algorithm that finds an optimal solution by repeatedly solving a relaxed minimax problem. In general, each relaxed problem is solved by simple search methods; however, for certain non-linear functions the algorithm employs closed form expressions.