\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.

Let \(\mathcal{G} = \qty {f_{1}\qty(x), f_{0}\qty(x) \mid x \in \mathcal{D}}\) be the set of achievable constraint/objective pairs. The Lagrange Dual Function \(g\qty(\lambda) = \text{inf}_{t,u \in G} \qty(t + \lambda u)\).

We will push this line all the way down, and then push up its slope as much as possible.

a quasiconvex function \(f: \mathbb{R}^{n} \to \mathbb{R}\) is quasiconvex if \(\text{dom } f\) is a convex set and the sublevel sets:

\begin{equation} S_{\alpha} = \qty {x \in \text{dom } f \mid f\qty(x) \leq \alpha } \end{equation}

are convex for all \(\alpha\). These functions are also called unimodal functions.

properties of quasiconvex functions

modified Jensen’s Inequality

\begin{equation} 0 \leq \theta \leq 1 \implies f\qty(\theta x + \qty(1-\theta)y) \leq\max\qty{f\qty(y), f\qty(x)} \end{equation}

l

first-order condition

differential \(f\) with convex domain is quasiconvex IFF

\begin{align} \min_{x}\quad & f_{0}\qty(x) \\ \textrm{s.t.} \quad & f_{i}\qty(x) \leq 0, i = 1 \dots m\\ &Ax = b \end{align}

Where \(f_{0}\) is quasiconvex, and \(f_{i\geq 1}\) is convex.

solution methods

convex representation of sublevel sets

if \(f_{0}\) is quasiconvex, then there exists a family of functions \(\phi_{t}\) for which:

\begin{equation} f_{0} \leq t \iff \phi_{t}\qty(x) \leq 0 \end{equation}

where \(\phi_{t}\) is convex for fixed \(t\).

bisection method for quasiconvex optimization

We can cast all quasiconvex problems into a binary search over \(t\). Solve the following convex feasibility problem: