---
title: "problem transformation"
type: concept
source: https://www.jemoka.com/posts/kbhproblem_transformation/
confidence: high
status: active
---

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} &amp;\min f_{0}\qty(x) \\ &amp;s.t.\ f_{i}\qty(x) \leq 0\\ &amp;h_{i}\qty(x) = 0 \end{align}
We can change variable \(x =\phi\qty(z)\).
\begin{align} &amp;\min \tilde f_{0}\qty(z)\\ &amp;s.t.\ \tilde f_{i}\qty(z) \leq 0,\quad i = 1,\dots,m\\ &amp;\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 &amp; \phi_{0}\qty(f_{0}\qty(x)) \\ \textrm{s.t.} \quad &amp; \phi_{i}\qty(f_{i}\qty(x)) \leq 0\\ &amp;\psi_{i}\qty(h_{i}\qty(x)) = 0 \end{align}
eliminating equality constraints for some constraint \(Ax = b\), write
\begin{align} &amp;\min_{z} f_{0}\qty(Fz + x_0)\\ &amp;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} &amp;\min f_{0}\qty(A_0 x + b_0)\\ &amp;s.t.\ f_{i}\qty(A_{i}x + b_{i}) \leq 0 \end{align}
is equivalent to
\begin{align} \min_{x,y_i}\quad &amp; f_{0}\qty(y_0)\\ \textrm{s.t.}\quad &amp; f_{i}\qty(y_i) \leq 0\\ &amp; y_i = A_i x + b_i \end{align}
introducing slack variables \begin{align} \min \quad &amp; f_{0}\qty(x)\\ \textrm{s.t.}\quad &amp; a_i^{T}x \leq b_i \end{align}
is equivalent to
\begin{align} \min_{x,s}\quad &amp; f_{0}\qty(x)\\ \textrm{s.t.}\quad &amp; a_i^{T}x + s_i = b_i\\ &amp; s_i \geq 0 \end{align}
epigraph form \begin{align} \min_{x,t} \quad &amp; t \\ \textrm{s.t.} \quad &amp; f_0\qty(x) - t \leq 0 \\ &amp; f_{i}\qty(x) \leq 0 \\ &amp; 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 &amp; c^{T}\qty(x,z) \\ \textrm{s.t.} \quad &amp; 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.&rsquo;&rsquo; We can solve it to \(z \in [0,1]^{q}\) instead, and then round.
