bluuebunny/crossref_metadata_2025 huggingface dataset:
Strong Consistency of the Variance Estimator in Steady-State Simulation Output Analysis
Authors: Damerdji Halim
Published: October 2008

In this paper, we study the problem of variance estimation in steady-state simulation output analysis. A confidence interval for the mean of an output sequence may be constructed using a (weakly) consistent estimator of the time-average variance constant of the process. Moreover, a strongly consistent estimator of the variance constant is required for fixed-width confidence-interval estimation procedures to be asymptotically valid. Here, we establish sufficient conditions to ensure strong consistency of the estimator of the variance constant obtained by several widely used methods of steady-state simulation output analysis, namely, batch means, overlapping batch means, spaced batch means, and standardized time series (area estimator). We also introduce the overlapping area estimator of the variance constant. The established sufficient conditions provide qualitative insight into the relation between the correlation of the process and certain parameters (e.g., batch size) of the output method used.
Average Case Analysis of a Heuristic for the Assignment Problem
Authors: Karp Richard M. , Kan Alexander H. G. Rinnooy , Vohra Rakesh V.
Published: October 2008

Our main contribution is an O(n log n) algorithm that determines with high probability a perfect matching in a random 2-out bipartite graph. We also show that this algorithm runs in O(n) expected time. This algorithm can be used as a subroutine in an O(n2) heuristic for the assignment problem. When the weights in the assignment problem are independently and uniformly distributed in the interval [0, 1], we prove that the expected weight of the assignment returned by thus heuristic is bounded above by 3 + O(n−α), for some posrtive constant a.
A Generalization of Weyl's Integration Theorem and Its Meaning for Stochastic Simulations
Authors: Schindler Werner
Published: October 2008

Due to Weyl's integration theorem the Haar probability measure and, further, a whole class of probability measures on a compact connected Lie group G can be represented as image measures of product measures of a specific type. It will be shown that this result holds even for a larger class of probability measures on G. As a consequence, a simulation of any distribution which is contained in this (larger) class can be decomposed into two simulation problems of smaller size which can be treated independently. This aspect will be investigated and instructions will be worked out for applying the concept of decomposition in a concrete case. Their use and the benefit of the decomposition concept will be demonstrated at the special case G = SO(3).
Double Band Policy for Stochastic Manufacturing Systems in Heavy Traffic
Authors: Krichagina Elena V. , Lou Sheldon X. C. , Taksar Michael I.
Published: October 2008

We consider the control of a manufacturing system producing one product. The demand for this product is random. The manager can produce the product at a fixed rate r, or choose to stop the production. Each time the production is resumed, a setup cost must be paid. To prevent the backlog, which is not allowed, the manager can buy the product from outside vendors, paying a fixed order cost and a variable cost. There is also a linear inventory holding cost. The objective is to minimize the total expected discounted cost. Under heavy traffic conditions, i.e. when the production capacity is close to the average demand, this problem is approximated by an impulse control problem for Brownian motion, which is solved explicitly. The solution is then used to derive a control policy for the original system. The resulting control IS characterized by three parameters 0 < q0 < Q0 < S0 and is dubbed double band policy. When the Inventory reaches S0 the machine is turned off and it is turned on again when inventory decreases to level Q0. An amount of q0 units is purchased from the outside vendor if the inventory level drops to zero. We prove that this policy is nearly optimal. That is, the relative difference between the cost under this policy and the optimal cost is small if traffic intensity is close to one.
Linear Stability of Generalized Equations Part I: Basic Theory
Authors: Liu Jiming
Published: October 2008

(Dedicated to Anthony V. Fiacco on the occasion of his 65th birthday.)

We consider a class of generalized equations involving set-valued maps, which formulate many problems from mathematical programming, complementarity theory and mathematical economics. Many results concerning the stability behavior of the solution sets of this class of generalized equations have been established, mainly focusing on “qualitative” characterizations. We develop a theory concentrating on “quantitative” characterizations of the stability behavior of solutions of generalized equations, and establish conditions which ensure the solution set of a generalized equation is “quantitatively” stable. In Part II of the paper, we use the concepts and methods developed here to treat norlinear programming problems.
Linear Stability of Generalized Equations, Part II: Applications to Nonlinear Programming
Authors: Liu Jiming
Published: October 2008

(Dedicated to Anthony V. Fiacco on the occasion of his 65th birthday.)

We present an approach by which the quantitative stability of solutions of a general nonlinear programming problem is obtained in the spirit of Part I of the paper. Under assumptions of the constraint regularity and the general second-order sufficient condition. we show that the solution set is linearly stable under small allowed perturbations in the sense of Part I of the paper, and derive bounds for the linear stability number which characterizes the quantitative stability of solutions of the problem in question. For standard nonlinear programs that are most commonly encountered in practical situations, we develop a method to compute these bounds. The results obtained here complement those of Robinson (1982).
On Lipschitzian Stability of Optimal Solutions of Parametrized Semi-Infinite Programs
Authors: Shapiro Alexander
Published: October 2008

