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.     

Applying the minimax criterion in stochastic recourse programs

We consider an optimization problem in which some uncertain parameters are replaced by random variables. The minimax approach to stochastic programming concerns the problem of minimizing the worst expected value of the objective function with respect to the set of probability measures that are consistent with the available information on the random data. Only very few practicable solution procedures have been proposed for this problem and the existing ones rely on simplifying assumptions. In this paper, we establish a number of stability results for the minimax stochastic program, justifying in particular the approach of restricting attention to probability measures with support in some known finite set. Following this approach, we elaborate solution procedures for the minimax problem in the setting of two-stage stochastic recourse models, considering the linear recourse case as well as the integer recourse case. Since the solution procedures are modifications of well-known algorithms, their efficacy is immediate from the computational testing of these procedures and we do not report results of any computational experiments.     

Asymptotically minimax testing ofr>2 simple hypotheses

In this paper, we consider the problem of asymptotically minimax testing ofr≥2 simple hypotheses when a general stochastic process is observed. We establish general conditions for the exponential decrease of maximal probability errors of minimax tests as the number of observations increases. At the present time, similar results for testing several multinomial schemes were obtained by Salihov [8]. Similar results for testing two simple hypotheses were obtained in [5]. In the proofs of the main results, we use the theory of large deviations ([3], [2]). In Sec. 1, the main result is proved. In Secs. 2–4, we analyze the i.i.d. case, nonhomogeneous Poisson processes, and renewal processes as examples. Published in Lietuvos Matematikos Rinkinys, Vol. 40, No. 3, pp. 313–320, July–September, 2000.     

A scenario aggregation algorithm for the solution of stochastic dynamic minimax problems

In this paper, we present a scenario aggregation algorithm for the solution of the dynamic minimax problem in stochastic programming. We consider the case where the joint probability distribution has a known finite support. The algorithm applies the Alternating Direction of Multipliers Method on a reformulation of the minimax problem using a double duality framework. The problem is solved by decomposition into scenario sub-problems, which are deterministic multi-period problems. Convergence properties are deduced from the Alternating Direction of Multipliers. The resulting algorithm can be seen as an extension of Rockafellar and Wets Progressive Hedging algorithm to the dynamic minimax context.     

Tight bounds for minimax grid matching with applications to the average case analysis of algorithms

The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2-dimensional bin packing. More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimen-sional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem. As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line bin packing and on-line dynamic allocation. The results also solve a long-open question in mathematical statistics.This research was supported by Air Force Contracts AFOSR-82-0326 and AFOSR-86-0078, NSF Grant 8120790, and DARPA contract N00014-80-C-0326. In addition, Tom Leighton was supported by an NSF Presidential Young Investigator Award with matching funds from Xerox and IBM.     

On distributionally robust multiperiod stochastic optimization

This paper considers model uncertainty for multistage stochastic programs. The data and information structure of the baseline model is a tree, on which the decision problem is defined. We consider “ambiguity neighborhoods” around this tree as alternative models which are close to the baseline model. Closeness is defined in terms of a distance for probability trees, called the nested distance. This distance is appropriate for scenario models of multistage stochastic optimization problems as was demonstrated in Pflug and Pichler (SIAM J Optim 22:1–23, 2012). The ambiguity model is formulated as a minimax problem, where the the optimal decision is to be found, which minimizes the maximal objective function within the ambiguity set. We give a setup for studying saddle point properties of the minimax problem. Moreover, we present solution algorithms for finding the minimax decisions at least asymptotically. As an example, we consider a multiperiod stochastic production/inventory control problem with weekly ordering. The stochastic scenario process is given by the random demands for two products. We determine the minimax solution and identify the worst trees within the ambiguity set. It turns out that the probability weights of the worst case trees are concentrated on few very bad scenarios.     

Decoupling problems around a trajectory: from linearity to nonlinearity

Given a nonlinear control system for which an admissible statetrajectory is specified, we solve approximately the input outputdecoupling problem around this nominal trajectory. An approximatesolution for this problem is obtained by dealing with the linearizedsystem along this trajectory. An exact solution to the inputoutput decoupling problem for the linearization is shown tobe an approximate solution to the input output decoupling problemaround the nominal trajectory for the original nonlinear system.In a similar way, we provide an approximate solution to thedisturbance decoupling problem around a specified trajectoryof the nonlinear system. The nonlinear model of a two link robotmanipulator is used to illustrate the results on input outputdecoupling.     

2×2列联表中二属性相关的Bayes检验

2×2列联表中二属性相关的假设检验是定性数据分析中的热点问题,针对此问题的研究频率学派已做过大量的工作,其理论方法已趋于成熟.利用Bayes检验研究2×2列联表中二属性的相关性迄今为止国内外的相关文献还为数不多.将依据Bayes理论对此问题提出新的检验方法,推出其Bayes因子计算公式,利用正态近似研究三项假设计算出有关的后验概率,不仅解决了频率学派难以处理的问题,并且为吸烟有害健康提供了理论支撑.     

