bluuebunny/crossref_metadata_2025_split huggingface dataset:
An Algorithm for Constrained Optimization with Semismooth Functions
Authors: Mifflin Robert 
Published: October 2008

We present an implementable algorithm for solving constrained optmization problems defined by functions that are not everywhere differenliable. The method is based on combining, modifying and extending the nonsmooth optimization work of Wolfe, Leraarechal, Feuer, Poljak and Merrill. It can be thought of as a generalized reset conjugate gradient algorithm. We also introduce the class of weakly upper semismooth functions. These functions are locally Lipschitz and have a semicontinuous relationship between their generalized gradient sets and their directional derivatives. The algorithm is shown to converge to stationary points of the optimization problem if the objective and constraint functions are weakly upper semismooth. Such points are optimal points if the problem functions are also semiconvex and a constraint qualification is satisfied. Under stronger convexity assumptions, bounds on the deviation from optimally of the algorithm iterates are given.
Nonconvex Duality in Multiobjective Optimization
Authors: Di Guglielmo F 
Published: October 2008

Nonconvex duality properties for multiobjective optimization problems are obtained by using a characterization of Pareto optima by means of generalized Tchebycheff norms. Bounds for the corresponding duality gap are given, and approximate Pareto multipliers are constructed. A generalized notion of Pareto multipliers for quasi-convex multiobjective problems is introduced.
Convergence of Interior Point Algorithms for the Monotone Linear Complementarity Problem
Authors: Bonnans J. Frédéric , Gonzaga Clovis C. 
Published: October 2008

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

Let vn(p) denote the value of the n-times repeated zero-sum game with incomplete information on one side and full monitoring and let u(p) be the value of the average game G(p). The error term ϵn(p) = vn(p) − cav(u)(p) is then converging to zero at least as rapidly as 1/√n. In this paper, we analyze the convergence of ψn(p) = √nϵn(p) in the games with square payoff matrices such that the optimal strategy of the informed player in the average game G(p) is unique, is completely mixed and does not depend on p. Our main result is that the existence of a solution ψ* to a partial differential equation with appropriate boundary conditions and regularity properties implies the uniform convergence of ψn to the Fenchel conjugate of ψ*. In particular cases, the P.D.E. problem is linear and its solution ψ* is then related to the multidimensional normal distribution.
Directional-Quasi-Convexity, Asymmetric Schur-Convexity and Optimality of Consecutive Partitions
Authors: Hwang Frank K. , Rothblum Uriel G. 
Published: October 2008

The current paper has the following distinct goals: 1. To generalize standard quasi-convexity to obtain a weaker property of functions that suffices for optimality of extreme points. Specifically, it is required that intersections of the level sets of the function with line segments having direction in a prescribed set are convex. 2. To characterize Schur-convexity for symmetric functions through the above generalization of quasi-convexity, thereby obtaining a previously unknown relationship of Schur-convexity and (standard) convexity. The new characterization is used to extend the definition of Schur-convexity to functions which are not symmetric. 3. To obtain new sufficient conditions for the optimality of consecutive partitions, by using the new definition of Schur-convexity for functions that are not necessarily symmetric. The conclusion that Schur-convexity is an instance of a convexity property that implies the optimality of extreme points, unifies two approaches that were used in the literature to prove optimality of subsets of the domain of real-valued functions. The two tools—quasi-convexity and Schur-convexity—were previously considered as distinct techniques.
Convergence Analysis of Stochastic Algorithms
Authors: Shapiro A. , Wardi Y. 
Published: October 2008

This paper investigates asymptotic convergence to stationary points of gradient descent algorithms where the functions involved are not available in closed form but are approximated by sequences of random functions. The algorithms take large stepsizes and use progressively finer precision at successive iterations. Two kinds of optimization algorithms are considered: one, where the limiting function (to be minimized) is differentiable but the random approximating functions can be nondifferentiable, and the other, where both the limiting and approximating functions are nondifferentiable and convex. Such functions often arise in discrete event dynamic system-models in various application areas. The analysis brings together ideas and techniques from the disciplines of nonlinear programming and nondifferentiable optimization on one hand, and stochastic processes and especially uniform laws of large numbers, on the other hand. A general algorithmic frame-work is first developed and analyzed, and then applied to the specific algorithms considered. The analysis extends the results derived to date for similar algorithms, and has a potential for further extensions in proving convergence of other algorithms as well.
Constrained Discounted Dynamic Programming
Authors: Feinberg Eugene A. , Shwartz Adam 
Published: October 2008

