Robust Optimization
and Applications


Optimization models


Robust Optimization Paradigm

Approximating a robust solution


LP as a conic problem

Second-order cone programming

Semidefinite programming

Dual form of conic program

Robust conic programming

Polytopic uncertainty

Robust LP

Robust LP with ellipsoidal uncertainty

Robust LP as SOCP

Example: robust portfolio design

Solution of robust portfolio problem

Robust SOCP

Example: robust least-squares

Robust SDP

Example: robust control

Analysis of robust conic problems


Quality estimates

Quality estimates: some results



Variations on Robust Conic Programming

A Boolean problem

Max-quad as a robust LP

Rank relaxation

Boolean optimization: geometric approach

SDP for boolean / nonconvex optimization

Robust boolean optimization

SDP relaxation of robust problem

Chance-constrained programming

Problems with adjustable parameters

Adjustable parameters: some results

Link with feedback control


Set estimation

Part I: summary

Slide 44

Part II: Contextual Applications

Robust path planning

Uncertainty in Markov Decision Process


Markov decision problem

Previous Work

Robust dynamic programming

Inner problem

Worst-case performance of a policy

Describing uncertainty

Joint estimation and optimization

Estimating a transition matrix

Likelihood regions

likelihood regions

Reduction to a 1-D problem

Complexity results

Application to aircraft routing

Markov chain model for the storms

information update  and recourse

Dynamic programming model

Nominal algorithm

Sample path planning

Improvements over obvious strategies


Optimality vs. uncertainty level

Errors in uncertainty level


Summary of results

Some references

Robust Classification

Linear Classification

What is a classifier?

Classification constraints

robust classification:
support vector machine

box uncertainty model



minimax probability machine

Problem statement

SOCP formulation

Dual problem

Geometric interpretation

Robust classification:
summary of results