bluuebunny/crossref_metadata_2025_split huggingface dataset:
Cores of Tangent Cones and Clarke's Tangent Cone
Authors: Martin D. H. , Watkins G. G. 
Published: October 2008

It is known that Clarke's tangent cone at any point of any subset of Rn is always both unique and convex. By contrast, nearly all other notions of convex tangent cone in the literature are monotone in the sense that if a convex cone K is a tangent cone at a point x0 of a set C ⊆ Rn, then K′ ⊆ K, C ⊆ C′ automatically implies that K′ is a tangent cone of the same type for C′ at x0. This carries the rider that such tangent cones are not unique and, in general, even maximal (convex) tangent cones are not unique. In this paper it is shown that for most monotone types, one can identify preferred tangent cones (for C at x0), called core tangent cones of that type, such that maximal core tangent cones are unique and convex.
Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
Authors: Grötschel M. , Pulleyblank W. R. 
Published: October 2008

The linear programming cutting plane approach for solving the travelling salesman problem has recently proven to be highly successful, cf. Crowder and Padberg (Crowder, H. P., M. W. Padberg. 1980. Solving large-scale symmetric travelling salesman problems to optimality. Management Sci. 26 495–509.), Grötschel (Grötschel, M. 1980a. On the symmetric travelling salesman problem: Solution of a 120 city problem. Math. Programming Stud. 12 61–77.), Padberg and Hong (Padberg, M. W., S. Hong. 1980. On the symmetric travelling salesman problem: A computational study. Math. Programming Stud. 12 78–107.). One of the reasons for this success is certainly the fact that instead of ordinary cutting planes (Gomory-cuts etc.) problem-specific cutting planes could be used which define facets of the underlying integer programming polytopes. In this paper we shall define a new class of inequalities (clique tree inequalities) valid for the travelling salesman polytope which properly contains many of the known classes of inequalities (like subtour elimination constraints, 2-matching constraints, comb inequalities), and we show that all these new inequalities induce facets of the travelling salesman polytope. Since the general structure of these new inequalities is quite simple we hope that it will be possible to use the inequalities efficiently in cutting plane procedures for the travelling salesman problem.
Structured Policies for a Sequential Design Problem with General Distributions
Authors: Benzing Harald , Kolonko Michael 
Published: October 2008

Consider the problem of allocating two treatments in a sequence of N trials such that the total expected reward is maximized. We assume that the distribution of outcomes is known for one of the treatments only (so-called one-armed bandit problem). In a suitable dynamic programming model we examine the structural properties of an optimal policy. In particular we extend results known for Bernoulli distributed outcomes to more general distributions. Our main technical results are monotonicity and convexity of the total expected reward.
Generalized Descent Methods for Asymmetric Systems of Equations
Authors: Hammond Janice H. , Magnanti Thomas L. 
Published: October 2008

We consider generalizations of the steepest descent algorithm for solving asymmetric systems of equations. We first show that if the system is linear and is defined by the matrix M, then the method converges if M2 is positive definite. We also establish easy to verify conditions on the matrix M that ensure that M2 is positive definite, and develop a scaling procedure that extends the class of matrices that satisfy the convergence conditions. In addition, we establish a local convergence result for nonlinear systems defined by uniformly monotone maps, and discuss a class of general descent methods. All of the methods that we consider reduce to standard nonlinear programming algorithms for equivalent optimization problems when the Jacobian of the underlying problem map is symmetric. We interpret the convergence conditions for the generalized steepest descent algorithms as restricting the degree of asymmetry of the problem map.
Solving SLP Recourse Problems with Arbitrary Multivariate Distributions—The Dependent Case
Authors: Frauendorfer Karl 
Published: October 2008

Bounding the expectation of a convex function of a multivariate random variable is of great importance for solving stochastic linear programming problems (SLP) with recourse. The classic bounds are those of Jensen and Edmundson-Madansky, whereby Jensen's inequality is available in the independent as well as in the dependent case, in contrast with the Edmundson-Madansky (E-M) inequality (Madansky, A. 1959. Bounds on the expectation of a convex function of multivariate random variable. Ann. Math. Statist. 30 743–746.) which is valid only in the independent case. This paper presents a straightforward extension of the E-M inequality for the dependent case, yielding a discrete distribution that is extremal with respect to a partial ordering of a set of distribution functions. Further, we prove that the bounds for the expectation behave monotonically by applying the obtained inequality to smaller and smaller subintervals. As this requires the evaluation of conditional probabilities and expectations, we replace the given distribution by a discrete one resulting from sampling, and determine the sampling size that keeps the statistical error negligible. Finally we conclude with the application to SLP recourse problems and state some computational results illustrating the effort for solving recourse problems.
Average, Sensitive and Blackwell Optimal Policies in Denumerable Markov Decision Chains with Unbounded Rewards
Authors: Dekker Rommert , Hordijk Arie 
Published: October 2008

