bluuebunny/crossref_metadata_2025_split huggingface dataset:
An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions
Authors: Kalantari B. , Rosen J. B. 
Published: October 2008

We present an algorithm for the global minimization of a quadratic function ψ(x, y) = −½xTQx + hTx + dTy, over a polytope Ω = {(x, y) ∈ ℝn+k: Ax + By ≤ b, x ≥ 0, y ≥ 0}, where x, h ∈ ℝn, y, d ∈ ℛk, b ∈ ℛm, and where A and B are m × n and m × k matrices, respectively, and Q is an n × n symmetric positive definite matrix. We first consider the case where k = 0 and construct a “tight” parallelpiped R, containing Ω by using an arbitrary set of Q-conjugate directions and by solving 2n linear programs. We show that the convex envelope of ψ with respect to R is linear and obtain an explicit formula for it. We then describe a branch and bound algorithm in which the linearity of the convex envelope allows efficient lower bounding for the subproblems. For each subproblem we obtain the linear convex envelope of ψ over a smaller parallelepiped, R′, with facets parallel to those of R. Then, we obtain a lower bound by minimizing this convex envelope over R′ ∩ Ω. If ψ* is the optimal objective value, for each ϵ ≥ 0, the algorithm generates a sequence of feasible points zj with nonincreasing function values ψj and a nondecreasing sequence Γj, of lower bounds to ψ*. Moreover if ϵ > 0, there exist j0 such that (ψj − Γj) ≤ ϵ for all j ≥ j0, and if ϵ = 0, (ψj − Γj) converges to 0. The results are then generalized to the case where k is nonzero and possibly much larger than n. Preliminary computational results are also presented.
On Waiting for Simultaneous Access to Two Resources
Authors: Honig Michael L. , Ott Teunis J. 
Published: October 2008

This paper studies the M/G/1 queue where a special (test) customer can get service only if he has simultaneous access to the server and a second resource. All other customers only need access to the server. The second resource becomes available after an exponentially distributed amount of time. The ordinary customers are served according to the FIFO discipline. The test customer has the freedom to leave his place in the queue at any time and join the end of the queue. If he reaches the server before the second resource becomes available, he then must return to the back of the queue. We derive the waiting time distribution of the test customer given that he always maintains his position in the queue until he reaches the server. A number of conditions are given under which this “move-along” policy is optimal, i.e., minimizes the test customer's mean delay until service. These conditions depend on the amount of information and freedom of action available to the test customer.
A Class of Euclidean Routing Problems with General Route Cost Functions
Authors: Anily S. , Federgruen A. 
Published: October 2008

In most vehicle routing problems, a given set of customers is to be partitioned into a collection of regions each of which is assigned to a single vehicle starting at a depot and returning there after visiting all of the region's customers exactly once in a route. In this paper we consider problem settings where the cost of a route may depend on its length ϑ as well as m, the number of points on the route, according to some general function f(ϑ, m), assumed to be nondecreasing and concave in ϑ. We describe a class of O(N logN) or O(N2) heuristics and show under mild probabilistic assumptions that the solutions generated are asymptotically optimal. We also show that lower and upper bounds on the system-wide costs may be computed (with even simpler procedures) and that these bounds are asymptotically tight under the same assumptions.
The Shapes of Polyhedra
Authors: Kannan Ravi , Lovász Lászlo , Scarf Herbert E. 
Published: October 2008

Let A be a real matrix of size (n + d + 1) × n. We assume that all n × n submatrices of A are nonsingular and define the condition number C = C(A) to be the ratio of the largest n × n subdeterminant of A to the smallest in absolute value. In addition we assume that there is a positive vector π such that πA = 0. This implies that for any b, the body Kb = {x∣Ax ≤ b} is bounded. Let f(A) be the number of subsets of the rows of A, of cardinality n + 1, for which a positive linear combination equals zero. The Banach-Mazur distance Ρ(Kb, Kc) for a pair of nonempty full dimensional bodies Kb and Kc is defined as follows: let λ1 be the smallest λ for which Kc ⊆ λ Kb + ξ1 for some ξ1 and λ2 the smallest λ for which Kb ⊆ λ Kc + ξ2 for some ξ2. Then Ρ(Kb, Kc) = log(λ1 ⋅ λ2). We show that for any ε > 0, there exists a subset of the bodies Kb, of cardinality not larger than f(A)⌈2 log2 (nC)/ε⌉d, such that every body is within distance ε from some member of the subset.
On-Line Optimization of Simulated Markovian Processes
Authors: Pflug G. Ch. 
Published: October 2008

