bluuebunny/crossref_metadata_2025 huggingface dataset:
Barrier Functions and Interior-Point Algorithms for Linear Programming with Zero-, One-, or Two-Sided Bounds on the Variables
Authors: Freund Robert M. , Todd Michael J.
Published: October 2008

This study examines two different barrier functions and their use in both path-following and potential-reduction interior-point algorithms for solving a linear program of the form: minimize cTx subject to Ax = b and l ≤ x ≤ u, where components of l and u can be nonfinite, so the variables xj, can have 0-, 1-, or 2-sided bounds, j = 1, …, n. The barrier functions that we study include an extension of the standard logarithmic barrier function and an extension of a barrier function introduced by Nesterov. In the case when both l and u have all of then components finite, these barrier functions are [Formula: see text] and [Formula: see text] Each of these barrier functions gives rise to suitable primal and dual metrics that are used to develop both path-following and potential-reduction interior-point algorithms for solving such linear programming problems. The resulting complexity bounds on the algorithms depend only on the number of bounded variables, rather than on the number of finite inequalities in the system 1 ≤ x ≤ u, in contrast to the standard complexity bounds for interior-point algorithms. These enhanced complexity bounds stem directly from the choice of a “natural” metric induced by the barrier function. This study also demonstrates the inter-connection between the notion of self-concordance (introduced by Nesterov and Nemirovsky) and properties of the two barrier functions that drive the results contained herein.
Successive Averages of Firmly Nonexpansive Mappings
Authors: Flåm Sjur Didrik
Published: October 2008

The problem considered here is to find common fixed points of (possibly infinitely) many firmly nonexpansive selfmappings in a Hilbert space. For this purpose we use averaged relaxations of the original mappings, the averages being Bochner integrals with respect to chosen measures. Judicious choices of such measures serve to enhance the convergence towards common fixed points. Since projection operators onto closed convex sets are firmly nonexpansive, the methods explored are applicable for solving convex feasibility problems. In particular, by varying the measures, our analysis encompasses recent developments of so-called block-iterative algorithms. We demonstrate convergence theorems which cover and extend many known results.
Stochastic Dominance on Unidimensional Grids
Authors: Fishburn Peter C. , Lavalle Irving H.
Published: October 2008

Special stochastic-dominance relations for probability distributions on a finite grid of evenly-spaced points are considered. The relations depend solely on iterated partial sums of grid-point probabilities and are very computer efficient. Their corresponding classes of utility functions for expected-utility comparisons consist of functions defined on the grid that mimic in the large the traditional continuous functions whose derivatives alternate in sign. The first-degree and second-degree relations are identical to their traditional counterparts defined from iterated integrals of cumulative distribution functions. The higher-degree relations differ from the traditional relations in interesting and sometimes subtle ways. The paper explores aspects of the partial-sums relations, including effects of grid refinements and extensions, and describes their relationships to the traditional relations.
An Infinitely Summable Series Implementation of Interior Point Methods
Authors: Saigal Romesh
Published: October 2008

We consider an alternative implementation of the interior point methods. In the popular implementations, a variant of sparse Cholesky factorization is integrated with a conjugate gradient type iterative method. In contrast, we set up the problem as an infinitely summable series of vectors. This series is then, iteratively, summed. At each iteration, a procedure based on “least squares” is used to obtain an estimate of the “tail” of the series. In addition, using Chebychev approximations, we show how to accelerate the convergence of this procedure. In this alternative approach, besides finding Cholesky factors of some simpler matrices, only multiplications by some matrix are involved. This may be an advantage since in the later part of these methods, the linear system to be solved has a tendency to become ill conditioned. We present some evidence (for the case of the dual affine scaling method applied to the assignment problem) which supports this conclusion.
On the Von Neumann Economic Growth Problem
Authors: Ye Yinyu
Published: October 2008

We study the complexity of the von Neumann economic growth problem: [Formula: see text] where A and B are given two nonnegative and rational m × n-matrices, and A has no all-zero column. Let the binary data length of A and B be L. We develop an interior-point algorithm to generate a γ̄, such that γ* − 2−1 ≤ γ̄ ≤ γ*, in O((m + n)(L + min(m, n)t)) iterations where each iteration solves a system of (m + n) linear equations.
Explicit Solution of Inventory Problems with Delivery Lags
Authors: Bar-Ilan Avner , Sulem Agnès
Published: October 2008

We consider a continuous-time inventory system with fixed delivery lag, subject to a demand modelled as a diffusion process with drift. Excess demand is backlogged. We prove that the optimal ordering policy is a function of the sum of the stock on hand and the stock ordered but not yet delivered. Moreover, we state a relation linking the value function when orders are pending with the value function when no order is pending. As a consequence, the (a priori) infinite dimensional Quasi-Variational inequality (QVI) satisfied by the value function reduces to a finite dimensional one. The one-product inventory problem is then solved explicitly in the case of linear holding and shortage costs with fixed and proportional ordering cost. The optimal policy is determined; it is an (s, S) policy applied to the sum of stock on hand and orders pending, which means that when this sum decays below a critical level s, an order to level S is placed.
A multiclass Station with Markovian Feedback in Heavy Traffic
Authors: Dai J. G. , Kurtz Thomas G.
Published: October 2008

