introducing new variables

Consider the original problem:

\begin{align} \min_{x}\quad & \norm{Ax - b} \end{align}

Now, we can reformulate and write \(y = Ax - b\). Now, remember the conjugate of the norm is:

\begin{equation} \norm{z} = \begin{cases} 0, \norm{z} \leq 1\\ \infty \end{cases} \end{equation}

And remember the dual is some massaging of the conjugate. And thus we can formulate a “norm conjugate”:

\begin{align} \max_{v}\quad & b^{T}v \\ \textrm{s.t.} \quad & A^{T}v = 0 \\ & \norm{v} \leq 1 \end{align}

Lagrange Dual Problem

Given the Lagrange Dual Function, we can formulate the Lagrange Dual Problem:

\begin{align} \max_{\lambda, v}\quad & g\qty(\lambda,v) \\ \textrm{s.t.} \quad & \lambda \succeq 0 \end{align}

• finds the best lower bound on \(p^{*}\), obtained from Lagrange dual function
• a convex optimization problem, even if original primal fiction is not
• dual optimal value denoted \(d^{*}\)

\(\lambda, v\) as “dual feasible” if \(\lambda \succeq 0, \qty(\lambda, v) \in \text{dom } g\).

Example Dual Problems

LPs

\begin{align} \min_{x}\quad & c^{T}x \\ \textrm{s.t.} \quad & Ax = b \\ & x \succeq x \end{align}

Consider feasible problems.

\begin{align} \min_{x}\quad & 0 \\ \textrm{s.t.} \quad & \dots \end{align}

so the optimal is either \(p^{*} = 0\) or \(p^{*} = +\infty\). And thus the Lagrange Dual Problem boils down to checking if \(d^{*} \geq 0\), if so, then the original problem is’nt feasible (since dual gives a lower bound.)

\begin{equation} Ax \leq 0, c^{T}x < 0 \end{equation}

and

\begin{equation} A^{T}y + c = 0, y \geq 0 \end{equation}

are strong alteratives. This is through duality.

investment arbitrage

1. invest \(x_{j}\) in each of \(n\) assets \(1 … n\) with prices \(p_1 … p_{n}\)
2. suppose \(V_{ij}\) is the payoff of asset \(j\) and outcome \(i\)
3. risk-free (cash): \(p_{1} = 1\), \(V_{i1} = 1\) for all \(i\) as our first investment

Arbitrage means there exists some \(x\) with \(p^{T}x < 0, V x \succeq 0\) (first thing is you borrow money?, and then second thing is you get more money back).

1st order condition

differentiable \(f\) with convex domain is convex IFF:

\begin{equation} f\qty(y) \geq f\qty(x) + \nabla f\qty(x)^{T} \qty(y-x), \forall x,y \in \text{dom } f \end{equation}

“the function is everywhere above the Taylor approximation” => “first-order Taylor approximation of \(f\) is a global underestimator of \(f\).”

2nd order condition

for twice differentiable \(f\) with convex domain, we have:

• \(f\) is convex IFF \(\nabla^{2} f\qty(x) \succeq 0, \forall x \in \text{dom } f\) (i.e. that the Hessian is PSD)
• if \(\nabla^{2} f\qty(x) \succ 0 \forall x \in \text{dom } f\), then we call \(f\) strictly convex (i.e. that the Hessian is PD)

you may enjoy using Cauchy-Schwartz Inequality to show these.