Modelling Robust Design Problems via Conic Optimization

Modelling Robust Design Problems via Conic Optimization

Chaerani, D.

Roos, C. (promotor)

Electrical Engineering, Mathematics and Computer Science

2006-11-07

This thesis deals with optimization problems with uncertain data. Uncertainty here means that the data is not known exactly at the time when its solution has to be determined. In many models the uncertainty is ignored and a representative nominal value of the data is used. The uncertainty may be due to measurement or modelling errors or simply to the unavailability of the information at the time of the decision. We use conic optimization (CO) models to find robust optimal solution of some uncertain design problems. We demonstrate this for the robust shortest path problem (RSPP), the robust maximum flow problem (RMFP) and the robust resistance network topology design (RNTD) problem. Robust optimal design of these problems are obtained by using the robust counterpart (RC) methodology of Ben-Tal and Nemirovskii. In the RSPP and RMFP, the uncertainty occurs only in the objective vector. We consider two types of uncertainty sets, namely boxes and ellipsoidal sets. The robust counterpart of RSPP with ellipsoidal uncertainty is a conic quadratic problem (CQP) with binary variables. Therefore it is not a computationally tractable problem since we need a branch and bound scheme to solve the problem. It needs further investigation. On the other hand, for both uncertainty types of sets, the RMFP is a usual maximum flow problem with modified arc capacities, and hence the RMFP can be solved in polynomial time. As far as we know this result is new. We present also a parametric variant for the RSPP and RMFP with ellipsoidal uncertainty set. In the RNTD problem, the robust model is obtained by using a simple variational principle which enables us to obtain the semidefinite representation of the dissipation. This implies that the multi-current case and a robust version of RNTD problem can be represented as a semidefinite problem. Using this semidefinite model, the robustness of a resistance network can be significantly improved.

robust optimization
conic optimization
boxes and ellipsoidal uncertainty sets

http://resolver.tudelft.nl/uuid:5bb2bb3c-c545-4d7f-9502-186ac0f5956e

90-8559-232-1

Institutional Repository

doctoral thesis

(c) 2006 D. Chaerani