Optimization problem with parameter dependent interval of functions

Question

I am working on an optimization problem but ran into a problem.

Here is a simplified version of the problem:

foo1a[t_] := {Cos[t], Sin[t]}
foo1b[t_] := {Cos[t], -Sin[t]}
foo1[a_] := 
 NMaxValue[{t + EuclideanDistance[foo1a[t], foo1b[t]] - a, 
   a <= t <= 2 a}, t]

foo2a[t_] := {-Cos[t], Sin[t]}
foo2b[t_] := {-Cos[t], -Sin[t]}
foo2[a_] := 
 NMaxValue[{t + EuclideanDistance[foo2a[t], foo2b[t]]*(0.5 + a), 
   a <= t <= 2 a}, t]

NMinimize[Max[foo1[a], foo2[a]], a]

So I want to minimize the max value of several functions, which return the max value of a function over a given interval. The problem is that the interval depends on the parameters but mathematica wants me to have fixed parameters (Returns error: NMaxValue: The following constraints are not valid: {a<=t,t<=2 a}. Constraints should be equalities, inequalities, or domain specifications involving the variables.).

Is there any way to solve this or could another approach circumvent this problem?

Answer 1

You are trying to solve a minimax problem, i.e. finding the value of your parameter $a$ that minimizes a function defined as the maximum of other functions. Take a look at a tutorial on these problems and at previous questions on this site, among which Minimax optimization in Mathematica provides multiple approaches.

First, you should restrict evaluation of the NMaxValue functions so they only evaluate after $a$ is given a numerical value. To achieve that, use NumericQ in the definition of the corresponding functions (see this FAQ):

ClearAll[foo1a, foo1b, foo1]
foo1a[t_] := {Cos[t], Sin[t]}
foo1b[t_] := {Cos[t], -Sin[t]}
foo1[a_?NumericQ] := 
  NMaxValue[{t + EuclideanDistance[foo1a[t], foo1b[t]] - a, a <= t <= 2 a}, t]

ClearAll[foo2a, foo2b, foo2]
foo2a[t_] := {-Cos[t], Sin[t]}
foo2b[t_] := {-Cos[t], -Sin[t]}
foo2[a_?NumericQ] := 
  NMaxValue[{t + EuclideanDistance[foo2a[t], foo2b[t]]*(0.5 + a), a <= t <= 2 a}, t]

Even after this, however, you get warnings when trying to run NMinimize with the modified definitions:

NMaxValue::nsol There are no points that satisfy the constraints {False}.

This is a problem with your constraints in the NMaxValue calls. In fact, the constraint $a\leq t\leq 2a$ is automatically false for any value of $t$ when $a$ is negative. This implies to me that your formulation implicitly assumes that $a$ is non-negative (or you have to rethink your constraints). That's fine, but we should make the minimizer aware of that constraint!

Including that constraint, and switching to the undocumented internal minimax solver for speed:

Optimization`FindMinimax[{{Max[foo1[a], foo2[a]]}, {a >= 0}}, {a}]

(* Out: {1.21818*10^-7, {a -> 8.18183*10^-9}} *)

This essentially says that the minimum value is $0$, and it is attained for $a=0$.

Answer 2

In version 13 on Windows 10

NMinimize[{Max[Evaluate[foo1[a]], Evaluate[foo2[a]]], a >= 0}, a, Method -> "DifferentialEvolution"]

{1.14277*10^-8, {a -> 2.28555*10^-9}}

in few minutes.