bluuebunny/crossref_metadata_2025 huggingface dataset:
Denumerable Constrained Markov Decision Processes and Finite Approximations
Authors: Altman Eitan
Published: October 2008

The purpose of this paper is two fold. First to establish the theory of discounted constrained Markov decision processes with a countable state and action spaces with general multi-chain structure. Second, to Introduce finite approximation methods.

We define the occupation measures and obtain properties of the set of all achievable occupation measures under the different admissible policies. We establish the optimality of stationary policies for the constrained control problem, and obtain an LP with a countable number of decision variables through which stationary optimal policies are computed.

Since for such an LP one cannot expect to find an optimal solution in a finite number of operations, we present two schemes for finite approximations and establish the convergence of optimal values and policies for both the discounted and the expected average cost, with unbounded cost.

Sometimes It turns out to be easier to solve the problem with infinite state space than the problem with finite yet large state space. Based on the optimal policy for the problem with infinite state space, we construct policies which are almost optimal for the problem with truncated state space. This method is applied to obtain an ε-optimal policy for a problem of optimal priority assignment under constraints for a system of K finite queues.
An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
Authors: Ye Yinyu , Todd Michael J. , Mizuno Shinji
Published: October 2008

We present an O(√nL)-iteration homogeneous and self-dual linear programming (LP) algorithm. The algorithm possesses the following features:

• It solves the linear programming problem without any regularity assumption concerning the existence of optimal, feasible, or interior feasible solutions.

• It can start at any positive primal-dual pair, feasible or infeasible, near the central ray of the positive orthant (cone), and it does not use any big M penalty parameter or lower bound.

• Each iteration solves a system of linear equations whose dimension is almost the same as that solved in the standard (primal-dual) interior-point algorithms.

• If the LP problem has a solution, the algorithm generates a sequence that approaches feasibility and optimality simultaneously; if the problem is infeasible or unbounded, the algorithm will correctly detect infeasibility for at least one of the primal and dual problems.
On the Complexity of Cooperative Solution Concepts
Authors: Deng Xiaotie , Papadimitriou Christos H.
Published: October 2008

We study from a complexity theoretic standpoint the various solution concepts arising in cooperative game theory. We use as a vehicle for this study a game in which the players are nodes of a graph with weights on the edges, and the value of a coalition is determined by the total weight of the edges contained in it. The Shapley value is always easy to compute. The core is easy to characterize when the game is convex, and is intractable (NP-complete) otherwise. Similar results are shown for the kernel, the nucleolus, the ε-core, and the bargaining set. As for the von Neumann-Morgenstern solution, we point out that its existence may not even be decidable. Many of these results generalize to the case in which the game is presented by a hypergraph with edges of size k > 2.
An Adjustment Process for an Economy with Linear Production Technologies
Authors: van den Elzen Antoon , van der Laan Gerard , Talman Dolf
Published: October 2008

In this paper an adjustment process for a general equilibrium model with linear production technologies is given. The process reaches an equilibrium in the economy by simultaneous adaptations of prices and activity levels. Initially the prices of the commodities in excess demand are relatively increased and the prices of the commodities in excess supply are relatively decreased. Firms have only a positive activity level when they make zero profit.

An important feature of the process is that it keeps track of the location of the starting price vector throughout its operation. Furthermore, the choice of the starting price vector is only limited by economic considerations. Besides, the process converges under rather weak conditions and possesses an appealing economic interpretation.
Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
Authors: Hochbaum Dorit S.
Published: October 2008

We demonstrate the impossibility of strongly polynomial algorithms for the allocation problem, in the comparison model and in the algebraic tree computation model, that follow from lower bound results. Consequently, there are no strongly polynomial algorithms for nonlinear (concave) separable optimization over a totally unimodular constraint matrix. This is in contrast to the case when the objective is linear.

We present scaling-based algorithms that use a greedy algorithm as a subroutine. The algorithms are polynomial for the allocation problem and its extensions and are also optimal for the sample allocation problem and the generalized upper bounds allocation problem, in that the complexity meets the lower bound derived from the comparison model. For other extensions of the allocation problem the scaling-based algorithms presented here are the fastest known.

These algorithms are also polynomial time algorithms for solving with ε accuracy the allocation problem and its extension in continuous variables.
On Finding Optimal Policies for Markov Decision Chains: A Unifying Framework for Mean-Variance-Tradeoffs
Authors: Huang Ying , Kallenberg L. C. M.
Published: October 2008

