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.     

Numerical solution of minimax optimal control problems by multiple shooting technique

This paper presents the application of the multiple shooting technique to minimax optimal control problems (optimal control problems with Chebyshev performance index). A standard transformation is used to convert the minimax problem into an equivalent optimal control problem with state variable inequality constraints. Using this technique, the highly developed theory on the necessary conditions for state-restricted optimal control problems can be applied advantageously. It is shown that, in general, these necessary conditions lead to a boundary-value problem with switching conditions, which can be treated numerically by a special version of the multiple shooting algorithm. The method is tested on the problem of the optimal heating and cooling of a house. This application shows some typical difficulties arising with minimax optimal control problems, i.e., the estimation of the switching structure which is dependent on the parameters of the problem. This difficulty can be overcome by a careful application of a continuity method. Numerical solutions for the example are presented which demonstrate the efficiency of the method proposed.     

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.     

Minimax Control of Parabolic Systems with Dirichlet Boundary Conditions and State Constraints

In this paper we formulate and study a minimax control problem for a class of parabolic systems with controlled Dirichlet boundary conditions and uncertain distributed perturbations under pointwise control and state constraints. We prove an existence theorem for minimax solutions and develop effective penalized procedures to approximate state constraints. Based on a careful variational analysis, we establish convergence results and optimality conditions for approximating problems that allow us to characterize suboptimal solutions to the original minimax problem with hard constraints. Then passing to the limit in approximations, we prove necessary optimality conditions for the minimax problem considered under proper constraint qualification conditions. Accepted 7 June 1996     

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.     

Minimax problems of discrete optimization invariant under majority operators

A special class of discrete optimization problems that are stated as a minimax modification of the constraint satisfaction problem is studied. The minimax formulation of the problem generalizes the classical problem to realistic situations where the constraints order the elements of the set by the degree of their feasibility, rather than defining a dichotomy between feasible and infeasible subsets. The invariance of this ordering under an operator is defined, and the discrete minimization of functions invariant under majority operators is proved to have polynomial complexity. A particular algorithm for this minimization is described.     

On a class of differential games without saddle-point solutions

The minimax solution of a linear regulator problem is considered. A model representing a game situation in which the first player controls the dynamic system and selects a suitable, minimax control strategy, while the second player selects the aim of the game, is formulated. In general, the resulting differential game does not possess a saddle-point solution. Hence, the minimax solution for the player controlling the dynamic system is sought and obtained by modifying the performance criterion in such a way that (a) the minimax strategy remains unchanged and (b) the modified game possesses a saddle-point solution. The modification is achieved by introducing a regularization procedure which is a generalization of the method used in an earlier paper on the quadratic minimax problem. A numerical algorithm for determining the nonlinear minimax strategy in feedback form, in which Pagurek's result on open-loop and closed-loop sensitivity is used to nontrivially simplify the computational aspects of the problem, is presented and applied on a simple example.     

Minimax regret solution to multiobjective linear programming problems with interval objective functions coefficients

The current paper focuses on a multiobjective linear programming problem with interval objective functions coefficients. Taking into account the minimax regret criterion, an attempt is being made to propose a new solution i.e. minimax regret solution. With respect to its properties, a minimax regret solution is necessarily ideal when a necessarily ideal solution exists; otherwise it is still considered a possibly weak efficient solution. In order to obtain a minimax regret solution, an algorithm based on a relaxation procedure is suggested. A numerical example demonstrates the validity and strengths of the proposed algorithm. Finally, two special cases are investigated: the minimax regret solution for fixed objective functions coefficients as well as the minimax regret solution with a reference point. Some of the characteristic features of both cases are highlighted thereafter.     

Continuous maximin knapsack problems with GLB constraints

This paper introduces the continuous minimax knapsack problem with generalized lower bound constraints and describes an algorithm that solves this problem in O(n logn) time. We also discuss the related problem with generalized upper bound constraints. This research is partially supported by the Natural Sciences and Engineering Council of Canada under Grant No. A5053.     

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.     

The prerestorative step in the sequential Gradient-Restoration Algorithm for mathematical Programming problems with inequality constraints*

In this paper, the problem of minimizing a function of several variables subject to inequality constraints is considered. The method employed is the sequential gradient-restoration algorithm with complete restoration. In this algorithm, the inequality constraints are transformed into equality constraints by suitable transformations. A modification of the sequential gradient-restoration algorithm, designed to improve the convergence characteristics, is presented. It consists of inserting a prerestorative step prior to any iteration of the algorithm. The aim of this prerestorative step is to reduce the constraint violation. Eight numerical examples are presented. They show the considerable beneficial effects associated with the above prerestorative step: on the average, the number of iterations of the modified algorithm is less than 50% of the number of iterations of the standard algorithm. An analogous remark holds for the computer time.     

Worst-case global optimization of black-box functions through Kriging and relaxation

A new algorithm is proposed to deal with the worst-case optimization of black-box functions evaluated through costly computer simulations. The input variables of these computer experiments are assumed to be of two types. Control variables must be tuned while environmental variables have an undesirable effect, to which the design of the control variables should be robust. The algorithm to be proposed searches for a minimax solution, i.e., values of the control variables that minimize the maximum of the objective function with respect to the environmental variables. The problem is particularly difficult when the control and environmental variables live in continuous spaces. Combining a relaxation procedure with Kriging-based optimization makes it possible to deal with the continuity of the variables and the fact that no analytical expression of the objective function is available in most real-case problems. Numerical experiments are conducted to assess the accuracy and efficiency of the algorithm, both on analytical test functions with known results and on an engineering application.     

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.     

Using tropical optimization to solve minimax location problems with a rectilinear metric on the line

Methods of tropical (idempotent) mathematics are applied to the solution of minimax location problems under constraints on the feasible location region. A tropical optimization problem is first considered, formulated in terms of a general semifield with idempotent addition. To solve the optimization problem, a parameter is introduced to represent the minimum value of the objective function, and then the problem is reduced to a parametrized system of inequalities. The parameter is evaluated using existence conditions for solutions of the system, whereas the solutions of the system for the obtained value of the parameter are taken as the solutions of the initial optimization problem. Then, a minimax location problem is formulated to locate a single facility on a line segment in the plane with a rectilinear metric. When no constraints are imposed, this problem, which is also known as the Rawls problem or the messenger boy problem, has known geometric and algebraic solutions. For the location problems, where the location region is restricted to a line segment, a new solution is obtained, based on the representation of the problems in the form of the tropical optimization problem considered above. Explicit solutions of the problems for various positions of the line are given both in terms of tropical mathematics and in the standard form.     

Minimax feature selection problem for constructing a classifier using support vector machines

A minimax feature selection problem for constructing a classifier using support vector machines is considered. Properties of the solutions of this problem are analyzed. An improvement of the saddle point search algorithm based on extending the bound for the step parameter is proposed. A new nondifferential optimization algorithm is developed that, together with the saddle point search algorithm, forms a hybrid feature selection algorithm. The efficiency of the algorithm for computing Dykstra’s projections as applied for the feature selection problem is experimentally estimated.     

Convergence of an Interior Point Algorithm for Continuous Minimax

We propose an algorithm for the constrained continuous minimax problem. The algorithm uses a quasi-Newton search direction, based on subgradient information, conditional on maximizers. The initial problem is transformed to an equivalent equality constrained problem, where the logarithmic barrier function is used to ensure feasibility. In the case of multiple maximizers, the algorithm adopts semi-infinite programming iterations toward epiconvergence. Satisfaction of the equality constraints is ensured by an adaptive quadratic penalty function. The algorithm is augmented by a discrete minimax procedure to compute the semi-infinite programming steps and ensure overall progress when required by the adaptive penalty procedure. Progress toward the solution is maintained using merit functions.     

On some properties of the control problem under a program disturbance in a formalization based on the minimax risk (regret) criterion

A control problem under uncertainty for a system described by an ordinary differential equation with a terminal performance index is considered. The control and disturbance are subject to geometric constraints. The problem is formalized in classes of nonanticipating control strategies and program disturbances with the use of constructive ideal motions and the Savage minimax risk (regret) criterion. The properties of the used motion bundles are described and a number of relations characterizing the optimal risk function, which is an element of the formalization, are presented.     

A lexicographic minimax algorithm for multiperiod resource allocation

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. We consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, we first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem's special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.     

A quadratic approximation method for minimizing a class of quasidifferentiable functions

Summary An unconstrained nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities arise from terms of the form max [f ₁(x), ...,f _n (x)], which may enter nonlinearly in the objective function. Local convex polyhedral upper approximations to the objective function are introduced. These approximations are used in an iterative method for solving the problem. The algorithm proceeds by solving quadratic programming subproblems to generate search directions. Approximate line searches ensure global convergence of the method to stationary points. The algorithm is conceptually simple and easy to implement. It generalizes efficient variable metric methods for minimax calculations.     

A relaxed cutting plane algorithm for solving fuzzy inequality systems

This paper studies a system of infinitely many fuzzy inequalities with concavemembership functions. By using the tolerance approach, we show that solving such system can be reduced to a semi-infinite programming problem. A relaxed cutting plane algorithm is proposed. In each iteration, we solve a finite convex optimization problem and add one or two more constraints. The proposed algorithm chooses a point at which the infinite constraints are violated to a degree rather than at which the violation is maximized. The iterative process ends when an optimal solution is identified. A convergence proof, under some mild conditions, is given. An efficient implementation based on the "method of centres" with "entropic regularization" techniques is also included. Some computational results confirm the efficiency of the proposed method and show its potential for solving large scale problems.