We study continuity properties of optimal solutions of parametrized semi-infinite programming problems. The involved constraints are formulated in a form of cone constraints and then a slightly modified general result of Shapiro and Bonnans (1992) on Lipschitzian stability of optimal solutions is applied. It is shown that under certain second-order sufficient conditions, optimal solutions of the semi-infinite programs are Lipschitzian stable provided a regularity assumption related to a linearization of the considered programs is satisfied.
Period Three Implies Heavy Discounting
Authors: Sorger Gerhard
Published: October 2008

A condition is derived that must be satisfied by a continuous function h: X → X in order to be the optimal policy function of a strictly concave deterministic dynamic programming problem which is defined on the state space X and which has a given discount factor ρ. We use this condition to show that there is no such dynamic programming problem on a one-dimensional state space that generates optimal solutions which are periodic with minimal period three unless the discount rate exceeds 82%. This bound holds uniformly for all strictly concave problems and all period-three-cycles.
A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
Authors: Barvinok Alexander I.
Published: October 2008

We prove that for any dimension d there exists a polynomial time algorithm for counting integral points in polyhedra in the d-dimensional Euclidean space. Previously such algorithms were known for dimensions d = 1, 2, 3, and 4 only.
Measures for Symmetric Rank-One Updates
Authors: Wolkowicz Henry
Published: October 2008

Measures of deviation of a symmetric positive definite matrix from the identity are derived. They give rise to symmetric rank-one, SR1, type updates. The measures are motivated by considering the volume of the symmetric difference of the two ellipsoids, which arise from the current and updated quadratic models in quasi-Newton methods. The measure defined by the problem—maximize the determinant subject to a bound of 1 on the largest eigenvalue—yields the SR1 update. The measure σ(A) = λ1(A)/det(A)1/n yields the optimally conditioned, sized, symmetric rank-one updates. The volume considerations also suggest a ‘correction’ for the initial stepsize for these sized updates. It is then shown that the σ-optimal updates, as well as the Oren-Luenberger self-scaling updates, are all optimal updates for the κ measure, the l2 condition number. Moreover, all four sized updates result in the same largest (and smallest) ‘scaled’ eigenvalue and corresponding eigenvector. In fact, the inversesized BFGS is the mean of the σ-optimal updates, while the inverse of the sized DFP is the mean of the inverses of the σ-optimal updates. The difference between these four updates is determined by the middle n − 2 scaled eigenvalues. The κ measure also provides a natural Broyden class replacement for the SR1 when it is not positive definite.
Stability Analysis of Variational Inequalities and Nonlinear Complementarity Problems, via the Mixed Linear Complementarity Problem and Degree Theory
Authors: Gowda M. Seetharama , Pang Jong-Shi
Published: October 2008

This paper is concerned with the mixed linear complementarity problem and the role it and its variants play in the stability analysis of the nonlinear complementarity problem and the Karush-Kuhn-Tucker system of a variational inequality problem. Under a nonsingular assumption, the mixed linear complementarity problem can be converted to the standard problem; in this case, the rich theory of the latter can be directly applied to the former. In this work, we employ degree theory to derive some sufficient conditions for the existence of a solution to the mixed linear complementarity problem in the absence of the nonsingularity property. Next, we extend this existence theory to the mixed nonlinear complementarity problem and establish a main stability result under a certain degree-theoretic assumption concerning the linearized problem. We then specialize this stability result and its consequences to the parametric variational inequality problem under the assumption of a unique set of multipliers. Finally, we consider the latter problem with the uniqueness assumption of the multipliers replaced by a convexity assumption and obtain stability results under some weak second-order conditions. In addition to the new existence results for the mixed linear complementarity problem, the main contributions of this paper in the stability category are the following: a resolution to a conjecture concerning the local solvability of a parametric variational inequality, the use of the generalized linear complementarity problem as a tool to broaden the second-order conditions, the characterization of the solution stability of the linear complementarity problem and the affine variational inequality problem in terms of the solution isolatedness under some weak hypotheses, and various stability theorems under some weak second-order conditions.
New Error Bounds for the Linear Complementarity Problem
Authors: Luo Z.-Q. , Mangasarian O. L. , Ren J. , Solodov M. V.
Published: October 2008

Recently Mangasarian and Solodov (1993) showed that every nonlinear complementarity problem (NCP) is equivalent to the unconstrained minimization of a certain implicit Lagrangian. In particular, it was shown that this implicit Lagrangian is nonnegative everywhere and its set of zeros coincides with the solution set of the original NCP. In this paper, we consider the linear complementarity problem (LCP), and show that the distance to the solution set of the LCP from any point sufficiently close to the set can be bounded above by the square root of the implicit Lagrangian for the LCP. In other words, the square root of the implicit Lagrangian is a local error bound for the LCP. Our proof is based on showing that the square root of the implicit Lagrangian is equivalent to the residual function used in a known local error bound (Robinson 1981, Luo and Tseng 1992). When the matrix associated with the LCP is nondegenerate, the new error bound is in fact global. This extends the error bound result of Mathias and Pang (1990) for the LCP with a P-matrix.
Primal-Dual Aggregation and Disaggregation for Stochastic Linear Programs
Authors: Wright S. E.
Published: October 2008

