Minimization Generalization
I've seen a couple of variants of problem where we are to minimize a function which is a sum of square roots. Let's generalize a solution!
Let f ( x , y ) = ( x + a ) 2 + ( y + b ) 2 + ( x − c ) 2 + ( y − d ) 2 for fixed a , b , c and d .
The function f has a global minimum which can be expressed as p ( a , b , c , d ) where p is a polynomial over N . Find the sum of the coefficients of p .
The answer is 8.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Your diagram doesn't match your equations, but otherwise it looks good.
Can you give me some advice on visualising problems like this etc...?
Log in to reply
The way I came up with the visualization was by realizing that:
- ( x + a ) 2 + ( y + b ) 2 and ( x − c ) 2 + ( y − d ) 2 are both the lengths of hypotenuses of right triangles with legs of length x + a & y + b and x − c & y − d respectively, and
- The triangle inequality A B + B C ≥ A C is a good way to minimize the sum of two distances
So I tried to arrange the two right triangles so that the hypotenuses shared an endpoint. Upon reflection, it was easier to cancel my variable if the second right triangle had legs of length c − x & d − y . I tried a couple of orientations of these triangles before I settled on the figure above.
Hope that helps!
Log in to reply
Thank you! But Can you tell it more generally? like how to solve problems like you do?
It's just the sum of two cones, both of slope 1 . So, the minimum is the same as the distance between points ( − a , − b ) and ( c , d ) which works out to
a 2 + 2 a c + c 2 + b 2 + 2 b d + d 2
so that the sum of the coefficients in the radical is 8 .
Liked your geometrical approach to an algebraic problem. That's how we can connect algebra with geometry to prove simple results.
Love math!!
The function f(x,y) is the sum of the distances of a point P(x,y) from two other points A(-a,-b) and B(c,d) on the Cartesian plane. The function f will be having a global minima when P is on the line segment AB.
f(x,y)_min = |PA| + |PB| = |AB| = sqrt{(a+c)^2 + (b+d)^2} = sqrt{p(a,b,c,d)} where p(a,b,c,d) = (a+c)^2 + (b+d)^2 = a^2 + b^2 + c^2 + d^2 + 2 a c + 2 b d. Therefore the sum of coefficients of the polynomial p is 1 + 1 + 1 + 1 + 2 + 2 = 8.
Consider the figure below.
Figure
A
B
=
(
x
+
a
)
2
+
(
y
+
b
)
2
and
B
C
=
(
x
−
c
)
2
+
(
y
−
d
)
2
. The sum
A
B
+
B
C
is minimized when
x
and
y
are such that
A
B
+
B
C
=
A
C
=
(
a
+
c
)
2
+
(
b
+
d
)
2
.
So p ( a , b , c , d ) = a 2 + 2 a c + c 2 + b 2 + 2 b d + d 2 and the sum of the coefficients is 8 .