0

Suppose that we have a general mathematical program $(P)$ with value \begin{align} \nu(P) := \min_{x,y}\; \{f(x,y) : g(x,y) \leq 0\}. \end{align} Is there a standard way to define functions $\tilde{f}$ and $\tilde{g}$ so that we can write the problem in terms of $x$ only? That is, can we always find $\tilde{f},\tilde{g}$ so that \begin{align} \nu(P) = \min_{x}\; \{\tilde{f}(x) : \tilde{g}(x) \leq 0\} \end{align} For example, when $g(x,y)=g(x)$, then \begin{align} \nu(P) = \min_{x}\; \{\tilde{f}(x) : g(x) \leq 0\}, \quad \tilde{f}(x) = \min_y f(x,y) \end{align} works. My question is what happens when $y$ is involved in the constraint?

jjjjjj
  • 2,671
  • 1
    why do you think this is generally possible? In what context do you need this result? – gt6989b Jul 27 '22 at 20:03
  • I'm not sure that we can do this generally. I ask because in the LP setting, this amounts to projecting the problem onto $x$. I wonder if there is something similar in general. – jjjjjj Jul 27 '22 at 20:15
  • In my case, I need this when $g$ is nonsmooth and nonconvex (e.g., something like $g(x,y) = \min(x,y) = 0$ that can be represented as an integer program) but $f$ is linear. – jjjjjj Jul 27 '22 at 20:18
  • Is there a specific problem you are looking to do? Perhaps a reformulation of some IP? – gt6989b Jul 27 '22 at 20:38
  • It is a network flow problem except for one additional constraint that is like $\min(x,y) = 0$. I take it that what I'm asking is only possible under very specific settings? – jjjjjj Jul 27 '22 at 20:44
  • 2
    Let $\tilde{f}(x) = \min_y f(x,y)$, $\tilde{g}(x) = \max_y g(x,y)$. This doesn't really help, however. – copper.hat Jul 27 '22 at 22:26

0 Answers0