In this paper we consider a (discrete-time) Markov decision chain with a denumerable state space and compact action sets and we assume that for all states the rewards and transition probabilities depend continuously on the actions. The first objective of this paper is to develop an analysis for average optimality without assuming a special Markov chain structure. In doing so, we present a set of conditions guaranteeing average optimality, which are automatically fulfilled in the finite state and action model. The second objective is to study simultaneously average and discount optimality as Veinott (Veinott, A. F., Jr. 1969. On discrete dynamic programming with sensitive discount optimality criteria. Ann. Math. Statist. 40 1635–1660.) did for the finite state and action model. We investigate the concepts of n-discount and Blackwell optimality in the denumerable state space, using a Laurent series expansion for the discounted rewards. Under the same condition as for average optimality, we establish solutions to the n-discount optimality equations for every n.
A Geometrically Convergent Subgradient Optimization Method for Nonlinearly Constrained Convex Programs
Authors: Rosenberg Eric 
Published: October 2008

In this paper we extend the geometrically convergent subgradient optimization method for minimizing a convex function, proposed independently by Goffin and also Shor and Gamburd, to a class of constrained convex programs. We permit both arbitrary set constraints and convex inequality constraints. Such programs arise, for example, in sizing trunks in a multi-hour alternate routing telecommunications network and in certain location and approximation problems. The geometric convergence rate depends upon a condition number of the convex program that we define. Our proof of geometric convergence, when explicit convex inequality constraints are present, is the first such result for subgradient optimization. We compare the iterates generated by our method to the limiting behavior, as the penalty parameter approaches infinity, of the sequence of iterates obtained by applying Goffin's method to the exact penalty function corresponding to the convex program. We also show that geometric convergence still holds when ϵ-subgradients (for sufficiently small ϵ > 0) are used instead of subgradients.
On the Facial Structure of Independence System Polyhedra
Authors: Conforti Michele , Laurent Monique 
Published: October 2008

A polyhedron P whose extreme points are the incidence vectors of the sets of an independence system ℐ is called an independence system polyhedron. In this paper, we consider the problem of describing the facial structure of independence system polyhedra. Using the fact that this structure is known when the independence system is a matroid, we study the polyhedron P by decomposing the independence system ℐ as a union of matroidal families. We provide a system of valid inequalities for P that contains all its facets. A consequence of this result is the following: the maximum number of distinct coefficients of a facet is bounded by the minimum number of matroidal families whose union gives ℐ. When the independence system ℐ is the union of two matroids, we give necessary and sufficient conditions for an inequality of the above system to define a facet of P.
Open Queueing Systems in Light Traffic
Authors: Reiman Martin I. , Simon Burton 
Published: October 2008

Many quantities of interest in open queueing systems are expected values which can be viewed as functions of the arrival rate to the system. We are thus led to consider f(λ), where λ is the arrival rate, and f represents some quantity of interest. The aim of this paper is to investigate the behavior of f(λ), for λ near zero. This ‘light traffic’ information is obtained in the form of f(0) and its derivatives, f(n)(0), n ≥ 1. Focusing initially on Poisson arrival processes, we provide a method to calculate f(n)(0) for any ‘admissible’ function f. We describe a large class of queueing networks for which we show several standard quantities of interest to be admissible. The proof that the method yields the correct values for the derivatives involves an interchange of limits, whose justification requires a great deal of effort. The determination of f(n)(0) involves consideration of sample paths with n + 1 or fewer arrivals over all of time. These calculations are illustrated via several simple examples. These results can be extended to arrival processes which, although not Poisson, are ‘driven’ by a Poisson process. We carry out the details for phase type renewal processes and nonstationary Poisson processes.
An Abstract Linear Duality Model
Authors: Carvalho P. C. P. , Trotter L. E. 
Published: October 2008