This paper proves constructively the existence of optimal policies for maximum one-period mean-to-standard-deviation-ratio, negative variance-with-bounded-mean and mean-penalized-by-variance Markov decision chains by reducing them to a related mathematical program. This program entails maximizing (xB/D(xb)) + C(xb) over x in a polytope and with given bounds on xb where C and D are convex and either D is constant or D is positive and nondecreasing, C is nondecreasing and xB is nonpositive. This program is in turn reduced to maximizing x(B + θb) over x in the polytope parametrically in θ. Along the way, under the nonnegative-initial-distribution assumption, we generalize the rule of constructing a stationary maximum-average-reward policy from an extreme optimal solution of the associated linear program. The paper unifies and extends formulations and existence results for problems discussed by White (1987), Filar and Lee (1985), Sobel (1985), Kawai (1987) and Filar, Kallenberg and Lee (1989), and gives an effective computational procedure to solve them that is related to a method used by Kawai (1987) in a special case.
Monotone Optimal Control of Permutable GSMPs
Authors: Glasserman Paul , Yao David D.
Published: October 2008

We consider Markovian GSMPs (generalized semi-Markov processes) in which the rates of events are subject to control. A control is monotone if the rate of one event is increasing or decreasing in the number of occurrences of other events. We give general conditions for the existence of monotone optimal controls. The conditions are functional properties for the one-step cost functions and, more importantly, structural properties for the GSMP. The main conditions on costs are submodularity or supermodularity with respect to pairs of events. The key structural condition is strong permutability, requiring that the state at any time be determined by the number of events of each type that have occurred, regardless of their order. This permits a reformulation of the original control problem into one based only on event counting processes. This reformulation leads to a unified treatment of a broad class of models and to meaningful generality beyond existing results.
On the Relation Between Recurrence and Ergodicity Properties in Denumerable Markov Decision Chains
Authors: Dekker R. , Hordijk A. , Spieksma F. M.
Published: October 2008

This paper studies two properties of the set of Markov chains induced by the deterministic policies in a Markov decision chain. These properties are called μ-uniform geometric ergodicity and μ-uniform geometric recurrence. μ-uniform ergodicity generalises a quasi-compactness condition. It can be interpreted as a strong version of stability, as it implies that the Markov chains generated by the deterministic stationary policies are uniformly stable. μ-uniform geometric recurrence can be shown to be equivalent to the simultaneous Doeblin condition, If μ is bounded. Both properties imply the existence of deterministic average and sensitive optimal policies.

The second Key theorem in this paper shows the equivalence of μ-uniform geometric ergodicity and weak μ-uniform geometric recurrence under appropriate continuity conditions.

In the literature numerous recurrence conditions have been used. The first Key theorem derives the relation between several of these conditions, which interestingly turn out to be equivalent in most cases.
The Lattice of Core (Sub)Matchings in a Two-Sided Matching Market
Authors: Quint Thomas
Published: October 2008

We consider the two-sided matching model of Demange and Gale (1985). Given a suitable partial ordering and a correct definition of “matching,” we show the set of core matchings is (under a nondegeneracy assumption) always a lattice. The results parallel the “set of core matchings is a lattice” theorem (Conway, in Knuth 1976) for the marriage market of Gale and Shapley (1962).
Variational Inequalities with Generalized Monotone Operators
Authors: Yao Jen-Chih
Published: October 2008

We investigate the variational inequality with pseudomonotone operators (in the sense of Karamardian) in Banach spaces. New existence results which extend many known results in infinite-dimensional spaces are derived under rather weak assumptions. New uniqueness results which also seem to be new even in finite-dimensional spaces are also derived. In particular, new existence and uniqueness results for the complementarity problem with pseudomonotone operators in Banach spaces are obtained. Also, existence and uniqueness results for minimization problems with pseudoconvex functions in Banach spaces are obtained.
Implicit Functions, Lipschitz Maps, and Stability in Optimization
Authors: Dontchev Asen L. , Hager William W.
Published: October 2008

We present an implicit function theorem for set-valued maps associated with the solutions of generalized equations. As corollaries of this theorem, we derive both known and new results. Strong regularity of variational inequalities and Lipschitz stability of optimization problems are discussed.
Lemke Paths on Simple Polytopes
Authors: Morris Walter D.
Published: October 2008

Lemke paths are often used in the solution of nonlinear programming problems. We investigate a number of properties of Lemke paths, motivated by the d-step conjecture for linear programming. Some negative results are presented, including families of Lemke paths, for which the length of the shortest grows exponentially, joining pairs of vertices of a sequence of polytopes.
Entropy-Like Proximal Methods in Convex Programming
Authors: Iusem Alfredo N. , Svaiter B. F. , Teboulle Marc
Published: October 2008

We study an extension of the proximal method for convex programming, where the quadratic regularization kernel is substituted by a class of convex statistical distances, called φ-divergences, which are typically entropy-like in form. After establishing several basic properties of these quasi-distances, we present a convergence analysis of the resulting entropy-like proximal algorithm. Applying this algorithm to the dual of a convex program, we recover a wide class of nonquadratic multiplier methods and prove their convergence.
Approximations of Two-Attribute Utility Functions
Authors: Fishburn Peter C.
Published: October 2008