This paper proves a heavy traffic limit theorem for a multiclass service station with Markovian feedback. This result generalizes the one proved by Reiman (Reiman, M. I. 1988. A multiclass feedback queue in heavy traffic. Adv. Appl. Probab. 20 179–207.). Our approach also significantly simplifies Reiman's original proof. Numerical examples are presented to illustrate the effectiveness of the QNET method which is rooted in the theorem.
Asymptotically Efficient Adaptive Strategies in Repeated Games Part I: Certainty Equivalence Strategies
Authors: Shimkin Nahum , Shwartz Adam
Published: October 2008

This paper addresses the problem of dynamic decision making in an uncertain and competitive environment. A decision maker (player 1) faces a system about which he has some (parametric) uncertainty, and which is affected also by the actions of other agents. We focus on a worst-case analysts from the viewpoint of player 1, using the simplified model of a repeated matrix game with lack of information on one side, where single-stage rewards are random but announced, and perfect observations are assumed. Certain ideas from the field of stochastic adaptive control are used to formulate performance criteria in a non-Bayesian setting, and to devise appropriate control strategies. The basic performance measure is the total reward accumulated by player 1 over all stages played; the purpose of player 1 is to guarantee that his expected total reward will be “close” to what he could guarantee under complete information. The present paper considers adaptive decision strategies of the Certainty Equivalence type, based on a (modified) Maximum Likelihood estimator, and studies their asymptotic (long-term) performance. A sequel paper will be devoted to “asymptotically optimal” strategies.
Complexity of Product Positioning and Ball Intersection Problems
Authors: Crama Yves , Hansen Pierre , Jaumard Brigitte
Published: October 2008

The product positioning problem consists in choosing the attributes of a new product in such a way as to maximize its market share, i.e., to attract a maximum number of customers. Mathematically, the problem can be formulated as follows: given a set of balls (with respect to some norm) and a weight associated to each ball, find a point which maximizes the sum of the weights of the balls containing it. The complexity of this problem is investigated in the case of the L∞ and of the Euclidean norms. In both cases, the problem is proved to be NP-hard, but to be polynomially solvable when the dimension of the space is fixed.
Diffusion Approximation for a Controlled Stochastic Manufacturing System with Average Cost Minimization
Authors: Krichagina Elena V. , Lou Sheldon X. C. , Sethi Suresh P. , Taksar Michael I.
Published: October 2008

We consider the problem of production control in a single machine, single product, unreliable manufacturing system facing a constant demand d. The goal is to minimize the expected average (per unit time) inventory/backlog costs. Under heavy traffic condition, i.e., when the average production capacity is close to demand, the problem is approximated by a singular stochastic control problem. The approximate problem can be solved explicitly. The solution is then interpreted in terms of the actual manufacturing system and a control policy for this system is derived. We prove that the resulting policy is nearly optimal under the heavy traffic condition. This policy is characterized by a critical level z0. That is, produce at maximal rate r when inventory is less than z0, and at the demand rate d when the inventory is equal to z0. The quality of the approximate control is also discussed by comparing it to known results, when they are available.
Convergence of Interior Point Algorithms for the Monotone Linear Complementarity Problem
Authors: Bonnans J. Frédéric , Gonzaga Clovis C.
Published: October 2008

The literature on interior point algorithms shows impressive results related to the speed of convergence of the objective values, but very little is known about the convergence of the iterate sequences.

This paper studies the horizontal linear complementarity problem, and derives general convergence properties for algorithms based on Newton iterations. This problem provides a simple and general framework for most existing primal-dual interior point methods. The conclusion is that most of the published algorithms of this kind generate convergent sequences. In many cases (whenever the convergence is not too fast in a certain sense), the sequences converge to the analytic center of the optimal face.
Repeated Games and Partial Differential Equations
Authors: De Meyer Bernard
Published: October 2008

Let vn(p) denote the value of the n-times repeated zero-sum game with incomplete information on one side and full monitoring and let u(p) be the value of the average game G(p). The error term ϵn(p) = vn(p) − cav(u)(p) is then converging to zero at least as rapidly as 1/√n.

In this paper, we analyze the convergence of ψn(p) = √nϵn(p) in the games with square payoff matrices such that the optimal strategy of the informed player in the average game G(p) is unique, is completely mixed and does not depend on p.

Our main result is that the existence of a solution ψ* to a partial differential equation with appropriate boundary conditions and regularity properties implies the uniform convergence of ψn to the Fenchel conjugate of ψ*.

In particular cases, the P.D.E. problem is linear and its solution ψ* is then related to the multidimensional normal distribution.
A Pivotal Method for Affine Variational Inequalities
Authors: Cao Menglin , Ferris Michael C.
Published: October 2008