We investigate an abstract linear duality model which has as special instances several duality systems of interest in combinatorial optimization: subspace orthogonality, cone polarity, lattice duality, blocking polyhedra and antiblocking polyhedra. The descriptive duality present in the model is that of specifying a set in terms of linear constraints or viewing a set as being generated by certain types of linear combinations. We define properties of Weyl, Farkas and Minkowski for the general model by analogy with classical results in cone polarity and we investigate relationships among these properties and further properties of Lehman and Fulkerson, defined by analogy with results on dual pairs of polyhedra of the blocking or antiblocking type. In particular, we show that, for any given duality system, the Weyl property is equivalent to the combined properties of Farkas and Minkowski (or Lehman), that the Farkas property implies the Fulkerson property and that the Minkowski property is equivalent to the combined properties of Lehman and Fulkerson. We also adapt results of Dixon (Dixon, J. D. 1981. On duality theorems. Linear Algebra Appl. 39 223–228.) in order to obtain general sufficient conditions for validity of the Weyl property. In the second part of the paper, specific instances of the model are examined in more detail. The instances studied here are “integral duality” and “nonnegative integral duality,” which are related to the problem of finding integral solutions and nonnegative integral solutions, respectively, for linear systems. For each instance, the validity of the Weyl, Minkowski, Farkas, Lehman and Fulkerson properties is examined. We also characterize the constrained sets under each duality.
An Axiomatic Approach to Proportionality Between Matrices
Authors: Balinski M. L. , Demange G. 
Published: October 2008

Given a matrix p ≥ 0 what does it mean to say that a matrix f (of the same dimension), whose row and column sums must fall between specific limits, is “proportional to” p? This paper gives an axiomatic solution to this question in two distinct contexts. First, for any real “allocation” matrix f. Second, for any integer constrained “apportionment” matrix f. In the case of f real the solution turns out to coincide with what has been variously called biproportional scaling and diagonal equivalence and has been much used in econometrics and statistics. In the case of f integer the problem arises in the simultaneous apportionment of seats to regions and to parties and also in the rounding of tables of census data.
Limiting Behavior of Trajectories Generated by a Continuation Method for Monotone Complementarity Problems
Authors: Kojima Masakazu , Mizuno Shinji , Noma Toshihito 
Published: October 2008

Defining the mapping F from the 2n-dimensional Euclidean space R2n into itself by F(x, y) = (x1 y1, …, xn yn, y1 − f1(x), …, yn − fn(x)) for every (x, y) ∈ R2n, we write the CP, the complementarity problem, with a mapping f: Rn → Rn as the system of equations F(x, y) = 0 and (x, y) ∈ R+2n, where R+2n denotes the nonnegative orthant of R2n. Under the assumption that f is a monotone function on R+n, we show that F maps the positive orthant R++2n of R2n homeomorphically. This result then ensures the existence of a trajectory consisting of the solutions (x, y, t) of the system of equations F(x, y) = w(t) and (x, y, t) ∈ R++2n × (0, 1], where w is a continuous mapping from the unit interval [0, 1] into F(R++2n) such that w(0) = 0; if t = 0, the system coincides with the CP. We study limiting behavior of the trajectory as t → 0, and give some sufficient conditions for the trajectory to lead to a solution of the CP. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving positive semidefinite linear complementarity problems.
Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
Authors: Goemans Michel X. , Bertsimas Dimitris J. 
Published: October 2008

We analyze probabilistically the classical Held-Karp lower bound derived from the 1-tree relaxation for the Euclidean traveling salesman problem (ETSP). We prove that, if n points are identically and independently distributed according to a distribution with bounded support and absolutely continuous part f(x)dx over the d-cube, the Held-Karp lower bound on these n points is almost surely asymptotic to βHK(d)n(d−1)/d ∫ f(x)(d−1)/d dx, where βHK(d) is a constant independent of n. The result suggests a probabilistic explanation of the observation that the lower bound is very close to the length of the optimal tour in practice, since the ETSP is almost surely asymptotic to βTSP(d)n(d−1)/d ∫ f(x)(d−1)/d dx. The techniques we use exploit the polyhedral description of the Held-Karp lower bound and the theory of subadditive Euclidean functionals.
An Implicit-Function Theorem for a Class of Nonsmooth Functions
Authors: Robinson Stephen M. 
Published: October 2008

In this paper we introduce the concept of strong approximation of functions, and a related concept of strong Bouligand (B-) derivative, and we employ these ideas to prove an implicit-function theorem for nonsmooth functions. This theorem provides the same kinds of information as does the classical implicit-function theorem, but with the classical hypothesis of strong Fréchet differentiability replaced by strong approximation, and with Lipschitz continuity replacing Fréchet differentiability of the implicit function. Therefore it is applicable to a considerably wider class of functions than is the classical theorem. In the last part of the paper we apply this implicit function result to analyze local solvability and stability of perturbed generalized equations.
Cyclic Schedules for Job Shops with Identical Jobs
Authors: Roundy Robin 
Published: October 2008

We consider the problem of finding cyclic schedules for a job shop in which all jobs are identical. Specifically, we assume that a single product is produced on a finite number of machines. Each part is manufactured by performing a given set of operations in a pre-determined sequence. Each operation can be performed on exactly one machine. Key structural properties of cyclic schedules are studied. A search algorithm based on these properties is proposed, and preliminary computational tests of the algorithm are reported.
A Fully Polynomial-Time Approximation Algorithm for Computing a Stationary Point of the General Linear Complementarity Problem
Authors: Ye Yinyu 
Published: October 2008

