0
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I don't get how this would work. What if $g(x,y) = \sum_{i_\in I} x_i y_i$? $\endgroup$
    – orpanter
    Commented Jun 8, 2023 at 11:06
  • $\begingroup$ 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$. $\endgroup$
    – orpanter
    Commented Jun 8, 2023 at 11:20
  • $\begingroup$ I updated my answer. $\endgroup$ Commented Jun 8, 2023 at 11:52
  • $\begingroup$ 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. $\endgroup$
    – orpanter
    Commented Jun 8, 2023 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.