This paper deals with constrained optimization of Markov Decision Processes with a countable state space, compact action sets, continuous transition probabilities, and upper semicontinuous reward functions. The objective is to maximize the expected total discounted reward for one reward function, under several inequality constraints on similar criteria with other reward functions. Suppose a feasible policy exists for a problem with M constraints. We prove two results on the existence and structure of optimal policies. First, we show that there exists a randomized stationary optimal policy which requires at most M actions more than a nonrandomized stationary one. This result is known for several particular cases. Second, we prove that there exists an optimal policy which is (i) stationary (nonrandomized) from some step onward, (ii) randomized Markov before this step, but the total number of actions which are added by randomization is at most M, (iii) the total number of actions that are added by nonstationarity is at most M. We also establish Pareto optimality of policies from the two classes described above for multi-criteria problems. We describe an algorithm to compute optimal policies with properties (i)–(iii) for constrained problems. The policies that satisfy properties (i)–(iii) have the pleasing aesthetic property that the amount of randomization they require over any trajectory is restricted by the number of constraints. In contrast, a randomized stationary policy may require an infinite number of randomizations over time.
Lower Bounds in Lot-Sizing Models: A Polyhedral Study
Authors: Constantino Miguel 
Published: October 2008

Variable lower bounds in Mixed Integer Programs are constraints with the general form x≥Ly,where xis a continuous variable and y is a binary or an integer variable. This type of constraints is present in some Lot-Sizing models, where x represents the amount of some article produced by a machine and y∈{0,1}indicates whether the machine is set-up for that article(y = 1) or not (y = 0). In these models, production below some level is not allowed, in order to make full use of resources. In this paper we study, from the polyhedral viewpoint, the mixed integer models whose feasible set includes an additive constraint Σxj ≤(≥, =)D, and constraints Lyj ≤ xj ≤ Kyj, where xj are continuous variables, yj are integer or binary variables, and K is a large constant. We derive families of strong valid inequalities and show they are sufficient to describe completely the convex hulls of the sets of feasible solutions. Moreover, we develop polynomial algorithms to solve the separation problem associated to each of the families obtained. Finally, we incorporate the inequalities obtained in a cutting plane algorithm, and test their ability to solve some multi-item lot-sizing problems.
On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
Authors: Pataki Gábor 
Published: October 2008

We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function. We provide upper bounds on the rank of extreme matrices in SDPs, and the first theoretically solid explanation of a phenomenon of intrinsic interest in eigenvalue-optimization. In the spectrum of an optimal matrix, the kth and (k + 1)st largest eigenvalues tend to be equal and frequently have multiplicity greater than two. This clustering is intuitively plausible and has been observed as early as 1975. When the matrix-valued function is affine, we prove that clustering must occur at extreme points of the set of optimal solutions, if the number of variables is sufficiently large. We also give a lower bound on the multiplicity of the critical eigenvalue. These results generalize to the case of a general matrix-valued function under appropriate conditions.
On Computing the Nucleolus of a Balanced Connected Game
Authors: Solymosi Tamás , Aarts Harry , Driessen Theo 
Published: October 2008

The question of “fairly” allocating costs or cost-savings among the participants of a joint enterprise is frequently answered by finding the nucleolus of a related cooperative game. In connection with various routing, sequencing and scheduling situations, connected games often arise. Their common feature is that all the essential coalitions (whose breaking up into subcoalitions is disadvantageous for its members) are connected with respect to a fixed order of the players (any player between two members of a coalition is also a member of the coalition). In the literature, several special classes of connected games are discussed that are shown to be balanced. In this paper, an algorithm is presented that computes the nucleolus of a general n-person balanced connected game. The input is the array of the explicitly given values of the n(n + 1)/2 connected coalitions. The algorithm generates a sequence of at most n(n − 1)/2 payoff vectors starting from a special vertex of the nonempty core and ending in the nucleolus. By exploiting the special structure of connected games, the initial as well as the subsequent payoff vectors are obtained by evaluating some simple recursive formulas. It is shown that the algorithm requires at most O(n4) time and O(n2) space. A 5-person illustrative example is also given.
Erratum: The Travelling Salesman and the PQ-Tree
Authors: Burkard Rainer E. , Deĭneko Vladimir G. , Woeginger Gerhard J. 
Published: October 2008

