# Continuous Min-Max problem

Being new to Mathematica, I tried my best to find some built-in functions or guides on how to solve the classical min-max problem

$$\min_{x} \max_{k} f(x,k,params)$$

with some additional variables $$params$$ and some simple constraints on the variables (e.g., $$x\in [x_{min},x_{max}]$$ and $$k\in [k_{min},k_{max}]$$) in the Mathematica language. Finding none (giving a link would be much appreciated), my approach was to first define function computing $$\max_{k} f(x,k)$$ e.g.,

fMax[x_,params_] :=
FindMaximum[{f[x,k,params_], k > kmin, k < kmax}, {k, kinit}];


with a parameter $$x$$ and then minimize fmax, e.g.,

fMinMax[x_,params_] :=
FindMinimum[{fMax[x_,params_], x > xmin, x < xmax}, {x, xinit}];


However, the following error is consistently raised.

FindMaximum::nrnum: The function value -((9.27923*10^11-2.95367*10^10 p)/(5.15531*10^17+1.64099*10^16 p)) is not a real number at {k} = {10.}.


although upon evaluating the function at that given point, the value is indeed real. I would be glad for any help. To give the full setting $$f$$ amounts to

$$f(x,k,a,b,\alpha) = \frac{\frac{k\pi}{b} \cosh \left(\frac{k\pi}{b} (a-\alpha)\right) + x \sinh \left(\frac{k\pi}{b} (a-\alpha)\right)}{\frac{k\pi}{b} \cosh \left(\frac{k\pi}{b} (a+\alpha)\right) + x \sinh \left(\frac{k\pi}{b} (a+\alpha)\right)}$$

where $$a,b,\alpha$$ are positive parrameters such that $$a>\alpha>0,b>0$$.

• Maybe Minimize[MaxValue[f[x, k], x], k] ? This can solve some simple problems. – wuyudi Sep 24 '20 at 10:08
• Thanks for the comment. I will check it out but I was honestly hoping for a fix of the above or even better explanation why it doesn't work. I feel like I must have missed some basic syntax or somthing like that. I feel like the error message is telling me that for the inner function the call took place without specifying the inner parameter - and that's why Mathematica thinks it's not a number - but don't know if that si indeed the case and if so then how to fix it. – michalOut Sep 24 '20 at 11:25
• Are these ResourceFunction's useful to you? ResourceFunction["GeneralMiniMaxApproximation"] and ResourceFunction["MiniMaxApproximation"] – flinty Sep 24 '20 at 13:27

## 2 Answers

There are a number of problems with your code. First of all: you have patterns (_) on the r.h.s. of the assignments. Second: for these sort of problems, it's best to restrict your function values to numerical inputs (by matching with _?NumericQ) wherever you can. Here's a quick example with parameters I randomly picked to get you going:

f[x_, k_, {a_, b_, α_}] := (k π/b Cosh[k π/b (a - α)] + x Sinh[k π /b (a - α)])/
(k π/b Cosh[k π/b (a + α)] + x Sinh[k π/b (a + α)])
kmin = 0;
kmax = 10;
xmin = -10;
xmax = 10;
fMax[x_?NumericQ, params_] := With[{
max = FindMaximum[
{f[x, k, params], k > kmin, k < kmax},
{k, Mean[{kmin, kmax}]}
]
},
ksol = k /. max[[2]]; (* store the found value of k *)
max[[1]]
];

fMinMax[params_] := FindMinimum[
{fMax[x, params], x > xmin, x < xmax},
{x, Mean[{xmin, xmax}]}
];


Test that fMax returns numerical values:

fMax[1, {1/10, 1, 1/10}]
ksol


0.833333

0.00134382

Do the full min-max problem:

fMinMax[{1/10, 1, 1/10}]
ksol


{0.333333, {x -> 10.}}

0.00277709

# Update

Some documentation about pattern constraints:

http://reference.wolfram.com/language/tutorial/Patterns.html

https://reference.wolfram.com/language/ref/NumericQ.html

Documentation about With:

http://reference.wolfram.com/language/tutorial/ModularityAndTheNamingOfThings.html

https://reference.wolfram.com/language/ref/With.html

What are the use cases for different scoping constructs?

