Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: How to find a bounding line?
Replies: 39   Last Post: Jul 12, 2013 5:39 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Woody

Posts: 44
Registered: 7/29/09
Re: How to find a bounding line?
Posted: Jul 10, 2013 4:52 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Wednesday, July 10, 2013 12:45:01 PM UTC-7, Ray Vickson wrote:
>The best line must pass through at most two of the data points; here is why.

> You can formulate the best-line problem as a linear program:
> maximize a + x_bar * b
> subject to a + x_i * b <= y_i, i=1,..., N
> Here, a and b are "free", not sign-restricted. This optimization problem has 2 variables (a, b) and N constraints. Its DUAL is
> minimize sum_i y_i * v_i
> subject to sum_i v_i = 1, sum x_i * v_i = x_bar and v_i >= 0 for i = 1,2,...,N.
> This problem has N variables (the dual variables v_i) and two constraints. The dual constraints are equalities because the primal variables a and b are "free"; the dual variables v_i are sign-restricted because the primal constraints are inequalities.
>
> There exists an optimal solution at a basic feasible solution of the dual; any basic solution (feasible or not) has at most as many non-zero variables as there are constraints, so in this case any basic solution has at most two positive variables. The positive dual variables correspond to tight primal constraints, so correspond to two points through which the bounding line must pass.


I know nothing about linear programming. Can you supply some references?

> Note: when we say it *must* pass through at most two data points, we mean that it *need not be forced* to pass through 3 or more; however, it can "accidentally" pass through 3 or more points. This would correspond to a dual linear program having a non-unique optimal solution.

I trust you didn't mean "must pass through at most two of the data points" then, as if all points were co-linear it would pass through all of them.

Interesting that this idea doesn't directly use the convex hull, although I suspect the linear programming solvers do something closely related.




Date Subject Author
7/7/13
Read How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
Scott Berg
7/7/13
Read Re: How to find a bounding line?
Peter Percival
7/7/13
Read Re: How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Woody
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Leon Aigret
7/8/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
RGVickson@shaw.ca
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
William Elliot
7/8/13
Read Re: How to find a bounding line?
Peter Percival
7/8/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
LudovicoVan
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.