• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter retspool
  • Start date
  • #1
36
0

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

  • #2
lanedance
Homework Helper
3,304
2
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
 
  • #3
36
0
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?
 
  • #4
lanedance
Homework Helper
3,304
2
you know a & (1-a) are both >0

now use what you know about Ax and Ay
 
  • #5
36
0
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
 
  • #6
lanedance
Homework Helper
3,304
2
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
 
  • #7
HallsofIvy
Science Advisor
Homework Helper
41,795
925
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?
 

Related Threads for: Optimization proof for Ax > b. Prove that set is convex

  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
10
Views
3K
Replies
10
Views
1K
  • Last Post
Replies
2
Views
4K
Replies
5
Views
4K
Top