We explain and justify a path-following algorithm for solving the equations AC(x) = a, where A is a linear transformation from ℝn to ℝn, C is a polyhedral convex subset of ℝn, and AC is the associated normal map. When AC is coherently oriented, we are able to prove that the path following method terminates at the unique solution of AC(x) = a, which is a generalization of the well known fact that Lemke's method terminates at the unique solution of LCP(q, M) when M is a P = matrix. Otherwise, we identity two classes of matrices which are analogues of the class of copositive-plus and L-matrices in the study of the linear complementarity problem. We then prove that our algorithm processes AC(x) = a when A is the linear transformation associated with such matrices. That is, when applied to such a problem, the algorithm will find a solution unless the problem is infeasible in a well specified sense.
Two Algorithmic Results for the Traveling Salesman Problem
Authors: Barvinok Alexander I.
Published: October 2008

For any norm in a Euclidean space and for any number δ > 0 we present a polynomial time algorithm which computes a Hamiltonian circuit with the given vertices in the space whose length approximates, with relative error less than δ, the largest length of a Hamiltonian circuit with these vertices. We also present an algorithm which for a given graph with n vertices computes the number of Hamiltonian circuits in this graph with 2n+O(log n) time complexity and a polynomial in n space complexity. As a by-product of our approach we prove that the permanent of a matrix can be computed in polynomial time provided the rank of the matrix is fixed.
Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
Authors: Bertsimas Dimitris , Niño-Mora José
Published: October 2008

We show that if performance measures in stochastic and dynamic scheduling problems satisfy generalized conservation laws, then the feasible region of achievable performance is a polyhedron called an extended polymatroid, that generalizes the classical polymatroids introduced by Edmonds. Optimization of a linear objective over an extended polymatroid is solved by an adaptive greedy algorithm, which leads to an optimal solution having an indexability property (indexable systems). Under a certain condition the indices possess a stronger decomposition property (decomposable systems). The following problems can be analyzed using our theory: multiarmed bandit problems, branching bandits, scheduling of multiclass queues (with or without feedback), scheduling of a batch of jobs. Consequences of our results include: (1) a characterization of indexable systems as systems that satisfy generalized conservation laws, (2) a sufficient condition for indexable systems to be decomposable, (3) a new linear programming proof of the decomposability property of Gittins indices in multiarmed bandit problems, (4) an approach to sensitivity analysis of indexable systems, (5) a characterization of the indices of indexable systems as sums of dual variables, and an economic interpretation of the branching bandit indices in terms of retirement options, (6) an analysis of the indexability of undiscounted branching bandits, (7) a new algorithm to compute the indices of indexable systems (in particular Gittins indices), as fast as the fastest known algorithm, (8) a unification of Klimov's algorithm for multiclass queues and Gittms' algorithm for multiarmed bandits as special cases of the same algorithm, (9) a closed formula for the maximum reward of the multiarmed bandit problem, with a new proof of its submodularity and (10) an understanding of the invariance of the indices with respect to some parameters of the problem. Our approach provides a polyhedral treatment of several classical problems in stochastic and dynamic scheduling and is able to address variations such as: discounted versus undiscounted cost criterion, rewards versus taxes, discrete versus continuous time, and linear versus nonlinear objective functions.
The Degree of an Exact Order Matrix
Authors: Sridhar R.
Published: October 2008

The classes of exact order k matrices for any positive integer k, were defined and studied by Mohan, Parthasarathy and Sridhar (Mohan, S. R., T. Parthasarathy, R. Sridhar. 1994. The linear complementarity problem with exact order matrices. Math. Oper. Res. 19 618–644.). Here, we prove results on the linear complementarity problem LCP(q, M), for M belonging to the class of exact order k, k ≥ 3, using the concepts of degree theory. Our main result in this paper consists in proving that a matrix M ∈ Rn×n of exact order k, for any positive integer n ≥ k + 3, belongs to the class Q if and only if the degree of M is either +1 or −1. Also, a complete characterization of exact order 2 matrices is presented, in terms of their inverse structure.
Maximum Entropy Reconstruction Using Derivative Information, Part 1: Fisher Information and Convex Duality
Authors: Borwein J. M. , Lewis A. S. , Noll D.
Published: October 2008

Maximum entropy spectral density estimation is a technique for reconstructing an unknown density function from some known measurements by maximizing a given measure of entropy of the estimate. Here we present a variety of new entropy measures which attempt to control derivative values of the densities. Our models apply among others to the inference problem based on the averaged Fisher information measure. The duality theory we develop resembles models used in convex optimal control problems. We present a variety of examples, including relaxed moment matching with Fisher information and best interpolation on a strip.
On the Pathwise Optimal Bernoulli Routing Policy for Homogeneous Parallel Servers
Authors: Koole Ger
Published: October 2008

A long-standing conjecture on the optimal Bernoulli routing policy is proven to be true. For the case of equal exponential service times it is shown that splitting equally among the queues minimizes the departure times in a stochastic pathwise sense. A new technique is used, showing that certain distributional properties related to Schur convexity propagate forward in time.
A Faster Combinatorial Algorithm for the Generalized Circulation Problem
Authors: Goldfarb Donald , Jin Zhiying
Published: October 2008