We apply a potential reduction algorithm to solve the general linear complementarity problem (GLCP) minimize xTy subject to Ax + By + Cz = q and (x, y, z) ≥ 0. We show that the algorithm is a fully polynomial-time approximation scheme (FPTAS) for computing an ε-approximate stationary point of the GLCP. Note that there are some GLCPs in which every stationary point is a solution (xTy = 0). These include the LCPs with row sufficient matrices. We also show that the algorithm is a polynomial-time algorithm for a special class of GLCPs.
Convergence of the Value Functions of Discounted Infinite Horizon Optimal Control Problems with Low Discount Rates
Authors: Wirth Fabian 
Published: October 2008

For autonomous, nonlinear, smooth optimal control systems on n-dimensional manifolds we investigate the relationship between the discounted and the average yield optimal value of infinite horizon problems. It is shown that the value functions of discounted problems converge to the value function of the average yield problem as the discount rate tends to zero, if there exist approximately optimal solutions satisfying some periodicity conditions. In general, the discounted value functions cannot be expected to converge, which is shown by a counterexample. A connection to geometric control theory is then made to establish a result of uniform convergence on compact subsets of the interior of control sets, if optimal trajectories do not leave a compact subset of the interior of these control sets.
Lot-Sizing with Constant Batches: Formulation and Valid Inequalities
Authors: Pochet Yves , Wolsey Laurence A. 
Published: October 2008

We consider the classical lot-sizing problem with constant production capacities (LCC) and a variant in which the capacity in each period is an integer multiple of some basic batch size (LCB). We first show that the classical dynamic program for LCC simplifies for LCB leading to an O(n2 min{n, C}) algorithm (where n is the number of periods and C the batch size). Using this new algorithm, we show how to formulate both problems as linear programs with O(n3) variables and constraints. A class of so-called (k, l, S, I) inequalities are described for LCB which capture both the dynamic nature of the problem as well as the capacity aspects. For LCB, we prove that these inequalities are the only facet-defining inequalities of a certain form. For LCC, we show that these inequalities include all the known classes of valid inequalities. Finally, we discuss several open questions and possible extensions.
A General Framework of Continuation Methods for Complementarity Problems
Authors: Kojima Masakazu , Megiddo Nimrod , Mizuno Shinji 
Published: October 2008

A general class of continuation methods is presented which, in particular, solve linear complementarity problems with compositive-plus and L*-matrices. Let a, b ∈ Rn be nonnegative vectors. We embed the complementarity problem with a continuously differentiable mapping f: Rn → Rn in an artificial system of equations (*)   F(x, y) = (μa, ζb) and (x, y) ≥ 0, where F: R2n → R2n is defined by F(x, y) = (x1y1, …, xnyn, y − f(x)) and μ ≥ 0 and ζ ≥ 0 are parameters. A pair (x, y) is a solution of the complementarity problem if and only if it solves (*) for μ = 0 and ζ = 0. A general idea of continuation methods founded on the system (*) is as follows: (1) Choose n-dimensional vectors a ≥ 0 and b > 0 such that the system (*) has a trivial solution (x1, y1) for some μ1, ζ1 ≥ 0. (2) Trace solutions of (*) from (x1, y1) with μ = μ1 and ζ = ζ1 as the parameters μ and ζ are decreased to zero. This idea provides a theoretical basis for various methods such as Lemke's method and a method of tracing the central trajectory of linear complementarity problems.
Stochastic Convexity and Concavity of Markov Processes
Authors: Li Haijun , Shaked Moshe 
Published: October 2008

In this paper we consider the temporal stochastic convexity and concavity properties of Markov processes {X(t), t ∈ S} in discrete time (then S = N+ ≡ {0, 1, 2, …}) or in continuous time (then S = [0, ∞)). That is, we obtain conditions on the process {X(t), t ∈ S} which imply that the expectation Ef(X(t)) is a monotone convex (concave) function of t whenever f is a monotone convex (concave) function. The theory is illustrated through some examples. After giving some background we define ℱ-monotonicity and then obtain some general results concerning stochastic convexity and concavity of Markov processes by using the notion of ℱ-monotone operators. We then introduce a method for identifying ℱ-monotone operators, and we discuss the relationship between our results concerning temporal convexity and other results in the literature. In particular, we center our attention on a notion of stochastic concavity. In this respect we show that a result of Shaked and Shanthikumar is incorrect and we prove two alternative versions of it. The approach that we use here is an operator-analytic approach. This approach is quite powerful, but not as intuitive as sample path approaches used in other papers. However, using it, we can obtain results that we could not obtain otherwise.
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).