Let {Zn} be a Markovian process, the transition of which depends on a control parameter x. Let μx be its invariant law. It is shown that the solution of the optimization problem F(x) := ∫ H(z, x) dμx(z) = min!, x ∈ S can be found with a recursive estimation procedure of the stochastic approximation-type. The method consists in finding a stochastic quasigradient of F(x) and in adapting the parameter x in the direction of descent. An a.s. convergence is proved and a practical example is given.
On the Cookie-Cutter Game: Search and Evasion on a Disc
Authors: Danskin John M. 
Published: October 2008

In the cookie-cutter game, there is a trapping circle, of radius 1, in which an evader hides. A searcher has a “cookie-cutter”, a disk of radius r < 1. If, when he places the cookie-cutter on the trapping circle, the evader is within it, the evader is caught and the searcher wins. Otherwise the evader wins. If r = √2/2, the problem is trivial. The evader should choose a point from the uniform distribution on the outer circumference of the trapping circle, and the searcher a point from the uniform distribution on the circle of radius r* = (1 − r2)1/2 concentric to that circle; this choice gives him maximum coverage of the outer circumference. For the case r ≧ 1/2, an easy and elegant solution was given by Gale and Glassey in 1974. Both players should go to the center with probability 1/7. The minimizer should go to the outer circumference, and the maximizer to r* = √3/2, both with probability 6/7. For other r the problem is difficult. This paper proves that there are no solutions based on finitely many radii if r < r0 ≐ 0.476, where r0 solves a cubic equation, finds two-point solutions on [r0, r1], where r1 ≐ 0.515 solves a trigonometric equation, and proves qualitative facts for r ∈ (r1, √2/2).
Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions
Authors: Monma Clyde L. , Schrijver Alexander , Todd Michael J. , Wei Victor K. 
Published: October 2008

Consider the following resource allocation problem on a directed acyclic graph (the precedence graph). Each vertex has a known work load, and a fixed amount of total resource is available. The time required to process a vertex is inversely proportional to the amount of the resource allocated to it. The time to complete all of the work is the length of (time to complete) a longest chain in the graph. The problem of finding an allocation which minimizes the time required to complete all of the work subject to the limited resource availability can be formulated as a separable convex programming problem. We use results from Lagrangian duality for convex programs, the length-width inequality, and Dilworth's Theorem for directed acyclic graphs, to obtain a strong relationship between optimal solutions of this problem and its dual. This allows us to obtain closed-form solutions for certain special classes of graphs, and leads to a generalization of the LYM Property for partially ordered sets. The computational complexity of the general problem is an open question. However, the ellipsoid method yields a fully-polynomial approximation scheme, and some light can be shed on the associated decision problem. The results of this paper are shown to extend to resource allocation problems on perfect graphs.
Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Objective Over a Polyhedron
Authors: Thakur Lakshman S. 
Published: October 2008

Using linear underestimating approximations and their dual solutions, we develop new results for the nonconvex problem of minimizing a quadratic concave function under linear constraints. For solving this problem, which has such important management applications as economies of scale, fixed charge, and quadratic assignment problems, some results provide and tighten bounds on the global minimum value, while others identify the domains of the variables which may be excluded from further consideration. This leads to successive reduction of domains containing a global solution, called domain contraction, and ideally, to a solution with the objective value within some acceptable error level. For most results, specific problem instances are provided to establish their use in theory. In practice, experience with solving the problems presented here indicates that a combination of the proposed domain contraction via linear underestimation and its dual information with the branch and bound approach offers a computational strategy competitive with the currently dominant methods: combinations of branch and bound with (1) cutting planes, (2) relaxation, or (3) domain partitioning. Problems with up to 100 variables and up to 50 linear constraints (50 × 100), comparable in difficulty and size with the largest published in the literature, are solved and included in the initial implementation of the approach.
A Method for the Parametric Center Problem, with a Strictly Monotone Polynomial-Time Algorithm for Linear Programming
Authors: Freund Robert M. , Tan Kok-Choon 
Published: October 2008

