UC Santa Barbara

This dissertation is divided into three parts. The first part presents three chapters on a class of stochastic dynamical systems designed to solve non-convex optimization problems on smooth manifolds. The first chapter develops the stochastic, hybrid optimization algorithm. In this chapter, we show that the proposed dynamics combine continuous-time flows, characterized by a differential equation, and discrete-time jumps, characterized by a stochastic difference inclusion in order to guarantee convergence with probability one to the set of global minimizers of the cost function. By using the framework of stochastic hybrid inclusions, a detailed stability characterization of the dynamics, as well as a simple extension to address learning problems in games defined on manifolds is provided. In the second chapter, we cast a stochastic, hybrid algorithm for global optimization on the unit sphere using the framework of stochastic hybrid inclusions. The algorithm includes hysteresis switching between two coordinate charts in order to be able to fully explore the sphere by flowing without encountering singularities in the flow vector field. It also combines gradient flow with jumps that aim to escape singular points of the function to minimize, other than those singular points corresponding to global minima. For this case, the algorithm is stochastic because the jumps involve random probing on the sphere. Solutions are not unique because the jumps are governed by a set-valued mapping, i.e., an inclusion. Regarding the coordinate charts employed, we discuss both the use of spherical coordinates as well as stereographic projection. By using the framework of stochastic hybrid inclusions, we establish uniform global asymptotic stability in probability for the set of global minimizers for arbitrary continuously differentiable (C1) functions defined on the sphere. Lastly in the third chapter, we develop a stochastic, hybrid optimization algorithm for globally minimizing an arbitrary (C1) function on the unit sphere intersected with an arbitrary half-space in R3. Hysteresis switching between coordinate charts is used to enable the algorithm to fully explore the sphere by flowing. During flows, the optimization algorithm uses (projected) gradient descent when near the boundary of the half-space. It may use an update rule inspired by accelerated gradient methods away from the boundary of the half-space. It uses hysteresis switching between the two continuous-time update methods. Periodically, stochastic probing on the sphere is used to attempt to improve the value of the cost function. A stability analysis of the algorithm is provided and the algorithm is demonstrated on a numericalexample. The second part of this dissertation consists of two chapters. The first chapter characterizes the asymptotic behavior that results from switching among asymptotically stable systems with distinct equilibria when the switching frequency satisfies an average dwell-time constraint with a small average rate. The asymptotic characterization is in terms of the Omega-limit set of an associated ideal hybrid system containing an average dwell-time automaton with the rate parameter set equal to zero. This set is globally asymptotically stable for the ideal system. The actual switched system, including small disturbances, constitutes a small perturbation of this ideal system, resulting in semi-global, practical asymptotic stability. In the second chapter, we consider some of convex optimization engineering challenges, such as those involving multiagent systems and resource allocation, where the objective function can persistently switch during the execution of an optimization algorithm. Motivated by such applications, in Chapter 6 we analyze the effect of persistently switching objectives in continuous-time optimization algorithms. In particular, we take advantage of the robust stability results from Chapter 5 for switched systems with distinct equilibria and extend these results to systems described by differential inclusions, making the results applicable to recent optimization algorithms that employ differential inclusions for improving efficiency and/or robustness. Within the framework of hybrid systems theory, we provide an accurate characterization, in terms of Omega-limit sets, of the set to which the optimization dynamics converge. Finally, by considering the switching signal to be constrained in its average dwell time, we establish semi-global practical asymptotic stability of these sets with respect to the dwell-time parameter. In the third part of this dissertation, Input-to-state stability (ISS) is considered for a nonlinear “soft-reset” system with inputs. The latter is a system that approximates a hard-reset system, which is modeled as a hybrid system with inputs. In contrast, a soft-reset system is modeled as a differential inclusion with inputs. Lyapunov conditions on the hard-reset system are given that guarantee ISS for the soft-reset system. In turn, it is shown when global asymptotic stability for the origin of the zero-input reset system guarantees ISS for nonzero inputs. Examples are given to demonstrate the theory.