# Represent the minimum between two terms as a continuous constraint

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.

• Perhaps you can clearly and explicitly write out a complete optimization problem specification. In particular, show is explicitly what A and B are. Nov 15 '21 at 20:04
• This is non-convex, so this can not be reformulated as a single LP. Nov 15 '21 at 21:32

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.