An optimal minimax algorithm

Computer game-playing programs repeatedly calculate minimax elements = min _i max _j M _ij of large pay off matricesM _ij . A straightforwardrow-by-row calculation of scans rows ofM _ij one at a time, skipping to a new row whenever an element is encountered that exceeds a current minimax. Anoptimal calculation, derived here, scans the matrix more erratically but finds after testing the fewest possible matrix elements. Minimizing the number of elements tested is reasonable when elements must be computed as needed by evaluating future game positions. This paper obtains the expected number of tests required when the elements are independent, identically distributed, random variables. For matrices 50 by 50 or smaller, the expected number of tests required by the row-by-row calculation can be at most 42% greater than the number for the optimal calculation. When the numbersR, C of rows and columns are very large, both calculations require an expected number of tests nearRC/InR.     

An optimal greedy routing algorithm for triangulated polygons

In this paper, we prove that a triangulated polygon G admits a greedy embedding into an appropriate semi-metric space such that using an appropriate distance definition, for any two vertices u and w in G, a most virtual distance decreasing path is always a minimum-edge path between u and w. Therefore, our greedy routing algorithm is optimal. The greedy embedding of G can be obtained in linear time. To the best of our knowledge, this is the first optimal greedy routing algorithm for a nontrivial subcategory of graphs.     

An algorithm for minimax

An algorithm is proposed for computing an unconstrained minimax, based on differential equations with suitable stabilization terms. Methods for accelerating the convergence are discussed. For computing a constrained minimax, the augmented Lagrangian algorithm of Powell, Hestenes and Rockafellar is generalized to minimax, assuming the unconstrained minimax algorithm as a subroutine. An estimate of the convergence rate is obtained.     

An algorithm for the minimax weber problem

The paper presents an algorithm for finding the weighted absolute center of a given set of points in the Euclidean plane.The algorithm is a specialized implementation of the method of feasible directions.The presentation includes a proof of convergence as well as computational experience.     

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.     

An algorithm for solving linearly constrained minimax problems

In this study, we propose an algorithm for solving a minimax problem over a polyhedral set defined in terms of a system of linear inequalities. At each iteration a direction is found by solving a quadratic programming problem and then a suitable step size along that direction is taken through an extension of Armijo's approximate line search technique. We show that each accumulation point is a Kuhn-Tucker solution and give a condition that guarantees convergence of the whole sequence of iterations. Through the use of an exact penalty function, the algorithm can be used for solving constrained nonlinear programming. In this case, our algorithm resembles that of Han, but differs from it both in the direction-finding and the line search steps.     

An improved SQP algorithm for solving minimax problems

In this work, an improved SQP method is proposed for solving minimax problems, and a new method with small computational cost is proposed to avoid the Maratos effect. In addition, its global and superlinear convergence are obtained under some suitable conditions.     

An algorithm for node-capacitated ring routing

A strongly polynomial time algorithm is described to solve the node-capacitated routing problem in an undirected ring network.     

A bundle-type algorithm for routing in telecommunication data networks

To optimize the quality of service through a telecommunication network, we propose an algorithm based on Lagrangian relaxation. The bundle-type dual algorithm is adapted to the present situation, where the dual function is the sum of a polyhedral function (coming from shortest path problems) and of a smooth function (coming from the congestion function).     

Optimal routing in non-geostationary satellite ATM networks with intersatellite link capacity constraints

The trend toward broadband communications in space is foreseeable, and its features predestine ATM as the basic mode of operation. Some of the low and medium earth orbit satellite concepts make use of intersatellite links (ISLs) to provide global connectivity with minimal usage of terrestrial fixed network resources. Interconnecting neighbouring satellites with ISLs results in a partially meshed switching subnetwork in space. The ISLs have a time-varying distance or may even lose sight of each other. This feature of the ISL topology dynamics significantly increases the complexity of connection-oriented network operation and routing. We deal with the routing problem to minimize the virtual path connection handover rate and path delay in the time-varying ISL subnetwork topology with ISL capacity constraints. A heuristic algorithm is proposed to deal with this problem, which is based on Lagrangean relaxation and dynamic programming. When there is sufficient capacity at every ISL, the algorithm produces an optimal solution easily using only dynamic programming. For evaluation of our algorithm, some computational results have been presented. These results show that our optimization algorithm can produce a solution close to an optimal solution when there exist ISL capacity constraints.     

