Represent the minimum between two terms as a continuous constraint

Question

Let's consider the following minimization problem:

\begin{align} \min_{x,a,b}&\quad X\tag1\\ \text{s.t.}&\quad X = \min(A,B)\tag2\end{align}

with $A,B$ functions that depend on $X$.

Is there a way to represent $(2)$ as a continuous constraint? i.e., I don't want to use binary variables.

I can't do: \begin{align} X \leq A \\ X \leq B \end{align} Because the minimization of $X$ would give me $X = 0$, and \begin{align} X \geq A \\ X \geq B \end{align} would give me the max.

Answer 1

As far as i know you will have to

• resort to a bi-level optimzation problem: $\min_{A,B} x $ subject to ($\max_x$ subject to $x\leq A$ $x \leq B$)
• solve a series of non linear problems where you approximate the $\max$ term by something non-linear (a soft max) and let that converge against $\max$
• be fine with an $\frac{1}{m}$ error and turn it into an Mixed Integer problem $A \leq X + \frac{1}{m}(B_A) + m(1-B_A)$ where $B_A$ is a boolean and $\sum_i B_i \geq 1$
• solve the pareto frontier of minimzing both $A$ and $B$ and pick your winner from the pareto front
• solve a series of feasibility problem without optimization criteria where you say $X=0.033$, $A\leq X$, $B \leq X$ and tweak the X value until you are satisfied, rejecting unfeasible points. Note this approach need special attention if things are non-convex.
• If you know that $A=B$ leaves a feasible (hopefully) convex subspace at the end of which is the minima of your problem $\min A$ subject to $A=B$ solves your problem. If you are not that sure because of bounded discontinuities relax that equality into $A - \varepsilon \leq B \leq A + \varepsilon$ optimize for A and the reverse optimize for B and pick the better one. The choice of $\varepsilon$ must be derived from your problem.

Or most simple:

• Minimize $A$, Minimize $B$ and pick the winner comparing the minimas. Provided that makes sense for your usecase.

Depending on the nature of $A,B$ and other constraints different approaches might be appropriate.