An official website of the United States government
Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games.
more »
« less
Experimental evaluation of complete safe coordination of astrobots for Sloan Digital Sky Survey V
Abstract The data throughput of massive spectroscopic surveys in the course of each observation is directly coordinated with the number of optical fibers which reach their target. In this paper, we evaluate the safety and the performance of the astrobots coordination in SDSS-V by conducting various experimental and simulated tests. We illustrate that our strategy provides a complete coordination condition which depends on the operational characteristics of astrobots, their configurations, and their targets. Namely, a coordination method based on the notion of cooperative artificial potential fields is used to generate safe and complete trajectories for astrobots. Optimal target assignment further improves the performance of the used algorithm in terms of faster convergences and less oscillatory movements. Both random targets and galaxy catalog targets are employed to observe the coordination success of the algorithm in various target distributions. The proposed method is capable of handling all potential collisions in the course of coordination. Once the completeness condition is fulfilled according to initial configuration of astrobots and their targets, the algorithm reaches full convergence of astrobots. Should one assign targets to astrobots using efficient strategies, convergence time as well as the number of oscillations decrease in the course of coordination. Rare incomplete scenarios are simply resolved by trivial modifications of astrobots swarms’ parameters.
more »
« less
- Award ID(s):
- 2034429
- PAR ID:
- 10465598
- Date Published:
- Journal Name:
- Experimental Astronomy
- Volume:
- 51
- Issue:
- 1
- ISSN:
- 0922-6435
- Page Range / eLocation ID:
- 77 to 94
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [DP11] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games.more » « less
-
BackgroundInnovative approaches are needed to understand barriers to and facilitators of physical activity among insufficiently active adults. Although social comparison processes (ie, self-evaluations relative to others) are often used to motivate physical activity in digital environments, user preferences and responses to comparison information are poorly understood. ObjectiveWe used an iterative approach to better understand users’ selection of comparison targets, how they interacted with their selected targets, and how they responded to these targets. MethodsAcross 3 studies, different samples of insufficiently active college students used the Fitbit system (Fitbit LLC) to track their steps per day as well as a separate, adaptive web platform each day for 7 to 9 days (N=112). The adaptive platform was designed with different layouts for each study; each allowed participants to select their preferred comparison target from various sets of options, view the desired amount of information about their selected target, and rate their physical activity motivation before and after viewing information about their selected target. Targets were presented as achieving physical activity at various levels below and above their own, which were accessed via the Fitbit system each day. We examined the types of comparison target selections, time spent viewing and number of elements viewed for each type of target, and day-level associations between comparison selections and physical activity outcomes (motivation and behavior). ResultsStudy 1 (n=5) demonstrated that the new web platform could be used as intended and that participants’ interactions with the platform (ie, the type of target selected, the time spent viewing the selected target’s profile, and the number of profile elements viewed) varied across the days. Studies 2 (n=53) and 3 (n=54) replicated these findings; in both studies, age was positively associated with time spent viewing the selected target’s profile and the number of profile elements viewed. Across all studies, upward targets (who had more steps per day than the participant) were selected more often than downward targets (who had fewer steps per day than the participant), although only a subset of either type of target selection was associated with benefits for physical activity motivation or behavior. ConclusionsCapturing physical activity–based social comparison preferences is feasible in an adaptive digital environment, and day-to-day differences in preferences for social comparison targets are associated with day-to-day changes in physical activity motivation and behavior. Findings show that participants only sometimes focus on the comparison opportunities that support their physical activity motivation or behavior, which helps explain previous, equivocal findings regarding the benefits of physical activity–based comparisons. Additional investigation of day-level determinants of comparison selections and responses is needed to fully understand how best to harness comparison processes in digital tools to promote physical activity.more » « less
-
This paper proposes a distributed estimation and control algorithm to allow a team of robots to search for and track an unknown number of targets. The number of targets in the area of interest varies over time as targets enter or leave, and there are many sources of sensing uncertainty, including false positive detections, false negative detections, and measurement noise. The robots use a novel distributed Multiple Hypothesis Tracker (MHT) to estimate both the number of targets and the states of each target. A key contribution is a new data association method that reallocates target tracks across the team. The distributed MHT is compared against another distributed multi-target tracker to test its utility for multi-robot, multi-target tracking.more » « less
-
This work concerns the analysis and design of distributed first-order optimization algorithms over time-varying graphs. The goal of such algorithms is to optimize a global function that is the average of local functions using only local computations and communications. Several different algorithms have been proposed that achieve linear convergence to the global optimum when the local functions are strongly convex. We provide a unified analysis that yields the worst-case linear convergence rate as a function of the condition number of the local functions, the spectral gap of the graph, and the parameters of the algorithm. The framework requires solving a small semidefinite program whose size is fixed; it does not depend on the number of local functions or the dimension of their domain. The result is a computationally efficient method for distributed algorithm analysis that enables the rapid comparison, selection, and tuning of algorithms. Finally, we propose a new algorithm, which we call SVL, that is easily implementable and achieves a faster worst-case convergence rate than all other known algorithms.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s10686-020-09687-4
