bluuebunny/crossref_metadata_2025 huggingface dataset:
A Superlinearly Convergent Infeasible-Interior-Point Algorithm for Geometrical LCPs Without a Strictly Complementary Condition
Authors: Mizuno Shinji
Published: October 2008

Some interior-point algorithms have superlinear convergence. When solving an LCP (linear complementarity problem), superlinear convergence had been achieved under the assumption that a strictly complementary solution exists, whether starting from a feasible or an infeasible interior point. In this paper, we propose an algorithm for solving monotone geometrical LCPs, and we prove its superlinear convergence without the strictly complementary condition. The algorithm can start from an infeasible interior point and has globally linear convergence. When we use a big initial point or an almost feasible initial point, the algorithm has polynomial time convergence.
Piecewise Smoothness, Local Invertibility, and Parametric Analysis of Normal Maps
Authors: Pang Jong-Shi , Ralph Daniel
Published: October 2008

This paper is concerned with properties of the Euclidean projection map onto a convex set defined by finitely many smooth, convex inequalities and affine equalities. Under a constant rank constraint qualification, we show that the projection map is piecewise smooth (PC1) hence B(ouligand)-differentiable, or directionally differentiable; and a relatively simple formula is given for the B-derivative. These properties of the projection map are used to obtain inverse and implicit function theorems for associated normal maps, using a new characterization of invertibility of a PC1 function in terms of its B-derivative. An extension of the implicit function theorem which does not require local uniqueness is also presented. Degree theory plays a major role in the analysis of both the locally unique case and its extension.
Overlapping Generation Games with Mixed Strategies
Authors: Gossner Olivier
Published: October 2008

This paper proves a Folk Theorem for overlapping generations games in the case where the mixed strategies used by a player are not observable by the others, but only their realizations are public.
Asymptotically Efficient Adaptive Strategies in Repeated Games Part II. Asymptotic Optimality
Authors: Shimkin Nahum , Shwartz Adam
Published: October 2008

This paper continues the analysis of a dynamic decision problem modeled as a two-person repeated game with random rewards, perfect observations, and incomplete information on one side. The emphasis is on strategies of player 1 (the uninformed player) which maximize his worst-case total reward in a strong non-Bayesian sense, namely, for all possible states of nature. An asymptotic bound on performance is first established, followed by the construction of strategies which achieve this bound. The analysis highlights the efficient acquisition of (statistical) information under conflict conditions, and especially the relations between information and payoff which are inherent in this problem.
Subgradients of Optimal-Value Functions in Dynamic Programming: The Case of Convex Systems Without Optimal Paths
Authors: Seeger Alberto
Published: October 2008

We study the first-order behaviour of the optimal-value function associated to a convex dynamic programming problem. The optimization process takes place in a certain environment characterized by some perturbation parameters affecting the transition costs and/or the evolution law of the dynamic system. An important aspect of this work is that we do not assume the existence of optimal paths to the unperturbed problem.
Compatible Measures and Merging
Authors: Lehrer Ehud , Smorodinsky Rann
Published: October 2008

Two measures, μ and μ̃, are updated as more information arrives. If with μ-probability 1, the predictions of future events according to both measures become close, as time passes, we say that μ̃ merges to μ. Blackwell and Dubins (Blackwell, D., L. Dubins. 1962. Merging of opinions with increasing information. Ann. Math. Statist. 38 882–886.) showed that if μ is absolutely continuous with respect to μ̃ then μ̃ merges to μ. Restricting the definition to prediction of near future events and to a full sequence of times yields the new notion of almost weak merging (AWM), presented here. We introduce a necessary and sufficient condition and show many cases with no absolute continuity that exhibit AWM. We show, for instance, that the fact that μ̃ is diffused around μ implies AWM.
Decomposition and Representation of Coalitional Games
Authors: Marinacci Massimo
Published: October 2008

A coalitional game is a real-valued set function ν defined on an algebra ℱ of subsets of a space X such that ν(Ø) = 0. We prove the existence of a one-to-one correspondence between coalitional games bounded with respect to the composition norm and countably additive measures defined on an appropriate space.
Recursive Repeated Games with Absorbing States
Authors: Flesch J. , Thuijsman F. , Vrieze O. J.
Published: October 2008

We show the existence of stationary limiting average ϵ-equilibria (ϵ > 0) for two-person recursive repeated games with absorbing states. These are stochastic games where all states but one are absorbing, and in the nonabsorbing state all payoffs are equal to zero. A state is called absorbing if the probability of a transition to any other state is zero for all available pairs of actions. For the purpose of our proof, we introduce properness for stationary strategy pairs. Our result is sharp since it extends neither to the case with more nonabsorbing states, nor to the n-person case with n > 2. Moreover, it is well known that the result cannot be strengthened to the existence of 0-equilibria and that repeated games with absorbing states generally do not admit stationary ϵ-equilibria.
The Crease Structure of the Karush-Kuhn-Tucker Set in Parametric Optimization
Authors: Günzel Harald
Published: October 2008