Test d'indépendance nonparametrique

We consider the minimax problem of testing the independence of the components of a d-dimensional random vector against a set of alternatives defined by L₂-norm. We are interested in finding the minimax rate of testing and a test that attains this rate. The bound of the error of the first kind is a positive sequence which can decrease to zero as the number of observations increases. To cite this article: A.F. Yode, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Density Deconvolution in the Circular Structural Model

We consider deconvolving bivariate irregular densities supported on the circumference of the unit circle. The errors are bivariate, and the observations are available on the plane. Assuming that the estimated density is smooth on the circle, we compute exact asymptotics of the minimax risks and develop asymptotically optimal estimators for the case of normal errors. The proposed estimators are automatically sharp minimax adaptive over a wide collection of smoothness classes. It is shown that the same rates of convergence hold for a variety of different types of error distributions. The interesting feature of the problem is that the optimal rates of convergence do not depend on the error distribution and are determined essentially by the problem geometry.     

一类无约束离散Minimax问题的区间调节熵算法

In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C^1. The paper deals with this problem by means of taking the place of maximum-entropy function with adjustable entropy function. By constructing an interval extension of adjustable entropy function and some region deletion test rules, a new interval algorithm is presented. The relevant properties are proven, The minimax value and the localization of the minimax points of the problem can be obtained by this method. This method can overcome the flow problem in the maximum-entropy algorithm. Both theoretical and numerical results show that the method is reliable and efficient.     

Test for autocorrelation change in discretely observed Ornstein-Uhlenbeck processes driven by Lévy processes

In this paper,we consider the problem of testing for an autocorrelation change in discretely observed Ornstein-Uhlenbeck processes driven by Lévy processes.For a test,we propose a class of test statistics constructed by an iterated cumulative sums of squares of the difference between two adjacent observations.It is shown that each of the test statistics weakly converges to the supremum of the square of a Brownian bridge.The test statistics are evaluated by some empirical results.     

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.     

An algorithm for optimal minimax routing in ATM networks

Asynchronous Transfer Mode (ATM) has been adopted by the CCITT as the transport mode in which Broadband ISDN will be based. In this paper, we formulate the problem of routing cells in an ATM network as an optimization problem. The objective is to minimize the largest cell loss probability among all links. The constraints correspond to a multicommodity network flow problem with gains. An algorithm to determine a global optimal flow assignment is presented. The minimax routing algorithm was implemented and tested on several sample networks. The computational experiments show that the algorithm is computationally efficient.Supported by NSF grant NCR 92-23148.     

A characterization of a minimax test in the problem of testing two composite hypotheses

We obtain a characterization of a minimax test in the problem of testing two composite hypotheses via a solution of a dual problem. In comparison to previous results, our characterization is valid under much weaker assumptions, which became possible, in particular, due to a modification of a dual problem.     

The Minimax Estimator of Stochastic Regression Coefficients and Parameters in the Class of All Estimators

In this paper, the authors address the problem of the minimax estimator of linear combinations of stochastic regression coefficients and parameters in the general normal linear model with random effects. Under a quadratic loss function, the minimax property of linear estimators is investigated. In the class of all estimators, the minimax estimator of estimable functions, which is unique with probability 1, is obtained under a multivariate normal distribution.     

Binary knapsack problems with random budgets

The binary knapsack problem is a combinatorial optimization problem in which a subset of a given set of elements needs to be chosen in order to maximize profit, given a budget constraint. In this paper, we study a stochastic version of the problem in which the budget is random. We propose two different formulations of this problem, based on different ways of handling infeasibility, and propose an exact algorithm and a local search-based heuristic to solve the problems represented by these formulations. We also present the results from some computational experiments.     

Risk-based optimal investment and proportional reinsurance of an insurer with hidden regime switching

In this paper, we study the optimal investment and proportional reinsurance strategy for an insurer in a hidden Markov regime-switching environment. A risk-based approach is considered, where the insurer aims at selecting an optimal strategy with a view to minimizing the risk described by a convex risk measure of its terminal wealth. We solve the problem in two steps. First, we employ the filtering theory to turn the optimization problem with partial observations into one with complete observations. Second, by using BSDEs with jumps, we solve the problem with complete observations.     

A simplex social spider algorithm for solving integer programming and minimax problems

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.     

Minimax pointwise estimation of an anisotropic regression function with unknown density of the design

Our aim in this paper is to estimate with best possible accuracy an unknown multidimensional regression function at a given point where the design density is also unknown. To reach this goal, we will follow the minimax approach: it will be assumed that the regression function belongs to a known anisotropic Hölder space. In contrast to the parameters defining the Hölder space, the density of the observations is assumed to be unknown and will be treated as a nuisance parameter. New minimax rates are exhibited as well as local polynomial estimators which achieve these rates. As these estimators depend on a tuning parameter, the problem of its selection is also discussed.