Minimization Problem?

Question

Minimization Problem?

Answer 1

This is Problem # 80 from the book "Geometric Inequalities and Minimum/Maximum Problems" by I. M. Yaglom. The solution involves the following steps (I use standard notatons, ABC's perimeter counterclockwise, inner angles α = β ≥ γ, required point - X). Follow the link below to see how it is looking like:

http://farm4.static.flickr.com/3252/2523368249_12449c816a_o.gif



1) Note that the minimum of D(X) = |AX| + |BX| - |CX| exists, since D is a continuous function of the point X in the ABC's plane, and D_min ≤ 0.

Indeed for X ≡ A (or X ≡ B) D ≤ 0 and if X is outside a large enough circle, encompassing the triangle ABC,

then D(X) > 0.



2) The required point is inside the angle γ, but cannot be inner point for ABC (it's either on the contour or outside - compare with jaz_will's answer above!). Indeed:

2a) Let X is inside ABC and X' is the intersecting point of CX and AB, then

|AX'| + |BX'| - |CX'| < |AX| + |BX| - |CX|

2b) Let X is inside the angle, opposite to γ and X' is symmetric to X with respect to the line, parallel to the base AB through C, then easily

|AX'| + |BX'| - |CX'| < |AX| + |BX| - |CX|

2c) Let X is inside the angle α(or, similarly β) and X' is symmetric to X with respect to AB, then again easily

|AX'| + |BX'| - |CX'| < |AX| + |BX| - |CX|

2d) Let X is inside the angle, opposite to α (or β),

taking X' ≡ A (or X' ≡ B) we have

AX' + BX' - CX' < AX + BX - CX



3) Let X is a point inside angle(CAB). Rotate the triangle ACX clockwise about A by 60° to position AC'X', then

|AX| + |BX| - |CX| = |X'X| + |BX| - |C'X'|,

but since the length of the broken line C'BXX' is at least the distance of its endpoints

|X'X| + |XB| + |BC'| ≥ |C'X'| then we'll have

|X'X| + |XB| - |C'X'| ≥ -|BC'|

The equality here is attained if C', B, X, X' are collinear and we'll have the required point then.



4) Let |AB| < |AC| = |BC|, i.e. γ < 60°, then B and C' do not coincide and since

angle(CBC') = angle(CC'B) = 150° - α

angle(C'BA) = 150° and the collinearity implies

angle(BAX) = angle(ABX) = 30°, angle(AXB) = 120°

/the same point is in the very good jaz_will's answer above/



5) If |AB| = |AC| = |BC| then B ≡ C', or |AX| + |BX| = |CX|,

hence angle(AXB) = 120° and there are infinitely many solutions - all points on the arc AB (not containing C) of the circumcircle.



6) If |AB| > |AC| = |BC| the above 3)-5) is invalid, then both vertexes A and B are optimal solutions.



P.S.(EDIT - after having read the additional details) Aha, now I see, knowing the answer (the problem is in both books) You are examining the Yahoo!Answers Community! No objections, I have nothing against, but promise to answer Your questions more carefully from now on.

Answer 2

I think smci pretty much got the answer correct, except one small detail. By the symmetry argument, f(x,+y) > f(x,-y), so the "minimum" should lie int he lower half plane, not the upper half.



Defining f(x,y) just like smci



f(x,y) = sqrt( (x-1)^2+y^2) + sqrt( (x+1)^2 + y^2) ) - sqrt( x^2 + (y-k)^2)



we calculate the partial derivatives:



f_x = (x-1)/sqrt( (x-1)^2+y^2) + (x+1)/sqrt( (x+1)^2 + y^2) ) - x/sqrt( x^2 + (y-k)^2)



Easy to check that x = 0 is a critical point. (this is obvious also by symmetry). By taking y < 0, (y-k)^2 = y^2 + 2|y|k + k^2 > y^2, then a simple comparison shows that



f_x > 0 for all x =/= 0 and y < 0.



assume now x = 0.



f_y = 2y / sqrt(1+y^2) - (y-k)/ |y-k| = 0



which implies



2y / sqrt(1+y^2) = +/- 1



3y^2 = 1



y = +/- sqrt(1/3)



Now, since we assume y < 0, |y-k| = k-y, the minus sign is consistent.