We study optimization problems depending on a parameter vector y. In particular, we consider the crease structure of the set Σ of pairs (x, y) where x is a Karush-Kuhn-Tucker point of the problem associated with parameter y; the Mangasarian-Fromovitz constraint qualification is assumed to hold. We present a lower bound for the fineness of Whitney regular stratifications of Σ. This provides an approximation of its crease structure.
Limiting Behavior of the Derivatives of Certain Trajectories Associated with a Monotone Horizontal Linear Complementarity Problem
Authors: Monteiro R. D. C. , Tsuchiya T.
Published: October 2008

Given a certain monotone horizontal linear complementarity problem (HLCP), we can naturally construct a family of systems of nonlinear equations parametrized by a parameter t ∈ (0, 1] with the property that, as t tends to 0, the corresponding system “converges” to the HLCP. Under reasonable conditions, it has been shown that each system of the family has a unique solution and that, as t tends to 0, these solutions converge to a specific solution of the HLCP. The main purpose of this paper is to study the asymptotic behavior of the derivative of the trajectory of solutions and therefore obtain information on the way the trajectory approaches the solution set of the HLCP. We show that the trajectory of solutions converges to the solution set along a unique and well-characterized direction. Moreover, if the HLCP has a solution satisfying strict complementarity then the direction forms a definite angle with any face of the feasible region which contains the limit point; otherwise, the direction is tangent to some face of the feasible region.
Barrier Functions in Interior Point Methods
Authors: Güler Osman
Published: October 2008

We show that the universal barrier function of a convex cone introduced by Nesterov and Nemirovskii is the logarithm of the characteristic function of the cone. This interpretation demonstrates the invariance of the universal barrier under the automorphism group of the underlying cone. This provides a simple method for calculating the universal barrier for homogeneous cones. We identify some known barriers as the universal barrier scaled by an appropriate constant. We also calculate some new universal barrier functions. Our results connect the field of interior point methods to several branches of mathematics such as Lie groups, Jordan algebras, Siegel domains, differential geometry, complex analysis of several variables, etc.
Second-Order Necessary Conditions for the Infinite-Horizon Variational Problems
Authors: Blot Joël , Hayek Naïla
Published: October 2008

We give new proofs of first-order and second-order necessary conditions for the infinite-horizon variational problems in the framework of the continuous time. We study the notion of conjugate points and we build new second-order necessary conditions. We also translate all of our results into the Hamiltonian formalism. Moreover, we apply these general results to the special Lagrangians in the form [Formula: see text].
A Subgame Property of Stable Equilibria
Authors: Govindan Srihari
Published: October 2008

Stable sets project onto stable sets of subgames in the following sense: stable sets consist of normal form perfect equilibria; for any given ϵ, we could therefore look at the set of strategy profiles in a subgame that are induced by the set of ϵ-perfect equilibria in a neighborhood of a stable set. Now take the limit, as ϵ goes to zero, of the closures of these sets. It is shown that the set so obtained contains a stable set of the subgame.
The Circuit Polytope: Facets
Authors: Bauer Petra
Published: October 2008

Given an undirected graph G = (V, E) and a cost vector c ∈ ℝE, the weighted girth problem is to find a circuit in G having minimum total cost. This problem is in general 𝒩𝒫-hard.

A promising approach to the solution of hard combinatorial optimization problems is given by the so-called cutting plane methods. These involve linear programming techniques based on a partial description of the convex hull of the incidence vectors of possible solutions.

We consider the weighted girth problem in the case where G is the complete graph Kn and study the facial structure of the circuit polytope PCn and some related polyhedra. In the appendix we give complete characterizations of PCn for n up to 6.

We were motivated to study the weighted girth problem by the fact that this problem and variations of it appear as a subproblem, namely the pricing problem, in a column generation approach to the vehicle routing problem.
Complexity of the Minimum Base Game on Matroids
Authors: Nagamochi Hiroshi , Zeng Dao-Zhi , Kabutoya Naohiśa , Ibaraki Toshihide
Published: October 2008

This paper studies the complexity of computing solution concepts for a cooperative game, called the minimum base game (MBG) (E, c), where its characteristic function c : 2E ↦ ℜ is defined as c(S) = (the weight w(B) of a minimum weighted base B ⊆ S), for a given matroid M = (E, ℐ) and a weight function w : E ↦ ℜ. The minimum base game contains, as a special case, the minimum spanning tree game (MSTG) in an edge-weighted graph in which players are located on the edges. By interpreting solution concepts of games (such as core, τ-value and Shapley value) in terms of matroid theory, we obtain: The core of MBG is nonempty if and only if the matroid M has no circuit consisting only of edges with negative weights; checking the concavity and subadditivity of an MBG can be done in oracle-polynomial time; the τ-value of an MBG exists if and only if the core is not empty, the τ-value of MSTG can be computed in polynomial time while there is no oracle-polynomial algorithm for a general MBG; computing the Shapley value of an MSTG is #P-complete, and there is no oracle-polynomial algorithm for computing the Shapley-value of an MBG.
On the Existence of Subjective Upper and Lower Probabilities
Authors: Jaffray Jean-Yves , Philippe Fabrice
Published: October 2008

