0

Problem

I want to find a line that maximises the sum of perpendicular distances from a set of points to the line such that the line passes through a fixed given point.

I have tried formulating the problem as follows:

$$\max\frac{\Vert Aw+eb \Vert^2}{\Vert w \Vert^2}\text{ such that }cw+b=0$$

where:

  • A is a matrix containing the points

  • $w,b$ are parameters of the line

  • $c$ is the given point

  • $e$ is s matrix containing ones of appropriate dimensions

Can anyone please guide me as to how to can this optimisation problem be solved ? The rational function is really making me upset

Santana Afton
  • 6,758
user3930879
  • 1
  • My 2 cents: You can simplify some things by assuming that $c$ is the origin, and that the line is defined by a unit vector. This then turns things into a maximization problem on a circle (the choice of unit vector), and you can pull it back to an interval using trigonometric functions. I'm not sure if the maximization problem is easier then, but at least you have fewer variables floating around, and you are studying a function on an interval, so I guess you can use numerical methods or something. – Elle Najt Apr 08 '17 at 06:53
  • maximize or minimize ? – Claude Leibovici Apr 08 '17 at 08:32

0 Answers0