This paper considers the assessment of von Neumann-Morgenstern utility functions u defined on two attributes from the viewpoint of mathematical approximation theory. It focuses on approximations v of u that can be written as v(x, y) = f1(x)g1(y) + ⋯ + fm(x)gm(y) where the fi and/or gi are based on single-attribute conditional utility functions. The paper does not rely on independence axioms that enable u(x, y) to be expressed in simplified forms when they are valid.
Optimal Replacement with Semi-Markov Shock Models Using Discounted Costs
Authors: Feldman Richard M.
Published: October 2008

Consider a system that is subject to a sequence of randomly occurring shocks; each shock causes some damage of random magnitude to the system. Any of the shocks might cause the system to fail, and the probability of such a failure is a function of the sum of the magnitudes of damage caused by all previous shocks. When the system fails, it must be immediately replaced and a failure cost is incurred. If the system is replaced before failure, a smaller replacement cost is incurred, and that cost may depend upon the state of the system at replacement time.

The purpose of this paper is to determine the optimal replacement policy among the class of policies that replace at shock times. The main assumption is that the cumulative damage process is a semi-Markov process. The cost criterion is to minimize the discounted cost of replacement. (See Feldman [Feldman, R. M. 1976. Optimal replacement with semi-Markov shock models. J. Appl. Probab. 13 108–117; Feldman, R. M. 1977. The maintenance of systems governed by semi-Markov shock models. Proceedings of the Conference on the Theory and Applications of Reliability with Emphasis on Bayesian and Nonparametric Methods. Edited by C. P. Tsokos. Academic Press.] for the average cost criterion case.) The general approach will be to apply optimal stopping theory to the replacement problem.
On the Convergence Rate of Algorithms for Solving Equations that are Based on Methods of Complementary Pivoting
Authors: Saigal R.
Published: October 2008

This paper considers the problem of solving a system of n nonlinear equations in n variables, when the underlying functions are continuously differentiable and their derivative satisfies a Lipschitz condition. We restrict our attention to methods which are based on complementary pivoting, also known as fixed point algorithms. We show that certain realizations of these methods achieve quadratic convergence when they reach sufficiently close to the solution. And in these cases, without using the derivatives of the mappings, the computational work involved is comparable to that of Newton's method.
A Note on Convergence of the Ford-Fulkerson Flow Algorithm
Authors: Tucker Alan
Published: October 2008

This note fills a gap in the theory of convergence of the Ford-Futkerson flow algorithm. We show that if the nodes labeled by the algorithm are scanned in a consistent manner, then this algorithm will always produce a maximal flow in a finite number of iterations.
Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
Authors: Karp Richard M.
Published: October 2008

We consider partitioning algorithms for the approximate solution of large instances of the traveling-salesman problem in the plane. These algorithms subdivide the set of cities into small groups, construct an optimum tour through each group, and then patch the subtours together to form a tour through all the cities. If the number of cities in the problem is n, and the number of cities in each group is t, then the worst-case error is [Formula: see text]. If the cities are randomly distributed, then the relative error is O(t−1/2) (with probability one). Hybrid schemes are suggested, in which partitioning is used in conjunction with existing heuristic algorithms. These hybrid schemes may be expected to give near-optimum solutions to problems with thousands of cities.
Graphs and Cooperation in Games
Authors: Myerson Roger B.
Published: October 2008

Graph-theoretic ideas are used to analyze cooperation structures in games. Allocation rules, selecting a payoff for every possible cooperation structure, are studied for games in characteristic function form. Fair allocation rules are defined, and these are proven to be unique, closely related to the Shapley value, and stable for a wide class of games.
Decision Problems with Expected Utility Criteria, II: Stationarity
Authors: Kreps David M.
Published: October 2008

The study of sequential decision problems with expected utility criteria is continued. Stationary problems are defined similarly to stationary problems with additive or separable utility, except that an additional requirement, stationarity of the preference structure, is imposed. The optimality of stationary and memoryless strategies is investigated for problems with upper and lower convergent utility or which are upper or lower transient. By example, the definition of stationarity is seen to be inadequate for generalizations of “average reward” criteria. Simplifications in the strategy iteration algorithm which result from stationarity are discussed.
A Nondiagonal Value on a Reproducing Space
Authors: Tauman Yair
Published: October 2008

The question of whether or not every value on a reproducing space is diagonal is answered in the negative by means of a counter example. A reproducing space is introduced upon which a nondiagonal value exists.
The Asymptotic Behavior of Undiscounted Value Iteration in Markov Decision Problems
Authors: Schweitzer P. J. , Federgruen A.
Published: October 2008

