Partly convex programming and zermelo's navigation problems

Mathematical programs, that become convex programs after freezing some variables, are termed partly convex. For such programs we give saddle-point conditions that are both necessary and sufficient that a feasible point be globally optimal. The conditions require cooperation of the feasible point tested for optimality, an assumption implied by lower semicontinuity of the feasible set mapping. The characterizations are simplified if certain point-to-set mappings satisfy a sandwich condition.The tools of parametric optimization and basic point-to-set topology are used in formulating both optimality conditions and numerical methods. In particular, we solve a large class of Zermelo's navigation problems and establish global optimality of the numerical solutions.Research partly supported by NSERC of Canada.     

Convergence of diagonally stationary sequences in convex optimization

LetX be a real normed linear space,f, f ⁿ, n , be extended real-valued proper closed convex functions onX. A sequence {x _n} inX is called diagonally stationary for {f ⁿ} if for alln there existsx* _n f ⁿ (x _n) such that x* _{n *} 0. Such sequences arise in approximation methods for the problem of minimizingf. Some general convergence results based upon variational convergence theory and appropriate equi-well-posedness are presented.     

k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

On the uniqueness of a local martingale with a given absolute value

Summary D. Gilat has shown that any non-negative submartingale (X, .) is equal in law to the absolute value of a martingale (M, .). This result may be strenthened so that the pairs (X,.) and (¦M¦,.) are synonomous. In this paper the question of uniqueness of M is considered. Conditions on a local martingale (M, .) are found that lead to an explicit formula for the finite-dimensional distributions of M in terms of the Doob-Meyer decomposition of the local martingale X. In many cases of interest the conditions on M are unnecessary. For example, if X is the pth power of an Itô integral it is shown that (M) is unique if p> 1 but not in general if p=1.     

Primitive Inner Illuminating Systems for Convex Bodies

A set X of boundary points of a (possibly unbounded) convex body KE ^d illuminating K from within is called primitive if no proper subset of X still illuminates K from within. We prove that for such a primitive set X of an unbounded, convex set KE ^d (distinct from a cone) one has X=2 if d=2, X6 if d=3, and that there is no upper bound for X if d4.     

Computations in choice groupoids

Defining achoice as a mapping of the subsets of a setX into their respective subsets, a one-to-one (and naturally) corresponding binary operation,sequential choice, is identified under which the power set ofX is closed as achoice groupoid. A complete logical diagram is given, exhibiting all the implications between conjunctions of the seven conditions: (1) idempotence, (2) consistency, (3) absorbence, and (4) homomorphism of a choice, and (5) commutativity, (6) associativity, and (7) path-independence of the corresponding sequential choice.     

Orientations of chain groups

We prove generalizations to chain groups, of Minty's Arc Colouring Lemma and its extension, the well-known Farkas Lemma. In these the orientation of the edges is replaced by an arbitrary chain.A function on a chain groupN isrepresentable if there exists a chainR such that (X)=R·X for allXN. Anorientation is a chain with values ±1. We prove that for a regular chain group a linear function that is representable by an orientation for each chainXN locally, is representable by an orientation globally.     

An existence theorem for generalized quasi-variational inequalities

In this paper, we deal with the following generalized quasi-variational inequality problem: given a closed convex subsetX ⁿ , a multifunction :X 2 ⁿ and a multifunction :X 2 ^X , find a point ( ) X × ⁿ such that We prove an existence theorem in which, in particular, the multifunction is not supposed to be upper semicontinuous.     

An Inequality for Tail Probabilities of Martingales with Bounded Differences

Let M _n =X₁+...+X_n be a martingale with bounded differences X_m=M_m-M_m-1 such that {|X_m| _m}=1 with some nonnegative _m. Write ²= ₁ ² + ... + _n ² . We prove the inequalities {M _nx}c(1-(x/)), {M _n x} 1- c(1- (-x/)) with a constant . The result yields sharp inequalities in some models related to the measure concentration phenomena.     

