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.

$\endgroup$
  • $\begingroup$ Aren't the x[i] undistinguished? They are probably all equal ... $\endgroup$ – Dr. belisarius Dec 3 '15 at 20:54
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – Michael E2 Dec 3 '15 at 21:22
  • $\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 '15 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 '15 at 21:56
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}} *)
$\endgroup$
  • $\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 '15 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 '15 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 '15 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 '15 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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