Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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.


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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.