On the singular graph and the Weyr characteristic of anM-matrix

LetA be anM-matrix in standard lower block triangular form, with diagonal blocksA _ii irreducible. LetS be the set of indices such that the diagonal blockA is singular. We define the singular graph ofA to be the setS with partial order defined by > if there exists a chain of non-zero blocksA _i, A_ij, , A_l.Let ₁ be the set of maximal elements ofS, and define thep-th level _p ,p = 2, 3, , inductively as the set of maximal elements ofS \( _{1 p-1}). Denote by _p the number of elements in _p . The Weyr characteristic (associated with 0) ofA is defined to be (A) = ( ₁, ₂,, _h ), where ₁ + + _p = dim KerA ^p ,p = 1, 2, , and _h > 0, _h+1 = 0.Using a special type of basis, called anS-basis, for the generalized eigenspaceE(A) of 0 ofA, we associate a matrixD withA. We show that(A) = ( ₁, , _h) if and only if certain submatricesD _p,p+1 ,p = 1, , h – 1, ofD have full column rank. This condition is also necessary and sufficient forE(A) to have a basis consisting of non-negative vectors, which is a Jordan basis for –A. We also consider a given finite partially ordered setS, and we find a necessary and sufficient condition that allM-matricesA with singular graphS have(A) = ( ₁, , _h). This condition is satisfied ifS is a rooted forest.The work of the second-named author was partly supported by the National Science Foundation, under grant MPS-08618 A02.     

Asymptotic analysis of the exponential penalty trajectory in linear programming