This paper considers undiscounted Markov Decision Problems. For the general multichain case, we obtain necessary and sufficient conditions which guarantee that the maximal total expected reward for a planning horizon of n epochs minus n times the long run average expected reward has a finite limit as n → ∞ for each initial state and each final reward vector. In addition, we obtain a characterization of the chain and periodicity structure of the set of one-step and J-step maximal gain policies. Finally, we discuss the asymptotic properties of the undiscounted value-iteration method.
Variance-Optimal Hedging in Discrete Time
Authors: Schweizer Martin
Published: October 2008

We solve the problem of approximating in ℒ2 a given random variable H by stochastic integrals GT(ϑ) of a given discrete-time process X. We interpret H as a contingent claim to be paid out at time T, X as the price evolution of some risky asset in a financial market, and G(ϑ) as the cumulative gains from trade using the hedging strategy ϑ. As an application, we determine the variance-optimal strategy which minimizes the variance of the net loss H − GT(ϑ) over all strategies ϑ.
Fatou's Lemma for Multifunctions with Unbounded Values
Authors: Balder Erik J. , Hess Christian
Published: October 2008

For multifunctions having unbounded sets as values we give Fatou-type inclusions for the Kuratowski limes superior. In finite as well as infinite dimensions. These are derived from similar, known Fatou-type inequalities for single-valued multifunctions (i.e., ordinary functions), that is, from Balder's unifying Fatou lemma in case the image set is finite-dimensional, and from an update of related results by Balder in the infinite dimensional case. For this extension from the single-valued to the multivalued situation a lemma due to Hess, used to prove earlier Fatou-type inclusions, is of critical importance. Also, an asymptotic correction term, introduced here, plays an important role. The two man results thus obtained subsume and extend an entire class of comparable Fatou lemmas.
Axiomatization of the Nucleolus
Authors: Snijders Chris
Published: October 2008

An axiomatization of the nucleolus on the set of all cooperative games with finite player set is provided. The nucleolus is shown to be completely characterized by singlevaluedness, anonymity, covariance and a new reduced game property.
Canonical Representation of Set Functions
Authors: Gilboa Itzhak , Schmeidler David
Published: October 2008

The representation of a cooperative transferable utility game as a linear combination of unanimity games may be viewed as an isomorphism between no-necessarily additive set functions on the players space and additive ones on the coalitions space. (Or, alternatively, between nonadditive probability measures on a state space and additive ones on the space of events.) We extend the unanimity-basis representation to general (infinite) spaces of players, study spaces of games which satisfy certain properties and provide some conditions for α-additivity of the resulting additive set function (on the space at coalitions). These results also allow us to extend some representations of the Choquet integral from finite to infinite spaces.
Using Expert Opinions in Bayesian Prediction of Component Lifetimes in a Shock Model
Authors: Gåsemyr Jørund , Natvig Bent
Published: October 2008

