In this paper, we consider the design of globally asymptotically stabilizing state-dependent switching rules for multimodal systems, first restricting attention to linear time-invariant (LTI) systems with only two states for the switch, and then generalizing the results to multimodal LTI systems and to nonlinear systems. In all cases, the systems considered do not allow the construction of a single quadratic Lyapunov function and, hence, fall in the class of problems that require multiple Lyapunov functions and thus are nonconvex. To address the challenge of nonconvexity, we introduce probabilistic algorithms, and prove their probability-one convergence under a new notion of convergence. Then, to reduce complexity, we develop modified versions of the algorithm. We also present a class of more general nonconvex problems to which this approach can be applied. The results are illustrated using two- and three-dimensional systems with multiple switch states.