2
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.