Multisided matching games with complementarities

The paper considers multisided matching games with transfereable utility using the approach of cooperative game theory. Stable matchings are shown to exist when characteristic functions are supermodular, i.e., agents' abilities to contribute to the value of a coalition are complementary across types. We analyze the structure of the core of supermodular matching games and suggest an algorithm for constructing its extreme payoff vectors. Received February 1997/Final version September 1998     

Barycenters of extreme points in the cone of non-negative entire functions

In the cone of non-negative (on the real axis) entire functions, a certain simple functionf(x) is shown not to be the barycenter of any finite number of extreme functions. This is in contradistinction to S. Karlin's result that every non-negativepolynomial is the barycenter oftwo extreme ones.     

The problem of optimal control with reflection studied through a linear optimization problem stated on occupational measures

We obtain a linear programming characterization for the minimum cost associated with finite dimensional reflected optimal control problems. In order to describe the value functions, we employ an infinite dimensional dual formulation instead of using the characterization via Hamilton-Jacobi partial differential equations. In this paper we consider control problems with both infinite and finite horizons. The reflection is given by the normal cone to a proximal retract set.     

An FPTAS for optimizing a class of low-rank functions over a polytope

We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of non-linear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme does not require the assumption of quasi-concavity on the objective function. For the special case of quasi-concave function minimization, we give an alternative FPTAS, which always returns a solution which is an extreme point of the polytope. Our technique can also be used to obtain an FPTAS for combinatorial optimization problems with non-linear objective functions, for example when the objective is a product of a fixed number of linear functions. We also show that it is not possible to approximate the minimum of a general concave function over the unit hypercube to within any factor, unless P = NP. We prove this by showing a similar hardness of approximation result for supermodular function minimization, a result that may be of independent interest.     

Explicit convex and concave envelopes through polyhedral subdivisions

In this paper, we derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of concave-extendable supermodular functions and the convex envelopes of disjunctive convex functions.     

Strong Domain of Attraction of Extreme Generalized Order Statistics

It is a well-known result in extreme value theory that the von Mises conditions imply the strong convergence of extreme order statistics. We extend this result to extreme generalized order statistics. A characterization of strong domains of attraction of joint distributions of a fixed number of extreme generalized order statistics by means of the corresponding result for generalized maxima is given. In particular, we determine the asymptotic joint distribution of (upper and lower) extreme generalized order statistics. Finally, we show that the Hill estimator based on extreme generalized order statistics is asymptotic normal.     

A review on consistency and robustness properties of support vector machines for heavy-tailed distributions

Support vector machines (SVMs) belong to the class of modern statistical machine learning techniques and can be described as M-estimators with a Hilbert norm regularization term for functions. SVMs are consistent and robust for classification and regression purposes if based on a Lipschitz continuous loss and a bounded continuous kernel with a dense reproducing kernel Hilbert space. For regression, one of the conditions used is that the output variable Y has a finite first absolute moment. This assumption, however, excludes heavy-tailed distributions. Recently, the applicability of SVMs was enlarged to these distributions by considering shifted loss functions. In this review paper, we briefly describe the approach of SVMs based on shifted loss functions and list some properties of such SVMs. Then, we prove that SVMs based on a bounded continuous kernel and on a convex and Lipschitz continuous, but not necessarily differentiable, shifted loss function have a bounded Bouligand influence function for all distributions, even for heavy-tailed distributions including extreme value distributions and Cauchy distributions. SVMs are thus robust in this sense. Our result covers the important loss functions ${\epsilon}$ -insensitive for regression and pinball for quantile regression, which were not covered by earlier results on the influence function. We demonstrate the usefulness of SVMs even for heavy-tailed distributions by applying SVMs to a simulated data set with Cauchy errors and to a data set of large fire insurance claims of Copenhagen Re.     

Supermodular covering knapsack polytope

The supermodular covering knapsack set is the discrete upper level set of a non-decreasing supermodular function. Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. In a recent paper Atamtürk and Narayanan (2009) study the lower level set of a non-decreasing submodular function.In this complementary paper we describe pack inequalities for the supermodular covering knapsack set and investigate their separation, extensions and lifting. We give sequence-independent upper bounds and lower bounds on the lifting coefficients. Furthermore, we present a computational study on using the polyhedral results derived for solving 0–1 optimization problems over conic quadratic constraints with a branch-and-cut algorithm.     

Comparison results for exchangeable credit risk portfolios

This paper is dedicated to risk analysis of credit portfolios. Assuming that default indicators form an exchangeable sequence of Bernoulli random variables and as a consequence of de Finetti’s theorem, default indicators are Binomial mixtures. We can characterize the supermodular order between two exchangeable Bernoulli random vectors in terms of the convex ordering of their corresponding mixture distributions. Thus we can proceed to some comparisons between stop-loss premiums, CDO tranche premiums and convex risk measures on aggregate losses. This methodology provides a unified analysis of dependence for a number of CDO pricing models based on factor copulas, multivariate Poisson and structural approaches.     

