Separating Hyperplanes

Documentation for SeparatingHyperplanes.jl.

Mathematical details can be found in Convex Optimization by Boyd and Vandenberghe, Section 8.6.1. Eventually, I intend to add in further functionality, e.g., a soft separating hyperplane.

Example

using SeparatingHyperplanes

# create two 2D pointclouds
P = rand(10, 2)
Q = 1.0 * ones(20, 2) + rand(20, 2)

# find a separating hyperplane
result = separating_hyperplane(P, Q)

# get the status
status = result.status

:Separable

# get the hyperplane
a, b = result.a, result.b

([-2.4161784647058906, -2.8031182175523486], -4.6380463318304805)

# get the separating distance
d = result.separating_distance

0.5404341594035615

We can now plot the results (for 2D):

using Plots

# Plots the hyerplane a' x = b
function plot_hyperplane!(a, b; tlims = (-1, 1), kwargs...)
        @assert length(a) == 2 "this function only works in 2D"
        # find one point on the plane
        x0 = (b / (a' * a)) * a
        # find the tangential vector
        n = [-a[2], a[1]]
        plot!(t-> (x0 + t * n)[1], t-> (x0 + t * n)[2], tlims...; kwargs...)
end

plot()
scatter!(P[:, 1], P[:, 2], label="P")
scatter!(Q[:, 1], Q[:, 2], label="Q")
plot_hyperplane!(a, b; tlims=(-0.5, 0.5), label="a'z = b")

API

SeparatingHyperplanes.Result — Type

Result{F}

Results struct containg

status: Symbol indicating the status of the solution
a: Vector of coefficients for the hyperplane
b: Scalar offset for the hyperplane
separating_distance: Distance between the two sets of points
osqp_result: The raw OSQP result object containing detailed solver information

This struct is used to encapsulate the results of the separating_hyperplane function.

The solver status can be one of the following:

:Separable: The sets are separable with a valid hyperplane.
:Not_separable: The sets are not separable.
:Separable_inaccurate: The sets are separable, but the solution is inaccurate.
:Not_separable_inaccurate: The sets are not separable, but the solution is inaccurate.
:Max_iter_reached: The solver reached the maximum number of iterations without convergence.
:Time_limit_reached: The solver reached the time limit without convergence.
:Interrupted: The solver was interrupted before completion.
:Unknown: The status is unknown or not recognized.

source

SeparatingHyperplanes.separating_hyperplane — Method

separating_hyperplane(P, Q; eps_abs=1e-10, eps_rel=1e-10, verbose=false, kwargs...)

Find a separating hyperplane between two sets of points P and Q in R^d. If a separating hyperplane exists, it returns a Result object containing the hyperplane parameters and the distance between the sets.

Arguments:

P: A matrix of points in R^d, arranged as N x d matrix
Q: A matrix of points in R^d, arranged as N x d matrix
eps_abs: Absolute tolerance for the OSQP solver (default: 1e-10)
eps_rel: Relative tolerance for the OSQP solver (default: 1e-10)
verbose: If true, prints solver information (default: false)
kwargs: Additional keyword arguments for the OSQP solver

Returns:

A Result struct.

This solves the problem

\[\begin{align*} \underset{a \in \mathbb{R}^d, b \in \mathbb{R}}{\operatorname{minimize}} \quad & \frac{1}{2} \Vert a \Vert^2\\ \operatorname{s.t.} \quad & a^T p_i - b \geq 1 \quad \forall p_i \in P \\ & a^T q_i - b \leq -1 \quad \forall q_i \in Q \end{align*}\]

If the sets are separable, the hyperplane slab $-1 \leq a^T z - b \leq 1$ separates the two point sets. The distance between the sets is given by 2 / norm(a).

source