Given a system of linear inequalities Ax ≤ b + dt and equalities Mx = g + ht, where the right-hand sides are parametrically deformed over the scalar t, the parametric center problem is to trace the parametric family of approximate solutions x̄(t) to the center problems P(t), where P(t) is the problem: maximize ∑i=1m ln(bi + dit − Aix) subject to Ax < b + dt and Mx = g + ht. We present an algorithm for tracing the parametric family of solutions x̄(t) over some given range. At the kth iterate of the algorithm, the point x̄(tk) is an approximate solution to the center problem P(tk) (in an appropriate measure of approximation). The value of tk is increased to tk+1, and a Newton step is used to generate x̄(tk+1) which is an approximate solution to the center problem P(tk+1). The sequence of values of t exhibit at least one of the following geometric rates of change: (TMAX − tk + 1) ≤ (TMAX − tk)(1 − 1/(128m)) (tk + 1 − TMIN) ≥ (tk − TMIN)(1 + 1/(128m)) where TMIN (TMAX) is the maximum (minimum) number t such that Ax ≤ b + dt, Mx = g + ht has a solution. Thus the iterates exhibit either linear growth away from TMIN or linear convergence toward TMAX, with a rate of change of 1/(128m), where m is the number of inequality constraints. When applied to the linear programming problem, the algorithm is an O(mL) iteration algorithm for linear programming, that strictly improves the primal objective value at each iteration, and requires no dual feasible solution (or even dual feasibility) to start. After O(mL) iterations, the algorithm either detects primal unboundedness or produces an interior solution that can be rounded to an optimal solution to the linear program.
On the Continuous Trajectories for a Potential Reduction Algorithm for Linear Programming
Authors: Monteiro Renato D. C. 
Published: October 2008

For a possibly degenerate linear program minx{cTx; Ax = b, x ≥ 0} (A is an m × n real matrix, b ∈ Rm and c ∈ Rn), whose optimal value is 0, we study the limiting behavior of the trajectories of the family of vector fields Φq(x) ≡ −XPAX [Xc − q≡1(cTx) 1]. for all values of q ≥ n, where X is the diagonal matrix associated with x and PAX is the projection operator onto the null space of AX. A polynomial algorithm based on the directions Φq(x) has been presented by Gonzaga [6] when q = n or q = n + √n. We show that all trajectories of Φq(x) converge to the unique “center” of the optimal face of the given linear program. When this face consists of a unique vertex, it is shown that any trajectory of Φq(x) approaches this vertex along the same direction. When the optimal face consists of more than one point, we show that there is a threshold value τ > 0 such that: for q > τ, “most” of the trajectories of Φq(x) converge to the “center” tangentially to the optimal face and that the direction of approach of a trajectory of Φq(x) depends on the initial condition: for q < τ (q = τ), the trajectories of Φq(x) converge to the “center” along a unique direction (along several directions which depend on the initial condition) forming a positive angle with the optimal face.
Neighbors of the Origin for Four by Three Matrices
Authors: Shallcross David 
Published: October 2008

Scarf has defined a neighborhood system for families of integer programs where the right-hand side is allowed to vary. This system depends on a matrix A of constraint and objective function coefficients of the integer programs. This paper characterizes the set of neighbors of the origin when A is four by three, showing that it may be described as the set of integer vectors in a union of two-dimensional polyhedra, where the number of polyhedra is quadratic in the bit size of A.
Normal Maps Induced by Linear Transformations
Authors: Robinson Stephen M. 
Published: October 2008