A multistage stochastic linear program can be approximated by replacing the underlying information structure by a coarser structure. Given the ordinary Lagrangian for the original problem, this amounts to restricting both the primal and dual variables to be adapted to the coarser information structure. The resulting primal problem has the same form as the original, but with aggregated constraints and decisions. Mutual upper and lower bounds on the optimal values of the original and aggregated problems are obtained via partially aggregated problems formed by restricting only the primal variables or only the dual variables to the coarser structure. The introduction of the partially aggregated problems leads to a general disaggregation framework for developing heuristic approaches to solving the original problem.
Rate of Convergence of Empirical Measures and Costs in Controlled Markov Chains and Transient Optimality
Authors: Altman Eitan , Zeitouni Ofer
Published: October 2008

The purpose of this paper is two fold. First, bounds on the rate of convergence of empirical measures in controlled Markov chains are obtained under some recurrence conditions. These include bounds obtained through large deviations and central limit theorem arguments. These results are then applied to optimal control problems. Bounds on the rate of convergence of the empirical measures that are uniform over different sets of policies are derived, resulting in bounds on the rate of convergence of the costs. Finally, new optimal control problems that involve not only average cost criteria but also measures on the transient behavior of the cost, namely the rate of convergence, are introduced and applied to a problem in telecommunications. The solution to these problems rely on the bounds introduced in previous sections.
Sensitive Optimality Criteria in Countable State Dynamic Programming
Authors: Hordijk A. , Sladký K.
Published: October 2008

Discrete time Markov decision processes with a countable state space are investigated. Under a condition of Liapunov function type the Laurent expansion of the total discounted expected return for the various policies is derived. Moreover, the equivalence of the sensitive optimality criteria as introduced by Veinott is shown.
Critical Cutsets of Graphs and Canonical Facets of Set-Packing Polytopes
Authors: Balas Egon , Zemel Eitan
Published: October 2008

A cutset in a graph G with node set N is the set of edges joining the nodes in a subset of N to those not in the subset. We call a cutset critical if its removal produces a graph whose independence number is greater than that of G. We use the concept of a critical cutset to give first a necessary, then a sufficient condition for an inequality with 0–1 coefficients to be a facet of the set-packing polytope defined by G.
Periods of Connected Networks and Powers of Nonnegative Matrices
Authors: Denardo Eric V.
Published: October 2008

Let P be an irreducible N × N matrix having nonnegative entries, and consider the (directed) network containing arc (i, j) if and only if Pij is positive. Theorem 1 expresses the period of this network in terms of any of its arborescences. Theorem 2 shows that if the network's period is one and if node i is contained in a cycle of length n, then the ith row and column of Pt are positive for t ≥ (N − 1)n. Theorem 3 shows how to compute the network's period with work proportional to the number of its arcs.
Computation of Solutions to Nonlinear Equations Under Homotopy Invariance
Authors: Garcia C. B.
Published: October 2008

The problem of finding a solution to nonlinear equations by way of the Homotopy Invariance Theorem is considered, using continuation methods for simplicial mappings.
Decision Problems with Expected Utility Critera, I: Upper and Lower Convergent Utility
Authors: Kreps David M.
Published: October 2008

A countable stage, countable state, finite action decision problem is considered where the objective is the maximization of the expectation of an arbitrary utility function defined on the sequence of states. Basic concepts are formulated, generalizing the standard notions of the optimality equations, conserving and unimprovable strategies, and strategy and value iteration. Analogues of positive, negative and convergent dynamic programming are analyzed.
Valid Inequalities and Superadditivity for 0–1 Integer Programs
Authors: Wolsey L. A.
Published: October 2008

It is shown that valid inequalities for 0–1 problems can be essentially characterized by two underlying functions, one of which is superadditive. These functions are essential to the characterization of maximal inequalities, the projection of valid inequalities and the definition of a master polytope. Similar properties are shown to hold for 0–1 group problems.
Stationary Markovian Decision Problems and Perturbation Theory of Quasi-Compact Linear Operators
Authors: Wijngaard Jacob
Published: October 2008

In this paper stationary Markov decision problems are considered with arbitrary state space and compact space of strategies. Conditions are given for the existence of an average optimal strategy. This is done by using the fact that a continuous function on a compact space attains its minimum. To prove the continuity of the average costs as function on the space of strategies some perturbation results for quasi-compact linear operators are used. In a first set of conditions the boundedness of the one-period cost functions and the quasi-compactness of the Markov processes are assumed. In more general conditions the boundedness of the cost functions is replaced by the boundedness, on a subset A of the state space, of the recurrence time and costs until A and the quasi-compactness of the Markov processes are replaced by the quasi-compactness of the embedded Markov processes on A.
New Finite Pivoting Rules for the Simplex Method
Authors: Bland Robert G.
Published: October 2008

