Thread: Convex Program

1. Convex Program

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!

2. Originally Posted by lpd
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.

3. Thanks. Clear and concise! you really helped me here!