We study a certain piecewise linear manifold, which we call the normal manifold, associated with a polyhedral convex set, and a family of continuous functions, called normal maps, that are induced on this manifold by continuous functions from Rn to Rn. These normal maps occur frequently in optimization and equilibrium problems, and the subclass of normal maps induced by linear transformations plays a key role. Our main result is that the normal map induced by a linear transformation is a Lipschitzian homeomorphism if and only if the determinant of the map in each n-cell of the normal manifold has the same (nonzero) sign.
The Generalized Basis Reduction Algorithm
Authors: Lovász László , Scarf Herbert E. 
Published: October 2008

Let F(x) be a convex function defined in Rn, which is symmetric about the origin and homogeneous of degree 1, and let L be the lattice of integers Zn. A definition of a reduced basis, b1, …, bn, of the lattice with respect to the distance function F is presented, and we describe an algorithm which yields a reduced basis in polynomial time, for fixed n. In the special case in which the bodies {x: F(x) ≤ t} are ellipsoids, the definition of a reduced basis is identical with that given by Lenstra, Lenstra and Lovász (1982) and the algorithm is the well-known basis reduction algorithm. We show that the basis vector b1, in a reduced basis, is an approximation to a shortest nonzero lattice point with respect to F and relate the basis vectors bi to Minkowski's successive minima. The results lead to an algorithm for integer programming which executes in polynomial time for fixed n, but which avoids the ellipsoidal approximations required by Lenstra's algorithm. We also discuss the properties of a Korkine-Zolotarev basis for the lattice.
Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
Authors: Federgruen A. , Queyranne M. , Zheng Yu-Sheng 
Published: October 2008

We consider a production/distribution network represented by a general directed acyclic network. Each node is associated with a specific “product” or item at a given location and/or production stage. An arc (i, j) indicates that item i is used to “produce” item j. External demands may occur at any of the network's nodes. These demands occur continuously at item specific constant rates. Components may be assembled in any given proportions. The cost structure consists of inventory carrying, and variable and fixed production/distribution costs. The latter depend, at any given replenishment epoch, on the specific set of items being replenished, according to an arbitrary set function merely assumed to be monotone and submodular. We show that a simply structured, so-called power-of-two policy is guaranteed to come within 2% of a lower bound for the minimum cost. Under a power-of-two policy, all items are replenished at constant intervals and only when their inventory drops to zero; moreover, these replenishment intervals are all power-of-two multiples of a common base planning period. The above results generalize those of Roundy (1986).
Stability Results for Ekeland's ε-Variational Principle and Cone Extremal Solutions
Authors: Attouch Hedy , Riahi Hassan 
Published: October 2008

Given X a Banach space and f: X → ℝ ∪ {+∞} a proper lower semicontinuous function which is bounded from below, the Ekeland's ε-variational principle asserts the existence of a point x̄ in X, which we call ε-extremal with respect to f, which satisfies f(u) > f(x̄) − ε‖u − x̄‖ for all u ∈ X, u ≠ x̄. By using set convergence notions (Kuratowski-Painlevé, Mosco, bounded Hausdorff) and their epigraphical versions we study the (semi) continuity properties of the mapping which to f associates ε-ext f the set of such ε-extremal points. The key for the geometrical understanding of such properties is to consider the equivalent Phelps extremization principle which, given a closed set D in X and a partial ordering with respect to a pointed cone, associates the set of elements of D maximal with respect to this order. Direct or potential applications are given in various fields (multicriteria optimization, numerical algorithmic, calculus of variations).
Random Walk and the Area Below its Path
Authors: Harel Arie 
Published: October 2008

A simple random walk with reflected origin is considered. The walk starts at the origin and it must return to the origin at time 2n. We show that the expected area below the path of this walk is n22n−1/Cn2n. If, however, the walk is required to return to the origin for the first time at time 2n, then the expected area below the path of this Bernoulli excursion is (2n − 1)22n−1/Cn2n. We also show that if V1 < ⋯ < Vn is the order statistics based on a sample of size n from a uniform distribution over (0, 1), and that if U1 < ⋯ < Un is another independent set of order statistics from the same distribution, then E [∑i=1n |Vi − Ui|] = n22n−1/[(2n + 1)Cn2n] We use this result to find an average-case performance of the Earliest Due Date (EDD) heuristic for one machine scheduling problem with earliness and tardiness penalties. We also apply some of the results to Larson's Queue Inference Engine (1990).
Global Convergence of Damped Newton's Method for Nonsmooth Equations via the Path Search
Authors: Ralph Daniel 
Published: October 2008