A simple proof of finiteness is given for the simplex method under an easily described pivoting rule. A second new finite version of the simplex method is also presented.
Sharp Bounds on Laplace-Stieltjes Transforms, with Applications to Various Queueing Problems
Authors: Eckberg A. E.
Published: October 2008

Several partial characterizations of positive random variables (e.g., certain moments) are considered. For each characterization, sharp upper and lower bounds on the Laplace-Stieltjes transform of the corresponding distribution function are derived. These bounds are then shown to be applicable to several problems in queueing and traffic theory. The results can prove useful in producing conservative estimates of a system's performance, in judging the information content of a partial characterization and in providing insight into approximations.
Optimal Inspections in a Stochastic Control Problem with Costly Observations
Authors: Anderson Robert F. , Friedman Avner
Published: October 2008

A Brownian motion z(t) is known to be developing in time with cost f(z(t)) per unit lime. One chooses a sequence of times σn in which to inspect the motion. If it is discovered that z(σn) is in a given set A then we continue with the motion, whereas if z(σn) is not in A then we shut off the motion with cost y(z(σn)). Each observation at t = σn costs β(z(σn)). In this paper we find a sequence of inspections for which the total cost is minimum. This is done, in Part I, by reducing the stochastic problem lo a free boundary problem in analysis (called a quasi variational inequality), which is then solved. In Part II we solve a similar problem whereby, instead of shutting off the motion when z(σn) is not in A, we innovate it by bringing it to the origin at some cost y(z(σn)). Finally, in Part III we consider the case where z(t) can only be observed (at the times σn) with an error.
Stochastic Orderings from Partially Known Utility Functions
Authors: Vickson R. G.
Published: October 2008

In an expected utility analysis of a decision problem, knowledge of the utility function at a few selected points may be available. When combined with general properties such as monotonicity or concavity, the limited knowledge of the utility function may be sufficient for ranking a pair of probability distributions unambiguously. Necessary and sufficient conditions for such stochastic orderings are presented for the following cases of partially specified utility functions: nondecreasing functions, and nondecreasing concave functions. Examples of these orderings are presented.
Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
Authors: Brucker Peter , Garey M. R. , Johnson D. S.
Published: October 2008

A basic problem of deterministic scheduling theory is that of scheduling n equal length tasks on m identical processors subject to precedence constraints. Although the general problem of finding a schedule which minimizes makespan is NP-complete, the important special case with “treelike” precedence constraints can be solved by a well-known algorithm of T. C. Hu. We consider an extension of this special case model to include the possibility of individual task deadlines, in which case the goal is to minimize maximum lateness. Our results show that it makes a considerable difference whether the precedence is of “in-tree” or “out-tree” form. In the former case the problem can be solved in lime O(n log n); in the latter it is NP-complete. We also discuss applications of our results to related scheduling problems.
On the Complexity of Mean Flow Time Scheduling
Authors: Sethi Ravi
Published: October 2008

There are n tasks lo be scheduled for processing on a set of identical parallel machines. We are interested in minimizing the mean flow time, which is related to the sum of the finishing times of all tasks. When tasks can be processed in any order, optimal schedules can be constructed in O(n log n) time on any number of identical machines. With arbitrary precedence constraints the problem becomes NP-complete even on one machine. However, for series-parallel precedence constraints an O(n log n) algorithm is known for one machine. We show that on two or more machines, the problem is NP-complete even if the precedence constraints are tree-like. We prove the result both for in-trees in which the root is the last task to be processed, and out-trees in which the root is the first task to be processed.
Continuous Values are Diagonal
Authors: Neyman Abraham
Published: October 2008

It is proved that every continuous value is diagonal, which in particular implies that every value on a closed reproducing space is diagonal. We deduce also that there are noncontinuous values.
Packing Spanning Trees
Authors: Barahona Francisco
Published: October 2008

We given an algorithm for packing spanning trees in a graph G = (V, E), with capacities on the edges. The problem reduces to O(|V|2) maximum flow computations. The algorithm is based on Nash-Williams's proof of a min-max relation for this problem.
On the Complexity of a Class of Projective Interior Point Methods
Authors: Goldfarb Donald , Shaw Dong X.
Published: October 2008

We present a generic projective interior point algorithm for linear programming which includes modified versions of Karmarkar's original algorithm and most other projective algorithms that have been proposed as special cases. We show that this class of algorithms has a worst case iteration bound of O(√nL) and is closely related to the class of potential reduction interior point methods.
Affine-Scaling Trajectories Associated with a Semi-Infinite Linear Program
Authors: Vanderbei Robert J.
Published: October 2008