• Thank you for your answer. The 'first of all' is a clear mistake on my part while writing the question here. I will try to find out more about the syntax you used - I am not familiar with _?NumericQ and the With statement in the definition. (In case you know of an easy resource to learn those, it would eb appreciated but if it is a common thing, it should be OK either way). As soon as I get this thing going in ym set-up, I'll mark the answer as correct :). – michalOut Sep 25 '20 at 10:43
• @michalOut Sure, see the "Update" section ;) – Sjoerd Smit Sep 25 '20 at 11:05
• I am very sorry that it took me several days to get back to this as you have responded so quickly in the first place. Nonetheless I think that I am getting the jist of it, thank oyu very much :). However, to be sure - when you define the local variable for fMax I guess you meant to use FindMaximum rather than FindMinimum as we wanna solve a min-max not a min-min problem. – michalOut Oct 6 '20 at 7:47
• @michalOut Oops, good point. I think I had that at some point, but I was tinkering around with the code so much that I messed that up somewhere. I updated the answer. – Sjoerd Smit Oct 6 '20 at 8:07
• @michalOut I think that's the way to do it, yes, but it only works for linear programming problems (which your problem isn't). You can't do gradient-based methods on integers, so I don't know how you'd do this with k constrained to integers. It's a completely different -and much more difficult- problem, tbh. For example, the following doesn't work: FindMaximum[{-(x - Pi)^2, x \[Element] Integers}, {x, 1}] – Sjoerd Smit Oct 6 '20 at 9:36

You can get an analytical min max expression for x>=0.

With graphical means, i derived, that the max w.r.t. k is always at k==0.

Edit Proof, that f reaches maximum at k==0.

Since Sinh and Cosh are greater zero for their argument greater zero, the numerator of f is always smaller than the denominator, exept for k==0 both are equal, means the maximum is at k==0.

f[x_, k_, a_, b_, \[Alpha]_] =
(k \[Pi]/b Cosh[k \[Pi]/b (a - \[Alpha])] +
x Sinh[k \[Pi]/b (a - \[Alpha])])/(\[Pi] k/b Cosh[
k \[Pi]/b (a + \[Alpha])] + x Sinh[k \[Pi]/b (a + \[Alpha])])

Reduce[{TrigExpand[(k \[Pi] Cosh[(k \[Pi] (a - \[Alpha]))/b])/b < (
k \[Pi] Cosh[(k \[Pi] (a + \[Alpha]))/b])/b], 0 <= k, 0 < x,
0 < \[Alpha], 0 < a, 0 < b}] //
Simplify[#, {0 <= k, 0 < x, 0 < \[Alpha], 0 < a, 0 < b}] &

(*   k > 0   *)


The same for x Sinh[.....]

Reduce[{TrigExpand[(k \[Pi] Cosh[(k \[Pi] (a - \[Alpha]))/b])/b == (
k \[Pi] Cosh[(k \[Pi] (a + \[Alpha]))/b])/b], 0 <= k, 0 < x,
0 < \[Alpha], 0 < a, 0 < b}] //
Simplify[#, {0 <= k, 0 < x, 0 < \[Alpha], 0 < a, 0 < b}] &

(*   k == 0    Again the same for Sinh   *)

lim[x_, a_, b_, \[Alpha]_] =
Limit[f[x, k, a, b, \[Alpha]], k -> 0, Direction -> -1]

(*   (1 + a x - x \[Alpha])/(1 + a x + x \[Alpha])   *)

Manipulate[
Plot3D[{0, f[x, k, a, b, \[Alpha]] - lim[x, a, b, \[Alpha]]}, {x, 0,
10}, {k, 0, 10}, AxesLabel -> {x, k, f}, PlotRange -> All,
PlotStyle -> {Red, Blue}], {{a, 1}, 0, 60,
Appearance -> "Labeled"}, {{\[Alpha], 1/2}, 0, a,
Appearance -> "Labeled"}, {{b, 1}, 0, 50,
Appearance -> "Labeled"}]


For x<0 you get singularities where the maximum over k is infinity.

The minimum over x>0 of the maximized values over k is then

min = Minimize[{lim[x, a, b, \[Alpha]], {0 <= x < 10,
0 < \[Alpha] < a, 0 < b}}, x]

(*   (1 + 10 a - 10 \[Alpha])/(1 + 10 a + 10 \[Alpha])   .....   *)


Get graphical confirmation of this result (minimum of the red curve).

Manipulate[{Plot[{lim[x, a, b, \[Alpha]], f[x, 1/2, a, b, \[Alpha]],
f[x, 3, a, b, \[Alpha]], f[x, 10, a, b, \[Alpha]]}, {x, 0, 10},
AxesLabel -> {x, lim}, PlotRange -> All,
PlotStyle -> {Red, Green, Blue, Magenta}], (
1 + 10 a - 10 \[Alpha])/(1 + 10 a + 10 \[Alpha]) // N}, {{a, 30},
0, 60, Appearance -> "Labeled"}, {{\[Alpha], 1}, 0, a,
Appearance -> "Labeled"}, {{b, 30}, 0, 150,
Appearance -> "Labeled"}]