Simplified Optimality Conditions for Minimizing the Difference of Vector-Valued Functions

This paper deals with an axiomatic approach to certain optimality conditions for the vector nonconvex minimization problem min{g(x)–h(x): xX}, where X is an arbitrary set and g, h are functions defined on X with values in an ordered topological vector space Z.     

Global Optimization in Practice: An Application to Interactive Multiple Objective Linear Programming

A multiple objective linear programming problem (P) involves the simultaneous maximization of two or more conflicting linear objective functions over a nonempty polyhedron X. Many of the most popular methods for solving this type of problem, including many well-known interactive methods, involve searching the efficient set X _E of the problem. Generally, however, X _E is a complicated, nonconvex set. As a result, concepts and methods from global optimization may be useful in searching X _E. In this paper, we will explain in theory, and show via an actual application to citrus rootstock selection in Florida, how the potential usefulness of the well-known interactive method STEM for solving problem (P) in this way, can depend crucially upon how accurately certain global optimization problems involving minimizations over X _E are solved. In particular, we will show both in theory and in practice that the choice of whether to use the popular but unreliable payoff table approach or to use one of the lesser known, more accurate global optimization methods to solve these problems can determine whether STEM succeeds or fails as a decision aid. Several lessons and conclusions of transferable value derived from this research are also given.     

A variational theory for monotone vector fields

Monotone vector fields were introduced almost 40 years ago as nonlinear extensions of positive definite linear operators, but also as natural extensions of gradients of convex potentials. These vector fields are not always derived from potentials in the classical sense, and as such they are not always amenable to the standard methods of the calculus of variations. We describe here how the selfdual variational calculus, developed recently by the author, provides a variational approach to PDEs and evolution equations driven by maximal monotone operators. To any such vector field T on a reflexive Banach space X, one can associate a convex selfdual Lagrangian L _T on the phase space X × X ^* that can be seen as a “potential” for T, in the sense that the problem of inverting T reduces to minimizing a convex energy functional derived from L _T . This variational approach to maximal monotone operators allows their theory to be analyzed with the full range of methods—computational or not—that are available for variational settings. Standard convex analysis (on phase space) can then be used to establish many old and new results concerned with the identification, superposition, and resolution of such vector fields. Dedicated to Felix Browder on his 80th birthday     

Optimal Operating Policy for an M/G/1 Exhaustive Server-Vacation Model

We consider an M/G/1 queueing system controlled by an exhaustive server–vacation policy, i.e, the server is turned off whenever the system becomes empty and it is turned on after a random time with at least a customer present in the system. In this paper, it is proved that there exists an exhaustive optimal policy which is of the form X + a(T - X)⁺, where, starting with the server off, X represents the time for the first arrival and T and a are non-negative real numbers. Using a classical average cost structure, the optimization problem is treated under the asymptotic average criterion. A structured definition of exhaustive policy is also derived.     

Risk minimizing hedging for a partially observed high frequency data model

Risk-minimizing hedging strategies for contingent claims are studied in a general model for intraday stock price movements in the case of partial information. The dynamics of the risky asset price is described throught a marked point process Y, whose local characteristics depend on some unobservable hidden state variable X. In the model presented the processes Y and X may have common jump times, which means that the trading activity may affect the law of X and could be also related to the presence of catastrophic events. The hedger is restricted to observing past asset prices. Thus, we are in presence not only of an incomplete market situation but also of partial information. Considering the case where the price of the risky asset is modeled directly under a martingale measure, the computation of the risk-minimizing hedging strategy under this partial information is obtained by using a projection result (M. Schweizer, Risk minimizing hedging strategies under restricted information, Mathematical Finance 4 (1994) 327–342). This approach leads to a filtering problem with marked point process observations whose solution, obtained via the Kushner-Stratonovich equation, allows us to provide a complete solution to the heding problem.     

Optimizing Phylogenetic Diversity with Ecological Constraints

Given an edge-weighted tree T{\mathcal {T}} with leaf set X, define the weight of a subset S of X as the sum of the edge-weights of the minimal subtree of T{\mathcal {T}} connecting the elements in S. It is known that the problem of selecting subsets of X of a given size to maximize this weight can be solved using a greedy algorithm. This optimization problem arises in conservation biology where the weight is referred to as the phylogenetic diversity of a taxa set S. Here, we consider the extension of this problem whereby we are only interested in selecting subsets of the taxa set that are ecologically “viable”. Such subsets are specified by an acyclic digraph which represents, for example, a food web. This additional constraint makes the problem computationally hard. In this paper, we analyze the complexity of different variations of the extended problem.     

