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

• retspool

## 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!

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?

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

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

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?