Analysis of the objective space in multiple objective linear programming

A multiple objective linear program is defined by a matrix C consisting of the coefficients of the linear objectives and a convex polytope X defined by the linear constraints. An analysis of the objective space Y = C[X] for this problem is presented. A characterization between a face of Y and the corresponding faces of X is obtained. This result gives a necessary and sufficient condition for a face to be efficient. The theory and examples demonstrate the collapsing (simplification) that occurs in mapping X to Y. These results form a basis for a new approach to analyzing multiple objective linear programs.     

On some methods for entropy maximization and matrix scaling

We describe and survey in this paper iterative algorithms for solving the discrete maximum entropy problem with linear equality constraints. This problem has applications e.g. in image reconstruction from projections, transportation planning, and matrix scaling. In particular we study local convergence and asymptotic rate of convergence as a function of the iteration parameter. For the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums, it is shown how the iteration parameters can be chosen in an optimal way. We also consider the related problem of finding a matrix X, diagonally similar to a given matrix, such that corresponding row and column norms in X are all equal. Reports of some numerical tests are given.     

Ordinals and set-valued zero-selections for hyperspaces

A continuous zero-selection f for the Vietoris hyperspace F(X) of the nonempty closed subsets of a space X is a Vietoris continuous map f:F(X)→X which assigns to every nonempty closed subset an isolated point of it. It is well known that a compact space X has a continuous zero-selection if and only if it is an ordinal space, or, equivalently, if X can be mapped onto an ordinal space by a continuous one-to-one surjection. In this paper, we prove that a compact space X has an upper semi-continuous set-valued zero-selection for its Vietoris hyperspace F(X) if and only if X can be mapped onto an ordinal space by a continuous finite-to-one surjection.     

Structure of modules over the stereotype algebra ℒ(X) of operators

It is well known that every module M over the algebra ?(X) of operators on a finite-dimensional space X can be represented as the tensor product of X by some vector space E, M ? = E ? X. We generalize this assertion to the case of topological modules by proving that if X is a stereotype space with the stereotype approximation property, then for each stereotype module M over the stereotype algebra ? (X) of operators on X there exists a unique (up to isomorphism) stereotype space E such that M lies between two natural stereotype tensor products of E by X, $E \circledast X \subseteq M \subseteq E \odot X.$ . As a corollary, we show that if X is a nuclear Fréchet space with a basis, then each Fréchet module M over the stereotype operator algebra ?(X) can be uniquely represented as the projective tensor product of X by some Fréchet space E, $M = E \widehat \otimes X$ .     

Almost all triple systems with independent neighborhoods are semi-bipartite

The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erd?s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

A local relaxation method for the cardinality constrained portfolio optimization problem

The NP-hard nature of cardinality constrained mean-variance portfolio optimization problems has led to a number of different algorithms with varying degrees of success in reaching optimality given limited computational resources and under the presence of strict time constraints present in practice. The proposed local relaxation algorithm explores the inherent structure of the objective function. It solves a sequence of small, local, quadratic-programs by first projecting asset returns onto a reduced metric space, followed by clustering in this space to identify sub-groups of assets that best accentuate a suitable measure of similarity amongst different assets. The algorithm can either be cold started using a suitable heuristic method such as the centroids of initial clusters or be warm started based on the last output. Results, using a basket of up to 3,000 stocks and with different cardinality constraints, indicates that the proposed algorithm can lead to significant performance gain over popular branch-and-cut methods. One key application of this algorithm is in dealing with large scale cardinality constrained portfolio optimization under tight time constraint, such as for the purpose of index tracking or index arbitrage at high frequency.     

Local equivalence relations

In this paper, we investigate the concept of local equivalence relation, a notion suggested by Grothendieck. A local equivalence relation on a topological space X is a global section of the sheaf of germs of equivalence relations on X. We investigate the extent to which a local equivalence relation can be described by a global one and analogously when can a global equivalence relation be recovered from its associated local one. We also look at the notion of a fiber map, which sheds further light on these concepts. A motivating example is that of a foliation on a manifold.     

Non-regular power homogeneous spaces

We show that the cardinality of any space X with Δ-power homogeneous semiregularization that is either Urysohn or quasiregular is bounded by ²c(X)πχ(X). This improves a result of G.J. Ridderbos who showed this bound holds for Δ-power homogeneous regular spaces. By introducing the notion of a local πθ-base, we show that this bound can be further sharpened. We also show that no H-closed extremally disconnected space is power homogeneous. This is a variation of a result of K. Kunen who showed that no compact F-space is power homogeneous.     

Convexity of momentum maps: A topological analysis

The Local-to-Global-Principle used in the proof of convexity theorems for momentum maps has been extracted as a statement of pure topology enriched with a structure of convexity. We extend this principle to not necessarily closed maps f:X→Y where the convexity structure of the target space Y need not be based on a metric. Using a new factorization of f, convexity of the image is proved without local fiber connectedness, and for arbitrary connected spaces X.     

Lipschitz-type functions on metric spaces

In order to find metric spaces X for which the algebra Lip^∗(X) of bounded Lipschitz functions on X determines the Lipschitz structure of X, we introduce the class of small-determined spaces. We show that this class includes precompact and quasi-convex metric spaces. We obtain several metric characterizations of this property, as well as some other characterizations given in terms of the uniform approximation and the extension of uniformly continuous functions. In particular we show that X is small-determined if and only if every uniformly continuous real function on X can be uniformly approximated by Lipschitz functions.     

Soft car sequencing with colors: Lower bounds and optimality proofs