Let D=(dij) be the n×n distance matrix of a set of n cities {1,2,…,n}, and let T be a PQ-tree with node degree bounded by d that represents a set Π(T) of permutations over {1,2,…,n}. We show how to compute for D in O(2dn3) time the shortest travelling salesman tour contained in Π(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the shortest pyramidal TSP tour. A consequence of our result is that the shortcutting phase of the “twice around the tree” heuristic for the Euclidean TSP can be optimally implemented in polynomial time. This contradicts a statement of Papadimitriou and Vazirani as published in 1984.
Random Sampling in Cut, Flow, and Network Design Problems
Authors: Karger David R. 
Published: October 2008

We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs. We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms. Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms. Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to 1 + O(√(log n)/k).
A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
Authors: Borgwardt Karl Heinz 
Published: October 2008

Consider a set {a 1, …, am , u, v} ⊂ ℝ n satisfying a mild nondegeneracy condition. When the polyhedron X = {x ∣ a 1 T x ≤ 1, …, am T x ≤ 1} ⊂ ℝ n is orthogonally projected on the two-dimensional plane lin(u, v), then some of its vertices may be mapped on vertices of the two-dimensional image of X. These vertices of X will be called shadow vertices under that projection. Their number will be denoted by S. This figure S has an outstanding relevance for the complexity of a special Simplex-Method, the dimension-by-dimension method, for solving LPs of the type maximize  vTx  s.t. a 1 Tx ≤ 1, …, am Tx ≤ 1 where x, v, a 1, …, am ∈ ℝ n and m ≥ n. This method applies the “shadow vertex algorithm” in n − 1 stages of increasing dimension, by constructing a Simplex-Path that visits only shadow vertices. In each stage specific versions of the vectors u and v are used to define the projection plane and to control the application of the “shadow vertex algorithm.” So S delivers an upper bound for the length of such a path in one stage. We want to study the average-case complexity of these algorithms and are therefore interested in Em,n (S), the expected value of S. For that purpose we assume a distribution of the linear programming problems corresponding to the rotation symmetry model (RSM): The vectors a 1, …, am , u, v are distributed on ℝ n \{0} independently, identically and symmetrically under rotations. In this paper we improve the upper bounds for Em,n (S) from our polynomiality-proofs of 1982 and 1987. There we had found an upper bound of m 1/( n −1) · n 3 · Const., valid for all RSM-distributions and all pairs (m ≥ n). Based on a refined evaluation technique for space-angles, on a reorganization and on substantial modifications of the old proof, we are now able to confirm a bound Em,n (S) ≤ m 1/( n −1) · n 2 · Const. for all pairs (m,n) with m ≥ n. This result had been desired since 1982, because then a bound m 1/( n −1) · n 2 · Const. had been derived exclusively for the situation, where n is fixed and m tends to infinity. All the time the question had been open, whether the asymptotical behaviour would be better than the behaviour in moderate dimensions, or whether the bound for the moderate case was crude. In addition, we know—from an asymptotic analysis in 1987—that for a special RSM-distribution, namely the uniform distribution on the unit sphere, there is a lower bound for Em,n (S) of type m 1/( n −1) · n 2 · Const. The combination of this result and the new upper bound shows that the new bound is sharp.
Asymmetric Rendezvous on the Line Is a Double Linear Search Problem
Authors: Alpern Steve , Beck Anatole 
Published: October 2008

We apply a new method of analysis to the asymmetric rendezvous search problem on the line (ARSPL). This problem, previously studied in a paper of Alpern and Gal (1995), asks how two blind, speed one players placed a distance d apart on the line, can find each other in minimum expected time. The distance d is drawn from a known cumulative probability distribution G, and the players are faced in random directions. We show that the ARSPL is strategically equivalent to a new problem we call the double linear search problem (DLSP), where an object is placed equiprobably on one of two lines, and equiprobably at positions ±d. A searcher is placed at the origin of each of these lines. The two searchers move with a combined speed of one, to minimize the expected time before one of them finds the object. Using results from a concurrent paper of the first author and J. V. Howard (1998), we solve the DLSP (and hence the ARSPL) for the case where G is convex on its support, and show that the solution is that conjectured in a paper of Baston and Gal (1998).
Spatial Queueing Processes
Authors: Huang Xiaotao , Serfozo Richard F. 
Published: October 2008

This study introduces a spatial queueing model for stochastic service systems in which customers or units move about and receive services in a region or a general space. The state of the system at any time is a point process that describes the numbers of units in subsets of the space, and the point process evolves over time as a Markov process. The system may be closed or open with a finite or unlimited capacity, and there may be multiple types of customers. The main result is a closed form expression for the stationary distribution of a spatial queueing process. Sufficient conditions are given for the process to be ergodic. Further results include formulas for throughputs, Little laws for average waiting times in sectors of the space, and necessary and sufficient conditions for various flows in open systems to be Poisson processes in time and space. Examples are given of systems with sector-dependent service rates, local-regional service rates, and multiclass customers. A large family of spatial systems are multi-class queueing networks in which the customer classes are nondiscrete marks or quantities (e.g., resources for services, temperature, physical characteristics) that affect services and routings.
The Recurrence Classification of Risk and Storage Processes
Authors: Harrison J. Michael , Resnick Sidney I. 
Published: October 2008

Let X = {X(t), t ≥ 0} be a Markov storage process with compound Poisson input A = {A(t), t ≥ 0} and general release rule r(·). In a previous paper, a necessary and sufficient condition for the positive recurrence of X was obtained, and its stationary distribution was computed. Here we complete the recurrence classification of X, determining the conditions for null recurrence and transience. Closely related to X is a Markov process X0 = {X0(t), t ≥ 0}. Its paths are absolutely continuous and increasing between downward jumps, the instantaneous rate of increase at time t being r(X0(t)). The jumps are generated by A but are truncated as necessary to keep X nonnegative. It is shown that X0 is positive recurrent iff X is transient, null recurrent iff X is null recurrent, and transient iff X is positive recurrent. Furthermore, in the case where X0 is transient, the probability that X0 ever hits zero (viewed as a function of the initial state) has the same density as the stationary distribution of X. A similar duality between the two processes is found in the case where X0 is positive recurrent.
Duality for Multiple Objective Convex Programs
Authors: Brumelle Shelby 
Published: October 2008

A duality theory for the problem of finding the properly efficient values of a multiple objective convex program is obtained using arguments and concepts analogous to those used by Rockafellar for scalar valued problems. A key result is that x̄ minimizes a convex, vector valued function f if and only if there is a “zero-like” subgradient of f at x̄. Consequently, if a vector valued convex program with a given perturbation is represented by a convex bifunction, then the properly efficient values of the program are equal to the perturbation function evaluated at zero-like perturbations. A dual program is defined in terms of the adjoint bifunction. Certain closure conditions insure the absence of a duality gap. The dual variables are matrices with the interpretation that the (i, j)-th element is the value of the ith resource in terms of the jth objective. A concept of optimality called Isermann efficiency is introduced and compared with efficiency and proper efficiency. Isermann efficiency generalizes a concept from Isermann's work on multiple objective linear programs.
Flows in Queueing Networks: A Martingale Approach
Authors: Walrand J. , Varaiya P. 
Published: October 2008

This paper applies the filtering theory for point process observations to the analysis of flows in networks. An abstract model for the study of Markovian queueing systems is developed and used to derive the filtering equations satisfied by the conditional probability distribution of the state given the past of an observed set of flows. These filtering equations are used to obtain a necessary and sufficient condition for that observation to be independent of the value of the state of the system at any time. This approach also yields a probabilistic interpretation of a necessary condition for a given flow in a multi-class Jackson network to be Poisson. These results are combined to give a proof of the “loop criterion” for single-class Jackson network and to show that this criterion does not apply to multi-class networks. Examples of loop-free Jackson networks are given for which some of the flows are not Poisson.
Team Guessing with Lacunary Information
Authors: Witsenhausen H. S. 
Published: October 2008

Let E be an event of probability q and let U1, …, Un be independent random variables. There are n observers, the ith observing the n-1 random variables other than Ui. Each observer must guess whether E occurred. Then if pi is the probability of error of observer i, one has [Formula: see text] where p = max(q, 1 − q), and this bound is sharp. One application is related to a coding theorem. The coding is used to reduce degradation when data transmission is split over n parallel channels, any one of which might have broken down. The result also has a more symmetric corollary which can be stated as a probabilistic inequality of an unusual type.