On Some Expectation and Derivative Operators Related to Integral Representations of Random Variables with Respect to a PII Process

Given a process with independent increments X (not necessarily a martingale) and a large class of square integrable r.v. H = f(X _T ), f being the Fourier transform of a finite measure μ, we provide a direct expression for Kunita-Watanabe and Föllmer-Schweizer decompositions of H. The representation is expressed by means of two significant maps: the expectation and derivative operators related to the characteristics of X. We also evaluate the expression for the variance optimal error when hedging the claim H with underlying process X. Those questions are motivated by finding the solution of the celebrated problem of global and local quadratic risk minimization in mathematical finance.     

Lexicographic and sequential equilibrium problems

The aim of this work is to analyze lexicographic equilibrium problems on a topological Hausdorff vector space X, and their relationship with some other vector equilibrium problems. Existence results for the tangled lexicographic problem are proved via the study of a related sequential problem. This approach was already followed by the same authors in the case of variational inequalities.     

Extreme VaR scenarios in higher dimensions

For a sequence of random variables X ₁, ..., X _n , the dependence scenario yielding the worst possible Value-at-Risk at a given level α for X ₁+...+X _n is known for n=2. In this paper we investigate this problem for higher dimensions. We provide a geometric interpretation highlighting the dependence structures which imply the worst possible scenario. For a portfolio (X ₁,..., X _n ) with given uniform marginals, we give an analytical solution sustaining the main result of Rüschendorf (Adv. Appl. Probab. 14(3):623–632, 1982). In general, our approach allows for numerical computations.      

Mirabolic Langlands duality and the quantum Calogero–Moser system

We give a generic spectral decomposition of the derived category of twisted D\mathcal{D} -modules on a moduli stack of mirabolic vector bundles on a curve X in characteristic p: that is, we construct an equivalence with the derived category of quasicoherent sheaves on a moduli stack of mirabolic local systems on X. This equivalence may be understood as a tamely ramified form of the geometric Langlands equivalence. When X has genus 1, this equivalence generically solves (in the sense of noncommutative geometry) the quantum Calogero–Moser system.     

Schlicht Envelopes of Holomorphy and Foliations by Lines

Given a domain Y in a complex manifold X, it is a difficult problem with no general solution to determine whether Y has a schlicht envelope of holomorphy in X, and if it does, to describe the envelope. The purpose of this paper is to tackle the problem with the help of a smooth 1-dimensional foliation ℱ of X with no compact leaves. We call a domain Y in X an interval domain with respect to ℱ if Y intersects every leaf of ℱ in a nonempty connected set. We show that if X is Stein and if ℱ satisfies a new property called quasiholomorphicity, then every interval domain in X has a schlicht envelope of holomorphy, which is also an interval domain. This result is a generalization and a global version of a well-known lemma from the mid-1980s. We illustrate the notion of quasiholomorphicity with sufficient conditions, examples, and counterexamples, and present some applications, in particular to a little-studied boundary regularity property of domains called local schlichtness.      

The rate of convergence of GMRES on a tridiagonal Toeplitz linear system

The Generalized Minimal Residual method (GMRES) is often used to solve a nonsymmetric linear system Ax = b. But its convergence analysis is a rather difficult task in general. A commonly used approach is to diagonalize A = XΛ X ⁻¹ and then separate the study of GMRES convergence behavior into optimizing the condition number of X and a polynomial minimization problem over A’s spectrum. This artificial separation could greatly overestimate GMRES residuals and likely yields error bounds that are too far from the actual ones. On the other hand, considering the effects of both A’s spectrum and the conditioning of X at the same time poses a difficult challenge, perhaps impossible to deal with in general but only possible for certain particular linear systems. This paper will do so for a (nonsymmetric) tridiagonal Toeplitz system. Sharp error bounds on and sometimes exact expressions for residuals are obtained. These expressions and/or bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first kind.     

Stochastic Integrals of Continuous Local Martingales,I

Consider a continuous local martingale X. We say that X satisfies the representation property if any martingale Y of X can be represented as stochastic ITǒ integral of X. Using the method of random time change systematically, in the present paper the representation problem for continuous local martingales is treated. We describe a class of martingales Y that can be represented as stochastic integral of X by probabilistic conditions. This leads to sufficient conditions for the representation property of X being true. Besides, an interesting characterization of continuous processes with independent increments is obtained. In part II. we proceed with general examples, applications to the n-dimensional case, and, in particular, to the n-dimensional time change of continuous local martingales with orthogonal components.     

