Special University Oral Exam
July 20, 1999
Convex and Robust Optimization and Applications in Finance
Miguel Sousa Lobo
The field of convex optimization has seen a major transformation is
recent years with the development of efficient interior-point methods
that scale gracefully with problem size. The possibility of
efficiently finding the global solution, even for very large scale
problems that are non-linear and non-differentiable, has opened many
new applications. Special interest has been devoted to conic
programs, including linear programs (LP), second-order cone programs
(SOCP), and semi-definite programs (SDP). In each of these programs,
the constraints are specified by a self-dual cone. Efficient methods
have been implemented for these programs that allow for the solution
of problems with a mix of constraints of each type. In this talk, we
give an overview of convex optimization, with special emphasis on
SOCP, which includes quadratically constrained quadratic programming
(QCQP) as a special case.
The interest in robust optimization arises from the fact that, in
practice, problem parameters are subject to uncertainty (such as due
to measurement or implementation errors, noise, etc.) The
optimization procedure will often ``find'' such errors, leading to
solutions that are very sensitive, or even useless. Dealing
explicitly with the uncertainty can have dramatic advantages. Among
other examples, we give robust versions of LP and of least squares
that result in SOCPs.
After a brief overview of some engineering applications of convex and
robust optimization, we consider applications in finance. We consider
single-period portfolio optimization in the Markowitz mean-variance
and shortfall risk settings, and list a number of convex portfolio
constraints. Transaction costs that are linear in the transaction
amount can also be handled in a convex framework. The inclusion of a
fixed cost per transaction leads to a difficult combinatorial problem,
for which we describe a heuristic based on convex relaxations.
In practice, it is difficult to obtain reliable estimates of the
expected returns and of the covariance matrix, which leads to a robust
optimization problem. We describe convex uncertainty sets for the
covariance matrix. A positivity constraint is included to ensure that
the matrix be a valid covariance matrix. Finding the worst-case
variance of a portfolio is then an SDP. This worst-case risk analysis
can be extended to the design problem, that is, to finding portfolios
that are robustly optimal. Robust portfolio design can be implemented
using cutting-plane methods.