A new flexibility index algorithm for systems under uncertainty and represented by quadratic inequalities is presented. Inspired by the outer-approximation algorithm for convex mixed-integer nonlinear programming, a similar iterative strategy is developed. The subproblem, which is a nonlinear program, is constructed by fixing the vertex directions since this class of systems is proved to have a vertex solution if the entries on the diagonal of the Hessian matrix are non-negative. By overestimating the nonlinear constraints, a linear min-max problem is formulated. By dualizing the inner maximization problem, and introducing new variables and constraints, the master problem is reformulated as a mixed-integer linear program. By iteratively solving the subproblem and master problem, the algorithm can be guaranteed to converge to the flexibility index. Numerical examples including a heat exchanger network, a process network, and a unit commitment problem are presented to illustrate the computational efficiency of the algorithm. (c) 2018 American Institute of Chemical Engineers AIChE J, 64: 2486-2499, 2018