2
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks very much for the in-depth answer and all the pointers! Adding NumericQ did the trick. Yeah, my posted sample problem might not make sense, but I could apply everything to my more complex problem. $\endgroup$
    – Wurzel
    Jun 29, 2022 at 20:26
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This gets it running, thanks. It didn't return the optimal solution for my more complex problem(but it might with some tweaking), so I will keep this approach in mind if I run into problems with MarcoB's approach. $\endgroup$
    – Wurzel
    Jun 29, 2022 at 17:05
  • $\begingroup$ @Wurzel: What was asked that was answered. You wrote " It didn't return the optimal solution for my more complex problem". Ask it as a new question. Good luck and deep regard! $\endgroup$
    – user64494
    Jun 30, 2022 at 10:54

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.