Consistency between preference under uncertainty modeled by Choquet expected utility theory and preference under imprecise risk (a particular situation of uncertainty characterized by the existence of objective upper and lower probabilities) modeled by linear utility theory is shown to imply that the Choquet capacity must coincide on the imprecisely probabilized events with a fixed linear combination of their upper and lower probabilities. This result is used to derive conditions for the existence of subjective upper and lower probabilities on all the events.
Corrected Diffusion Approximations for a Multistage Production-Inventory System
Authors: Glasserman Paul , Liu Tai-Wen
Published: October 2008

We analyze a multistage inventory system with limited production capacity facing stochastic demands. Each node follows a periodic-review base-stock policy for echelon inventory: in each period, each node attempts to produce enough material to restore cumulative down-stream inventory to a fixed target level. We develop approximations to the key measures of interest (average inventories, average backorders, and service levels) by simultaneously letting the mean demand approach the system's bottleneck capacity and letting the base-stock level for finished goods increase without bound. Using a method of Siegmund, we thus obtain diffusion limits with higher-order correction terms. A numerical example suggests that the correction terms can substantially improve the accuracy of the approximations.
Optimal Adaptive Policies for Markov Decision Processes
Authors: Burnetas Apostolos N. , Katehakis Michael N.
Published: October 2008

In this paper we consider the problem of adaptive control for Markov Decision Processes. We give the explicit form for a class of adaptive policies that possess optimal increase rate properties for the total expected finite horizon reward, under sufficient assumptions of finite state-action spaces and irreducibility of the transition law. A main feature of the proposed policies is that the choice of actions, at each state and time period, is based on indices that are inflations of the right-hand side of the estimated average reward optimality equations.
Asymptotic Analysis for Penalty and Barrier Methods in Convex and Linear Programming
Authors: Auslender A. , Cominetti R. , Haddou M.
Published: October 2008

We consider a wide class of penalty and barrier methods for convex programming which includes a number of specific functions proposed in the literature. We provide a systematic way to generate penalty and barrier functions in this class, and we analyze the existence of primal and dual optimal paths generated by these penalty methods, as well as their convergence to the primal and dual optimal sets. For linear programming we prove that these optimal paths converge to single points.
Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
Authors: Goldberg Andrew V. , Karzanov Alexander V.
Published: October 2008

Suppose we are given an undirected graph with nonnegative integer-valued edge capacities and costs in which a subset of nodes is specified. We consider the problem of finding a collection of flows between arbitrary pairs of specified nodes such that the capacity constraints are satisfied and the sum of costs of flows is minimum, provided that the sum of values of flows is maximum. It is known that this problem has a half-integer optimal solution and such a solution can be found in strongly polynomial time using the ellipsoid method.

In this paper we give two “purely combinatorial” polynomial algorithms for finding a half-integer optimal solution. These are based on capacity and cost scaling techniques and use the double covering method earlier worked out for the problem.
Simpson Points in Planar Problems with Locational Constraints. The Round-Norm Case
Authors: Carrizosa Emilio , Conde Eduardo , Muñoz-Márquez Manuel , Puerto Justo
Published: October 2008

The Simpson set is one of the most popular solution concepts in location models with voting. In this paper we address the problem of finding such a set for planar models with locational constraints when the metric in use is induced by a round norm.

After formulating the problem as a mathematical program, we first propose a general algorithm that enables the evaluation of the corresponding objective function. Then, we show how to solve the problem by proving the existence of a finite dominating set of locations, the best of which can be found by inspection (using the evaluation algorithm proposed).
Simpson Points in Planar Problems with Locational Constraints. The Polyhedral-Gauge Case
Authors: Carrizosa Emilio , Conde Eduardo , Muñoz-Márquez Manuel , Puerto Justo
Published: October 2008

In this paper we address the problem of finding Simpson points in planar models with locational constraints when distances are measured by polyhedral gauges. Making use of the results we have stated in a previous paper, we show here the existence of a finite set of points in the plane, independent of the weights associated with the users, that contains at least a Simpson point.

Connection between Simpson points (as a result of a voting process) and Weber points (as the outcome of a planning process) are explored. It is shown by means of an example that the existing relations for the unconstrained case are no longer true when locational constraints are imposed. In order to reconcile both voting and planning processes, a biobjective problem is described, for which we construct a finite dominating set.
On the Convergence of the Iteration Sequence of Infeasible Path Following Algorithms for Linear Complementarity Problems
Authors: Bonnans J. Frédéric , Potra Florian A.
Published: October 2008