This paper presents a modified version of Algorithm MCF proposed by Goldberg, Plotkin and Tardos for the generalized circulation problem. This new combinatorial algorithm has a worst-case complexity that is better than the complexities of the MCF and Fat-Path combinatorial algorithms of Goldberg, Plotkin, and Tardos (Goldberg, A. V., S. A. Plotkin, E. Tardos. 1991. Combinatorial algorithms for the generalized circulation problem. Math. Oper. Res. 16 351–379.).
Directional-Quasi-Convexity, Asymmetric Schur-Convexity and Optimality of Consecutive Partitions
Authors: Hwang Frank K. , Rothblum Uriel G.
Published: October 2008

The current paper has the following distinct goals:

1. To generalize standard quasi-convexity to obtain a weaker property of functions that suffices for optimality of extreme points. Specifically, it is required that intersections of the level sets of the function with line segments having direction in a prescribed set are convex.

2. To characterize Schur-convexity for symmetric functions through the above generalization of quasi-convexity, thereby obtaining a previously unknown relationship of Schur-convexity and (standard) convexity. The new characterization is used to extend the definition of Schur-convexity to functions which are not symmetric.

3. To obtain new sufficient conditions for the optimality of consecutive partitions, by using the new definition of Schur-convexity for functions that are not necessarily symmetric.

The conclusion that Schur-convexity is an instance of a convexity property that implies the optimality of extreme points, unifies two approaches that were used in the literature to prove optimality of subsets of the domain of real-valued functions. The two tools—quasi-convexity and Schur-convexity—were previously considered as distinct techniques.
Global Methods for Nonlinear Complementarity Problems
Authors: Moré Jorge J.
Published: October 2008

Global methods for nonlinear complementarity problems formulate the problem as a system of nonsmooth nonlinear equations, or use continuation to trace a path defined by a smooth system of nonlinear equations. We formulate the nonlinear complementarity problem as a bound-constrained nonlinear least squares problem. Algorithms based on this formulation are applicable to general nonlinear complementarity problems, can be started from any nonnegative starting point, and each iteration only requires the solution of systems of linear equations. Convergence to a solution of the nonlinear complementarity problem is guaranteed under reasonable regularity assumptions. The converge rate is Q-linear, Q-superlinear, or Q-quadratic, depending on the tolerances used to solve the subproblems.
Convergence Analysis of Stochastic Algorithms
Authors: Shapiro A. , Wardi Y.
Published: October 2008

This paper investigates asymptotic convergence to stationary points of gradient descent algorithms where the functions involved are not available in closed form but are approximated by sequences of random functions. The algorithms take large stepsizes and use progressively finer precision at successive iterations. Two kinds of optimization algorithms are considered: one, where the limiting function (to be minimized) is differentiable but the random approximating functions can be nondifferentiable, and the other, where both the limiting and approximating functions are nondifferentiable and convex. Such functions often arise in discrete event dynamic system-models in various application areas.

The analysis brings together ideas and techniques from the disciplines of nonlinear programming and nondifferentiable optimization on one hand, and stochastic processes and especially uniform laws of large numbers, on the other hand. A general algorithmic frame-work is first developed and analyzed, and then applied to the specific algorithms considered. The analysis extends the results derived to date for similar algorithms, and has a potential for further extensions in proving convergence of other algorithms as well.
Deterministic Near-Optimal Controls. Part II: Dynamic Programming and Viscosity Solution Approach
Authors: Zhou Xun Yu
Published: October 2008

Near-optimization is as sensible and important as optimization for both theory and applications. This paper concerns dynamic near-optimization, or near-optimal controls, for systems governed by deterministic ordinary differential equations, and uses dynamic programming to study the near-optimality. Since nonsmoothness is inherent in this subject, the viscosity solution approach is employed to investigate the problem. The dynamic programming equation is derived in terms of ϵ-superdifferential/subdifferential. The relationships among the adjoint functions, the value functions, and the Hamiltonian along near-optimal trajectories are revealed. Verification theorems with which near-optimal feedback controls can be constructed are obtained.
The Computation of a Continuum of Constrained Equilibria
Authors: Herings Jean-Jacques , Talman Dolf , Yang Zaifu
Published: October 2008

The equilibria of a model of an exchange economy with price rigidities are called constrained equilibria. A simplicial algorithm on the unit cube is proposed to compute an approximation of a continuum of zero points of the excess demand correspondence of such an economy. This continuum of zero points corresponds to a continuum of constrained equilibria of the economy, linking the two so-called trivial equilibria. Moreover, the convergence properties of the algorithm and the accuracy of the approximate constrained equilibria obtained by the algorithm are discussed. Finally, an example is given as an illustration.
Proximity of Information in Games with Incomplete Information
Authors: Monderer Dov , Samet Dov
Published: October 2008

Existing notions of proximity of information fail to satisfy desired continuity properties of equilibria in games with incomplete information. We demonstrate this failure and propose a topology on information structures which is the minimal one that satisfies those continuity requirements. This topology is defined in terms of the common belief players have about the proximity of each player's information.
The Modified Nucleolus as Canonical Representation of Weighted Majority Games
Authors: Sudhölter Peter
Published: October 2008

