[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhproblem_transformation.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "problem transformation" source: https://www.jemoka.com/posts/kbhproblem_transformation/ --- 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.