A variational approach to define robustness for parametric multiobjective optimization problems

In contrast to classical optimization problems, in multiobjective optimization several objective functions are considered at the same time. For these problems, the solution is not a single optimum but a set of optimal compromises, the so-called Pareto set. In this work, we consider multiobjective optimization problems that additionally depend on an external parameter ${\lambda \in \mathbb{R}}$ , so-called parametric multiobjective optimization problems. The solution of such a problem is given by the λ-dependent Pareto set. In this work we give a new definition that allows to characterize λ-robust Pareto points, meaning points which hardly vary under the variation of the parameter λ. To describe this task mathematically, we make use of the classical calculus of variations. A system of differential algebraic equations will turn out to describe λ-robust solutions. For the numerical solution of these equations concepts of the discrete calculus of variations are used. The new robustness concept is illustrated by numerical examples.     

Ultrapowers ofL 1(μ) and the subsequence splitting principle

We study the ultrapowers $L_1 (\mu )_\mathfrak{U} $ of aL ₁(μ) space, by describing the components of the well-known representation $L_1 (\mu )_\mathfrak{U} = L_1 (\mu _\mathfrak{U} ) \oplus _1 L_1 (\nu _\mathfrak{U} )$ , and we give a representation of the projection from $L_1 (\mu )_\mathfrak{U} $ onto $L_1 (\mu _\mathfrak{U} )$ . Moreover, the subsequence splitting principle forL ₁(μ) motivates the following question: if $\mathfrak{V}$ is an ultrafilter on ? and $[f_i ] \in L_1 (\mu )_\mathfrak{V} $ , is it possible to find a weakly convergent sequence (g _i ) ?L ₁(μ) following $\mathfrak{V}$ and a disjoint sequence (h _i ) ?L ₁(μ) such that [f _i ]=[g _i ]+[h _i ]? If $\mathfrak{V}$ is a selective ultrafilter, we find a positive answer by showing that $f = [f_i ] \in L_1 (\mu )_\mathfrak{V} $ belongs to $L_1 (\mu _{_\mathfrak{V} } )$ if and only if its representatives {f _i } are weakly convergent following $\mathfrak{V}$ and $f \in L_1 (\nu _\mathfrak{V} )$ if and only if it admits a representative consisting of pairwise disjoint functions. As a consequence, we obtain a new proof of the subsequence splitting principle. If $\mathfrak{V}$ is not a p-point then the above characterizations of $L_1 (\nu _{_\mathfrak{V} } )$ and $L_1 (\nu _{_\mathfrak{V} } )$ fail and the answer to the question is negative.     

The Nakamura Theorem for coalition structures of quota games

This paper considers a model of society $S$ with a finite number of individuals,n, a finite set off alternatives, Ω effective coalitions that must contain ana priori given numberq of individuals. Its purpose is to extend the Nakamura Theorem (1979) to the quota games where individuals are allowed to form groups of sizeq which are smaller than the grand coalition. Our main result determines the upper bound on the number of alternatives which would guarantee, for a given e andq, the existence of a stable coalition structure for any profile of complete transitive preference relations. Our notion of stability, $S$ -equilibrium, introduced by Greenberg-Weber (1993), combines bothfree entry andfree mobility and represents the natural extension of the core to improper or non-superadditive games where coalition structures, and not only the grand coalition, are allowed to form.     

Determination of the element numbers of the regular polytopes

Let ?? be a set of n-dimensional polytopes. A set ?? of n-dimensional polytopes is said to be an element set for ?? if each polytope in ?? is the union of a finite number of polytopes in ?? identified along (n ? 1)-dimensional faces. The element number of the set ?? of polyhedra, denoted by e(??), is the minimum cardinality of the element sets for ??, where the minimum is taken over all possible element sets ${\Omega \in \mathcal{E}(\Sigma)}$ . It is proved in Theorem 1 that the element number of the convex regular 4-dimensional polytopes is 4, and in Theorem 2 that the element numbers of the convex regular n-dimensional polytopes is 3 for n ?? 5. The results in this paper together with our previous papers determine completely the element numbers of the convex regular n-dimensional polytopes for all n ?? 2.     

On constrained and regularized high-dimensional regression

