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

-
Just using linearly constrained quadratic programming to find $P_0$ isn't an option? –  DikobrAz Feb 27 '13 at 13:51
$\Re$ denotes the real part of a complex number, not the set of real numbers $\mathbb R$. // Also, I wonder why Mike Spivey's answer was deleted. It looks correct to me. –  Rahul Feb 27 '13 at 20:27
Well, that bounty sure went to waste... –  Rahul Mar 4 '13 at 9:33

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$$

-
Sorry for the late answer. I have just a couple of questions: (i) Does the objective function need the square root? [I guess not] (ii) Your inequalitites are different from the problem described, does this changes anything? I guess that if your solution works, it does for any values of c and d (not only positive values), am I right? –  Jack May 29 '13 at 16:44
(i) You are right. No need for square root; I just used the regular definition of distance. (ii) I am modifying the equations. That was my typo.. You may look at this answer for a practical application. math.stackexchange.com/questions/392375/… –  Occupy Gezi May 29 '13 at 17:55
Thank you for your answer. I mark it as accepted due to your major contribution. Still there are some considerations on a possible practical implementation on a software: The last KKT condition seems that basically says that there are always a set of constraints that are strict (with s = 0) and the rest of constraints not strict (with s > 0). When a constraint is not strict its lambda value is 0, if it is strict the corresponding lambda must be != 0 (it should be intuitive that it cannot be 0). –  Jack May 30 '13 at 8:44
Under such circumstances how do I pick the set of strict constraints (like a base) ? Is there there a Simplex-like algorithm that "prune" combinations of constraints based on how the objective function grow? –  Jack May 30 '13 at 8:47
Actually I am not aware of generic computational algorithm for KKT. The most used one which employs slack variables as in KKT is interior point algorithm. –  Occupy Gezi May 30 '13 at 12:14
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.
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)$.