Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Just a calculus problem:

As a function of $K \geq 1$, what is the minimum value of $f/a + f/b + f/c + f/d + f/e$ subject to the following constraints? $$\begin{cases} 1 \leq a \leq c \\ 1 \leq b \leq c \\ 1 \leq d \\ 1 \leq e \\ f = \frac{a^2 b^2 d e}{c} \\ f = K \end{cases}$$

I am fine with a reasonably detailed "here is how you do this calculus" answer, or "here is how to ask wolfram alpha/maple" answer (that works). I need to be able to handle variations (the formula for f is always a "monomial" but the powers on the variables can change, and the inequalities amongst the $a,b,c,d,e$ variables might change slightly, though all of them are always at least 1).


A version I can do: As a function of K ≥ 1, find the minimum value of $f/a + f/b + f/c + f/d + f/e$ subject to the following constraints: $$\begin{cases} 1 \leq a,b,c,d,e \\ f = abcde \\ f = K \end{cases}$$

This version is highly symmetric and I basically understand the region I am optimizing over. Setting any variable to 1 results in a highly non-optimal solution, so the minimum occurs in the middle of the surface where abcde = K, and so the gradient of the objective function is a scalar multiple of the normal to the surface. Both are very symmetric and the algebra involved in solving them is almost silly. The answer is the expected $a=b=c=d=e=K^{1/5}$ due to symmetry.


Motivation: In the background, $a,b,c,d,e,f$ are all positive odd integers describing the structure of an unknown group. In the previous incarnations of this problem, I assumed they were real numbers bounded below by 1, and the calculus minimum was in fact the group theory minimum.

On the new problem, I asked maple to give the unconstrained (except for the "f=" constraints) problem a shot, and it claims there is only one local extrema, and it involves a lot of negative numbers. I guess that means the minimum is at a "corner" (discontinuity of the function defining the boundary of the feasible region), but I have no idea what that means in more than 2 dimensions, and I am a little nervous that such an answer is wrong, at least from the group theory standpoint.

share|improve this question
    
This seems like an highly difficult optimization problem at first glance, but optimization theory has some tools you may want to try out... Have you ever heard of Karush-Kuhn-Tucker conditions? If (I believe you have) ever used Lagrange multipliers, this is a variant of it under which the constraint functions are allowed to be inequalities. There are many constraints in your problem though, it looks heavy to do but since there isn't too many fancy stuff... I believe that's possible. I might give it a try later. –  Patrick Da Silva May 16 '11 at 3:08

1 Answer 1

up vote 0 down vote accepted

Now solved (more or less). In case anyone wants to see it:


Solution as stated: First off, as stated the problem is likely silly. Set a=b=c=d=e=∞, f=1, (so make sure c goes to infinity at the right rate), and the minimum is 0.


Corrections: As I tell my students: it is possible for a real life problem to be unbounded, but usually it just means someone forgot a constraint.

The forgotten constraints are that a,b,c,d,e ≤ f. What a difference this makes!

Also while I'm being honest, the objective function was wrong too! Obj = 2f/a + 2f/b + f/c + f/d + f/e. I forgot some 2s. This will repair some symmetry in the answer.


Solution:

Now we have a compact polytope to start with: Fix f=K. Now 1 ≤ a ≤ c ≤ f, 1 ≤ b ≤ c ≤ f, 1 ≤ d ≤ f, 1 ≤ e ≤ f. Of course we slice a hypersurface out of this: f = aabbde/c.

The resulting set is compact and so the minimum will really be obtained. It could happen in two kinds of places: in the "middle" of the hypersurface, so that the polytope doesn't matter, or on the boundary of the polytope, so that in some weak sense the hypersurface doesn't matter.

Which is it? If it were in the middle of the hypersurface, then Lagrange multipliers would apply:

∇obj = ( -2f/(aa), -2f/(bb), -f/(cc), -f/(dd), -f/(ee) )

∇sur = ( 2abbde/c, 2aabde/c, -aabbde/(cc), aabbe/c, aabbd/c )

The direction of greatest decrease in the objective function should be normal to the hypersurface, and so there is some real number λ such that: λ ∇obj = ∇sur.

We check what this means in the first and third components. On the one hand, -2λf/(aa) = 2abbde/c so that -λf/a = aabbde/c = f, and so a = -λ. On the other hand, -λf/(cc) = -aabbde/(cc) so that -λf/c = -aabbde/c = -f, and c = λ. In particular, one cannot have both a and c are positive!

This contradicts our polytope constraints, and so the minimum occurs on the boundary. Where? Well, this is a little shifty, but I think it is "clear" that the inequality that needs to become an equality is c ≤ f. We want c big, so that a,b,d,e can be big.

Ok, so set c=f and redo the problem:

For fixed f, minimize obj = 2f/a + 2f/b + f/d + f/e + 1 subject to each variable a,b,d,e bounded between 1 and f, and subject to ff = aabbde.

We again have the intersection of a polytope (a hypercube!) with a hypersurface, so we check for middle extrema first:

∇obj = (-2f/(aa), -2f/(bb), -f/(dd), -f/(ee) )

∇sur = ( 2abbde, 2aabde, aabbe, aabbd )

There must be a number λ such that λ∇obj = ∇sur. We examine the components: -2fλ/(aa) = 2abbde, -fλ/a = f, and a = -λ. Similarly b = -λ. Then -fλ/(dd) = aabbe, -fλ/d = aabbde = f, and again d = -λ. Similarly e = -λ.

Hence our solution is:

$$ a=b=d=e = f^{(1/3)}, c=f, \min = 6f^{(2/3)} + 1$$


Caveat: One should be a lot more cautious checking the boundary, but this answer agrees with my preconceived notion and so I am happy for now.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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