Semi-infinite linear programs often arise as the limit of a sequence of approximating linear programs. Hence, studying the behavior of extensions of linear programming algorithms to semi-infinite problems can yield valuable insight into the behavior of the underlying linear programming algorithm when the number of constraints or the number of variables is very large. In this paper, we study the behavior of the affine-scaling algorithm on a particular semi-infinite linear programming problem. We show that the continuous trajectories converge to the optimal solution but that, for any strictly positive step, there are starting points for which the discrete algorithm converges to nonoptimal boundary points.
Solvability of Two-Player Game Forms with Infinite Sets of Strategies
Authors: Abdou Joseph
Published: October 2008

A game form is N-solvable for a class of payoff functions. If for every pair of payoff functions of that class, the associated game in strategic form has a Nash equilibrium. A finite game form is N-solvable (for the universal class of preferences) if and only if it is tight—that is if its α-effectivity function and its β-effectivity function are equal. We extend this result to various models of two-player game forms with infinite sets of strategies and/or alternatives. This is done by an appropriate definition of tightness relative to the underlying structure (topology, Boolean algebra, σ-algebra). We apply the current results along with well-known results on the determinacy of games with perfect information to infinitely repeated game forms. We prove that a repeated tight game form is tight on Bore1 sets.
Strong Approximations for Time-Dependent Queues
Authors: Mandelbaum Avi , Massey William A.
Published: October 2008

A time-dependent Mt/Mt/1 queue alternates through periods of under-, over-, and critical loading. We derive period-dependent, pathwise asymptotic expansions for its queue length, within the framework of strong approximations. Our main results include time-dependent fluid approximations, supported by a functional strong law of large numbers, and diffusion approximations, supported by a functional central limit theorem. This complements and extends previous work on asymptotic expansions of the queue-length transition probabilities.
Vector Summation in Banach Space and Polynomial Algorithms for Flow Shops and Open Shops
Authors: Sevast'janov Sergey
Published: October 2008

We consider the flow shop and the open shop problems with m machines and n jobs: M is the total processing time of the most loaded machine, t* is the maximum operation length. Two functions are defined, μ(m) is the minimum number such that the optimum of any flow shop is at most M + μ(m)t*; η(m) is the minimum number for which the inequality M ≥ η(m)t* ensures that the optimum of the open shop is equal to M Upper and lower bounds for functions μ(m) and η(m) are derived and two polynomial algorithms are suggested: the first one delivers an optimal schedule of an open shop provided M ≥ η′(m)t* (for some function η′(m) ≥ η(m)); the second one computes a near-optimal approximation schedule of a flow shop. Both algorithms are based on a vector summation algorithm in m-dimensional banach space.
Constrained Markov Decision Models with Weighted Discounted Rewards
Authors: Feinberg Eugene A. , Shwartz Adam
Published: October 2008

This paper deals with constrained optimization of Markov Decision Processes. Both objective function and constraints are sums of standard discounted rewards, but each with a different discount factor Such models arise, e.g., in production and in applications involving multiple time scales. We prove that it a feasible policy exists, then 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 bounded by the number of constraints. Optimality of such policies for multi-criteria problems is also established.

These new policies have the pleasing aesthetic property that the amount of randomization they require over any trajectory is restricted by the number of constraints. This result is new even for constrained optimization with a single discount factor, where the optimality of randomized stationary policies is known. However, a randomized stationary policy may require an infinite number of randomizations over time.

We also formulate a linear programming algorithm for approximate solutions of con-strained weighted discounted models.
Proportional Discounting of Future Costs and Benefits
Authors: Harvey Charles
Published: October 2008

Social benefits in the distant future receive very little importance when a public policy analysis uses a constant-discounting model with its geometric timing weights to compare future benefits with present costs. This paper defines conditions on social preferences that imply a model having arbitrary timing weights. We then introduce a condition on preferences that restricts this general model to one in which the timing weights are linear fractional This model is proposed as an alternative to the constant-discounting model. It accords far more importance to the distant future than does constant discounting, and like constant discounting it depends on the assessment of a single parameter.
The General One Center Location Problem
Authors: Durier Roland
Published: October 2008

The general one center location problem deals with the location of a point in a real normed space X in order to minimize an objective function G which depends on the distances to a finite number of centers and on initial costs. The function G is defined by G(x) = γ(c1 + w1‖x − a1‖, …, cn + wn‖x − an‖), where a1, …, an are n given points in X, w1, …, wn are positive numbers, c1, …, cn are nonnegative initial costs and γ is a monotone norm on ℝn. A geometrical description of the set of optimal solutions to the problem minx∈X G(x) is provided. The peculiar role of the minisum problem, where γ is the l1-norm, is emphasized and the minimax problem, where γ is the lx-norm, is used to illustrate the general geometrical description.
Asymptotic Convergence Analysis of the Forward-Backward Splitting Algorithm
Authors: Zhu Ciyou
Published: October 2008