We consider the linear program min{cx: Axb} and the associated exponential penalty functionf _r(x) = cx + rexp[(A _ix – b_i)/r]. Forr close to 0, the unconstrained minimizerx(r) off _r admits an asymptotic expansion of the formx(r) = x ^* + rd^* + (r) wherex ^* is a particular optimal solution of the linear program and the error term(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to : the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.Corresponding author. Both authors partially supported by FONDECYT.     

Predictable projections for point process filtrations

Summary We consider a point process with the Polish phase space (X,X) and a system of -fields (x),xX, generated by on certain sets (x)X. We define predictability for random processes indexed byX and for random measures onX and prove the existence and uniqueness of predictable and dual predictable projections under a regularity condition on . ForX= ₂ ⁺ and under monotonicity assumptions on the sets x we will identify the predictable projections of some simple processes as regular versions of certain martingales.     

Metrics with finite sets of primitive extensions

In this paper, we give a complete characterization for the class of rational finite metrics with the property that the set () of primitive extensions of is finite. Here, for a metric on a setT, a positive extensionm of to a setV T is calledprimitive if none of the convex combinations of other extensions of toV is less than or equal tom. Our main theorem asserts that the following the properties are equivalent: (i) () is finite; (ii) Up to an integer factor, is a submetric of the path metric d ^H of a graphH with |(d ^H )=1; (iii) A certain bipartite graph associated with contains neither isometrick-cycles withk6 nor induced subgraphsK _3,3 ^– . We then show that () is finite if and only if the dimension of the tight span of is at most two. We also present other results, discuss applications to multicommodity flows, and raise open problems.This research was supported by grant 97-01-00115 from the Russian Foundation of Basic Research and a grant from the Sonderforschungsbereich 343, Bielefeld Universität, Bielefeld, Germany.     

φ-Factors for Function Seminorms

Let (, A, ) be a measure space, a function seminorm on M, the space of measurable functions on , and M the space {f M : (f) < }. Every Borel measurable function : [0, ) [0, ) induces a function : M M by (f)(x) = (|f(x)|). We introduce the concepts of -factor and -invariant space. If is a -subadditive seminorm function, we give, under suitable conditions over , necessary and sufficient conditions in order that M be invariant and prove the existence of -factors for . We also give a characterization of the best -factor for a -subadditive function seminorm when is -finite. All these results generalize those about multiplicativity factors for function seminorms proved earlier.     

Shock fluctuations in the asymmetric simple exclusion process

Summary We consider the one dimensional nearest neighbors asymmetric simple exclusion process with ratesq andp for left and right jumps respectively;q<p. Ferrari et al. (1991) have shown that if the initial measure isv _, , a product measure with densities and to the left and right of the origin respectively, <, then there exists a (microscopic) shock for the system. A shock is a random positionX _t such that the system as seen from this position at timet has asymptotic product distributions with densities and to the left and right of the origin respectively, uniformly int. We compute the diffusion coefficient of the shockD=lim _t t ^–1(E(X _t )²–(EX _t )²) and findD=(p–q)(–)^–1((1–)+(1–)) as conjectured by Spohn (1991). We show that in the scale the position ofX _t is determined by the initial distribution of particles in a region of length proportional tot. We prove that the distribution of the process at the average position of the shock converges to a fair mixture of the product measures with densities and . This is the so called dynamical phase transition. Under shock initial conditions we show how the density fluctuation fields depend on the initial configuration.     

Some homological properties of commutative semitrivial ring extensions

LetR be a commutative ring with 1 andM anR-module. If:M _R MR is anR-module homomorphism satisfying(mm)=(mm) and(mm)m=m(mm), the additive abelian groupRM becomes a commutative ring, if multiplication is defined by (r,m)(r,m)=(rr+(mm),rm+rm). This ring is called the semitrivial extension ofR byM and and it is denoted byR M. This generalizes the notion of a trivial extension and leads to a more interesting variety of examples. The purpose of this paper is to studyR M; in particular, we are interested in some homological properties ofR M as that of being Cohen-Macaulay, Gorenstein or regular. A sample result: Let (R,m) be a local Noetherian ring,M a finitely generatedR-module and Im() m. ThenR M is Gorenstein if and only if eitherRM is Gorenstein orR is Gorenstein,M is a maximal Cohen-Macaulay module andMM ^*, where the isomorphism is given by the adjoint of.     

Fractionally colouring total graphs

Bchzad and Vizing have conjectured that given any simple graph of maximum degree , one can colour its edges and vertices with +2 colours so that no two adjacent vertices, or two incident edges, or an edge and either of its ends receive the same colour. We show that for any simple graphG, V(G)E(G) can be fractionally coloured with +2 colours.     

C*-Algebra Homomorphisms and kk-Theory

Let A be a simple C^*-algebra which can be written as an inductive limit of P₁M_n(C(X₁ ))P₁ P₂M_n(C(X₂ ))P₂ ···, where X_n are finite CW complexes with sup dim(X_n < + and P_i M_n(C(X_i)) are projections. Let X be a finite CW complex. In this paper, we will give a necessary and sufficient condition for a KK-element KK(C(X),A) to be realized by a C^*- algebra homomorphism : C(X) A. If we further suppose that A has a unique trace, then the set of all injective homomorphisms from C(X) to A can be characterized up to modulo approximately unitary equivalence.     

Aufeinanderfolgende Elemente in multiplikativen Zahlenmengen

LetM be a multiplicative set with 1M andmnM if and only ifmM,nM for (m,n)=1. It is shown by elementary means that there exists the asymptotic density of the setM(M–1) for every multiplicative setM. The density is positive if and only ifM possesses a positive density and 2M for some . This result is slightly generalized to sums over multiplicative functionsf with |f|1.     

A separation theorem for semicontinuous functions on preordered topological spaces

Suppose that X is a topological space with preorder , and that –g, f are bounded upper semicontinuous functions on X such that g(x) f(y) whenever x y. We consider the question whether there exists a bounded increasing continuous function h on X such that g h f, and obtain an existence theorem that gives necessary and sufficient conditions. This result leads to an extension theorem giving conditions that allow a bounded increasing continuous function defined on an open subset of X to be extended to a function of the same type on X. The application of these results to extremally disconnected locally compact spaces is studied.Received: 26 May 2004