-
作者：Scholtes, S
摘要：This article is mainly concerned with the homeomorphism problem for piecewise affine mappings (PA-maps), i.e., mappings which coincide with an affine mapping on each polyhedron of some finite polyhedral subdivision of R(n). In the first part, we prove that a PA-map can be defined without referring to a subdivision of R(n) as a continuous mapping which coincides at every point x is an element of R(n) with al least one function from a finite collection of affine functions. The second part studie...
-
作者：Guler, O
摘要：We show that the universal barrier function of a convex cone introduced by Nesterov and Nemirovskii is the logarithm of the characteristic function of the cone. This interpretation demonstrates the invariance of the universal barrier under the automorphism group of the underlying cone. This provides a simple method for calculating the universal barrier for homogeneous cones. We identify some known barriers as the universal barrier scaled by an appropriate constant. We also calculate some new u...
-
作者：Pang, JS; Ralph, D
作者单位：University of Melbourne
摘要：This paper is concerned with properties of the Euclidean projection map onto a convex set defined by finitely many smooth, convex inequalities and affine equalities. Under a constant rank constraint qualification, we show that the projection map is piecewise smooth (PC1) hence B(ouligand)-differentiable, or directionally differentiable; and a relatively simple formula is given for the B-derivative. These properties of the projection map are used to obtain inverse and implicit function theorems...
-
作者：Flesch, J; Thuijsman, F; Vrieze, OJ
摘要：We show the existence of stationary limiting average epsilon-equilibria (epsilon > 0) for two-person recursive repeated games with absorbing states. These are stochastic games where all states but one are absorbing, and in the nonabsorbing state ail payoffs are equal to zero. A state is called absorbing if the probability of a transition to any other state is zero for all available pairs of actions. For the purpose of our proof, we introduce properness for stationary strategy pairs. Our result...
-
作者：Bertsimas, D; Nino-Mora, J
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We show that if performance measures in stochastic and dynamic scheduling problems satisfy generalized conservation laws, then the feasible region of achievable performance is a polyhedron called an extended polymatroid, that generalizes the classical polymatroids introduced by Edmonds. Optimization of a linear objective over an extended polymatroid is solved by an adaptive greedy algorithm, which leads to an optimal solution having an indexability property (indexable systems). Under a certain...
-
作者：Goldfarb, D; Jin, ZY
摘要：This paper presents a modified version of Algorithm MCF proposed by Goldberg, Plotkin and Tardos for the generalized circulation problem. This new combinatorial algorithm has a worst-case complexity that is better than the complexities of the MCF and Fat-Path combinatorial algorithms of Goldberg, Plotkin, and Tardos (1991).
-
作者：Leizarowitz, A
摘要：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-now, or to the individual sample paths, yielding almost-sure optimality results. We use the existence of a solution pair (Phi(.), lambda) to the optimality equation L Phi(x) = lambda to establish and characterize optimal strategies. For finite state-spaces we derive sufficient, as well as necessary conditions for ov...
-
作者：FLAM, SD
摘要：The problem considered here is to find common fixed points of (possibly infinitely) many firmly nonexpansive selfmappings in a Hilbert space. For this purpose we use averaged relaxations of the original mappings, the averages being Bochner integrals with respect to chosen measures. Judicious choices of such measures serve to enhance the convergence towards common fixed points. Since projection operators onto closed convex sets are firmly nonexpansive, the methods explored are applicable for so...
-
作者：TAMIR, A
摘要：We prove that a bounded generalized polymatroid has a least weakly submajorized (supermajorized) vector. Such a vector simultaneously minimizes every nondecreasing (nonincreasing), symmetric and quasi-convex function defined on the generalized polymatroid. The same result herds also for the set of integer vectors of a bounded integral generalized polymatroid. We then extend these results to more general sets, and discuss several computational aspects.
-
作者：IUSEM, AN; TEBOULLE, M
作者单位：Tel Aviv University
摘要：The phi-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 phi-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 phi-divergences for which superlinear convergence is attained both for optimization problems with strongly convex objectives at the...
