Quadratically perturbed chance constrained programming : theory and application in transceiver design

Abstract

More and more optimization based decision-makings are taking parameter uncertainty into account, and chance constrained programming (CCP) is an important framework for decision-making under uncertainty. In particular, the quadratically perturbed CCP is an important subclass of general CCP problems, and finds widespread applications from wireless communication, machine learning to control problems.

Despite its importance, previous solutions for quadratically perturbed CCP problem are safe approximation based, and mainly focus on some special classes of uncertainty, e.g., Gaussian and Uniform distributed uncertainty. For CCP with non-Gaussian uncertainty, the optimization is generally intractable owing to the complicated probability density function (PDF). Using a simple fitted distribution with an additional Kullback-Leibler (KL) divergence constraint is a systematic way to tackle CCP with non-Gaussian uncertainty. However, the essential difficulty of using this methodology is choosing the fitted PDF, which should be close to the true PDF while providing a tractable safe approximation to the resulting CCP problem.

In the first part of this thesis, we derive a novel safe approximation by proposing the flexible t-distribution to be the fitted PDF. More specifically, after the CCP with non-Gaussian uncertainty is transformed into the CCP with a fitted PDF, the property of the regularized outage probability is analysed. Then, the unimodal distributional property of the quadratic form under t-distributed perturbation is established. Based on the unimodal property and the regularized outage analysis, the analytical condition to make the safe approximation with fitted t-distribution having larger feasible set than the safe approximation with fitted Gaussian is obtained.

On the other hand, although safe approximation is a leading approach in solving CCP problems, and the fitted t-distribution based safe approximation is general enough to handle non-Gaussian uncertainty, a common drawback of this class of method is that they do not provide optimality guarantee for the solutions. In order to improve safe approximation solutions, in the second part of this thesis, a new optimization methodology is proposed to solve the CCP problem under continuous uncertainty distribution. The generally intractable chance constraints and unknown convexity are overcome by novel analyses of local structure of the feasible set. Then a convergent set squeezing procedure is established with local optimal or tight solution guaranteed under mild conditions. Efficient algorithms are also derived for the set squeezing procedure under the widely used quadratically perturbed constraints.

Finally, we illustrate the performance of the two proposed methods for quadratically perturbed CCP with the mean square error (MSE) constrained transceiver design problem in wireless communications. In particular, with Logistic and Gaussian mixture channel uncertainties as examples, simulation results validate the less conservative property of the transceiver design with fitted t-distribution based safe approximation, compared to that with fitted Gaussian and the classic moment method. Furthermore, with safe approximation solutions as initializations, simulation results under Gaussian, uniform, and Gaussian mixture channel uncertainties show that tight solutions for probabilistic MSE constrained transceiver designs are obtained by the proposed set squeezing procedure. The tight control of the outage probability using the proposed approach enables a flexible balance between the MSE outage probability and transmit power, compared to various safe approximation methods.