# Linear Programming

• Sep 24th 2009, 03:51 PM
jupitertang
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.

Thanks
Jupiter
• Sep 26th 2009, 12:23 AM
Opalg
Quote:

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 $x^2+y^2=1$ if it is on the same side of each tangent to the circle as the origin.

The tangent to the circle at the point $(\cos\theta,\sin\theta)$ has equation $x\cos\theta+y\sin\theta=1$. So the linear constraint will be $x\cos\theta+y\sin\theta\leqslant1$. If the point (x,y) satisfies that constraint for all $\theta$, then it will satisfy $x^2+y^2\leqslant1$.