On minimax optimization problems

We give a short proof that in a convex minimax optimization problem ink dimensions there exist a subset ofk + 1 functions such that a solution to the minimax problem with thosek + 1 functions is a solution to the minimax problem with all functions. We show that convexity is necessary, and prove a similar theorem for stationary points when the functions are not necessarily convex but the gradient exists for each function.     

On Noetherian Modules over Minimax Abelian Groups

We consider modules over minimax Abelian groups. We prove that if A is an Abelian minimax subgroup of the multiplicative group of a field k and if the subring K of the field k generated by the subgroup A is Noetherian, then the subgroup A is the direct product of a periodic group and a finitely generated group.     

Asymptotic minimax risk for sup-norm loss: Solution via optimal recovery

Summary We study the problem of estimating an unknown function on the unit interval (or itsk-th derivative), with supremum norm loss, when the function is observed in Gaussian white noise and the unknown function is known only to obey Lipschitz- smoothness, >k0. We discuss an optimization problem associated with the theory ofoptimal recovery. Although optimal recovery is concerned with deterministic noise chosen by a clever opponent, the solution of this problem furnishes the kernel of the minimax linear estimate for Gaussian white noise. Moreover, this minimax linear estimator is asymptotically minimax among all estimates. We sketch also applications to higher dimensions and to indirect measurement (e.g. deconvolution) problems.Dedicated to R.Z. Khas'minskii for his 60th birthday     

Multinomial approximations for nonparametric experiments which minimize the maximal loss of Fisher information

Summary Certain nonparametric product experimentsP _n ⁿ can asymptotically be approximated by multinomial experiments obtained by a finite interval partition of the sample space, the real line. For specific familiesP _n defined in terms of bounded Fisher information and monotone likelihood ratios with bounded derivatives we study the problem to calculate a partition which is optimal in the sense that it minimizes the maximal loss of Fisher information caused by the discretization. This leads to a minimax problem. By considering partitions of the sample space intok intervals which have equal probability under a densityh and then lettingk we obtain an expansion for the quantity loss of Fisher information which is of orderk ^-2 under regularity conditions. The corresponding minimax problem for the first order term of this expansion is shown to be the unique solution of a free boundary problem.This work has been supported by the Deutsche Forschungsgemeinschaft     

Penalization techniques in L ∞ optimization problems with unbounded horizon

In this work we present a numerical procedure for the ergodic optimal minimax control problem. Restricting the development to the case with relaxed controls and using a perturbation of the instantaneous cost function, we obtain discrete solutions U _ε ^k that converge to the optimal relaxed cost U when the relation ship between the parameters of discretization k and penalization ε is an appropriate one. This paper aims to be a tribute to Prof. Roberto L.V. González who died after we finished this work. This paper was supported by grant PIP 5379 CONICET.     

Solution of an equiweighted minimax location problem on a hemisphere

A particular continuous single facility minimax location problem on the surface of a hemisphere is discussed. We assume that all the demand points are equiweighted. An algorithm, based on spherical trigonometry, for finding the minimax point is presented. The minimax point thus obtained is unique and the algorithm is O(n ²) in the worst case.     

A primal‐dual method for the Meyer model of cartoon and texture decomposition

In this paper, we study the original Meyer model of cartoon and texture decomposition in image processing. The model, which is a minimization problem, contains an l₁‐based TV‐norm and an l_∞‐based G‐norm. The main idea of this paper is to use the dual formulation to represent both TV‐norm and G‐norm. The resulting minimization problem of the Meyer model can be given as a minimax problem. A first‐order primal‐dual algorithm can be developed to compute the saddle point of the minimax problem. The convergence of the proposed algorithm is theoretically shown. Numerical results are presented to show that the original Meyer model can decompose better cartoon and texture components than the other testing methods.     

Optimal m-stage Runge-Kutta schemes for steady-state solutions of hyperbolic equations

A numerical scheme is developed to find optimal parameters and time step of m-stage Runge-Kutta (RK) schemes for accelerating the convergence to -steady-state solutions of hyperbolic equations. These optimal RK schemes can be applied to a spatial discretization over nonuniform grids such as Chebyshev spectral discretization. For each m given either a set of all eigenvalues or a geometric closure of all eigenvalues of the discretization matrix, a specially structured nonlinear minimax problem is formulated to find the optimal parameters and time step. It will be shown that each local solution of the minimax problem is also a global solution and therefore the obtained m-stage RK scheme is optimal. A numerical scheme based on a modified version of the projected Lagrangian method is designed to solve the nonlinear minimax problem. The scheme is generally applicable to any stage number m. Applications in solving nonsymmetric systems of linear equations are also discussed. © 1993 John Wiley & Sons, Inc.     

Optimal designs with respect to Elfving's partial minimax criterion in polynomial regression