A new solution concept for cooperative transferable utility games is introduced, which is strongly related to the nucleolus and therefore called modified nucleolus. It has many properties in common with the prenucleolus and can be considered as the canonical restriction of the prenucleolus of a certain replicated game. For weighted majority games this solution concept induces a representation of the game. In the special case of weighted majority constant-sum games and homogeneous games respectively the nucleolus and the minimal integer representation respectively are adequate candidates for a canonical representation (see Peleg [Peleg, B. 1968. On weights of constant-sum majority games. SIAM J. Appl. Math. 16 527–532.] and Ostman [Ostmann, A. 1987a. On the numerical representation of homogeneous games. Int. J. Game Theory 16 69–81.]). Fortunately the modified nucleolus coincides with the just mentioned solutions in these special cases and can, therefore, be seen as a canonical representation in the general weighted majority case.
Computing the Nucleolus by Solving a Prolonged Simplex Algorithm
Authors: Potters Jos A. M. , Reijnierse Johannes H. , Ansing Michel
Published: October 2008

This paper describes a fast algorithm to find the nucleolus of any game with a nonempty imputation set. It is based on the algorithm scheme of Maschler et al. (Maschler, M., J. Potters, S. Tijs. 1992. The general nucleolus and the reduced game property. Internal. J. Game Theory 21 83–106.) for the general nucleolus.
Following a “Balanced” Trajectory from an Infeasible Point to an Optimal Linear Programming Solution with a Polynomial-Time Algorithm
Authors: Freund Robert M.
Published: October 2008

This paper is concerned with the problem of following a trajectory from an infeasible starting point directly to an optimal solution of the linear programming problem. A class of trajectories for the problem is defined, based on the notion of a β-balanced solution to the problem. Given a prespecified positive balancing constant β, an infeasible solution x is said to be β-balanced if the optimal value gap is less than or equal to β times the infeasibility gap. Mathematically, this can be written as cTx − z* ≤ βξTx, where the linear form ξTx is the Phase I objective function and z* is the optimal objective value of the linear program. The concept of a β-balanced solution is used to define a class of trajectories from an infeasible point to an optimal solution of a given linear program. Each trajectory has the property that all points on or near the trajectory (in a suitable metric) are β-balanced. The main thrust of the paper is the development of an algorithm that traces a given β-balanced trajectory from a starting point near the trajectory to an optimal solution to the given linear programming problem in polynomial time. More specifically, the algorithm allows for fixed improvement in the bound on the Phase I and the Phase II objectives in O(n) Newton steps.
Hilbert Bases and the Facets of Special Knapsack Polytopes
Authors: Weismantel Robert
Published: October 2008

We present a linear description of the 0/1 knapsack polytope for the special case when the number of different weights of the items is two. The inequalities needed for this description involve elements of the Hilbert basis of the cone of exchange vectors.
Calculating K-Connectedness Reliability Using Steiner Bounds
Authors: Chari Manoj K. , Provan J. Scott
Published: October 2008

The K-connectedness reliability problem considered in this paper has as input undirected graph G, subset K of terminal vertices, and common edge failure probability p, and as output the probability R(G, K, p) that—when edges fail independently each with probability p—the set of operating edges connect every pair of vertices of K. We show how the Steiner property held by the underlying simplicial complex associated with this problem can lead to an extension of the Ball-Provan shellability bounds to this more general problem. We show in computational studies that this bound performs quite favorably in comparison with known approximation techniques.
Constrained Discounted Dynamic Programming
Authors: Feinberg Eugene A. , Shwartz Adam
Published: October 2008

This paper deals with constrained optimization of Markov Decision Processes with a countable state space, compact action sets, continuous transition probabilities, and upper semicontinuous reward functions. The objective is to maximize the expected total discounted reward for one reward function, under several inequality constraints on similar criteria with other reward functions.

Suppose a feasible policy exists for a problem with M constraints. We prove two results on the existence and structure of optimal policies. First, we show that there exists a randomized stationary optimal policy which requires at most M actions more than a nonrandomized stationary one. This result is known for several particular cases. Second, we prove that there exists an optimal policy which is (i) stationary (nonrandomized) from some step onward, (ii) randomized Markov before this step, but the total number of actions which are added by randomization is at most M, (iii) the total number of actions that are added by nonstationarity is at most M.

We also establish Pareto optimality of policies from the two classes described above for multi-criteria problems. We describe an algorithm to compute optimal policies with properties (i)–(iii) for constrained problems.

The policies that satisfy properties (i)–(iii) have the pleasing aesthetic property that the amount of randomization they require over any trajectory is restricted by the number of constraints. In contrast, a randomized stationary policy may require an infinite number of randomizations over time.
Integrals of Set-Valued Functions with a Countable Range
Authors: Khan M. Ali , Sun Yeneng
Published: October 2008