This paper is a study of the car sequencing problem, when feature spacing constraints are soft and colors of vehicles are taken into account. Both pseudo-polynomial algorithms and lower bounds are presented for parts of the problem or family of instances. With this set of lower bounds, we establish the optimality (up to the first non-trivial criteria) of 54% of best known solutions for the benchmark used for the Roadef Challenge 2005. We also prove that the optimal penalty for a single ratio constraint N/P can be computed in O(P) and that determining the feasibility of a car sequencing instance limited to a pair of simple ratio constraints can be achieved by dynamic programming. Finally, we propose a solving algorithm exploiting these results within a local search approach. To achieve this goal, a new meta-heuristic (star relinking) is introduced, designed for the optimization of an aggregation of criteria, when the optimization of each single criterion is a polynomial problem.     

A subanalytic triangulation theorem for real analytic orbifolds

Let X be a real analytic orbifold. Then each stratum of X is a subanalytic subset of X. We show that X has a unique subanalytic triangulation compatible with the strata of X. We also show that every Cr-orbifold, 1?r?∞, has a real analytic structure. This allows us to triangulate differentiable orbifolds. The results generalize the subanalytic triangulation theorems previously known for quotient orbifolds.     

Fundamental groups and finite sheeted coverings

It is well known that for a connected locally path-connected semi-locally 1-connected space X, there exists a bi-unique correspondence between the pointed d-fold connected coverings and the transitive representations of the fundamental group of X in the symmetric group Σ_d of degree d.The classification problem becomes more difficult if X is a more general space, particularly if X is not locally connected. In attempt to solve the problem for general spaces, several notions of coverings have been introduced, for example, those given by Lubkin or by Fox. On the other hand, different notions of ‘fundamental group’ have appeared in the mathematical literature, for instance, the Brown-Grossman-Quigley fundamental group, the ?ech-Borsuk fundamental group, the Steenrod-Quigley fundamental group, the fundamental profinite group or the fundamental localic group.The main result of this paper determines different ‘fundamental groups’ that can be used to classify pointed finite sheeted connected coverings of a given space X depending on topological properties of X.     

Noetherian types of homogeneous compacta and dyadic compacta

The Noetherian type of a space is the least κ such that it has a base that is κ-like with respect to reverse inclusion. Just as all known homogeneous compacta have cellularity at most c, they satisfy similar upper bounds in terms of Noetherian type and related cardinal functions. We prove these and many other results about these cardinal functions. For example, every homogeneous dyadic compactum has Noetherian type ω. Assuming GCH, every point in a homogeneous compactum X has a local base that is c(X)-like with respect to containment. If every point in a compactum has a well-quasiordered local base, then some point has a countable local π-base.     

Premium principles and translation invariance

Premium principles τ are examined with respect to the property of translation invariance, that means τ(X + c) = τ(X) + c holds for all real c (and all risks X). It is shown that this condition of translation invariance is highly overdetermined: For all known principles the range of c can be reduced to a large extent from all the reals to only two (or one) single values of c respectively.     

Banach space properties sufficient for normal structure

In this paper we establish lower bounds for the weakly convergent sequence coefficient WCS(X) of a Banach space X, in terms of some well known moduli and coefficients. By mean of these bounds we identify several properties, of geometrical nature, which imply normal structure. We show that these properties are strictly more general than other previously known sufficient conditions for normal structure.     

Idempotent elements of the semigroup corresponding to an X-semilattice of unions of the class Σ16(X, 6)

It is known that if we know all XI-subsemilattices of a given X-semilattice of unions, then we can determine all idempotent elements of the semigroup, and the structure of idempotent elements is characterized. In this work, we find idempotent elements of the semigroup corresponding to X-semilattices of unions of the class ??₁₆(X, 6). Moreover, we give formulas for the number of idempotent elements, where X is finite.     

Geometric Models for Quasicrystals II. Local Rules Under Isometries

The atomic structures of quasicrystalline materials exhibit long range order under translations. It is believed that such materials have atomic structures which approximately obey local rules restricting the location of nearby atoms. These local constraints are typically invariant under rotations, and it is of interest to establish conditions under which such local rules can nevertheless enforce order under translations in any structure that satisfies them. A set of local rules in is a finite collection of discrete sets {Y _i } containing 0, each of which is contained in the ball of radius ρ around 0 in . A set X satisfies the local rules under isometries if the ρ -neighborhood of each is isometric to an element of . This paper gives sufficient conditions on a set of local rules such that if X satisfies under isometries, then X has a weak long-range order under translations, in the sense that X is a Delone set of finite type. A set X is a Delone set of finite type if it is a Delone set whose interpoint distance set X-X is a discrete closed set. We show for each minimal Delone set of finite type X that there exists a set of local rules such that X satisfies under isometries and all other Y that satisfy under isometries are Delone sets of finite type. A set of perfect local rules (under isometries or under translations, respectively) is a set of local rules such that all structures X that satisfy are in the same local isomorphism class (under isometries or under translations, respectively). If a Delone set of finite type has a set of perfect local rules under translations, then it has a set of perfect local rules under isometries, and conversely. Received February 14, 1997, and in revised form February 14, 1998, February 19, 1998, and March 5, 1998.     

Separable complete ANR's admitting a group structure are Hilbert manifolds

Let X be a complete-metrizable, separable ANR. The following two facts are shown: (a) if X admits a topological group structure, then either this is a Lie group structure or X is an l₂-manifold; (b) If X is a closed convex set in a complete metric linear space, then X is either locally compact or homeomorphic to l₂.