We study several approaches to orbital optimization in selected configuration interaction (SCI) plus perturbation theory methods and test them on the ground and excited states of three molecules using the semistochastic heat-bath configuration interaction method. We discuss the ways in which the orbital optimization problem in SCI resembles and differs from that in complete active space self-consistent field. Starting from natural orbitals, these approaches divide into three classes of optimization methods according to how they treat coupling between configuration interaction coefficients and orbital parameters, namely uncoupled, fully coupled, and quasi-fully coupled methods. We demonstrate that taking the coupling into account is crucial for fast convergence and recommend two quasi-fully coupled methods for such applications: accelerated diagonal Newton and Broyden-Fletcher-Goldfarb-Shanno. © 2021 American Chemical Society.