Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximations of countably-infinite linear programs over bounded measure spaces
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study a class of countably-infinite-dimensional linear programs (CILPs) whose feasible sets are bounded subsets of appropriately defined spaces of measures. The optimal value, optimal points, and minimal points of these CILPs can be approximated by solving finite-dimensional linear programs. We show how to construct finite-dimensional programs that lead to approximations with easy-to-evaluate error bounds, and we prove that the errors converge to zero as the size of the finite-dimensional programs approaches that of the original problem. We discuss the use of our methods in the computation of the stationary distributions, occupation measures, and exit distributions of Markov~chains.
rate research
Read More
In this paper we study, by probabilistic techniques, the convergence of the value function for a two-scale, infinite-dimensional, stochastic controlled system as the ratio between the two evolution speeds diverges. The value function is represented as the solution of a backward stochastic differential equation (BSDE) that it is shown to converge towards a reduced BSDE. The noise is assumed to be additive both in the slow and the fast equations for the state. Some non degeneracy condition on the slow equation are required. The limit BSDE involves the solution of an ergodic BSDE and is itself interpreted as the value function of an auxiliary stochastic control problem on a reduced state space.
Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, when the ambiguity set constitutes a 2-Wasserstein ball centered at a discrete distribution, then the distributionally robust linear program is equivalent to a copositive program (if the problem has complete recourse) or can be approximated arbitrarily closely by a sequence of copositive programs (if the problem has sufficiently expensive recourse). These results directly extend to the classical robust setting and motivate strong tractable approximations of two-stage problems based on semidefinite approximations of the copositive cone. We also demonstrate that the two-stage distributionally robust optimization problem is equivalent to a tractable linear program when the ambiguity set constitutes a 1-Wasserstein ball centered at a discrete distribution and there are no support constraints.
Multidimensional scaling (MDS) is a popular technique for mapping a finite metric space into a low-dimensional Euclidean space in a way that best preserves pairwise distances. We study a notion of MDS on infinite metric measure spaces, along with its optimality properties and goodness of fit. This allows us to study the MDS embeddings of the geodesic circle $S^1$ into $mathbb{R}^m$ for all $m$, and to ask questions about the MDS embeddings of the geodesic $n$-spheres $S^n$ into $mathbb{R}^m$. Furthermore, we address questions on convergence of MDS. For instance, if a sequence of metric measure spaces converges to a fixed metric measure space $X$, then in what sense do the MDS embeddings of these spaces converge to the MDS embedding of $X$? Convergence is understood when each metric space in the sequence has the same finite number of points, or when each metric space has a finite number of points tending to infinity. We are also interested in notions of convergence when each metric space in the sequence has an arbitrary (possibly infinite) number of points.
For each integer $n$ we present an explicit formulation of a compact linear program, with $O(n^3)$ variables and constraints, which determines the satisfiability of any 2SAT formula with $n$ boolean variables by a single linear optimization. This contrasts with the fact that the natural polytope for this problem, formed from the convex hull of all satisfiable formulas and their satisfying assignments, has superpolynomial extension complexity. Our formulation is based on multicommodity flows. We also discuss connections of these results to the stable matching problem.
In this article, we propose a Krasnoselskiv{i}-Mann-type algorithm for finding a common fixed point of a countably infinite family of nonexpansive operators $(T_n)_{n geq 0}$ in Hilbert spaces. We formulate an asymptotic property which the family $(T_n)_{n geq 0}$ has to fulfill such that the sequence generated by the algorithm converges strongly to the element in $bigcap_{n geq 0} operatorname{Fix} T_n$ with minimum norm. Based on this, we derive a forward-backward algorithm that allows variable step sizes and generates a sequence of iterates that converge strongly to the zero with minimum norm of the sum of a maximally monotone operator and a cocoercive one. We demonstrate the superiority of the forward-backward algorithm with variable step sizes over the one with constant step size by means of numerical experiments on variational image reconstruction and split feasibility problems in infinite dimensional Hilbert spaces.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
