Tools and analysis for improving the small-signal stability of a stochastic power system by optimal power dispatch in each short time horizon, such as five-minute intervals, are provided in this paper. An objective function which characterizes the maximal exit probability from the static stability region (−π/2,π/2) across the phase-angle differences of all power lines is formulated. This objective function is proven to be Lipschitz continuous, nondifferentiable, and nonconvex, with a finite minimum defined over the region of power supply vectors. The formulas of the generalized subgradient and directional derivative of the objective function are provided, and based on these formulas, a two-step algorithm is designed to approximate a minimizer accompanied by the convergence proof: (1) using a projected generalized subgradient method to compute an effective initial vector, and (2) applying the steepest descent method to approximate a local minimizer. The algorithms have been verified using a synthesized power network, demonstrating computational validity and effectiveness in minimizing the maximal exit probability of all power lines.