High-dimensional feature selection has become increasingly crucial for seeking parsimonious models in estimation. For selection consistency, we derive one necessary and sufficient condition formulated on the notion of degree of separation. The minimal degree of separation is necessary for any method to be selection consistent. At a level slightly higher than the minimal degree of separation, selection consistency is achieved by a constrained $L_0$ -method and its computational surrogate—the constrained truncated $L_1$ -method. This permits up to exponentially many features in the sample size. In other words, these methods are optimal in feature selection against any selection method. In contrast, their regularization counterparts—the $L_0$ -regularization and truncated $L_1$ -regularization methods enable so under slightly stronger assumptions. More importantly, sharper parameter estimation/prediction is realized through such selection, leading to minimax parameter estimation. This, otherwise, is impossible in the absence of a good selection method for high-dimensional analysis.     

The type and stable type of the boundary of a Gromov hyperbolic group

Consider an ergodic non-singular action \(\Gamma \curvearrowright B\) of a countable group on a probability space. The type of this action codes the asymptotic range of the Radon–Nikodym derivative, also called the ratio set. If \(\Gamma \curvearrowright X\) is a pmp (probability-measure-preserving) action, then the ratio set of the product action \(\Gamma \curvearrowright B\times X\) is contained in the ratio set of \(\Gamma \curvearrowright B\) . So we define the stable ratio set of \(\Gamma \curvearrowright B\) to be the intersection over all pmp actions \(\Gamma \curvearrowright X\) of the ratio sets of \(\Gamma \curvearrowright B\times X\) . By analogy, there is a notion of stable type which codes the stable ratio set of \(\Gamma \curvearrowright B\) . This concept is crucially important for the identification of the limit in pointwise ergodic theorems established by the author and Amos Nevo. Here, we establish a general criteria for a nonsingular action of a countable group on a probability space to have stable type \(III_\lambda \) for some \(\lambda >0\) . This is applied to show that the action of a non-elementary Gromov hyperbolic group on its boundary with respect to a quasi-conformal measure is not type \(III_0\) and, if it is weakly mixing, then it is not stable type \(III_0\) .     

A generalization of the Nash equilibrium theorem on bimatrix games

In this article, we consider a two-person game in which the first player picks a row representative matrixM from a nonempty set $A$ ofm ×n matrices and a probability distributionx on {1,2,...,m} while the second player picks a column representative matrixN from a nonempty set ? ofm ×n matrices and a probability distribution y on 1,2,...,n. This leads to the respective costs ofx ^t My andx ^t Ny for these players. We establish the existence of an ?-equilibrium for this game under the assumption that $A$ and ? are bounded. When the sets $A$ and ? are compact in ?^mxn, the result yields an equilibrium state at which stage no player can decrease his cost by unilaterally changing his row/column selection and probability distribution. The result, when further specialized to singleton sets, reduces to the famous theorem of Nash on bimatrix games.     

The Two-Weighted Inequalities for Sublinear Operators Generated by B Singular Integrals in Weighted Lebesgue Spaces

In this paper, the authors establish several general theorems for the boundedness of sublinear operators (B sublinear operators) satisfies the condition (1.2), generated by B singular integrals on a weighted Lebesgue spaces $L_{p,\omega,\gamma}(\mathbb{R}_{k,+}^{n})$ , where $B=\sum_{i=1}^{k} (\frac{\partial^{2}}{\partial x_{k}^{2}} + \frac{\gamma_{i}}{x_{i}}\frac{\partial}{\partial x_{i}} )$ . The condition (1.2) are satisfied by many important operators in analysis, including B maximal operator and B singular integral operators. Sufficient conditions on weighted functions ω and ω ₁ are given so that B sublinear operators satisfies the condition (1.2) are bounded from $L_{p,\omega,\gamma}(\mathbb{R}_{k,+}^{n})$ to $L_{p,\omega_{1},\gamma}(\mathbb{R}_{k,+}^{n})$ .     

K-Functionals and Exact Values of n-Widths of Certain Classes in the Spaces C(2\pi ) and L_1 (2\pi )

For classes of $2\pi $ -periodic functions whose K-functionals are majorized by functions satisfying certain constraints, exact values of Kolmogorov, Bernstein, and trigonometric n-widths in the spaces $C(2\pi )$ and $L_1 (2\pi )$ are obtained. Examples of majorants that satisfy the requirements stated in this paper are given.     

The influence of large coalitions

