problem transformation — Jemoka Knowledge Base

change of variables \begin{equation} \phi :\mathbb{R}^{n} \to \mathbb{R}^{n} \end{equation} is a one-to-one mapping with \phi \left(\text{dom } \phi\right) \subseteq \mathcal{D}. We can have a possibly non-convex problem:

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

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

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

where \tilde f_{i}\left(z\right) = f_{i}\left(\phi\left(z\right)\right) and \tilde h_{i}\left(z\right) = h_{i}\left(\phi\left(z\right)\right). converting maximization to minimization transform using -f\left(x\right), which makes maximizing concave f\left(x\right) to minimizing convex transform using \frac{1}{f\left(x\right)} makes maximizing concave positive f\left(x\right) to minimizing convex objective / constraint transformation for: monotone increasing \phi_{0} \phi_{i}\left(u\right) \leq 0 iff u \leq 0 \psi_{i}\left(u\right) = 0 iff u = 0 then optimization is identical to

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

eliminating equality constraints for some constraint Ax = b, write

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

such that Ax = b \Leftrightarrow x = Fz + x_0 for some z. introducing equality constraints \begin{align} &\min f_{0}\left(A_0 x + b_0\right)\ &s.t.\ f_{i}\left(A_{i}x + b_{i}\right) \leq 0 \end{align} is equivalent to

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

introducing slack variables \begin{align} \min \quad & f_{0}\left(x\right)\ \textrm{s.t.}\quad & a_i^{T}x \leq b_i \end{align} is equivalent to

\begin{align} \min_{x,s}\quad & f_{0}\left(x\right)\\ \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\left(x\right) - t \leq 0 \ & f_{i}\left(x\right) \leq 0 \ & Ax = b \end{align} convex relaxation Start with a non-convex problem, find convex function \hat{h} \leq h\left(x\right) 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}\left(x,z\right) \ \textrm{s.t.} \quad & F\left(x,z\right) \preceq g, ; A\left(x,z\right)=b, ; z \in \left{0,1\right}^{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.