# Optimization proof for Ax > b. Prove that set is convex

## Homework Statement

Consider a feasible region S defined by a set of linear constraints

S = {x:Ax<b}

Prove that S is convex

## Homework Equations

All what i know is that, a set is convex if and only if the elements x, and y of S

ax + (1-a)y belongs to S
for all 0 <a < 1

## The Attempt at a Solution

I don't even know where to begin!

## Answers and Replies

lanedance
Homework Helper
so take x,y in S then Ax < b and Ay <b, now take z = ax + (1-a)y

now see if you can show z is in S, using
Az = aAx + (1-a)Ay

I still haven't gotten it

I take x,y in S so i have Ax < b and Ay < b

so ax + (1-a)y is in S

now Az = aAx + (1-a)y

what to do now?

lanedance
Homework Helper
you know a & (1-a) are both >0

now use what you know about Ax and Ay

Ok, i am seriously lost, i don't know where to bring in z from..

I am attaching the only pages where convex sets have been defined and from the material, and with the information given, it seems difficult to prove the above

lanedance
Homework Helper
if any point z = ax + (1-a)y is within the set for any x & y, then you have proved it is convex, so all you are trying to show is that
Az < b

Then z is clearly part of the set

HallsofIvy
Science Advisor
Homework Helper
I still haven't gotten it

I take x,y in S so i have Ax < b and Ay < b

so ax + (1-a)y is in S

now Az = aAx + (1-a)y
No, Az= aAx+(1- a)Ay.

Ax< b and Ay< b since they are both in S. So aAx+ (1-a)Ay< ab+ (1- a)b= b.

what to do now?