A generalized class of infeasible-interior-point methods for solving horizontal linear complementarity problems is analyzed and sufficient conditions are given for the convergence of the sequence of iterates produced by methods in this class. In particular it is shown that the largest step path following algorithms generates convergent iterates even when starting from infeasible points. The computational complexity of the latter method is discussed in detail and its local convergent rate is analyzed. The primal-dual gap of the iterates produced by this method is superlinearly convergent to zero. A variant of the method has quadratic convergence.
A Closed Form Solution for the Asymmetric Random Polling System with Correlated Levy Input Process
Authors: Lee Thomas (Yew Sing)
Published: October 2008

We introduce a simple approach for modeling and analyzing the random polling system with asymmetric arrival rates, service times, and switchover times. It is assumed that the customer arrival processes at all queues are correlated Levy input processes. Two classes of service disciplines, random gated and 1-limited, are considered. The random gated service discipline generalizes several known service disciplines. We obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, the queue length at the beginning of a cycle of service and the expected delay observed by a customer. For the special case of independent Poisson input processes at all queues, we also provide new proof of several well-known pseudo-conservation laws.
The Compactness of a Policy Space in Dynamic Programming Via an Extension Theorem for Carathéodory Functions
Authors: Yushkevich Alexander A.
Published: October 2008

The background for this paper is a dynamic programming model with a Borel state space and compact action sets. A new simple proof of the compactness of a space of measures corresponding to randomized stationary policies is given, in a topology induced by Carathéodory functions on the state-action space. For this purpose an extension theorem for Carathéodory functions is proved, which is a new version of the Tietze's extension theorem for continuous functions.
Colourful Linear Programming and its Relatives
Authors: Bárány Imre , Onn Shmuel
Published: October 2008

We consider the following Colourful generalization of Linear Programming: given sets of points S1, …, Sk ⊂ ℝd, referred to as colours, and a point b ∈ ℝd, decide whether there is a colourful T = {s1, …, sk} such that b ∈ conv(T), and if there is one, find it. Linear Programming is obtained by taking k = d + 1 and S1 = ⋯ = Sd+1. If k = d + 1 and b ∈ ∩i=1d+1 conv(Si) then a solution always exists: we describe an efficient iterative approximation algorithm for this problem, that finds a colourful T whose convex hull contains a point ϵ-close to b, and analyze its real arithmetic and Turing time complexities. In contrast, we show that Colourful Linear Programming is strongly 𝒩𝒫-complete. We consider a class of linear algebraic relatives of Colourful Linear Programming, and give a computational complexity classification of the related decision and counting problems that arise. We also introduce and discuss the complexity of a hierarchy of (w1, w2)-Matroid-Basis-Nonbasis problems, and give an application of Colourful Linear Programming to the algorithmic problems of Tverberg's theorem in combinatorial geometry.
Averaging Schemes for Variational Inequalities and Systems of Equations
Authors: Magnanti Thomas L. , Perakis Georgia
Published: October 2008

We study averaging methods for solving variational inequalities whose underlying maps are nonexpansive and for solving systems of (asymmetric) equations. Our goal is to establish global convergence results using weaker assumptions than are traditional in the literature. We examine averaging schemes for relaxation algorithms and for their specialization as projection and linearization methods and as Cohen's auxiliary framework. For solving systems of equations, we consider averaging for a general class of methods that includes, as a special case, a generalized steepest descent method. We also develop a new interpretation of a norm condition typically used for establishing convergence of relaxation schemes, by associating it with a strong-f-monotonicity condition.
Optimal Impulse Control When Control Actions Have Random Consequences
Authors: Korn Ralf
Published: October 2008

We consider a generalised impulse control model for controlling a process governed by a stochastic differential equation. The controller can only choose a parameter of the probability distribution of the consequence of his control action which is therefore random. We state optimality results relating the value function to quasi-variational inequalities and a formal optimal stopping problem. We also remark that the value function is a viscosity solution of the quasi-variational inequalities which could lead to developments and convergence proofs of numerical schemes. Further, we give some explicit examples and an application in financial mathematics, the optimal control of the exchange rate.
On Lower Bounds of the Second-Order Directional Derivatives of Ben-Tal, Zowe, and Chaney
Authors: Huang L. R. , Ng K. F.
Published: October 2008

Let f be a regular, locally Lipschitz real-valued function defined on an open convex subset of a normed space. We show that at any unit direction u, the upper second-order derivative D+2f(·; u, 0) (in the sense of Dem'yanov and Pevnyi [Dem'yanov, V. F., A. B. Pevnyi. 1974. Expansion with respect to a parameter of the extremal values of game problems. USSR Computational Math. and Math. Phys. 14 33–45.]; Ben-Tal and Zowe [Ben-Tal, A., J. Zowe. 1982. Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems. Math. Programming 24 70–91.]) has the same lower bounds as the lower second-order derivatives D−2f(·; u, 0). Consequently, one can characterize the convexity of f in terms of these derivatives. We also obtain the corresponding results in terms of Chaney's second-order directional derivatives.
On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data
Authors: Filipowski Sharon
Published: October 2008