A natural damping of Newton's method for nonsmooth equations is presented. This damping, via the path search instead of the traditional line search, enlarges the domain of convergence of Newton's method and therefore is said to be globally convergent. Convergence behavior is like that of line search damped Newton's method for smooth equations, including Q-quadratic convergence rates under appropriate conditions. Applications of the path search include damping Robinson-Newton's method for nonsmooth normal equations corresponding to nonlinear complementarity problems and variational inequalities, hence damping both Wilson's method (sequential quadratic programming) for nonlinear programming and Josephy-Newton's method for generalized equations. Computational examples from nonlinear programming are given.
The Linear Complementarity Problem with Exact Order Matrices
Authors: Mohan S. R. , Parthasarathy T. , Sridhar R. 
Published: October 2008

(Dedicated to Professor K. G. Ramamurthy on the occasion of his 60th birthday.) A real n by n matrix A is called an N(P)-matrix of exact order k if the principal minors of A of order 1 through (n + k) are negative (positive) and (n − k + 1) through n are positive (negative). In this paper the properties of exact order 1 and 2 matrices are investigated, using the linear complementarity problem LCP(q, A) for each q ∈ Rn. A complete characterization of the class of exact order 1 based on the number of solutions to the LCP(q, A) for each q ∈ Rn is presented. In the last season we consider the problem of computing a solution to the LCP(q, A) when A is a matrix of exact order 1 or 2.
Construction of Stationary Markov Equilibria in a Strategic Market Game
Authors: Karatzas Ioannis , Shubik Martin , Sudderth William D. 
Published: October 2008

This paper studies stationary noncooperative equilibria in an economy with fiat money, one nondurable commodity, countably many time-periods, no credit or futures market, and a measure space of agents—who may differ in their preferences and in the distributions of their (random) endowments. These agents are immortal, and hold fiat money as a means of hedging against the random fluctuations in their endowments of the commodity. In the aggregate, these fluctuations offset each other, and equilibrium prices are constant. We carry out an equilibrium analysis that focuses on distribution of wealth, on consumption, and on price formation. A careful analysis of the one-agent, infinite-horizon optimization problem, and of the invariant measure for the associated optimally controlled Markov chain, leads by aggregation to a stationary noncooperative or competitive equilibrium. This consists of a price for the commodity and of a distribution of wealth across agents which, under appropriate simple strategies for the agents, stay fixed from period to period and preserve the basic quantities of the model. We hope that, in future work, we shall be able to address additional features of the model treated here, such as borrowing and lending at appropriate (endogenously determined) interest rates, the endogenous production of commodity, overlapping generations of agents, and bankruptcy and treatment of creditors.
Some Stochastic Bounds for Dams and Queues
Authors: Harrison J. Michael 
Published: October 2008

Let X = {X(t), t > 0} be a process of the form X(t) = Z(t) − ct, where c is a positive constant and Z is an infinitely divisible, nondecreasing pure jump process. Assuming E[X(t)] < 0. let U be the d.f. of M = sup X(t). As is well known, U is the contents distribution of a dam with input Z and release rate c. If Z is compound Poisson, one can alternately view U as the waiting time distribution for an M/G/1 queue or 1 − U as the ruin function for a risk process. Letting X and X0 be two processes of the indicated form, it is shown that U ≤ U0 if the two jump measures are ordered in a sense weaker than stochastic dominance. In the case where E(M) = E(M0), a different condition on the jump measures yields E[f(M)] ≤ E[f(M0)] for all concave f, this resulting from second-order stochastic dominance of the supremum distributions. By way of application, processes with deterministic jumps are shown to be extremal in certain ways, and those with exponential jumps are shown to be extremal among the class having IFR jump distribution. Finally, an extremal property of Brownian Motion (which is not among the class of processes considered) is demonstrated, this yielding simple bounds for E[f(M)] with f concave or convex. It is shown how all the bounds obtained for U or E[f(M)] can be further sharpened with additional computation.