(Note that since k > sqrt(3), both solutions +/- sqrt(1/3) are < k, so the only one consistent with the original expression



2y/sqrt(1+y^2) = -1



is y < 0, NOT y > 0 and inside the triangle. In fact, it is easy to argue that for any point inside the triangle, moving south (away from the point C and toward the segment AB), we necessary reduce MA and MB while increase MC, thereby reducing MA+MB- MC.



Edit: Ooh... shiny! I like Duke's answer. Seeing a purely geometric proof is so much more enlightening than just seeing the brute-force via calculus.



Edit2: To Quadrillator, you are absolutely right. I forgot the condition that AB < BC. This is illustrated very well in Duke's answer. In fact, one should also check the points A,B,C just to make sure they are not minima: the function f(x,y) defined above is only C^0 and not C^1, so we can have extremum values occurring at kinks. In fact, in the case where AB = AC = BC, the function f(x,y) at the point I constructed is exactly 0, and f(A) = 0 and f(B) = 0: all three points minimizes the distance. And for AB > BC, the minimizers are just the points A and B: the point I constructed is merely a saddle point.

Answer 3

Interesting.



I always translate these things to Cartesian coords, even if they have clever geometric solutions which are hard to spot.

[Sidenote: if we wanted to minimize MA + MB - MC, it would be the Steiner centre]

There may also be symmetry about the y-axis here.

I'm guessing the answer is the asymptote (0,+y) as y→∞



So by translation, rotation and scaling, let the coords ABC be

A (-1,0) B (1,0) C (0,k) for some k>0



>with AC = BC ≥ AB

=> √(1²+k²) > 2

=> 1+k² > 4

=> k² > 3

=> k > √3



For which point M(x,y) in the plane of the triangle will MA + MB - MC be a minimum?



Well MA + MB - MC is some fn of (x,y), call it f(x,y)

Remember A (-1,0) B (1,0) C (0,k)

MA = √((x+1)² + y²)

MB = √((x-1)² + y²)

MC = √(x² + (y-k)²)



f(x,y) = √((x+1)² + y²) + √((x-1)² + y²) - √(x² + (y-k)²)



I think we start by remarking that we always have f(x,+y) > f(x,-y) due to C being in the upper half-plane. Hence M must be in the upper half-plane.



Next, prove that the optimal M* must lie inside the triangle.

=> 0


Next, to justify why the optimal M* must lie on the y-axis,

consider f for some arbitrary M(x,y) and consider M'(0,y) i.e. when M is projected onto the y-axis.

We want to prove that in all cases, f(0,y)> f(x,y).

Consider that y is fixed and x is our variable

Now: f(x,y) = √((x+1)² + y²) + √((x-1)² + y²) - √(x² + (y-k)²)

and

f(0,y) = √(1 + y²) + √(1 + y²) - √((y-k)²)

Now can we prove this difference is always positive:

d(x,y) = f(0,y) - f(x,y)

= √(1 + y²) + √(1 + y²) - √((y-k)²) - √((x+1)² + y²) - √((x-1)² + y²) + √(x² + (y-k)²)

= [√(1 + y²) - √((x+1)² + y²)] + [√(1 + y²) - √((x-1)² + y²)]

+ [√((y-k)²) - √(x² + (y-k)²)]

I think you can use Triangle Inequality to prove that.



If we can justify all this, it reduces to minimizing:

f(0,y) = 2√(1 + y²) - √((y-k)²)

When 0
f(0,y) = 2√(1 + y²) + (k-y)



∂f/∂y = 2y/√(1 + y²) -1

∂f/∂y = 0 => 2y/√(1 + y²) = 1

2y = √(1 + y²)

4y² = 1 + y²

3y² = 1

y = 1/√3



Thus the solution is M*(0, 1/√3)

and the minimal value of f

is f*(0, 1/√3) = 2√(4/3) + (k-1/√3)

= 4/√3 + (k -1/√3)

= k + √3

[curious that M* is not influenced by k]



The general derivative would be:

(∂f/∂x, ∂f/∂y) =

( 2(x+1)/ √((x+1)² + y²) + 2(x-1)/√((x-1)² + y²) - 2x/√(x² + (y-k)²),

2y/ √((x+1)² + y²) + 2y/√((x-1)² + y²) - 2(y-k)/√(x² + (y-k)²) )



f(x,y) is minimized when del f(x,y) = (0,0)

For the y-component, solve:

2y/ √((x+1)² + y²) + 2y/√((x-1)² + y²) = 2(y-k)/√(x² + (y-k)²)



and so on.

Answer 4

From the bludgeon a problem to death school of thought comes...



So far, noone seems to be making use of the part that says BC ≥ AB... (well, they hadn't when I started writing this up).



Let BC = a = AC be the legs of the isosceles triangle, AB = c is the base. Furthermore, I draw this with C *below* AB and the origin at the midpoint of AB.



MA + MB = k defines an ellipse (where k ≥ c). So we are interested to know, for a fixed k, where the minimum of k - MC is. That is, what is the maximal circle (centered at C) that can be drawn to intersect with the ellipse MA + MB = k? Let's let the radius of this circle be r. Clearly, whereever M is to achieve minimality, the tangent to the circle and to the ellipse at that point coincide. It should also be clear that for a fixed k, as r grows, there will be a few points of mutual tangency (between the ellipse and the circle) and since we're interested in the one for the largest r, that puts the point above the x-axis (this was the reason for choosing C below the x-axis).



Thus, we'd like to minimize k - r subject to:

(1): x²/k² + y²/(k-c)² = 1/4 (The equation of the ellipse)

(2): (y + √(a²-(c/2)²))² + x² = r²

For ease of reading, set h = the altitude of ABC so that h² = a² - (c/2)² so that

(2a): (y + h)² + x² = r²

(3): -x / (y + h) = -(k²-c²)x / (k²y)



The part on the left side of (3) is the tangent slope of the circle, while the part on the right is the tangent slope of the ellipse. From (3), one possibility is that x=0. But let's also look at what happens if x ≠ 0. Clear the -x, cross multiply, eliminate k²y to arrive at:



x = 0 or y = h(k² - c²) / c² = hk²/c² - h



Let's take x=0 first. In this case, from (2) r = y + h. From (1) we have (4): y² = (k² - c²) / 4 or y = ½√(k² - c²). Recall we want to minimize k - r = k - (y + h) = k - h - ½√(k² - c²). (We could do this without derivatives, but we're already appealing to slopes above so...) take a derivative with respect to k, set it equal to 0, cross multiply and square to arrive at k² = 4(k²-c²) or 3k² = 4c² or k = 2c/√3. From (4) that means the minimum is at M = (x,y) = (0,½c/√3). The minimum at this point is 2c/√3 - ½(c/√3) - h = ½c√3 - h.





Now let's look at the 2nd case y = hk²/c² - h. Plugging into (2) yields x² = r² - (hk²/c²)². Plugging into the equation for the ellipse (1) we get: x²/k² + h²(k²-c²)/c^4 = 1/4 or

(r²/k² - h²k²/c^4) + h²(k²-c²)/c^4 = 1/4 where the middle two terms cancel to r²/k² - h²/c² = 1/4 or

r² = k²(1/4 + h²/c²) = [From the note to (2a)] k²(a²/c²) so

r = ka/c

Since we want to minimize k - r = k(1-a/c) over all k...



Case 2a: a=c => the minimum is 0, where h=½c√3 (so that the minimum from Case 1 is also 0) occurring when x²=r²-(hk²/c²)²=k²(1-¾(k/c)²) as k ranges from c to 2c/√3 and the corresponding y is ½(k²-c²)√3/c



Case 2b: a0, the minimum will happen when k is minimal: k=c. The minimum is c-a, r=a, x²=r²-h²=(c/2)² so x = ±c/2 and y=0. Ie. M=A or M=B. Of course this minimum should be compared against that from Case 1, but it is indeed less:

a
(2-√3)a < (2-√3)c

(2-√3)ac < (¾+1+¼-√3)c²

a²-¼c² < a² + ac(√3-2) + c²(¾+1-√3) = a² + ac(√3-2) + c²(½√3-1)²

h² < (a + c(½√3-1))²

h < a + c(½√3-1) so

c - a < ½c√3 - h



Case 2c: a>c (The original problem). Since (1-a/c)<0 the minimum = k(1-a/c) would seem to be arbitrarily large as k becomes large. However, this k is bounded since x² ≥ 0. We have x² = r² - (hk²/c²)² = (ka/c)² - (hk²/c²)² = (k²/c²)(a² - (hk/c)²) ≥ 0 so a² ≥ (hk/c)² or k <= ac/h. Thus, the minimum is achieved at k=ac/h where the minimum is (the negative) a(c-a)/h. r=a²/h, x=0, and y = h(a²/h²-1) = (a²-h²)/h = ¼c²/h. Again we compare the results against Case 1:

¼(a-c)² ≥ 0

¼a² + ¼c² - ½ac ≥ 0

(a-¼c)² ≥ ¾(a² - ¼c²) (now take square roots)

a ≥ ½h√3 + ¼c

ac ≥ ½hc√3 + ¼c²

a(c-a) ≥ ½hc√3 - (a² - ¼c²)

a(c-a)/h ≥ ½c√3 - h

Minimum of Case 2 >= Minimum of Case 1 so Case 1 wins.



Summary:

Erect isosceles triangle ABD with D on the same side of AB as C is, with legs DA=DB= AB/√3 = c/√3. Circle D will be the circle with center at D and radius equal to the leg DA of ABD. Arc AB will refer to the arc of circle D from A to B that is on the opposite side of AB from D. All of the minimal points M are to be found on Arc AB!!!



Edit:

I like the following definintion of Arc AB better: Erect equilateral triangle ABD so that D and C are on the same side of AB. Arc AB will refer to the arc of the circumcircle of ABD that does not contain D. The radius is AB/√3 = c/√3.





For BC=a < c=AB the minimal points are at A and B with a minimum of c-a.





For a=c, the minimum 0 is achieved for all M on Arc AB. You can see this by plugging k² = c² + 2yc/√3 into the expression for x² = k² (1 - ¾k²/c²) and seeing that a standard form for a circle pops out.





For a > c, the minimum is ½c√3 - h = ½c√3 - √(a² - ¼c²) which is achieved where the perpendicular bisector of AB meets arc AB. This is ½c/√3 away from AB. It is also pt. M of rhombus AOBM, where O is the center of the circle.