Approximate versions, both of Lyapunov-type results on the compactness and convexity of the integral of a correspondence, and Fatou-type results on the preservation of upper semicontinuity by integration, are well known in the context of an infinite dimensional space. We report exact versions of these two types of results for integrals of Banach space valued correspondences with a countable range. We present results on both Bochner and Gel’fand integration.
Homeomorphism Conditions for Coherently Oriented Piecewise Affine Mappings
Authors: Scholtes Stefan
Published: October 2008

This article is mainly concerned with the homeomorphism problem for piecewise affine mappings (PA-maps), i.e., mappings which coincide with an affine mapping on each polyhedron of some finite polyhedral subdivision of ℝn. In the first part, we prove that a PA-map can be defined without referring to a subdivision of ℝn as a continuous mapping which coincides at every point x ∈ ℝn with at least one function from a finite collection of affine functions. The second part studies the recession function of a PA-map. It is shown that the recession function is piecewise linear and that a coherently oriented PA-map is a homeomorphism if and only if its recession function is a homeomorphism. In the last part we prove that a coherently oriented PA-map is a homeomorphism if it admits a corresponding polyhedral subdivision of ℝn such that for some number k ∈ {2, …, n} every face of codimension k is contained in at most 2k polyhedra, provided the subdivision contains at least one face of codimension k.
On Vaidya's Volumetric Cutting Plane Method for Convex Programming
Authors: Anstreicher Kurt M.
Published: October 2008

We describe a simplified and strengthened version of Vaidya's volumetric cutting plane method for finding a point in a convex set 𝒞 ⊂ Rn. At each step the algorithm has a system of linear inequality constraints which defines a polyhedron 𝒫 ⊃ 𝒞, and an interior point x ∈ 𝒫. The algorithm then either drops one constraint, or calls an oracle to check if x ∈ 𝒞, and, if not, obtain a new constraint that separates x from 𝒞. Following the addition or deletion of a constraint, the algorithm takes a small number of Newton steps for the volumetric barrier V(·). Progress of the algorithm is measured in terms of changes in V(·). The algorithm is terminated when either it is discovered that x ∈ 𝒞, or V(·) becomes large enough to demonstrate that the volume of 𝒞 must be below some prescribed amount. The complexity of the algorithm compares favorably with that of the ellipsoid method, especially in terms of the number of calls to the separation oracle. Compared to Vaidya's original analysis, we decrease the total number of Newton steps required for termination by a factor of about 1.3 million, while at the same time decreasing the maximum number of constraints used to define 𝒫 from 107n to 200n.
Separating Clique Trees and Bipartition Inequalities Having a Fixed Number of Handles and Teeth in Polynomial Time
Authors: Carr Robert
Published: October 2008

Many important cutting planes have been discovered for the traveling salesman problem. Among them are the clique tree inequalities and the more general bipartition inequalities. Little is known in the way of exact algorithms for separating these inequalities in polynomial time in the size of the fractional point x* which is being separated. An algorithm is presented here that separates bipartition inequalities of a fixed number of handles and teeth, which includes clique tree inequalities of a fixed number of handles and teeth, in polynomial time.
Classification of Acceptance Criteria for the Simulated Annealing Algorithm
Authors: Schuur Peter C.
Published: October 2008

We present a complete and explicit description of the class of all acceptance criteria for the simulated annealing algorithm that uniformly depend on the cost of the current and the candidate configuration and that lead to detailed balance when combined with a symmetric generation matrix. Here the cost dependence is called uniform if it is expressed by one and the same function for all cost functions. As an important special case we identify the subclass consisting of those acceptance criteria that depend uniformly on the difference in cost. Furthermore, we present a simple characterization of the Metropolis and the Barker criterion.
Free-Steering Relaxation Methods for Problems with Strictly Convex Costs and Linear Constraints
Authors: Kiwiel Krzysztof C.
Published: October 2008

We consider dual coordinate ascent methods for minimizing a strictly convex (possibly nondifferentiable) function subject to linear constraints. Such methods are useful in large-scale applications (e.g., entropy maximization, quadratic programming, network flow), because they are simply, can exploit sparsity and in certain cases are highly parallelizable. We establish their global convergence under weak conditions and a free-steering order of relaxation. Previous comparable results were restricted to special problems with separable costs and equality constraints. Our convergence framework unifies to a certain extent the approaches of Bregman, Censor and Lent, De Pierro and Iusem, and Luo and Tseng, and complements that of Bertsekas and Tseng.
Hyperbolic Polynomials and Interior Point Methods for Convex Programming
Authors: Güler Osman
Published: October 2008

Hyperbolic polynomials have their origins in partial differential equations. We show in this paper that they have applications in interior point methods for convex programming. Each homogeneous hyperbolic polynomial p has an associated open and convex cone called its hyperbolicity cone. We give an explicit representation of this cone in terms of polynomial inequalities. The function F(x) = −log p(x) is a logarithmically homogeneous self-concordant barrier function for the hyperbolicity cone with barrier parameter equal to the degree of p. The function F(x) possesses striking additional properties that are useful in designing long-step interior point methods. For example, we show that the long-step primal potential reduction methods of Nesterov and Todd and the surface-following methods of Nesterov and Nemirovskii extend to hyperbolic barrier functions. We also show that there exists a hyperbolic barrier function on every homogeneous cone.
Potentials and Weighted Values of Nonatomic Games
Authors: Hart Sergiu , Monderer Dov
Published: October 2008

