Find the point in a sub-space defined by linear constraints closer to an external point I have the following


*

*$P \in \mathbb R^d$

*A set of $k$ linear constraints $c_i \in \mathbb R^d,d_i \in \mathbb R$ 


I need to find the point $P_0$ that satisfies all the $k$ constraints (i.e. $c_i^TP_0 \geq d_i$  $\forall i=1...k$) and is closer to the point $P$.
Having a space generated by a matrix $A$ I would use the least squares, however in presence of such constraints the Simplex seems to be the answer but I can't find the proper objective function.
Do you have any suggestions?
 A: Please tell me if my reconstruction is wrong. As far as I understand you want a point as close as possible (I assume Euclidian distance) to a given point and satisfy the linear constraints. Sorry that you can't solve it with Simplex but here is the solution
$$min_{x_1,x_2,...,x_d}\ \sqrt{(x_1-x_{1,p})^2+\ldots + (x_d-x_{d,p})^2}$$ 
subject to
$$-c_{1,1}x_1-\ldots -c_{1,d}x_d\le -d_1$$
$$\cdots$$
$$-c_{k,1}x_1-\ldots -c_{k,d}x_d\le -d_k$$
First get rid of functional inequalities by using dummy variables
$$-c_{1,1}x_1-\ldots -c_{1,d}x_d+s_1= -d_1$$
$$\cdots$$
$$-c_{k,1}x_1-\ldots -c_{k,d}x_d+s_k= -d_k$$
$$s_1,\ldots,s_k\ge 0$$
Then construct the Lagrangian
$$Z=\sqrt{(x_1-x_{1,p})^2+\ldots + (x_d-x_{d,p})^2}+\lambda_1\big(d_1-c_{1,1}x_1-\ldots -c_{1,d}x_d+s_1\big)+\ldots$$
$$+\lambda_k\big(d_k-c_{k,1}x_1-\ldots -c_{k,d}x_d+s_k\big)$$
For regular variables (w/o nonnegativity constraint) use the first order condition as is
$$\frac{\partial Z}{\partial x_1}=0$$
$$\cdots$$
$$\frac{\partial Z}{\partial x_d}=0$$
$$\frac{\partial Z}{\partial \lambda_1}=0$$
$$\cdots$$
$$\frac{\partial Z}{\partial \lambda_k}=0$$
For dummy variables the first order condition must be modified according to Kuhn Tucker conditions
$$s_1\frac{\partial Z}{\partial s_1}=0$$
$$\cdots$$
$$s_k\frac{\partial Z}{\partial s_k}=0$$
After solving the equations you have to be sure that the feasible set satisfies below conditions
$$\frac{\partial Z}{\partial s_i}\ge 0\quad \land \quad s_i\ge 0\quad i=1,...,k$$
A: As Mike Spivey's deleted answer said, you can take your objective to be simply the squared distance between $P$ and $P_0$. Then you have a quadratic objective and linear constraints, making the problem quite directly an instance of quadratic programming. There's nothing more to it.

It is not possible to the simplex method to solve your problem. The simplex method is an algorithm to solve linear programming problems, and the optimum of a linear programming problem, if it exists, is always attained at a vertex of the feasible polytope. This is not the case for your problem.
For example, consider the problem of finding the point $(x,y)$ closest to $(1,-1)$ subject to $x\ge0$, $y\ge0$. This is an instance of your problem with $n=2$, $d=2$. Clearly $(1,0)$ is the unique solution. However, the feasible polytope only has one vertex, namely $(0,0)$, so any linear objective will either have an optimum at $(0,0)$ or be unbounded. There is no way to use linear programming to obtain the solution $(1,0)$.
