Thread: Linear Programming

Hi I have a question with regarding to a linear programming question.

suppose the problem has a disk constraint of the form

x^2+y^2<=1. this constraint is non linear and hence cannot b written in the form of AX<=b. for some finite matrix A and vector b. describe a construction of an infinite number of linear constraints on x such that the feasible set for all of these constraints together is equal to the disk.

Your help will greatly appreciate.

Thanks
Jupiter

Originally Posted by jupitertang

Hi I have a question with regarding to a linear programming question.

suppose the problem has a disk constraint of the form

x^2+y^2<=1. this constraint is non linear and hence cannot b written in the form of AX<=b. for some finite matrix A and vector b. describe a construction of an infinite number of linear constraints on x such that the feasible set for all of these constraints together is equal to the disk.

Think about it geometrically. A point will lie inside the circle if it is on the same side of each tangent to the circle as the origin.

The tangent to the circle at the point has equation . So the linear constraint will be . If the point (x,y) satisfies that constraint for all , then it will satisfy .