# Min-convex function as constraint

I have a constraint that is as follows:

$$Ax - f(x) \leq 0$$

where $$f(x)=min_y(g(x,y))$$. Which is convex. I can even get the gradient in $$x$$. How can I reformulate my constraint? or what approach should/could I follow to solve a problem like this?

If $$y$$ was binary (and that is added to the minimization function $$f(x)$$. Could I still solve this? Do you have any tips or reading that I could do about this?

Note that $$x$$ and $$y$$ are vectors of variables.

In case $$y$$ belongs to a finite domain (e.g., if binary), you can split your difficult constraint into multiple simpler (one for each element of the domain) using: $$Ax \leq \min_y g(x,y) \quad\Longleftrightarrow\quad Ax \leq g(x,y) \;\; \forall y.$$

In case $$y$$ belongs to an infinite domain (e.g., continuous) you can reformulate if you are able to derive a strong dual problem, satisfying $$\min_y g(x,y) = \max_\lambda h(x,\lambda)$$, in which case you end up with a single constraint $$Ax \leq \min_y g(x,y) = \max_\lambda h(x,\lambda) \quad\Longleftrightarrow\quad Ax \leq h(x,\lambda).$$

EDIT: One way to derive a strong dual is by first reformulating to some well-known standard form. As example, if $$\min_y g(x,y)$$ could be reformulated as a linear optimization problem with $$đť‘Ą$$ as the cost coefficient, then $$\begin{array}{rcl} \min_y g(x,y) &=& \min\{ x^T y \;:\; By = b,\; y \geq 0 \},\\ &=& \max\{ b^T \lambda \;:\; B^T\lambda \leq x \}, \end{array}$$

holds by linear duality theory, and tells you that it is possible rewrite $$Ax \leq \min_y g(x,y) \quad\Longleftrightarrow\quad Ax \leq b^T \lambda,\;\; B^T\lambda \leq x.$$

For nonlinear functions I recommend going through the conic standard form which has well-studied duality properties. If there exists a conic reformulation, there also exists a conic reformulation that satisfies strong duality to make the trick above work. The MOSEK cookbook is a good source on how to formulate conic optimization problems.

• I don't get how this would work. What if $g(x,y) = \sum_{i_\in I} x_i y_i$? Commented Jun 8, 2023 at 11:06
• Okey, maybe that was a bad example of $g(x,y)$. Maybe more complex something like $g(x,y) = \sum_{i} a_{i} y^1_{i} + \sum_{j} b_j y^j_1 + \sum_{i,j} x^j_i y_i^j$, where $a_i$ and $b_i$ are positive or negative parameters. What I mean, is that if the function is more complex, I could simply do that for each $y$ because it depends on more than one $y$. Commented Jun 8, 2023 at 11:20
• I updated my answer. Commented Jun 8, 2023 at 11:52
• Amazing answer! Thank you! I am learning to work in problems that don't have integer variables. Incredible how it is so different yet so close. Commented Jun 8, 2023 at 15:54