An algorithm that solves symmetric linear programs specified with approximate data is given. The algorithm uses knowledge that several of the constraint matrix coefficients of the actual (unknown) instance are equal to zero to reduce the data precision necessary to solve the instance in question. The algorithm is computationally efficient and requires not much more data accuracy than the minimum amount necessary to solve the actual instance. This work aids in the development of a computational complexity theory that uses approximate data and knowledge.
Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
Authors: Goldfarb Donald , Jin Zhiying , Orlin James B.
Published: October 2008

This paper presents two new combinatorial algorithms for the generalized circulation problem. After an initial step in which all flow-generating cycles are canceled and excesses are created, both algorithms bring these excesses to the sink via highest-gain augmenting paths. Scaling is applied to the fixed amount of flow that the algorithms attempt to send to the sink, and both node and arc excesses are used. The algorithms have worst-case complexities of O(m2(m + n log n) log B), where n is the number of nodes, m is the number of arcs, and B is the largest integer used to represent the gain factors and capacities in the network. This bound is better than the previous best bound for a combinatorial algorithm for the generalized circulation problem, and if m = O(n4/3−ϵ), it is better than the previous best bound for any algorithm for this problem.
Nearly Optimal Competitive Online Replacement Policies
Authors: El-Yaniv Ran , Karp Richard M.
Published: October 2008

This paper studies the online replacement problem. In this problem an online player is engaged at each time in one activity. Associated with each activity are a changeover cost and flow rate. While involved in an activity the player's budget is depleted at the activity's flow rate. The player can switch to a new activity whenever it is offered but he pays a changeover cost. The player's goal is to decide when to switch activities so that his total cost is minimized. Typical applications are: equipment, jobs and supplier replacement, mortgage refinancing, etc.

With respect to the competitive ratio performance measure, this paper seeks to determine the best possible competitive ratio achievable by an online replacement policy. Our results include the following: a general lower bound on the performance of any deterministic policy, a policy that is optimal in several special cases and a simple policy that is approximately optimal.
Heavy Tails and Long Range Dependence in On/Off Processes and Associated Fluid Models
Authors: Heath David , Resnick Sidney , Samorodnitsky Gennady
Published: October 2008

On/off models are common inputs for a variety of communication network models as well as storage and inventory models. A stationary renewal process alternating periods of activity (active transmission, fluid buildup, etc) with periods of inactivity (silence, no transmission, inputs off, etc) induces a stationary indicator process which indicates if the system is active or not. Heavy tails for the on periods induces a covariance function for the indicator process which decreases slowly at a rate characteristic of long range dependence. This has dramatic consequences for fluid models where fluid flows in at constant rate and there is a constant rate of release.
An Operational Calculus for Matrix-Exponential Distributions, with Applications to a Brownian (q, Q) Inventory Model
Authors: Asmussen Søren , Perry David
Published: October 2008

A distribution G on (0, ∞) is called matrix-exponential if the density has the form αeTz s where α is a row vector, T a square matrix and s a column vector. Equivalently, the Laplace transform is rational. For such distributions, we develop an operator calculus, where the key step is manipulation of analytic functions f(z) extended to matrix arguments.

The technique is illustrated via an inventory model moving according to a reflected Brownian motion with negative drift, such that an order of size Q is placed when the stock process down-crosses some level q. Explicit formulas for the stationary density are found under the assumption that the leadtime Z has a matrix-exponential distribution, and involve expressions of the form f(T) where f(z) = √1 − 2z.
Nondegeneracy Concepts for Zeros of Piecewise Smooth Functions
Authors: Sznajder Roman , Gowda M. Seetharama
Published: October 2008

A zero of a piecewise smooth function f is said to be nondegenerate if the function is Fréchet differentiable at that point. Using this concept, we describe the usual nondegeneracy notions in the settings of nonlinear (vertical, horizontal, mixed) complementarity problems and the variational inequality problem corresponding to a polyhedral convex set. Some properties of nondegenerate zeros of piecewise affine functions are described. We generalize a recent result of Ferris and Pang on the existence of a nondegenerate solution of an affine variational inequality problem which itself is a generalization of a theorem of Goldman and Tucker.
On Two Interior-Point Mappings for Nonlinear Semidefinite Complementarity Problems
Authors: Monteiro R. D. C. , Pang Jong-Shi
Published: October 2008

Extending our previous work (Monteiro and Pang 1996), this paper studies properties of two fundamental mappings associated with the family of interior-point methods for solving monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. The first of these maps lead to a family of new continuous trajectories which include the central trajectory as a special case. These trajectories completely “fill up” the set of interior feasible points of the problem in the same way as the weighted central paths do the interior of the feasible region of a linear program. Unlike the approach based on the theory of maximal monotone maps taken by Shida and Shindoh (1996) and Shida, Shindoh, and Kojima (1995), our approach is based on the theory of local homeomorphic maps in nonlinear analysis.
Polling Systems in Heavy Traffic: A Bessel Process Limit
Authors: Coffman E. G. , Puhalskii A. A. , Reiman M. I.
Published: October 2008

