1
$\begingroup$

Given a positive integer $d$ and some $0 < t < 1$ I would like to find a global minimum1 for $$ \sum_{k = 1}^n d^2 \tan\left(\frac{\pi}{2} \, x_k\right) + 8 d $$ over $n \in \Bbb{Z}_{> 0}$ and $x_1,\dotsc,x_n \in [a,b]$ for some fixed $0 < a < b < 1$, subject to the constraint $$ 1 - \prod_{k = 1}^n (1-x_k) \geq t. $$ At this point I should probably mention that in my studies I had very little experience with numerical optimization, and that I am very new to Mathematica — I learned it while toying with this problem.

This is the code I have so far

a = Rationalize[0.1];
b = Rationalize[0.95];

(* Target function *)
fFactory[n_, d_] := Sum[d^2 * Tan[x[i] * Pi/2] + 8*d, {i, n}];

(* Constraints *)
gFactory[n_] := 1 - Product[(1 - x[i]), {i, n}];
cFactory[n_, t_] := Join[{g >= t}, Table[a <= x[i] <= b, {i, n}]];

vFactory[n_] := Array[x, n];
min[n_, d_, t_] := NMinimize[{fFactory[n, d], cFactory[n, t]}, vFactory[n]];

and it does seem to work. For example min[3, 1, 0.85] results in

{27.0299, {x[1] -> 0.612702, x[2] -> 0.612702, x[3] -> 0.1}}

However this isn't actually a global minimum. For example

gRoot[n_, t_] := 1 - Surd[1 - t, n];
expectedMin[n_, d_, t_] := n*genF[1, d] /. x[1] -> gRoot[n, t];

allows us to compute the value of the target function for

$$ x_1 = \dotsb = x_n = 1 - \sqrt[n]{1-t} $$

and expectedMin[3, 1, 0.85] gives 26.7184. I tried changing the Method option of NMinimize (as detailed in the documentation), but all of "NelderMead", "DifferentialEvolution", "SimulatedAnnealing", and "RandomSearch" gave the same result.

Is there a way to tweak the options of NMinimize, or another function altogether, that would allow me to get a better result?

[1] You can find more background on this problem from the related questions on Mathematics.SE and Arqade.

Note: I would actually like an exact solution, but from the documentation it seems that the algorithms used by Minimize don't work for this problem. Therefore I'd welcome some pointers on how to solve this problem using the Lagrange multipliers or the Karush–Kuhn–Tucker conditions.

Improve this question
$\endgroup$
3
  • $\begingroup$ Aren't the x[i] undistinguished? They are probably all equal ... $\endgroup$
    – Dr. belisarius
    Dec 3, 2015 at 20:54
  • $\begingroup$ Thanks @MichaelE2. Oddly enough, this is the first time I find myself on the receiving end of a comment template on an SE site... ;) $\endgroup$
    – A.P.
    Dec 3, 2015 at 21:44
  • $\begingroup$ @belisariushassettled What do you mean precisely by "undistinguished"? If I understand you correctly yes, the problem is symmetric in the variables. I conjectured that the solution should be $x_1 = \dotsb = x_n = 1 - \sqrt[n]{1-t} =: p_n$ for the maximum $n$ such that $$n \left(d^2 \tan\left(\frac{\pi}{2} \, p_n\right) + 8 d \right) < (n-1) \left(d^2 \tan\left(\frac{\pi}{2} \, p_{n-1}\right) + 8 d \right)$$but I don't know how to prove it. $\endgroup$
    – A.P.
    Dec 3, 2015 at 21:56

1 Answer 1

Reset to default
1
$\begingroup$ 
{a, b} = {1/10, 95/100};
(*Target function*)
v[n_] := Array[x, n]
ff[n_?NumericQ, d_?NumericQ] := Sum[d^2*Tan[i*Pi/2] + 8*d, {i, v@n}]

(*Constraints*)
gf[n_?NumericQ] := (1 - Product[(1 - i), {i, v@n}])
cf[n_?NumericQ, t_?NumericQ] := Join[{gf[n] >= t}, Thread[a <= v@n <= b]];

min[n_, d_, t_] := NMinimize[{ff[n, d], cf[n, t]}, v@n];
min[3, 1, 0.85]

(* {26.7184, {x[1] -> 0.468671, x[2] -> 0.468671, x[3] -> 0.468671}} *)
Improve this answer
$\endgroup$
4
  • $\begingroup$ I feel stupid for not changing the constraints when I refactored my code... most importantly, though, while comparing your code with mine I noticed that re-evaluating a modified cell didn't update the functions I defined in it. Is this standard behaviour? If so, where is it documented? $\endgroup$
    – A.P.
    Dec 3, 2015 at 21:26
  • $\begingroup$ By the way, I understand that you likely did this on purpose — sometimes dull-looking questions on MSE inspire a tiny bit of sadism in me, though I usually don't follow through with it — but you could have mentioned that the only significant thing you changed was the definition of the constraints. On the other hand, you taught me how to impose constraints on a function's arguments, of which I'm grateful. $\endgroup$
    – A.P.
    Dec 3, 2015 at 21:35
  • 1
    $\begingroup$ @A.P. I started with your code, refactored a few things forth and back, and posted it when it worked. I didn't look back to see what I finally changed. I wasn't "hiding" it :) $\endgroup$
    – Dr. belisarius
    Dec 3, 2015 at 22:52
  • 1
    $\begingroup$ @A.P. Re: "I noticed that re-evaluating a modified cell didn't update the functions I defined in it. Is this standard behaviour?" ... The answer is yes, unless you use exactly the same pattern for the function arguments. You can query all standing definitions for your function by using DownValues[ function] or Information[function]. Try f[x_] := x^2; f[x_?NumericQ] := x^3; DownValues[f] $\endgroup$
    – Dr. belisarius
    Dec 3, 2015 at 23:14

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.