The “potential approach” to value theory for finite games was introduced by Hart and Mas-Colell (Hart, S., A. Mas-Colell. 1989. Potential, value, and consistency. Econometrica 57 589–614.). Here this approach is extended to non-atomic games. On appropriate spaces of differentiable games there is a unique potential operator, that generates the Aumann and Shapley (Aumann, R. J., L. S. Shapley. 1974. Values of nonatomic games. Princeton University Press, Princeton, New Jersey.) value. As a corollary we obtain the uniqueness of the Aumann-Shapley value on certain subspaces of games. Next, the potential approach is applied to the weighted case, leading to “weighted non-atomic values.” It is further shown that the asymptotic weighted value is well-defined, and that it coincides with the weighted value generated by the potential.
On the Determinateness of m × ∞-Bimatrix Games
Authors: Norde Henk , Potters Jos
Published: October 2008

In this paper a positive answer is given to the question of whether every semi-infinite bimatrix game is weakly determined.
Stability of Multiclass Queueing Networks Under FIFO Service Discipline
Authors: Chen Hong , Zhang Hanqin
Published: October 2008

In this paper, we first formally identify a FIFO fluid network that corresponds to the queueing network under a first-in first-out (FIFO) service discipline, thus complementing the result of Dai (Dai, J. G. 1995a. On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5 49–77.) for the use of the fluid model for the stability of a multiclass queueing network under a FIFO service discipline. Then we establish two sufficient conditions for the stability of a multiclass FIFO queueing network. The results extend the previous work on the single class network, the single station network and a network studied by Rybko and Stolyar (Rybko, A. N., A. L. Stolyar. 1992. Ergodicity of stochastic processes describing the operations of open queueing networks. Problemy Peredachi Informatsii 28 2–26.). Finally we establish a fluid approximation theorem for the queueing network under FIFO service discipline.
A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
Authors: Iwata Satoru , Murota Kazuo , Shigeno Maiko
Published: October 2008

This paper presents a fast algorithm to solve the intersection problem for a pair of nondecreasing and nonincreasing strong map sequences of submodular systems. The worst-case time bound is the same as that of the push/relabel algorithm for a single intersection problem. This extends the Gallo-Grigoriadis-Tarjan (GGT) method for parametric maximum flow problems and reveals an algorithmic significance of the concept of strong maps for submodular systems.
Analysis of Simple Algorithms for Dynamic Load Balancing
Authors: Alanyali Murat , Hajek Bruce
Published: October 2008

The principle of load balancing is examined for dynamic resource allocation subject to certain constraints. The emphasis is on the performance of simple allocation strategies which can be implemented on-line. Either finite capacity constraints on resources or migration of load can be incorporated into the setup. The load balancing problem is formulated as a stochastic optimal control problem. Variants of a “Least Load Routing” policy are shown to lead to a fluid type limit and to be asymptotically optimal.
The Delay of Open Markovian Queueing Networks: Uniform Functional Bounds, Heavy Traffic Pole Multiplicities, and Stability
Authors: Humes C. , Ou J. , Kumar P. R.
Published: October 2008