A. D. Alexandrov’s problem for non-positively curved spaces in the sense of Busemann

This paper is the last of a series devoted to the solution of Alexandrov’s problem for non-positively curved spaces. Here we study non-positively curved spaces in the sense of Busemann. We prove that isometries of a geodesically complete connected at infinity proper Busemann space X are characterized as follows: If a bijection f: X → X and its inverse f ⁻¹ preserve distance 1, then f is an isometry.     

Weak Convergence and Fluid Limits in Optimal Time-to-Empty Queueing Control Problems

We consider a class of controlled queue length processes, in which the control allocates each server’s effort among the several classes of customers requiring its service. Served customers are routed through the network according to (prescribed) routing probabilities. In the fluid rescaling, Xⁿ(t)=\frac1n X(nt)X^{n}(t)=\frac{1}{n} X(nt), we consider the optimal control problem of minimizing the integral of an undiscounted positive running cost until the first time that X ⁿ =0. Our main result uses weak convergence ideas to show that the optimal value functions V ⁿ of the stochastic control problems for X ⁿ (t) converge (as n→∞) to the optimal value V of a control problem for the limiting fluid process. This requires certain equicontinuity and boundedness hypotheses on {V ⁿ }. We observe that these are essentially the same hypotheses that would be needed for the Barles-Perthame approach in terms of semicontinuous viscosity solutions. Sufficient conditions for these equicontinuity and boundedness properties are briefly discussed.     

The steiner minimal network for convex configurations

SupposeX is a convex configuration with radius of maximum curvaturer and at most one of the edges joining neighboring points has length strictly greater thanr. We use the variational approach to show the Steiner treeS coincides with the minimal spanning tree and consists of all these edges with a longest edge removed. This generalizes Graham's problem for points on a circle, which we had solved. In addition we describe the minimal spanning tree for certain convex configurations.     

The optimization problem over a distributive lattice

In this paper we give a necessary and sufficient condition for existence of minimal solution(s) of the linear system A * X ≥ b where A, b are fixed matrices and X is an unknown matrix over a lattice. Next, an algorithm which finds these minimal solutions over a distributive lattice is given. Finally, we find an optimal solution for the optimization problem min {Z = C * X | A * X ≥ b} where C is the given matrix of coefficients of objective function Z. This research was completed while the author was a visitor of the Center for Informatics and Applied Optimization, University of Ballarat, Ballarat, Australia.     

Minimal entropy and simplicial volume

We prove that MinEnt (Y) ∥Y∥ = MinEnt(X) ∥X∥, for manifolds Y whose fundamental group is a subexponential extension of the fundamental group of some negatively curved, locally symmetric manifold X. This is a particular case of a more general result holding for an arbitrary representation ρ : π₁ (Y) →π₁ (X), which relates the minimal entropy and the simplicial volume of X to some invariants of the couple (Y, ker (ρ)). Then, we discuss some applications to the minimal volume problem and to Einstein metrics. Received: 23 December 1998     

Planar Maximum Box Problem

Given two finite sets of points X ⁺ and X ⁻ in ℝ ^d , the maximum box problem asks to find an axis-parallel box B such that B∩X ⁻=∅ and the total number of points from X ⁺ covered is maximized. In this paper we consider the version of the problem for d = 2 (and find the smallest solution box). We present an O(n ³ log⁴ n) runtime algorithm, thus improving previously best known solution by almost quadratic factor. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the derived category of a regular toric scheme

Let X be a quasi-compact scheme, equipped with an open covering by affine schemes U _σ = Spec A ^σ . A quasi-coherent sheaf on X gives rise, by taking sections over the U _σ , to a diagram of modules over the coordinate rings A ^σ , indexed by the intersection poset Σ of the covering. If X is a regular toric scheme over an arbitrary commutative ring, we prove that the unbounded derived category of quasi-coherent sheaves on X can be obtained from a category of Σ^op-diagrams of chain complexes of modules by inverting maps which induce homology isomorphisms on hyper-derived inverse limits. Moreover, we show that there is a finite set of weak generators, one for each cone in the fan Σ. The approach taken uses the machinery of Bousfield–Hirschhorn colocalisation of model categories. The first step is to characterise colocal objects; these turn out to be homotopy sheaves in the sense that chain complexes over different open sets U _σ agree on intersections up to quasi-isomorphism. In a second step it is shown that the homotopy category of homotopy sheaves is equivalent to the derived category of X.