change of variables

\begin{equation} \phi :\mathbb{R}^{n} \to \mathbb{R}^{n} \end{equation}

is a one-to-one mapping with \(\phi \qty(\text{dom } \phi) \subseteq \mathcal{D}\). We can have a possibly non-convex problem:

\begin{align} &\min f_{0}\qty(x) \\ &s.t.\ f_{i}\qty(x) \leq 0\\ &h_{i}\qty(x) = 0 \end{align}

We can change variable \(x =\phi\qty(z)\).

\begin{align} &\min \tilde f_{0}\qty(z)\\ &s.t.\ \tilde f_{i}\qty(z) \leq 0,\quad i = 1,\dots,m\\ &\tilde h_{i}\qty(z) = 0,\quad i = 1,\dots,p \end{align}

where \(\tilde f_{i}\qty(z) = f_{i}\qty(\phi\qty(z))\) and \(\tilde h_{i}\qty(z) = h_{i}\qty(\phi\qty(z))\).

converting maximization to minimization

• transform using \(-f\qty(x)\), which makes maximizing concave \(f\qty(x)\) to minimizing convex
• transform using \(\frac{1}{f\qty(x)}\) makes maximizing concave positive \(f\qty(x)\) to minimizing convex

objective / constraint transformation

for:

• monotone increasing \(\phi_{0}\)
• \(\phi_{i}\qty(u) \leq 0\) iff \(u \leq 0\)
• \(\psi_{i}\qty(u) = 0\) iff \(u = 0\)

then optimization is identical to

\begin{align} \min_{x}\quad & \phi_{0}\qty(f_{0}\qty(x)) \\ \textrm{s.t.} \quad & \phi_{i}\qty(f_{i}\qty(x)) \leq 0\\ &\psi_{i}\qty(h_{i}\qty(x)) = 0 \end{align}

eliminating equality constraints

for some constraint \(Ax = b\), write

\begin{align} &\min_{z} f_{0}\qty(Fz + x_0)\\ &s.t.\ f_{i}\qty(Fz + x_0) \leq 0 \end{align}

such that \(Ax = b \Leftrightarrow x = Fz + x_0\) for some \(z\).

introducing equality constraints

\begin{align} &\min f_{0}\qty(A_0 x + b_0)\\ &s.t.\ f_{i}\qty(A_{i}x + b_{i}) \leq 0 \end{align}

is equivalent to

\begin{align} \min_{x,y_i}\quad & f_{0}\qty(y_0)\\ \textrm{s.t.}\quad & f_{i}\qty(y_i) \leq 0\\ & y_i = A_i x + b_i \end{align}

introducing slack variables

\begin{align} \min \quad & f_{0}\qty(x)\\ \textrm{s.t.}\quad & a_i^{T}x \leq b_i \end{align}

is equivalent to

\begin{align} \min_{x,s}\quad & f_{0}\qty(x)\\ \textrm{s.t.}\quad & a_i^{T}x + s_i = b_i\\ & s_i \geq 0 \end{align}

epigraph form

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

convex relaxation

Start with a non-convex problem, find convex function \(\hat{h} \leq h\qty(x)\) for all \(x \in \text{dom } h\). Find convex set \(\hat{C} \subseteq C\) described by linear inequalities.

example

Convex Relaxation with Boolean LP

\begin{align} \min_{x,z}\quad & c^{T}\qty(x,z) \\ \textrm{s.t.} \quad & F\qty(x,z) \preceq g, \; A\qty(x,z)=b, \; z \in \qty {0,1}^{q} \end{align}

we call \(z \in \mathbb{R}^{q}\) are called ``boolean variables.’’ We can solve it to \(z \in [0,1]^{q}\) instead, and then round.