An algorithm for convex constrained minimax optimization based on duality

We consider the problem of finding the minimum value of the upper hull ofn convex functionals on a Hilbert space, subject to convex constraints. The problem is reformulated as that of finding the minimum of the worst convex combination of these functionals, which eventually yields a saddle-point problem. We propose a new algorithm to solve this problem that simplifies the task of updating the dual variables. Simultaneously, the constraints can be dualized by introducing other dual multipliers. Convergence proofs are given and a concrete example shows the practical and computational advantages of the proposed algorithm and approach.This research has been supported by the Centre National de la Recherche Scientifique (CNRS-France) under Contract No. ATP-2340.     

Uniqueness of the solution for optimal static routing in open BCMP queueing networks

Optimal static routing problems in open BCMP queueing networks with state-independent arrival and service rates are studied. They include static routing problems in communication networks and optimal static load balancing problems in distributed computer systems. We consider an overall optimal policy that is the routing policy whereby the overall mean response (or sojourn) time of a job is minimized. We obtain the routing decisions of the overall optimal policy and show that they may not be unique, but that the utilization of each service center is uniquely determined by the overall optimal policy. We also consider an individually optimal policy whereby jobs are routed so that each job may feel that its own expected response time is minimized if it knows the mean delay time for each path.     

An optimal algorithm for geometrical congruence

An algorithm is given which, in time O(n log n), determines all the Euclidean congruences (if any) between two n-point sets in 3-dimensional space. The algorithm is shown to be optimal to within a constant factor.     

New minimax algorithm

The purpose of this paper is to suggest a new, efficient algorithm for the minmax problem $$\mathop {min}\limits_x \mathop {max}\limits_i f_i (x), x \in \Re ^n , i = 1, \ldots ,m,$$ wheref _i ,i=1,...,m, are real-valued functions defined on ? ⁿ . The problem is transformed into an equivalent inequality-constrained minimization problem, mint, s.t.f _i (x)?t≤0, for alli, i=1,...,m. The algorithm has these features: an active-set strategy with three types of constraints; the use of slack variables to handle inequality constraints; and a trust-region strategy taking advantage of the structure of the problem. Following Tapia, this problem is solved by an active set strategy which uses three types of constraints (called here nonactive, semiactive, and active). Active constraints are treated as equality constraints, while semiactive constraints are treated as inequality constraints and are assigned slack variables. This strategy helps to prevent zigzagging. Numerical results are provided.     

A dual algorithm for minimax problems

In this paper, a dual algorithm, based on a smoothing function of Bertsekas (1982), is established for solving unconstrained minimax problems. It is proven that a sequence of points, generated by solving a sequence of unconstrained minimizers of the smoothing function with changing parametert, converges with Q-superlinear rate to a Kuhn-Tucker point locally under some mild conditions. The relationship between the condition number of the Hessian matrix of the smoothing function and the parameter is studied, which also validates the convergence theory. Finally the numerical results are reported to show the effectiveness of this algorithm.     

A minimax optimal control problem

A control system x=f(t,x,u) is considered, and a cost functional ess supT ₀tT ₁ G(t, x(t),u(t)) is to be minimized. Necessary conditions for optimality (maximum principle and transversality conditions) are derived. It is also shown that an optimal control is optimal for the corresponding problem on a subinterval of [T ₀,T ₁], if a certain controllability condition is satisfied.     

Nonmonotone algorithm for minimax optimization problems

Many real life problems can be stated as a minimax optimization problem, such as the problems in economics, finance, management, engineering and other fields. In this paper, we present an algorithm with nonmonotone strategy and second-order correction technique for minimax optimization problems. Using this scheme, the new algorithm can overcome the difficulties of the Maratos effect occurred in the nonsmooth optimization, and the global and superlinear convergence of the algorithm can be achieved accordingly. Numerical experiments indicate some advantages of this scheme.     

Stochastic approximation algorithm for minimax problems

A stochastic approximation algorithm for minimax optimization problems is analyzed. At each iterate, it performs one random experiment, based on which it computes a direction vector. It is shown that, under suitable conditions, it a.s. converges to the set of points satisfying necessary optimality conditions. The algorithm and its analysis bring together ideas from stochastic approximation and nondifferentiable optimization.