Robust and chance-constrained optimization under polynomial uncertainty

A chance-constrained optimization problem, induced from a robust design problem with polynomial dependence on the uncertainties, is, in general, non-convex and difficult to solve. By introducing a novel concept-the kinship function-an easily computable convex relaxation of this problem is proposed. In particular, optimal polynomial kinship functions, which can be computed a priori and once for all, are introduced and used to bound the probability of constraint violation. Moreover, it is proven that the solution of the relaxed problem converges to that of the original robust optimization problem as the degree of the polynomial kinship function increases. Finally, by relying on quadrature formulae for computation of integrals of polynomials, it is shown that the computational complexity of the proposed approach is polynomial on the number of uncertainty parameters.