Suggest edit — Quadratic Program

Title

Name

Note

---
title: "Quadratic Program"
type: concept
related: [Linear Constraint Optimization, Quadratic Program]
source: https://www.jemoka.com/posts/kbhquadratic_program/
confidence: high
status: active
---

This is a Linear Program but quadratic now.
\begin{align} \min_{x}\ &amp;\qty(\frac{1}{2}) x^{T} P x + q^{T} x + r \\ s.t.\ &amp;Gx \preceq h \\ &amp; 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\).
Thus the risk-average decision problem is:
\begin{align} &amp;\min \mathbb{E}c^{T}x + \gamma \text{var}\qty(c^{T}x) \\ &amp;s.t.\ G x \preceq h, Ax = b \end{align}
where \(\gamma &gt; 0\) is risk-aversion: trading off expected cost \(\mathbb{E} c^{T}x\) and variance \(\text{var}\qty(c^{T}x)\). So, writing in terms of a QP:
minimize ¯cT x + yxT Σx subject to Gx  h, Ax = b