This paper studies the classical polling model under the exhaustive-service assumption; such models continue to be very useful in performance studies of computer/communication systems. The analysis here extends earlier work of the authors to the general case of nonzero switchover times. It shows that, under the standard heavy-traffic scaling, the total unfinished work in the system tends to a Bessel-type diffusion in the heavy-traffic limit. It verifies in addition that, with this change in the limiting unfinished-work process, the averaging principle established earlier by the authors carries over to the general model.
Persistency in 0-1 Polynomial Programming
Authors: Adams Warren P. , Lassiter Julie Bowers , Sherali Hanif D.
Published: October 2008

An optimal solution to the continuous relaxation of a mixed-integer 0-1 linear programming problem is defined to be persistent if the set of 0-1 variables realizing binary values retains those same binary values in at least one integer optimum. A mixed-integer 0-1 linear program is said to possess the persistency property, or equivalently to be persistent, if every optimal solution to the continuous relaxation is a persistent solution. We study the issue of persistency for a special family of mixed-integer 0-1 linear programming problems which derive from the linearization strategy of Sherali and Adams (1990). In particular, we first examine the hierarchy of linearizations which result from applying this strategy to the general class of unconstrained 0-1 polynomial programming problems, and then consider a class of specially-structured constrained problems. Our study of persistency differs from previous works in that we use the explicit algebraic representation of the convex hull of feasible binary solutions available at the highest level of this hierarchy as a tool for making inferences relative to optimal integer solutions from optimal continuous solutions. Each level of this hierarchy consists of a mixed-integer 0-1 linear program, and we provide, for any given optimal solution to the continuous relaxation of any member of this hierarchy, a set of sufficient conditions on the optimal dual multipliers for the solution to be persistent. These sufficient conditions turn out to be satisfied at every optimal solution of the quadratic level, and thus allow for the reformulation of any unconstrained 0-1 quadratic programming problem as a persistent mixed-integer linear program in a suitably-defined higher-dimensional space. We subsequently address the family of constrained 0-1 polynomial programs and use a projection operation to prove that a special family of 0-1 linear programs possesses the persistency property; included in this family is a generalization of the vertex packing problem that permits quadratic objective function coefficients. Unlike earlier published works on the vertex packing and related problems, our proofs do not rely on Balinski's (1965) extreme point characterization.
A Simplicial Approach to the Determination of an Integer Point of a Simplex
Authors: Dang Chuangyin , van Maaren Hans
Published: October 2008

We propose an algorithm to find an integer point of a simplex. The algorithm is based on an integer labeling rule and a triangulation of the space. Starting at an integer point, the algorithm leaves it along one of n rays and generates a sequence of adjacent simplices of varying dimension. Within a finite number of iterations, the algorithm either yields an integer point of the simplex or proves that no such point exists.
On the Convergence of Fictitious Play
Authors: Krishna Vijay , Sjöström Tomas
Published: October 2008

We study the Brown-Robinson fictitious play process for non-zero sum games. We show that, in general, fictitious play cannot converge cyclically to a mixed strategy equilibrium in which both players use more than two pure strategies.
Finitely Repeated Games with Finite Automata
Authors: Neyman Abraham
Published: October 2008

In honor of R. J. Aumann's 65th birthday

The paper studies the implications of bounding the complexity of the strategies players may select, on the set of equilibrium payoffs in repeated games. The complexity of a strategy is measured by the size of the minimal automation that can implement it.

A finite automation has a finite number of states and an initial state. It prescribes the action to be taken as a function of the current state and a transition function changing the state of the automaton as a function of its current state and the present actions of the other players. The size of an automaton is its number of states.

The main results imply in particular that in two person repeated games, the set of equilibrium payoffs of a sequence of such games, G(n), n = 1, 2, …, converges as n goes to infinity to the individual rational and feasible payoffs of the one shot game, whenever the bound on one of the two automata sizes is polynomial or subexponential in n and both, the length of the game and the bounds of the automata sizes are at least n.

A special case of such result justifies cooperation in the finitely repeated prisoner's dilemma, without departure from strict utility maximization or complete information, but under the assumption that there are bounds (possibly very large) to the complexity of the strategies that the players may use.
Rectangularity and Tightness: A Normal Form Characterization of Perfect Information Extensive Game Forms
Authors: Abdou J.
Published: October 2008

We give an alternative proof of a theorem by Gurvich: A game form G is equivalent to a free extensive game form with perfect information if and only if G is rectangular and tight. It follows that any rectangular and tight game form is Nash solvable. We also present some basic properties of rectangular game forms.
The Travelling Salesman and the PQ-Tree
Authors: Burkard Rainer E. , Deĭneko Vladimir G. , Woeginger Gerhard J.
Published: October 2008