This paper is concerned with the combination of k expert opinions about the lifetimes of n components of a binary system. This problem has been treated in the single component case by Huseby (Huseby, A. B. 1986. Combining experts' opinions, a retrospective approach. Tech. Rep., Centre for Industrial Research, Oslo; Huseby, A. B. 1988. Combining opinions in a predictive case. J. M. Bernardo, M. H. DeGroot, D. V. Lindley, A. F. M. Smith, eds. Bayesian Statistics, Vol. 3. Oxford University Press, NY, 641–651.). Since the experts often share data, he argues that their assessments Will typically be dependent and that this difficulty cannot be handled without making judgements concerning the underlying sources of information and to what extent these are available to each of the experts. The information available to the experts is modeled as a set of observations Y1, …, Ym. These observations are then reconstructed as far as possible from the information provided by the experts and used as a basis for the combined judgement. This is called the retrospective approach. Huseby (Huseby, A. B. 1988. Combining opinions in a predictive case. J. M. Bernardo, M. H. DeGroot, D. V. Lindley, A. F. M. Smith, eds. Bayesian Statistics, Vol. 3. Oxford University Press, NY, 641–651.) treats a predictive case where the uncertain quantity is modeled as a future observation Y, from the same distribution as the Yi's. For the case n > 1, where each expert is giving opinions about more than one component, additional dependencies between the reliabilities of the components come into play. This is for instance true if two or more components are of similar type, are sharing a common environment or are exposed to common cause failures. For the case n = 2, the retrospective approach and, in particular, the predictive case are treated in Natvig (Natvig, B. 1993. Using expert opinions in Bayesian estimation of system reliability. R. E. Barlow, C. A. Clarotti, F. Spizzichiao, eds. Reliability and Decision Making. Elsevier, London, 347–362.). In the present paper, the predictive case is considered for an arbitrary n and for an arbitrary overlapping of the observation sets from the different experts. The component lifetimes are assumed to have a multivariate exponential distribution of the Marshall-Olkin type. At the end of the paper, it is shown how the joint distribution of the lifetimes of the n components can easily be updated in the case of getting real data.
Fast Approximation Algorithms for Fractional Packing and Covering Problems
Authors: Plotkin Serge A. , Shmoys David B. , Tardos Éva
Published: October 2008

This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangian relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running time of a Lagrangian relaxation-based algorithm.

We give several applications of our algorithms. The new approach yields several orders of magnitude of improvement over the best previously known running times for algorithms for the scheduling of unrelated parallel machines in both the preemptive and the nonpreemptive models, for the job shop problem, for the Held and Karp bound for the traveling salesman problem, for the cutting-stock problem, for the network embedding problem, and for the minimum-cost multicommodity flow problem.
Generalized Linear Complementarity Problems
Authors: Güler Osman
Published: October 2008

We introduce the concept of the generalized (monotone) linear complementarity problem (GLCP) in order to unify LP, convex QP, monotone LCP, and mixed monotone LCP. We establish the basic properties of GLCP and develop canonical forms for its representation. We show that the GLCP reduces to a monotone LCP in the same variables. This implies that many results which hold true for monotone LCP extend to GLCP. In particular, any interior point algorithm for monotone LCP extends to an interior point algorithm for GLCP.
Least Majorized Elements and Generalized Polymatroids
Authors: Tamir Arie
Published: October 2008

We prove that a bounded generalized polymatroid has a least weakly submajorized (supermajorized) vector. Such a vector simultaneously minimizes every nondecreasing (nonincreasing), symmetric and quasi-convex function defined on the generalized polymatroid. The same result holds also for the set of integer vectors of a bounded integral generalized polymatroid. We then extend these results to more general sets, and discuss several computational aspects.
The Simplest Semidefinite Programs are Trivial
Authors: Vanderbei Robert J. , Yang Bing
Published: October 2008

We consider optimization problems of the following type: [Formula: see text] Here, tr(·) denotes the trace operator, C and X are symmetric n × n matrices, B is a symmetric m × m matrix and A(·) denotes a linear operator. Such problems are called semidefinite programs and have recently become the object of considerable interest due to important connections with max-min eigenvalue problems and with new bounds for integer programming. In the context of symmetric matrices, the simplest linear operators have the following form: [Formula: see text] where M is an arbitrary m × n matrix. In this paper, we show that for such linear operators the optimization problem is trivial in the sense that an explicit solution can be given.
Nonlinear Extensions of Farkas’ Lemma with Applications to Global Optimization and Least Squares
Authors: Jeyakumar V. , Glover B. M.
Published: October 2008

A nonlinear extension of Farkas’ lemma for systems involving the difference of sublinear functions is presented. This extension of Farkas’ lemma is applied to give a complete characterization of global optimality for constrained global optimization problems in which the objective function is the difference of a convex and sublinear function and the constraints are systems of difference sublinear functions. An application to certain fractional programming problems is also given. These results are achieved with merely a stronger consistency condition which reduces to the usual feasibility requirement for problems with sublinear constraints. Further generalizations of Farkas’ lemma for systems involving convex and difference sublinear functions are also presented. Moreover, a generalized Farkas’ lemma for certain specially structural convex inequality systems is shown to be related to the solution of appropriate constrained least squares problems.
A Geometric Buchberger Algorithm for Integer Programming
Authors: Thomas Rekha R.
Published: October 2008

Let IP{A, c} denote the family of integer programs of the form Min cx: Ax = b, x ∈ Nn obtained by varying the right-hand side vector b but keeping A and c fixed. A test set for IPA, c is a set of vectors in Zn such that for each nonoptimal solution α to a program in this family, there is at least one element g in this set such that α − g has an improved cost value as compared to α. We describe a unique minimal test set for this family called the reduced Gröbner basis of IP{A, c}. An algorithm for its construction is presented which we call a geometric Buchberger algorithm for integer programming and we show how an integer program may be solved using this test set. The reduced Gröbner basis is then compared with some other known test sets from the literature. We also indicate an easy procedure to construct test sets with respect to all cost functions for a matrix A ∈ Z(n−2)×n of full row rank.
Optimal Investment Policies for a Firm With a Random Risk Process: Exponential Utility and Minimizing the Probability of Ruin
Authors: Browne Sid
Published: October 2008

We consider a firm that is faced with an uncontrollable stochastic cash flow, or random risk process. There is one investment opportunity, a risky stock, and we study the optimal investment decision for such firms. There is a fundamental incompleteness in the market, in that the risk to the investor of going bankrupt cannot be eliminated under any investment strategy, since the random risk process ensures that there is always a positive probability of ruin (bankruptcy). We therefore focus on obtaining investment strategies which are optimal in the sense of minimizing the risk of ruin. In particular, we solve for the strategy that maximizes the probability of achieving a given upper wealth level before hitting a given lower level. This policy also minimizes the probability of ruin. We prove that when there is no risk-free interest rate, this policy is equivalent to the policy that maximizes utility from terminal wealth, for a fixed terminal time, when the firm has an exponential utility function. This validates a longstanding conjecture about the relation between minimizing probability of ruin and exponential utility. When there is a positive risk-free interest rate, the conjecture is shown to be false. We also solve for the optimal policy for the related objective of minimizing the expected discounted penalty paid upon ruin.
Egalitarian Solutions of Large Games: I. A Continuum of Players
Authors: Hart Sergiu , Mas-Colell Andreu
Published: October 2008

This is the first of two papers devoted to the study of egalitarian solutions for nontransferable utility (NTU) games with a large number of players. This paper is concerned with the construction of egalitarian solutions for the limit situation with a continuum of players. We build on the concept of the Potential introduced in Hart and Mas-Colell (Hart, S., A. Mas-Colell. 1989. Potential, value and consistency. Econometrica 57 589–614.) and exploit partial differential equations techniques. In particular, we associate to the egalitarian solutions a variational problem which may be viewed as a generalization—to the nontransferable utility context—of the diagonal principle of Aumann and Shapley (Aumann, R. J., L. S. Shapley. 1974. Values of Non-Atomic Games. Princeton University Press, Princeton, New Jersey.) in the transferable utility setting.
Light-Traffic Analysis for Queues with Spatially Distributed Arrivals
Authors: Kroese Dirk P. , Schmidt Volker
Published: October 2008

We consider the following continuous polling system: Customers arrive according to a homogeneous Poisson process (or a more general stationary point process) and wait on a circle in order to be served by a single server. The server is “greedy,” in the sense that he always moves (with constant speed) towards the nearest customer. The customers are served according to an arbitrary service time distribution, in the order in which they are encountered by the server. First-order and second-order Taylor-expansions are found for the expected configuration of customers, for the mean queue length, and for expectation and distribution function of the workload. It is shown that under light traffic conditions the greedy server works more efficiently than the cyclically polling server.
Repeated Games, Duality and the Central Limit Theorem
Authors: De Meyer Bernard
Published: October 2008

This paper is concerned with the repeated zero-sum games with one-sided information and standard signaling. We introduce here dual games that allow us to analyze the “Markovian” behavior of the uninformed player, and to explicitly compute his optimal strategies. We then apply our results on the dual games to explain the appearance of the normal density in the n−1/2-term of the asymptotic expansion of vn as a consequence of the Central Limit Theorem.
Computing Zeros of Sections of Vector Bundles Using Homotopies and Relocalization
Authors: Brown Donald J. , Demarzo Peter M. , Eaves B. Curtis
Published: October 2008

An algorithm is described for computing fixed points on a Grassmannian manifold. The method can be applied in the more general setting of solving equations on abstract smooth manifolds into vector bundles. This development is part of a project to compute economic equilibria in the presence of incomplete markets.
Rounding of Polytopes in the Real Number Model of Computation
Authors: Khachiyan Leonid G.
Published: October 2008

Let 𝒜 be a set of m points in ℝn. We show that the problem of (1 + ϵ)n-rounding of 𝒜, i.e., the problem of computing an ellipsoid E ⊆ ℝn such that [(1 + ϵ)n]−1E ⊆ conv. hull(𝒜) ⊆ E, can be solved in O(mn2(ϵ−1 + ln n + ln ln m)) arithmetic operations and comparisons. This result implies that the problem of approximating the minimum volume ellipsoid circumscribed about 𝒜 can be solved in O(m3.5 ln(mϵ−1)) operations to a relative accuracy of ϵ in the volume. The latter bound also applies to the (1 + ϵ)n-rounding problem. Our bounds hold for the real number model of computation.
Coordination Complexity of Parallel Price-Directive Decomposition
Authors: Grigoriadis Michael D. , Khachiyan Leonid G.
Published: October 2008

The general block-angular convex resource sharing problem in K blocks and M nonnegative block-separable coupling constraints is considered. Applications of this model are in combinatorial optimization, network flows, scheduling, communication networks, engineering design, and finance. This paper studies the coordination complexity of approximate price-directive decomposition (PDD) for this problem, i.e., the number of iterations required to solve the problem to a fixed relative accuracy as a function of K and M.

First a simple PDD method based on the classical logarithmic potential is shown to be optimal up to a logarithmic factor in M in the class of all PDD methods that work with the original (unrestricted) blocks. It is then shown that logarithmic and exponential potentials generate a polylogarithmically-optimal algorithm for a wider class of PDD methods which can restrict the blocks by the coupling constraints.

As an application, the fastest currently-known deterministic approximation algorithm for minimum-cost multicommodity flows is obtained.
A Polynomial Primal-Dual Dikin-Type Algorithm for Linear Programming
Authors: Jansen B. , Roos C. , Terlaky T.
Published: October 2008

In this paper we present a new primal-dual affine scaling method for linear programming. The method yields a strictly complementary optimal solution pair, and also allows a polynomial-time convergence proof. The search direction is obtained by using the original idea of Dikin, namely by minimizing the objective function (which is the duality gap in the primal-dual case), over some suitable ellipsoid. This gives rise to completely new primal-dual affine scaling directions, having no obvious relation with the search directions proposed in the literature so far. The new directions guarantee a significant decrease in the duality gap in each iteration, and at the same time they drive the iterates to the central path. In the analysis of our algorithm we use a barrier function which is the natural primal-dual generalization of Karmarkar's potential function. The iteration bound is O(nL), which is a factor O(L) better than the iteration bound of an earlier primal-dual affine scaling method (Monteiro, Adler and Resende [Monteiro, R. D. C., I. Adler, M. G. C. Resende. 1990. A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math. Oper. Res. 15 191–214.]).
Analysis of Sample-Path Optimization
Authors: Robinson Stephen M.
Published: October 2008

Sample-path optimization is a method for optimizing limit functions occurring in stochastic modeling problems, such as steady-state functions in discrete-event dynamic systems. It is closely related to retrospective optimization techniques and to M-estimation. The method has been computationally tested elsewhere on problems arising in production and in project planning, with apparent success. In this paper we provide a mathematical justification for sample-path optimization by showing that under certain assumptions—which hold for the problems just mentioned—the method will almost surely find a point that is, in a specified sense, sufficiently close to the set of optimizers of the limit function.
Derivatives of Spectral Functions
Authors: Lewis A. S.
Published: October 2008

A spectral function of a Hermitian matrix X is a function which depends only on the eigenvalues of X, λ1(X) ≥ λ2(X) ≥ ⋯ ≥ λn(X), and hence may be written f(λ1(X), λ2(X), …, λn(X)) for some symmetric function f. Such functions appear in a wide variety of matrix optimization problems. We give a simple proof that this spectral function is differentiable at X if and only if the function f is differentiable at the vector λ(X), and we give a concise formula for the derivative. We then apply this formula to deduce an analogous expression for the Clarke generalized gradient of the spectral function. A similar result holds for real symmetric matrices.
Properties of an Interior-Point Mapping for Mixed Complementarity Problems
Authors: Monteiro R. D. C. , Pang Jong-Shi
Published: October 2008

Using a unified theory of local homeomorphic maps, we establish some basic properties of a fundamental mapping associated with the family of path-following interior-point methods for solving a mixed nonlinear complementarity problem.
The Limit Distribution of Pure Strategy Nash Equilibria in Symmetric Bimatrix Games
Authors: Stanford William
Published: October 2008

In a “random” symmetric bimatrix game, let X and Y represent the numbers of symmetric and asymmetric pure strategy Nash equilibria occurring, respectively. We find the probability distributions of both X and Y depending on m, the number of pure strategies for each of the two players. We show the distribution of X approaches the Poisson distribution with mean one and the distribution of ½Y approaches the Poisson distribution with mean ½ as m increases. We determine the joint distribution of X and Y and the limit distribution of X + Y. From this we see the probability of at least one pure strategy Nash equilibrium approaches 1 − e−1.5 ≈ .7769 as m increases. For general bimatrix games, the corresponding limit of probabilities is 1 − e−1 ≈ .6321. Thus in this sense, pure strategy Nash equilibria are seen to be significantly more common under the condition of symmetry than otherwise.
Noncoercive Optimization Problems
Authors: Auslender Alfred
Published: October 2008

This paper modifies a recent sufficient condition for the existence of optimal solutions proposed by Buttazzo and Tomarelli, to obtain a condition that is necessary and sufficient. Applications to mathematical programming are given and stability results established.
A Superlinear Infeasible-Interior-Point Algorithm for Monotone Complementarity Problems
Authors: Wright Stephen , Ralph Daniel
Published: October 2008

We use the globally convergent framework proposed by Kojima, Noma, and Yoshise to construct an infeasible-interior-point algorithm for monotone nonlinear complementarity problems. Superlinear convergence is attained when the solution is nondegenerate and also when the problem is linear with a strictly complementary solution. Numerical experiments confirm the efficacy of the proposed approach.
Self-Scaled Barriers and Interior-Point Methods for Convex Programming
Authors: Nesterov Yu. E. , Todd M. J.
Published: October 2008

This paper provides a theoretical foundation for efficient interior-point algorithms for convex programming problems expressed in conic form, when the cone and its associated barrier are self-scaled. For such problems we devise long-step and symmetric primal-dual methods. Because of the special properties of these cones and barriers, our algorithms can take steps that go typically a large fraction of the way to the boundary of the feasible region, rather than being confined to a ball of unit radius in the local norm defined by the Hessian of the barrier.
A Robust Control Framework for Option Pricing
Authors: McEneaney William M.
Published: October 2008

A new approach is taken to the problem of option pricing. In the standard framework, the option pricing problem involves determining a price such that the option writer can guarantee a certain bound on the cost almost surely. Due to this form, the problem may be reformulated in terms of deterministic differential games of the type employed in robust and H∞ control. Different models yield different prices. The standard model yields the Black and Scholes price. Both a deterministic model and the standard model with the Ito integral replaced by the Stratonovich integral yield the price corresponding to a stop-loss hedging technique. With these methods, it can also easily be shown that for the standard model with a bounded, stochastic volatility, the Black and Scholes price corresponding to the upper bound for volatility is sufficient to hedge the option.
Semismooth Karush-Kuhn-Tucker Equations and Convergence Analysis of Newton and Quasi-Newton Methods for Solving these Equations
Authors: Qi Liqun , Jiang Houyuan
Published: October 2008

There are several forms of systems of nonsmooth equations which are equivalent to the Karush-Kuhn-Tucker (KKT) system of a nonlinearly constrained optimization problem (NLP). If the NLP is twice continuously differentiable and the Hessian functions of its objective and constraint functions are locally Lipschitzian, then these KKT equations are strongly semismooth. If furthermore the linear independence condition and the strong second-order sufficiency condition are satisfied at a KKT point, then the generalized Jacobians of these KKT equations are nonsingular at that point and the sequence generated by the generalized Newton method converges to this point Q-quadratically. However, direct application of quasi-Newton methods cannot guarantee Q-superlinear convergence. We present a mixed quasi-Newton method which converges Q-superlinearly with common symmetrical updating rules under the above conditions for the generalized Newton method. Superlinear convergence of the primal variables and global convergence are also discussed.
On a Wide Region of Centers and Primal-Dual Interior Point Algorithms for Linear Programming
Authors: Sturm Jos F. , Zhang Shuzhong
Published: October 2008

In the adaptive step primal-dual interior point method for linear programming, polynomial algorithms are obtained by computing Newton directions towards targets on the central path, and restricting the iterates to a neighborhood of this central path. In this paper, the adaptive step methodology is extended, by considering targets in a certain central region, which contains the usual central path, and subsequently generating iterates in a neighborhood of this region. The size of the central region can vary from the central path to the whole feasible region by choosing a certain parameter.

An 𝒪(√nL) iteration bound is obtained under mild conditions on the choice of the target points. In particular, we leave plenty of room for experimentation with search directions. The practical performance of the new primal-dual interior point method is measured on part of the Netlib test set for various sizes of the central region.
Survival and Growth with a Liability: Optimal Portfolio Strategies in Continuous Time
Authors: Browne Sid
Published: October 2008

We study the optimal behavior of an investor who is forced to withdraw funds continuously at a fixed rate per unit time (e.g., to pay for a liability, to consume, or to pay dividends). The investor is allowed to invest in any or all of a given number of risky stocks, whose prices follow geometric Brownian motion, as well as in a riskless asset which has a constant rate of return. The fact that the withdrawal is continuously enforced, regardless of the wealth level, ensures that there is a region where there is a positive probability of ruin. In the complementary region ruin can be avoided with certainty. Call the former region the danger-zone and the latter region the safe-region. We first consider the problem of maximizing the probability that the safe-region is reached before bankruptcy, which we call the survival problem. While we show, among other results, that an optimal policy does not exist for this problem, we are able to construct explicit ϵ-optimal policies, for any ϵ > 0. In the safe-region, where ultimate survival is assured, we turn our attention to growth. Among other results, we find the optimal growth policy for the investor, i.e., the policy which reaches another (higher valued) goal as quickly as possible. Other variants of both the survival problem as well as the growth problem are also discussed. Our results for the latter are intimately related to the theory of Constant Proportions Portfolio Insurance.
Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
Authors: Hall Leslie A. , Schulz Andreas S. , Shmoys David B. , Wein Joel
Published: October 2008

In this paper we introduce two general techniques for the design and analysis of approximation algorithms for 𝒩𝒫-hard scheduling problems in which the objective is to minimize the weighted sum of the job completion times. For a variety of scheduling models, these techniques yield the first algorithms that are guaranteed to find schedules that have objective function value within a constant factor of the optimum. In the first approach, we use an optimal solution to a linear programming relaxation in order to guide a simple list-scheduling rule. Consequently, we also obtain results about the strength of the relaxation. Our second approach yields on-line algorithms for these problems: in this setting, we are scheduling jobs that continually arrive to be processed and, for each time t, we must construct the schedule until time t without any knowledge of the jobs that will arrive afterwards. Our on-line technique yields constant performance guarantees for a variety of scheduling environments, and in some cases essentially matches the performance of our off-line LP-based algorithms.
On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
Authors: Dyer Martin , Kannan Ravi
Published: October 2008

We describe a simplification of a recent polynomial-time algorithm of A. I. Barvinok for counting the number of lattice points in a polyhedron in fixed dimension. In particular, we show that only very elementary properties of exponential sums are needed to develop a polynomial-time algorithm.