Abstract:

Uncertainty is a very important factor in many mathematical models. One way to incorporate uncertainty into optimization models is using parametric optimization techniques. In addition to uncertainty factor, in most of the practical applications it is necessary to know how sensitive the solution is to data perturbations. Similarly to the classical sensitivity analysis, where only one model parameter is perturbed, in parametric optimization some set of model parameters, which are held constant in the original deterministic problem, are assumed to be uncertain or variable. So, mathematical models in general and optimization problems in particular often involve unknown or uncertain parameters and the goal of parametric optimization is to calculate the optimal solution for all relevant values of these unknown parameters. Discretization approaches are non-rigorous since there is no optimality warranty between the mesh points. With an exception of a few algorithms for parametric linear optimization the available literature assumes that parameters only influence the objective function or the right-hand side of the constraints. Algorithms dealing with the general multi-parametric case are desired as well, but not well studied.

In the recent decade a new class of convex optimization models, that deals with the problem of minimizing a linear function subject to an affine set intersected with a convex cone, has appeared. It is known as conic optimization. Although the conic optimization model seems to be restrictive, any convex optimization problem can be cast as a conic optimization model and there are efficient solution algorithms (e.g., Interior Point Methods) for many classes of conic models such as Conic Linear Optimization. Conic optimization has many interesting applications in engineering, image processing, finance, economics, medicine, etc.

The goal of this research proposal is to outline use of the Interior Point Methods framework to conducting parametric analysis of Conic Linear Optimization problems including quadratic, second-order conic and semidefinite optimization. Development of methodologies and algorithms that allow finding an optimal solution vector and the optimal value function without discretization of the parameter space and without solving the optimization problem at every discretization point would be the primary target. The topics I am planning to cover include developing theoretical background for multi-parametric quadratic optimization; researching on theory for uni-parametric and multi-parametric second order conic optimization problems; investigating possibilities for performing practical parametric analysis for semidefinite optimization; developing efficient algorithms for the problems mentioned above; creating the link from the algorithms to the software packages and incorporating parametric analysis into such packages as SeDuMi and McIPM; looking at the practical optimization problems and their parametric counterparts and establishing the relations between different ways of incorporating uncertainty into the optimization models, such as parametric analysis and robust optimization.