The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 ∈ T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean space. When the problem has a nonempty solution set, and T is split in the form T = ℱ + h with ℱ being maximal monotone and h being co-coercive with modulus greater than ½, convergence rates are shown, under mild conditions, to be linear, superlinear or sublinear depending on how rapidly ℱ−1 and h−1 grow in the neighborhoods of certain specific points.

As a special case, when both ℱ and h are polyhedral functions, we get R-linear convergence and 2-step Q-linear convergence without any further assumptions on the strict monotonicity on T or on the uniqueness of the solution. As another special case when h = 0, the splitting algorithm reduces to the proximal point algorithm, and we get new results, which complement R. T. Rockafellar's and F. J. Luque's earlier results on the proximal point algorithm.
Generalized-Quasi-Variational Inequality Problems with Discontinuous Mappings
Authors: Yao Jen-Chih
Published: October 2008

We derive several existence results for generalized quasi-variational inequality problems where the mappings under consideration need not have any continuity properties. As applications, we obtained several existence results for equilibrium problems involving abstract economies.
Iteration Functions in Some Nonsmooth Optimization Algorithms
Authors: Poliquin René , Qi Liqun
Published: October 2008

Recently, several globally convergent model algorithms based on iteration functions have been proposed for solving nonsmooth optimization problems. In particular, Pang, Han and Rangaraj proposed such an algorithm for minimizing a locally Lipschitzian function. We determine properties of iteration functions (calculus, existence); we also identify characteristics of functions that possess iteration functions. We show that a locally Lipschitzian function has a Pang-Han-Rangaraj iteration function only when the function is pseudo-regular (in the sense of Borwein), and that a subsmooth (lower-C1) function always has a Pang-Han-Rangaraj iteration function.
An Integral Inequality for Convex Functions, with Application to Teletraffic Congestion Problems
Authors: Pearce C. E. M. , Pečarić J. E.
Published: October 2008

An integral inequality for convex functions is deduced from Jensen's inequality. This gives as a special case a commonly-used inequality in the analysis of call congestion in queueing theory which has previously been derived only by rather longer ad hoc procedures.
A Randomized Algorithm to Optimize Over Certain Convex Sets
Authors: Kannan Ravi , Mount John , Tayur Sridhar
Published: October 2008

This paper presents a randomized polynomial time algorithm to nearly minimize a linear function over an up-monotone convex set in the positive orthant given only by a membership oracle. Our original motivation for this is a stochastic optimization problem called the component commonality problem in the literature.
Convex Relaxations of (0, 1)-Quadratic Programming
Authors: Poljak Svatopluk , Wolkowicz Henry
Published: October 2008

We consider three parametric relaxations of the (0, l)-quadratic programming problem. These relaxations are to: quadratic maximization over simple box constraints, quadratic maximization over the sphere, and the maximum eigenvalue of a bordered matrix. When minimized over the parameter, each of the relaxations provides an upper bound on the original discrete problem. Moreover, these bounds are efficiently computable. Our main result is that, surprisingly, all three bounds are equal.
Capacitated Facility Location: Valid Inequalities and Facets
Authors: Aardal Karen , Pochet Yves , Wolsey Laurence A.
Published: October 2008

We examine the polyhedral structure of the convex hull of feasible solutions of the capacitated facility location problem. In particular we derive necessary and sufficient conditions for a family of “effective capacity” inequalities to be facet-defining, and further results on a more general family called “submodular” inequalities.
On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex Optimization
Authors: Ruszczyński Andrzej
Published: October 2008

A decomposition method for large-scale convex optimization problems with block-angular structure and many linking constraints is analysed. The method is based on a separable approximation of the augmented Lagrangian function. Weak global convergence of the method is proved and speed of convergence analysed. It is shown that convergence properties of the method are heavily dependent on sparsity of the linking constraints. Application to large-scale linear programming and stochastic programming is discussed.
Convergence Rate Analysis of Nonquadratic Proximal Methods for Convex and Linear Programming
Authors: Iusem Alfredo N. , Teboulle Marc
Published: October 2008

The φ-divergence proximal method is an extension of the proximal minimization algorithm, where the usual quadratic proximal term is substituted by a class of convex statistical distances, called φ-divergences. In this paper, we study the convergence rate of this nonquadratic proximal method for convex and particularly linear programming. We identify a class of φ-divergences for which superlinear convergence is attained both for optimization problems with strongly convex objectives at the optimum and linear programming problems, when the regularization parameters tend to zero. We prove also that, with regularization parameters bounded away from zero, convergence is at least linear for a wider class of φ-divergences, when the method is applied to the same kinds of problems. We further analyze the associated class of augmented Lagrangian methods for convex programming with nonquadratic penalty terms, and prove convergence of the dual generated by these methods for linear programming problems under a weak nondegeneracy assumption.
Partial Affine-Scaling for Linearly Constrained Minimization
Authors: Tseng Paul
Published: October 2008

We propose an interior point method for finding a stationary point of a nonlinear program with linear equality and nonnegativity constraints. This method maintains a basis at each iteration and updates the iterate by taking an affine-scaling step in the space of nonbasic variables. In the general case, we propose to choose the basis according to a rule that maximizes the basic components of the iterate. In the case where the feasible region is the product of simplices, we propose an alternative rule that minimizes the basic components of the cost gradient. We analyze the convergence of the method under each rule. A key feature of this method is that it can be implemented much like the simplex method.
Lipschitz Continuity of Solutions of Variational Inequalities with a Parametric Polyhedral Constraint
Authors: Yen N. D.
Published: October 2008

It is proved that the metric projection from a point onto a moving polyhedron is Lipschitz continuous with respect to the perturbations on the right-hand sides of the linear inequalities defining the polyhedron. The property leads to a simple sufficient condition for Lipschitz continuity of a locally unique solution of parametric variational inequalities with a moving polyhedral constraint set. Applications of these results to traffic network equilibrium problems are given in detail.
Egalitarian Solutions of Large Games: II. The Asymptotic Approach
Authors: Hart Sergiu , Mas-Colell Andreu
Published: October 2008

This is the second of two papers devoted to the study of egalitarian solutions for nontransferable utility (NTU) games with a large number of players. This paper is concerned with the egalitarian solutions of finite games as the number of players increases. We show that these converge to the egalitarian solution of the limit game with a continuum of players as defined in our previous paper. The same convergence holds for the underlying potential functions. These asymptotic results are particularly significant since they provide the definitive justification for our definitions in the limit continuum case.
Asymptotic Stochastic Programs
Authors: Pflug Georg Ch.
Published: October 2008

Consider a stochastic program with unique solution. By the notion of epi-convergence in distribution in local coordinates, we define the asymptotic stochastic program associated to it. Stochastic programs may be classified according to the type of the pertaining asymptotic program. In particular, three such types are studied in detail: the normal shift program, the Wiener-type program and the Poisson-hyperplane program. Conditions for the convergence to each of the three types are given.
On a Newton Type Iterative Method for Solving Inclusions
Authors: Azé D. , Chou C. C.
Published: October 2008

We introduce a notion of strict differentiability for multifunctions by means of a notion of tangency based on a uniform property of Clarke's tangent cone. Given a multifunction G and a point (a, b) ∈ G and assuming that the derivative DG(a, b) is surjective and has a bounded inverse, we build a sequence ((xn, yn)) ⊂ G, such that d(xn+1 − xn, DG(a, b)−1(−yn)) converges to 0. The sequence ((xn, yn)) is shown to converge to (x, 0) where x is a solution of 0 ∈ G(x) provided the norm of ‖y0‖ is small enough. As a consequence we obtain an open mapping theorem for multifunctions whose proof is constructive.
Second-order Sufficiency and Quadratic Growth for Nonisolated Minima
Authors: Bonnans Joseph Frédéric , Ioffe Alexander
Published: October 2008

For standard nonlinear programming problems, the weak second-order sufficient condition is equivalent to the quadratic growth condition as far as the set of minima consists of isolated points and some qualification hypothesis holds. This kind of condition is instrumental in the study of numerical algorithms and sensitivity analysis. The arm of the paper is to study the relations between various types of sufficient conditions and quadratic growth in cases when the set of minima may have nonisolated points.
Symmetric Inequalities and Their Composition for Asymmetric Travelling Salesman Polytopes
Authors: Queyranne Maurice , Wang Yaoguang
Published: October 2008

The Asymmetric Travelling Salesman (ATS) polytope ATSP(V) is the convex hull of incidence vectors of all Hamiltonian circuits in a complete digraph with node set V. This paper studies classes of valid symmetric inequalities ay ≤ a0 for ATS polytopes with coefficients satisfying aij = aji for all pair of cities i and j. Of particular interest are those inequalities derived from facet-defining inequalities for Symmetric Travelling Salesman Polytopes (STSPs). We show that known classes of STSP facet-defining inequalities, such as Path, Wheelbarrow, Chain, and Ladder inequalities, induce symmetric ATSP facet-defining inequalities. For ATSP(V) with |V| ≤ 8, we show that there are precisely four types of STSP facet-defining inequalities that do not induce ATSP facets. We propose a Tree Composition of symmetric inequalities and use it to generate a large new class of symmetric facet-defining inequalities for ATS polytopes, subsuming all nonspanning Clique Tree inequalities. A Hamiltonian path approach is used for most of the polyhedral proofs in the paper.
A Convex Analytic Framework for Ergodic Control of Semi-Markov Processes
Authors: Bhatnagar Shalabh , Borkar Vivek S.
Published: October 2008