For open Markovian queueing networks, we study the functional dependence of the mean number in the system (and thus also the mean delay since it is proportional to it by Little's Theorem) on the arrival rate or load factor. We obtain linear programs (LPs) which provide bounds on the pole multiplicity M of the mean number in the system, and automatically obtain lower and upper bounds on the coefficients {Ci} of the expansion ρCM/(1 − ρ)M + ρCM−1/(1 − ρ)M−1 + ⋯ + ρC1/(1 − ρ) + ρC0, where ρ is the load factor, which are valid for all ρ ∈ [0, 1). Our LPs can thus establish the stability of open networks for all arrival rates within capacity, while providing uniformly bounding functional expansions for the mean delay, valid for all arrival rates in the capacity region. The coefficients {Ci} can be optimized to provide the best bound at any desired value of the load factor, while still maintaining its validity for all ρ ∈ [0, 1). While the above LPs feature L(L + 1)(M + 1)/2 variables where L is the number of buffers in the network, for balanced systems we further provide a lower dimensional LP featuring just S(S + 1)/2 variables, where S is the number of stations in the network. This bound asymptotically dominates in heavy traffic a bound obtainable from the Pollaczek-Khintchine formula, and can capture interactions between multiple bottleneck stations in heavy traffic. We also provide an explicit upper bound for all scheduling policies in acyclic networks, and for the FBFS policy in open re-entrant lines.
Cooperation Indices and Weighted Shapley Values
Authors: Amer Rafel , Carreras Francesc
Published: October 2008

The weighted Shapley values are extended to situations defined by a cooperative game and a cooperation index. Two main axiomatic characterizations for the modified values are provided. We also develop further axiomatizations of the classical values and discuss two examples.
Multi-Parameter Surfaces of Analytic Centers and Long-Step Surface-Following Interior Point Methods
Authors: Nesterov Yu. , Nemirovski A.
Published: October 2008

We develop a long-step polynomial time version of the Method of Analytic Centers for non-linear convex problems. The method traces a multi-parameter surface of analytic centers rather than the usual path, which allows to handle cases with noncentered and possibly infeasible starting point.
Lower Bounds in Lot-Sizing Models: A Polyhedral Study
Authors: Constantino Miguel
Published: October 2008

Variable lower bounds in Mixed Integer Programs are constraints with the general form x≥Ly,where xis a continuous variable and y is a binary or an integer variable.

This type of constraints is present in some Lot-Sizing models, where x represents the amount of some article produced by a machine and y∈{0,1}indicates whether the machine is set-up for that article(y = 1) or not (y = 0). In these models, production below some level is not allowed, in order to make full use of resources.

In this paper we study, from the polyhedral viewpoint, the mixed integer models whose feasible set includes an additive constraint Σxj ≤(≥, =)D, and constraints Lyj ≤ xj ≤ Kyj, where xj are continuous variables, yj are integer or binary variables, and K is a large constant.

We derive families of strong valid inequalities and show they are sufficient to describe completely the convex hulls of the sets of feasible solutions. Moreover, we develop polynomial algorithms to solve the separation problem associated to each of the families obtained. Finally, we incorporate the inequalities obtained in a cutting plane algorithm, and test their ability to solve some multi-item lot-sizing problems.
Pricing of American Contingent Claims with Jump Stock Price and Constrained Portfolios
Authors: Buckdahn Rainer , Hu Ying
Published: October 2008

In this paper, we study the problem of pricing American contingent claims in an incomplete market where the stock price process is supposed to be driven by both a Wiener process and a Poisson random measure and the portfolios are constrained. We formulate this problem as to find the minimal solution of a backward stochastic differential equation (BSDE) with constraints. We use the penalization method to construct a sequence of BSDEs with respect to Wiener process and Poisson random measure, and we show that the solutions of these equations converge to the minimal solution we are interested in. Finally, in the Markovian case, we characterize the minimal hedging price as the minimal viscosity supersolution of an integral-partial differential inequality with constraints.
On the Glivenko-Cantelli Problem in Stochastic Programming: Linear Recourse and Extensions
Authors: Pflug Georg Ch. , Ruszczyñski Andrzej , Schultz Rüdiger
Published: October 2008

Integrals of optimal values of random optimization problems depending on a finite dimensional parameter are approximated by using empirical distributions instead of the original measure. Under fairly broad conditions, it is proved that uniform convergence of empirical approximations of the right hand sides of the constraints implies uniform convergence of the optimal values in the linear and convex case.
Shadow Prices in Infinite-Dimensional Linear Programming
Authors: Romeijn H. Edwin , Smith Robert L.
Published: October 2008

We consider the class of linear programs that can be formulated with infinitely many variables and constraints but where each constraint has only finitely many variables. This class includes virtually all infinite horizon planning problems modeled as infinite stage linear programs. Examples include infinite horizon production planning under time-varying demands and equipment replacement under technological change. We provide, under a regularity condition, conditions that are both necessary and sufficient for strong duality to hold. Moreover we show that, under these conditions, the Lagrangean function corresponding to any pair of primal and dual optimal solutions forms a linear support to the optimal value function, thus extending the shadow price interpretation of an optimal dual solution to the infinite dimensional case. We illustrate the theory through an application to production planning under time-varying demands and costs where strong duality is established.
Integral Solutions of Linear Complementarity Problems
Authors: Cunningham William H. , Geelen James F.
Published: October 2008

We characterize the class of integral square matrices M having the property that for every integral vector q the linear complementarity problem with data M, q has only integral basic solutions. These matrices, called principally unimodular matrices, are those for which every principal nonsingular submatrix is unimodular. As a consequence, we show that if M is rank-symmetric and principally unimodular, and q is integral, then the problem has an integral solution if it has a solution. Principal unimodularity can be regarded as an extension of total unimodularity, and our results can be regarded as extensions of well-known results on integral solutions to linear programs. We summarize what is known about principally unimodular symmetric and skew-symmetric matrices.
On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
Authors: Pataki Gábor
Published: October 2008

We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function.

We provide upper bounds on the rank of extreme matrices in SDPs, and the first theoretically solid explanation of a phenomenon of intrinsic interest in eigenvalue-optimization. In the spectrum of an optimal matrix, the kth and (k + 1)st largest eigenvalues tend to be equal and frequently have multiplicity greater than two. This clustering is intuitively plausible and has been observed as early as 1975.

When the matrix-valued function is affine, we prove that clustering must occur at extreme points of the set of optimal solutions, if the number of variables is sufficiently large. We also give a lower bound on the multiplicity of the critical eigenvalue. These results generalize to the case of a general matrix-valued function under appropriate conditions.