Let D = (dij ) be the n × n distance matrix of a set of n cities {1, 2, …, n}, and let T be a PQ-tree with node degree bounded by d that represents a set Π(T) of permutations over {1, 2, …, n}. We show how to compute for D in O(2 dn 3) time the shortest travelling salesman tour contained in Π(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the shortest pyramidal TSP tour.

A consequence of our result is that the shortcutting phase of the “twice around the tree” heuristic for the Euclidean TSP can be optimally implemented in polynomial time. This contradicts a statement of Papadimitriou and Vazirani as published in 1984.
Locating an Undesirable Facility by Generalized Cutting Planes
Authors: Carrizosa Emilio , Plastria Frank
Published: October 2008

We address the problem of locating an undesirable facility within a compact set by minimizing a strictly decreasing boundedly lower subdifferentiable function of the squared Euclidean distances to a set of fixed points.

Using (generalized) cutting planes, the resolution of this problem is reduced to solving a sequence of maxmin problems. These maxmin problems have a clear geometrical interpretation, which enables to solve them sequentially by means of an on-line enumeration of the vertices of polyhedra in higher dimensions.
The Global Linear Convergence of a Noninterior Path-Following Algorithm for Linear Complementarity Problems
Authors: Burke James V. , Xu Song
Published: October 2008

A noninterior path-following algorithm is proposed for the linear complementarity problem. The method employs smoothing techniques introduced by Kanzow. If the LCP is P0 + R0 and satisfies a nondegeneracy condition due to Fukushima, Luo, and Pang, then the algorithm is globally linearly convergent. As with interior point path-following methods, the convergence theory relies on the notion of a neighborhood for the central path. However, the choice of neighborhood differs significantly from that which appears in the interior point literature. Numerical experiments are presented that illustrate the significance of the neighborhood concept for this class of methods.
Sensitivity Analysis of Optimization Problems Under Second Order Regular Constraints
Authors: Bonnans J. Frédéric , Cominetti Roberto , Shapiro Alexander
Published: October 2008

We present a perturbation theory for finite dimensional optimization problems subject to abstract constraints satisfying a second order regularity condition. This is a technical condition that is always satisfied in the case of semi-definite optimization. We derive Lipschitz and Hölder expansions of approximate optimal solutions, under a directional constraint qualification hypothesis and various second order sufficient conditions that take into account the curvature of the set defining the constraints of the problem. We show how the theory applies to semi-infinite programs in which the contact set is a smooth manifold and the quadratic growth condition in the constraint space holds, and discuss the differentiability of metric projections as well as the Moreau-Yosida regularization. Finally we show how the theory applies to semi-definite optimization.
High Order Infeasible-Interior-Point Methods for Solving Sufficient Linear Complementarity Problems
Authors: Stoer Josef , Wechs Martin , Mizuno Shinji
Published: October 2008

In this paper we develop systematically infeasible-interior-point methods of arbitrarily high order for solving horizontal linear complementarity problems that are sufficient in the sense of Cottle, Pang and Venkateswaran (1989). The results apply to degenerate problems and problems having no strictly complementary solution. Variants of these methods are described that eventually avoid recentering steps, and for which all components of the approximate solutions converge superlinearly at a high order, and other variants which even terminate with a solution of the complementarity problem after finitely many steps.
A General Class of Greedily Solvable Linear Programs
Authors: Queyranne Maurice , Spieksma Frits , Tardella Fabio
Published: October 2008

A greedy algorithm solves a dual pair of linear programs where the primal variables are associated to the elements of a sublattice B of a finite product lattice, and the cost coefficients define a submodular function on B. This approach links and generalizes two well-known classes of greedily solvable linear programs. The primal problem generalizes the (ordinary and multi-index) transportation problems satisfying a Monge condition (Hoffman 1963; Bein et al. 1995) to the case of forbidden cells where the nonforbidden cells form a sublattice. The dual problem generalizes to an arbitrary finite product lattice the linear optimization problem over submodular polyhedra (Lovász 1983; Fujishige and Tomizawa 1983), which stemmed from the work of Edmonds (1970) on polymatroids. Our model and results also encompass the dual pairs of linear programs and their greedy solutions defined by Lovász (1983) for the special case of the Boolean algebra, and by Faigle and Kern (1996) for the case of so-called “rooted forests.” We also discuss relationships between Monge properties and submodularity, and present a class of problems with submodular costs arising in production and logistics.
Minimum-Aggregate-Concave-Cost Multicommodity Flows in Strong-Series-Parallel Networks
Authors: Ward Julie A.
Published: October 2008

This work develops a polynomial-time dynamic-programming algorithm for minimum-aggregate-concave-cost multicommodity flow problems in strong-series-parallel networks. Many important problems from production and inventory management, capacity planning, network design and transportation can be formulated in these terms. Our results include a characterization of extreme flows in strong-series-parallel networks and an algorithm based on this characterization that searches extreme flows efficiently to find an optimal one. The algorithm runs in time proportional to A(N + K), where A, N and K are respectively the numbers of arcs, nodes and commodities in the network, and appears to be the first to solve the problem in polynomial time. When applied to the dynamic economic-order-quantity problem, the algorithm matches the performance of that of Wagner and Whitin (1958). Moreover, our algorithm has broader applications, including the multi-division capacity expansion problem and the generalization of the dynamic economic-order-quantity problem to series-parallel production processes in which subassemblies are assembled into a finished product.
Primal-Dual Affine-Scaling Algorithms Fail for Semidefinite Programming
Authors: Muramatsu Masakazu , Vanderbei Robert J.
Published: October 2008

In this paper, we give an example of a semidefinite programming problem in which primal-dual affine-scaling algorithms using the HRVW/KSH/M, MT, and AHO directions fail. We prove that each of these algorithms can generate a sequence converging to a non-optimal solution and that, for the AHO direction, even its associated continuous trajectory can converge to a non-optimal point. In contrast with these directions, we show that the primal-dual affine-scaling algorithm using the NT direction for the same semidefinite programming problem always generates a sequence converging to the optimal solution. Both primal and dual problems have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and are nondegenerate everywhere.
Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
Authors: Anstreicher Kurt M. , Ji Jun , Potra Florian A. , Ye Yinyu
Published: October 2008

We consider an infeasible-interior-point algorithm, endowed with a finite termination scheme, applied to random linear programs generated according to a model of Todd. Such problems have degenerate optimal solutions, and possess no feasible starting point. We use no information regarding an optimal solution in the initialization of the algorithm. Our main result is that the expected number of iterations before termination with an exact optimal solution is O(n ln(n)).
Ellipsoidal Approximations of Convex Sets Based on the Volumetric Barrier
Authors: Anstreicher K. M.
Published: October 2008

Let C ⊂R n be a convex set. We assume that ‖x‖∞ ≤ 1 for all x ∈ C, and that C contains a ball of radius 1/R. For x ∈ R n , r ∈ R, and B and n × n symmetric positive definite matrix, let E(x, B, r) = {y|(y − x) T B(y − x) ≤ r 2}. A β-rounding of C is an ellipsoid E(x, B, r) such that E(x, B, r/β) ⊂ C ⊂ E(x, B, r). In the case that C is characterized by a separation oracle, it is well known that an O(n 3/2)-rounding of C can be obtained using the shallow cut ellipsoid method in O(n 3 ln(nR)) oracle calls. We show that a modification of the volumetric cutting plane method obtains an O(n 3/2)-rounding of C in O(n 2 ln(nR)) oracle calls. We also consider the problem of obtaining an O(n)-rounding of C when C has an explicit polyhedral description. Our analysis uses a new characterization of circumscribing ellipsoids centered at, or near, the volumetric center of a polyhedral set.
Repeated Games with Incomplete Information on One Side: The Case of Different Discount Factors
Authors: Lehrer Ehud , Yariv Leeat
Published: October 2008

Two players engage in a repeated game with incomplete information on one side, where the underlying stage-games are zero-sum. In the case where players evaluate their stage-payoffs by using different discount factors, the payoffs of the infinitely repeated game are typically non zero-sum. However, if players grow infinitely patient, then the equilibrium payoffs will sometimes approach the zero-sum result, depending on the asymptotic relative patience of the players. We provide sufficient conditions that ensure a zero-sum limit. Moreover, we provide examples of games violating these conditions that possess “cooperative” equilibria whose payoffs are bounded away from the zero-sum payoffs set.
Weak Univalence and Connectedness of Inverse Images of Continuous Functions
Authors: Gowda M. Seetharama , Sznajder Roman
Published: October 2008

A continuous function f with domain X and range f(X) in Rn is weakly univalent if there is a sequence of continuous one-to-one functions on X converging to f uniformly on bounded subsets of X. In this article, we establish, under certain conditions, the connectedness of an inverse image f−1(q). The univalence results of Radulescu-Radulescu, Moré-Rheinboldt, and Gale-Nikaido follow from our main result. We also show that the solution set of a nonlinear complementarity problem corresponding to a continuous P0-function is connected if it contains a nonempty bounded clopen set; in particular, the problem will have a unique solution if it has a locally unique solution.
Convergence of a Class of Inexact Interior-Point Algorithms for Linear Programs
Authors: Freund Roland W. , Jarre Florian , Mizuno Shinji
Published: October 2008

We present a convergence analysis for a class of inexact infeasible-interior-point methods for solving linear programs. The main feature of inexact methods is that the linear systems defining the search direction at each interior-point iteration need not be solved to high accuracy. More precisely, we allow that these linear systems are only solved to a moderate accuracy in the residual, but no assumptions are made on the accuracy of the search direction in the search space. In particular, our analysis does not require that feasibility is maintained even if the initial iterate happened to be a feasible solution of the linear program. We also present a few numerical examples to illustrate the effect of using inexact search directions on the number of interior-point iterations.