The ergodic control problem for semi-Markov processes is reformulated as an optimization problem over the set of suitably defined ‘ergodic occupation measures.’ This set is shown to be closed and convex, with its extreme points corresponding to stationary strategies. This leads to the existence of optimal stationary strategies under additional hypotheses. A pathwise analysis of the joint empirical occupation measures of the state and control processes shows that this optimality is in the strong (i.e., almost sure) sense.
Minimizing Maximum Promptness and Maximum Lateness on a Single Machine
Authors: Hoogeveen J. A.
Published: October 2008

We consider the following single-machine bicriteria scheduling problem. A set of n independent jobs has to be scheduled on a single machine that can handle only one job at a time and that is available from time zero onwards. Each job Jj requires processing during a given positive uninterrupted time pj, and has a given target start time sj and due date dj with A ≤ dj − sj ≤ A + pj for some constant A. For each job Jj (j = 1, …, n), its promptness Pj is defined as the difference between the target start time and the actual start time, and its lateness Lj as the difference between the completion time and the due date. We consider the problem of finding a schedule that minimizes a function F of maximum promptness Pmax = max1≤j≤nPj and maximum lateness Lmax = max1≤j≤nLj; we assume that F is nondecreasing in both arguments. We present an O(n2) algorithm for the variant in which idle time is not allowed and an O(n2 log n) algorithm for the special case in which the objective function is linear. We prove that the problem is 𝒩𝒫-hard if neither of these restrictions is imposed. As a side result, we prove that the special case of minimizing maximum lateness subject to release dates that lie in the interval [dj − pj − A, dj − A], for all j = 1, …, n and for some constant A, is solvable in O(n log n) time if no machine idle time is allowed and in O(n2 log n) time if machine idle time is allowed.
Stability and Instability of Fluid Models for Reentrant Lines
Authors: Dai J. G. , Weiss G.
Published: October 2008

Reentrant lines can be used to model complex manufacturing systems such as wafer fabrication facilities. As the first step to the optimal or near-optimal scheduling of such lines, we investigate their stability. In light of a recent theorem of Dai (Dai, J. G. 1995. On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid models. Ann. Appl. Probab. 5 49–77.) which states that a scheduling policy is stable if the corresponding fluid model is stable, we study the stability and instability of fluid models. To do this we utilize piecewise linear Lyapunov functions. We establish stability of First-Buffer-First-Served (FBFS) and Last-Buffer-First-Served (LBFS) disciplines in all reentrant lines, and of all work-conserving disciplines in any three buffer reentrant lines. For the four buffer network of Lu and Kumar we characterize the stability region of the Lu and Kumar policy, and show that it is also the global stability region for this network. We also study stability and instability of Kelly-type networks. In particular, we show that not all work-conserving policies are stable for such networks; however, all work-conserving policies are stable in a ring network.
Overtaking and Almost-Sure Optimality for Infinite Horizon Markov Decision Processes
Authors: Leizarowitz Arie
Published: October 2008

We consider infinite horizon optimal control of Markov chains on complete metric spaces. We employ the overtaking optimality criterion, which is either applied to the expected cost-flow, or to the individual sample paths, yielding almost-sure optimality results.

We use the existence of a solution pair (Φ(·), λ) to the optimality equation ℒΦ(x) = λ to establish and characterize optimal strategies. For finite state-spaces we derive sufficient, as well as necessary conditions for overtaking optimality.
Geometric Convergence Rates for Stochastically Ordered Markov Chains
Authors: Lund Robert B. , Tweedie Richard L.
Published: October 2008

Let {Φn} be a Markov chain on the state space [0, ∞) that is stochastically ordered in its initial state; that is, a stochastically larger initial state produces a stochastically larger chain at all other times. Examples of such chains include random walks, the number of customers in various queueing systems, and a plethora of storage processes. A large body of recent literature concentrates on establishing geometric ergodicity of {Φn} in total variation; that is, proving the existence of a limiting probability measure π and a number r > 1 such that [Formula: see text] for every deterministic initial state Φ0 ≡ x. We seek to identity the largest r that satisfies this relationship. A dependent sample path coupling and a Foster-Lyapunov drift inequality are used to derive convergence rate bounds; we then show that the bounds obtained are frequently the best possible. Application of the methods to queues and random walks are included.
An Impossibility Result in Axiomatic Location Theory
Authors: Hansen Pierre , Roberts Fred S.
Published: October 2008

We show that certain reasonable axioms for an optimal solution to the problem of locating a facility on a network, i.e., axioms of distance determination, Pareto optimality, and anonymity, and a weak Lipschitz condition, can be self-contradictory. In particular, we show that they fail for any network that has a cycle. It follows that under the axioms of distance determination, Pareto optimality, and anonymity, choice of optimal location may be very sensitive to changes in the locations of the users.
The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
Authors: Yakir Benjamin
Published: October 2008

The algorithm LDM (largest differencing method) divides a list of n random items into two blocks. The parameter of interest is the expected difference between the two block sums. It is shown that if the items are i.i.d. and uniform then the rate of convergence of this parameter to zero is n−Θ(log n). An algorithm for balanced partitioning is constructed, with the same rate of convergence to zero.