On the supermodular knapsack problem

In this paper we introduce binary knapsack problems where the objective function is nonlinear, and investigate their Lagrangean and continuous relaxations. Some of our results generalize previously known theorems concerning linear and quadratic knapsack problems. We investigate in particular the case in which the objective function is supermodular. Under this hypothesis, although the problem remains NP-hard, we show that its Lagrangean dual and its continuous relaxation can be solved in polynomial time. We also comment on the complexity of recognizing supermodular functions. The particular case in which the knapsack constraint is of the cardinality type is also addressed and some properties of its optimal value as a function of the right hand side are derived.Work done while the authors were visiting Rutgers University.     

ESTIMATES OF LINEAR RELATIVE n-WIDTHS IN L~p [0,1]

In this paper we will show that if an approximation process { L n }n ∈ N is shapepreserving relative to the cone of all k-times differentiable functions with non-negative k-th derivative on [0,1],and the operators L n are assumed to be of finite rank n,then the order of convergence of D k L n f to D k f cannot be better than n 2 even for the functions x k,x k+1,x k+2 on any subset of [0,1] with positive measure.Taking into account this fact,we will be able to find some asymptotic estimates of linear relative n-width of sets of differentiable functions in the space L p [0,1],p ∈ N.     

On the extreme inequalities of infinite group problems

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous. S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611.     

Supermodularity in Various Partition Problems

Supermodular and submodular functions have attracted a great deal of attention since the seminal paper of Lovász. Recently, supermodular functions were studied in the context of some optimal partition problems. We completely answer a question arisen there whether a certain partition function is supermodular.     

超级模数博弈的存在性

本文定义了一类在有序Banach空间上的超模博弈,并利用著名的Birkhoff不动点定理证明了有序Banach空间上超模博弈Nash均衡的存在性.     

Remarkable polyhedra related to set functions,games and capacities

Set functions are widely used in many domains of operations research (cooperative game theory, decision under risk and uncertainty, combinatorial optimization) under different names (TU-game, capacity, nonadditive measure, pseudo-Boolean function, etc.). Remarkable families of set functions form polyhedra, e.g., the polytope of capacities, the polytope of p-additive capacities, the cone of supermodular games, etc. Also, the core of a set function, defined as the set of additive set functions dominating that set function, is a polyhedron which is of fundamental importance in game theory, decision-making and combinatorial optimization. This survey paper gives an overview of these notions and studies all these polyhedra.     

Geometry of the copositive and completely positive cones

The copositive cone, and its dual the completely positive cone, have useful applications in optimisation, however telling if a general matrix is in the copositive cone is a co-NP-complete problem. In this paper we analyse some of the geometry of these cones. We discuss a way of representing all the maximal faces of the copositive cone along with a simple equation for the dimension of each one. In doing this we show that the copositive cone has faces which are isomorphic to positive semidefinite cones. We also look at some maximal faces of the completely positive cone and find their dimensions. Additionally we consider extreme rays of the copositive and completely positive cones and show that every extreme ray of the completely positive cone is also an exposed ray, but the copositive cone has extreme rays which are not exposed rays.     

Preface

The problem of maximizing a pseudoboolean function (or equivalently a set function) which is supermodular, has many interesting applications e.g. in combinatorial optimization, Operations Research etc. Up to now, a number of special cases of pseudoboolean functions have been known, the maximization of which can be converted into the search for a maximum flow in an associated network. These were essentially the so-called negative-positive pseudoboolean functions (which, as will be noted here, turn out to be supermodular). First it is shown here how these results on negative-positive functions can be more easily derived by using the concept of conflict graph. The conflict graph approach is then generalized to extend the class of problems amenable to maximum network flow problems to the whole set of cubic supermodular pseudoboolean functions.     

Approximations for Bivariate Extreme Values

We study the tail behavior of distributions in the domain of attraction of bivariate extreme value distributions (this includes bivariate extreme value distributions themselves). We provide results on finite approximations of the tail behavior and its analytical shape. The results could form a basis to improve current statistical modeling of bivariate extreme values.     

Exact inference for a simple step-stress model from the exponential distribution under time constraint

In reliability and life-testing experiments, the researcher is often interested in the effects of extreme or varying stress factors such as temperature, voltage and load on the lifetimes of experimental units. Step-stress test, which is a special class of accelerated life-tests, allows the experimenter to increase the stress levels at fixed times during the experiment in order to obtain information on the parameters of the life distributions more quickly than under normal operating conditions. In this paper, we consider the simple step-stress model from the exponential distribution when there is time constraint on the duration of the experiment. We derive the maximum likelihood estimators (MLEs) of the parameters assuming a cumulative exposure model with lifetimes being exponentially distributed. The exact distributions of the MLEs of parameters are obtained through the use of conditional moment generating functions. We also derive confidence intervals for the parameters using these exact distributions, asymptotic distributions of the MLEs and the parametric bootstrap methods, and assess their performance through a Monte Carlo simulation study. Finally, we present two examples to illustrate all the methods of inference discussed here.