This is a Linear Program but quadratic now.

\begin{align} \min_{x}\ &\qty(\frac{1}{2}) x^{T} P x + q^{T} x + r \\ s.t.\ &Gx \preceq h \\ & Ax = b \end{align}

We want \(P \in S_{+}^{n}\), so PSD. So its convex quadratic.

Examples

Least Squares

Obviously least-squares is a basic Quadratic Program

\begin{equation} \norm{A x - b}^{2}_{2} \end{equation}

Linear Program with Random Cost

Consider a linear program with stochastic cost \(c\) with mean \(\bar{c}\) and covariance \(\Sigma\). Hence, a Linear Program objective \(c^{T}x\) is a random variable with mean \(\bar{c}^{T}x\) and variance \(x^{T} \Sigma x\).

Two approaches to handling uncertainty. Consider an LP:

\begin{align} &\min c^{T}x \\ &s.t. a_{i}^{x} \leq b_{i} \end{align}

what if our constraints are uncertain. Both of these reduce to an SOCP. See slides.

Deterministic Worst-Case

\begin{align} &\min c^{T}x \\ &s.t.\ a_{i}^{T} x \leq b_{i}, \forall a_{i} \in \epsilon_{i} \end{align}

Stochastic

\begin{align} &\min c^{T}x \\ &s.t.\ \text{prob}\qty(a_{i}^{T} x \leq b_{i}) \geq \eta, i = 1 \dots m \end{align}

\begin{align} &\min c^{T}x \\ &s.t.\ x_1 F_1 + x_2 F_2 + \dots + x_{n} F_{n} + G \preceq 0 \\ & Ax = b \end{align}

Key Sequence

Notation

New Concepts

• Disciplined Convex Programming
• more ways of checking convexity
  • perspective
  • conjugate function
• quasiconvex function
• optimization (math)
  • convex problems
  • feasible
  • optimal value and locally optimal
• special convex problems
  • Linear Program

Important Results / Claims

• Cash Flow Return Tracking
• properties of quasiconvex functions

Questions

Interesting Factoids

Fun example

Key Sequence

Notation

New Concepts

• Types of convex problems
  • Linear Program
  • Quadratic Program
  • Quadratically constrained quadratic program
  • Second-order cone programming
  • Robust Optimization
  • Semidefinite Program
  • Convex Problem Hiearchy
• problem transformation

Important Results / Claims

Questions

Interesting Factoids