This paper contains two results on influence in collective decision games. The first part deals with general perfect information coin-flipping games as defined in [3].Baton passing (see [8]), ann-player game from this class is shown to have the following property: IfS is a coalition of size at most \(\frac{n}{{3\log n}}\) , then the influence ofS on the game is only \(O\left( {\frac{{\left| S \right|}}{n}} \right)\) . This complements a result from [3] that for everyk there is a coalition of sizek with influence Ω(k/n). Thus the best possible bounds on influences of coalitions of size up to this threshold are known, and there need not be coalitions up to this size whose influence asymptotically exceeds their fraction of the population. This result may be expected to play a role in resolving the most outstanding problem in this area: Does everyn-player perfect information coin flipping game have a coalition ofo(n) players with influence 1?o(1)? (Recently Alon and Naor [1] gave a negative answer to this question.) In a recent paper Kahn, Kalai and Linial [7] showed that for everyn-variable boolean function of expectation bounded away from zero and one, there is a set of \(\frac{{n\omega (n)}}{{\log n}}\) variables whose influence is 1?o(1), wherew(n) is any function tending to infinity withn. They raised the analogous question where 1?o(1) is replaced by any positive constant and speculated that a constant influence may be always achievable by significantly smaller sets of variables. This problem is almost completely solved in the second part of this article where we establish the existence of boolean functions where only sets of at least \(\Omega \left( {\frac{n}{{\log ^2 n}}} \right)\) variables can have influence bounded away from zero.     

Optimal Set of the Modulus of Continuity in the Sharp Jackson Inequality in the Space $$L_2 $$

To a function $f \in L_2 [ - \pi ,\pi ]$ and a compact set $Q \subset [ - \pi ,\pi ]$ we assign the supremum $\omega (f,Q) = \sup _{t \in Q} ||f( \cdot + t) - f( \cdot )||_{L_2 [ - \pi ,\pi ]} $ , which is an analog of the modulus of continuity. We denote by $K(n,Q)$ the least constant in Jackson's inequality between the best approximation of the function f by trigonometric polynomials of degree $n - 1$ in the space $L_2 [ - \pi ,\pi ]$ and the modulus of continuity $\omega (f,Q)$ . It follows from results due to Chernykh that $K(n,Q) \geqslant 1/\sqrt 2 $ and $K(n,[0,\pi /\pi ]) = 1/\sqrt 2 $ . On the strength of a result of Yudin, we show that if the measure of the set Q is less than $\pi /n$ , then $K(n,Q) >1/\sqrt 2 $ .     

Stasheff polytopes and the coordinate ring of the cluster \mathcal X -variety of type A_n

We define Stasheff polytopes in the spaces of tropical points of cluster \(\mathcal A \) -varieties. We study the supports of products of elements of canonical bases for cluster \(\mathcal X \) -varieties. We prove that, for the cluster \(\mathcal X \) -variety of type \(A_n\) , such supports are Stasheff polytopes.     

On the existence of an equivalent supermartingale density for a fork-convex family of stochastic processes

We prove that a fork-convex family $ \mathbb{W} $ of nonnegative stochastic processes has an equivalent supermartingale density if and only if the setH of nonnegative random variables majorized by the values of elements of $ \mathbb{W} $ at fixed instants of time is bounded in probability. A securities market model with arbitrarily many main risky assets, specified by the set $ \mathbb{W}\left( \mathbb{S} \right) $ of nonnegative stochastic integrals with respect to finite collections of semimartingales from an arbitrary indexed family S, satisfies the assumptions of this theorem.     

Under which conditions is the Jacobi space L_{w^{(a,b)} }^p [ - 1,1] subset of L_{w^{(\alpha ,\beta )} }^1 [ - 1,1] ?

Exact conditions for α, β, a, b > ?1 and 1 ≤ p ≤ ∞ are determined under which the inclusion property $L_{w^{(a,b)} }^p [ - 1,1]$ ? $L_{w^{(\alpha ,\beta )} }^1 [ - 1,1]$ is valid. It is shown that the conditions characterize the inclusion property. The paper concludes with some results, in which the inclusion property can be detected in relation with estimates of Jacobi differential operators and with Muckenhoupt’s transplantation theorems and multiplier theorems for Jacobi series.     

Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem

This paper presents branch-and-bound algorithms for the partial inverse mixed integer linear programming (PInvMILP) problem, which is to find a minimal perturbation to the objective function of a mixed integer linear program (MILP), measured by some norm, such that there exists an optimal solution to the perturbed MILP that also satisfies an additional set of linear constraints. This is a new extension to the existing inverse optimization models. Under the weighted $L_1$ and $L_\infty $ norms, the presented algorithms are proved to finitely converge to global optimality. In the presented algorithms, linear programs with complementarity constraints (LPCCs) need to be solved repeatedly as a subroutine, which is analogous to repeatedly solving linear programs for MILPs. Therefore, the computational complexity of the PInvMILP algorithms can be expected to be much worse than that of MILP or LPCC. Computational experiments show that small-sized test instances can be solved within a reasonable time period.     

An analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.     

Affine Mirković-Vilonen polytopes

Each integrable lowest weight representation of a symmetrizable Kac-Moody Lie algebra \(\mathfrak{g}\) has a crystal in the sense of Kashiwara, which describes its combinatorial properties. For a given \(\mathfrak{g}\) , there is a limit crystal, usually denoted by B(?∞), which contains all the other crystals. When \(\mathfrak{g}\) is finite dimensional, a convex polytope, called the Mirkovi?-Vilonen polytope, can be associated to each element in B(?∞). This polytope sits in the dual space of a Cartan subalgebra of \(\mathfrak{g}\) , and its edges are parallel to the roots of \(\mathfrak{g}\) . In this paper, we generalize this construction to the case where \(\mathfrak{g}\) is a symmetric affine Kac-Moody algebra. The datum of the polytope must however be complemented by partitions attached to the edges parallel to the imaginary root δ. We prove that these decorated polytopes are characterized by conditions on their normal fans and on their 2-faces. In addition, we discuss how our polytopes provide an analog of the notion of Lusztig datum for affine Kac-Moody algebras. Our main tool is an algebro-geometric model for B(?∞) constructed by Lusztig and by Kashiwara and Saito, based on representations of the completed preprojective algebra Λ of the same type as  \(\mathfrak{g}\) . The underlying polytopes in our construction are described with the help of Buan, Iyama, Reiten and Scott’s tilting theory for the category \(\Lambda \text {\upshape -}\mathrm {mod}\) . The partitions we need come from studying the category of semistable Λ-modules of dimension-vector a multiple of δ.     

Nonzero-sum constrained discrete-time Markov games: the case of unbounded costs

In this paper, we consider discrete-time \(N\) -person constrained stochastic games with discounted cost criteria. The state space is denumerable and the action space is a Borel set, while the cost functions are admitted to be unbounded from below and above. Under suitable conditions weaker than those in (Alvarez-Mena and Hernández-Lerma, Math Methods Oper Res 63:261–285, 2006) for bounded cost functions, we also show the existence of a Nash equilibrium for the constrained games by introducing two approximations. The first one, which is as in (Alvarez-Mena and Hernández-Lerma, Math Methods Oper Res 63:261–285, 2006), is to construct a sequence of finite games to approximate a (constrained) auxiliary game with an initial distribution that is concentrated on a finite set. However, without hypotheses of bounded costs as in (Alvarez-Mena and Hernández-Lerma, Math Methods Oper Res 63:261–285, 2006), we also establish the existence of a Nash equilibrium for the auxiliary game with unbounded costs by developing more shaper error bounds of the approximation. The second one, which is new, is to construct a sequence of the auxiliary-type games above and prove that the limit of the sequence of Nash equilibria for the auxiliary-type games is a Nash equilibrium for the original constrained games. Our results are illustrated by a controlled queueing system.     

Symmetric Graphs from Polytopes of High Rank

Given a polytope ${{\mathcal{P}}}$ of rank 2n, the faces of middle ranks n ? 1 and n constitute the vertices of a bipartite graph, the medial layer graph ${{M(\mathcal{P})}}$ of ${{\mathcal{P}}}$ . The group ${{D(\mathcal{P})}}$ of automorphisms and dualities of ${{\mathcal{P}}}$ has a natural action on this graph. We prove algebraic and combinatorial conditions on ${{\mathcal{P}}}$ that ensure this action is transitive on k-arcs in ${{M(\mathcal{P})}}$ for some small k (in particular focussing on k?=?3), and provide examples of families of polytopes that satisfy these conditions. We also examine how ${{D(\mathcal{P})}}$ acts on the k-stars based at vertices of ${{M(\mathcal{P})},}$ and describe self-dual regular polytopes (in particular those of rank 6) for which this action is transitive on the k-stars for small k.     

Ein zerlegungssatz für P(ϰ)

We shall prove the following partition theorems:

1. For every setS and for each cardinal ? ≥ ω, |S| ≥ ? there exists a partitionT: [S]^? → 2^? such that for every pairwise disjoint familie and everyα < 2^? there exists a set
2. Suppose ? ≥ ω, 2 ^{andS an arbitrary set, 2|S| ≤ (2?)+ω Then there exists a partitionT: P(S) → 2? such that for every pairwise disjoint family and everyα < 2? there exists a set Both theorems will give partial answers to an Erd?s problem.}