Convex Program

lpd

Sep 2009
100
1
I'm having trouble with this question:

Show that the midpoint bteween any two feasible points in a convex program is itself feasible.

I can show that any point on a line drawn between any two feasible points in a convex program is itself feasible.

If the points are
and
, then any point on the line between then can be
expressed as
for some
.

Say
is convex,



Since
and both
and
are feasible. Furthermore, since
is affine,



Therefore any point on the line is feasible between any two feasible points in a convex program.

The question is, how do I show that the midpoint between any two feasible points in a convex program is also feasible??

Thanks for your help!
 

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
I'm having trouble with this question:

Show that the midpoint bteween any two feasible points in a convex program is itself feasible.

I can show that any point on a line drawn between any two feasible points in a convex program is itself feasible.
Then you are done, aren't you? the midpoint between two points is certainly on the line between them.

If the points are
and
, then any point on the line between then can be
expressed as
for some
.

Say
is convex,



Since
and both
and
are feasible. Furthermore, since
is affine,



Therefore any point on the line is feasible between any two feasible points in a convex program.

The question is, how do I show that the midpoint between any two feasible points in a convex program is also feasible??

Thanks for your help!
You've done much more than was asked. You finish the problem by showing that the midpoint between any two points is on the line between the two points.

Now, exactly how is "midpoint" defined in your course? Most of the time it is defined as "point c is the 'midpoint between points a and b if and only if it lies on the line between a and b and is equidistant from a and b." If that is your definition, then you are done.

I suppose it would be possible to define a point c to be the midpoint between a and b by saying that the distance from c to a is the same as the distance from c to b and the sum of those distances is the distance from a to b (or, equivalently, that each distance is 1/2 the distance from a to b.) In that case, you can prove that "midpoint" lies on the line from a to b: suppose it were not. That the line from a to c, the line from c to b, and the line from a to c form a triangle. Since a straight line is the "shortest distance between two points", the total distance from a to c and from c to b must be larger than the distance from a to b, a contradiction.
 
Last edited:
  • Like
Reactions: lpd

lpd

Sep 2009
100
1
Thanks. Clear and concise! you really helped me here!