Regime shifts refer to sudden changes in the structure and function of a system due to forces from external disturbances. Such shifts occur because the system has alternative stable states and external disturbances force the system's operating point to shift from one stable state to another. Examples of regime shifts include the collapse of coastal fisheries as a result of human-induced nutrient enrichment and the voltage collapse in power network due to variations in storm frequency or user demand. Due to such undesired consequences, there is a great challenge in finding methods to forecast their occurrence. The work presented in this thesis addresses this challenge using techniques from polynomial optimization. We first identify two mechanisms by which regime shifts may occur and then formulate some real-valued quantities that can be used as indicators of how close a system is to each type of regime shifts. The first regime shift mechanism will be referred to as bifurcation-induced regime shifts and it occurs because variation in the system's parameters exceeds a critical threshold and forces the system's equilibria to undergo a bifurcation. We use a quantity known as the minimum distance to bifurcation as a measure of how close a system is to this type of regime shift and then formulate polynomial optimization problems that can be used to compute the global minimum of this quantity. We show that by using techniques from algebraic geometry and polynomial optimization, the computation of this quantity in a class of nonnegative systems with kinetic realizations can be simplified. The second regime shift mechanism will be referred to as noise-induced regime shifts and it occurs because the underlying system has multiple stable equilibria and external stochastic disturbances drive the system's state from the region of attraction (ROA) of one stable equilibrium to the ROA of an alternative stable equilibrium. We use probabilistic quantities called mean first passage times and safety probability to characterize the expected time and the likelihood for this type of regime shifts to occur. We also formulate polynomial optimization problems that can be used to compute upper bounds for these quantities.