For the polynomial regression model on the interval [a, b] the optimal design problem with respect to Elfving's minimax criterion is considered. It is shown that the minimax problem is related to the problem of determining optimal designs for the estimation of the individual parameters. Sufficient conditions are given guaranteeing that an optimal design for an individual parameter in the polynomial regression is also minimax optimal for a subset of the parameters. The results are applied to polynomial regression on symmetric intervals [–b, b] (b1) and on nonnegative or nonpositive intervals where the conditions reduce to very simple inequalities, involving the degree of the underlying regression and the index of the maximum of the absolute coefficients of the Chebyshev polynomial of the first kind on the given interval. In the most cases the minimax optimal design can be found explicitly.Research supported in part by the Deutsche Forschungsgemeinschaft.Research supported in part by NSF Grant DMS 9101730.     

Price Expectations and Cobwebs Under Uncertainty

Classical approaches to location problems are based on the minimization of the average distance (the median concept) or the minimization of the maximum distance (the center concept) to the service facilities. The median solution concept is primarily concerned with the spatial efficiency while the center concept is focused on the spatial equity. The k-centrum model unifies both the concepts by minimization of the sum of the k largest distances. In this paper we investigate a solution concept of the conditional median which is a generalization of the k-centrum concept taking into account the portion of demand related to the largest distances. Namely, for a specified portion (quantile) of demand we take into account the entire group of the corresponding largest distances and we minimize their average. It is shown that such an objective, similar to the standard minimax, may be modeled with a number of simple linear inequalities. Equitable properties of the solution concept are examined.     

Selection of the number of regression variables; A minimax choice of generalized FPE

Summary A generalized Final Prediction Error (FPE_α)_ criterion is considered. Based onn observations, the numberk of regression variables is selected from a given range 0≦k≦K, so as to minimize . It is shown that if α tends to infinity withn, the selection is consistent but the maximum of the mean squared error of estimates of parameters diverges to infinity with the same order of divergence as that of α. A meaningful minimax choice of α exists for a regret type mean squared error, while for simple mean squared error it is trivially 0. The minimax regret choice of α converges to a constant, approximately 3.5 forK≧8 ifn−K increases simultaneously withn, otherwise it diverges to infinity withn.     

State estimation for a dynamical system described by a linear equation with unknown parameters

We investigate the state estimation problem for a dynamical system described by a linear operator equation with unknown parameters in a Hilbert space. In the case of quadratic restrictions on the unknown parameters, we propose formulas for a priori mean-square minimax estimators and a posteriori linear minimax estimators. A criterion for the finiteness of the minimax error is formulated. As an example, the main results are applied to a system of linear algebraic-differential equations with constant coefficients.     

Poisson convergence in the restricted k‐partitioning problem

The randomized k‐number partitioning problem is the task to distribute N i.i.d. random variables into k groups in such a way that the sums of the variables in each group are as similar as possible. The restricted k‐partitioning problem refers to the case where the number of elements in each group is fixed to N/k. In the case k = 2 it has been shown that the properly rescaled differences of the two sums in the close to optimal partitions converge to a Poisson point process, as if they were independent random variables. We generalize this result to the case k > 2 in the restricted problem and show that the vector of differences between the k sums converges to a k ‐ 1‐dimensional Poisson point process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

The dynamic programming algorithm of [12.] for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(n^k) steps and simultaneous O(n^k) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(n^k) steps and simultaneous O(n^k) space and is in the class NSPACE(log n).     

Adaptive minimax test of independence

The paper is concerned with the adaptive minimax problem of testing the independence of the components of a d-dimensional random vector. The functions under alternatives consist of smooth densities supported on [0, 1]d and separated away from the product of their marginals in L2-norm. We are interested in finding the adaptive minimax rate of testing and a test that attains this rate. We focus mainly on the tests for which the error of the first kind an can decrease to zero as the number of observations increases. We show also how this property of the test affects its error of the second kind.     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.     

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.* This work was supported in part by NSF grant CCR-9700239 and by DIMACS. This work was done while a postdoctoral fellow at DIMACS.     

A branch-and-cut algorithm based on semidefinite programming for the minimum <Emphasis Type="Italic">k</Emphasis>-partition problem

The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. The two key ingredients for this algorithm are: the combination of semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the MkP problem. We compare ICH to the hyperplane rounding techniques of Goemans and Williamson and of Frieze and Jerrum, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the MkP problem. ICH is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-bound tree. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing a fast exact approach for k≥3.     

Adaptive chi-square tests

The minimax hypothesis-testing problem is considered. Let H₀: f=f₀≡1 and H₁ consist of smooth densities. It is shown that the optimal, in the minimax sense, order of distinguishing is attained by a procedure based on simultaneous use ofχ ²-tests corresponding to the growing number of intervals of grouping of the sample. Bibliography: 16 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 244, 1997, pp. 150–166. Translated by S. Yu. Pilyugin.