Separation by ellipsoids using

semidefinite programming

François Glineur

Faculté Polytechnique de Mons Journée du 3ème cycle F.N.R.S.

Han-sur-Lesse 8^{th} May 1998.

Plan

• Introduction

• Semidefinite Programming • Model

• Results

• Conclusions

Introduction

Problem

Let C be a set of n classes. Each class C_{i} is a homogeneous set of entities. Each entity has d numerical characteristics.

C = {C_{i} ∈ ℝ^{d}, i = 1, 2, …, n}

We want to separate these classes, i.e. partition ℝ^{d} such that each class belongs to a different set of the partition.

Classification

1. Group some well-known entities into homogeneous classes (learning set)

2. Separate those classes

3. Use this partition to classify other entities (generalization)

Examples : Character recognition, weather prediction, medical diagnostic, etc.

Approach

To separate the classes, we compute n ddimensional ellipsoids E_{i} such that

• C_{i} ⊂ E_{i} ∀i

• C_{j} ∩ E_{i} = ∅ ∀i ≠ j These ellipsoids can be computed one at a time ⇒ n independent subproblems The problem of computing the best ellispoid can be modelled as a semidefinite program N.B. We do not require these ellipsoids to be disjoint.

Optimization objective

Feasible ellipsoid ⇔ Separating ellipsoid Best ellipsoid ⇔ Maximal separation

Semidefinite Programming

Definitions

𝕊^{n} = space of n × n symmetric matrices Inner product on 𝕊^{n} : A • B = trace (A^{T}B) A is positive definite ⇔ A ≻ 0 ⇔ all eigenvalues > 0 ⇔ u^{T} Au > 0 ∀u ≠ 0 A is positive semidefinite ⇔ A ⪰ 0 ⇔ all eigenvalues ≥ 0 ⇔ u^{T} Au ≥ 0 ∀u Löwner order : A ⪰ B ⇔ A − B ⪰ 0 and A ≻ B ⇔ A − B ≻ 0

Formulation

Min C • X s.t. A_{i} • X = b_{i} and X ⪰ 0 with X ∈ 𝕊^{n} and i = 1, 2, …, m Data : b ∈ ℝ^{m}, C, A_{i} ∈ 𝕊^{n}, n^{2} variables, m constraints, one objective. Linear programming is a special case.

Dual

Max b^{T} y s.t. ∑_{i=1}^{m} y_{i}A_{i} ⪯ C with y ∈ ℝ^{m}

Algorithms

Convex problem : interior points methods, very efficient (low parameter self-concordant barrier, Nesterov & Nemirovsky)

Primal-dual scheme (generalization of infeasible primal-dual path-following methods for linear programming ⇔ same concepts : logarithmic barrier function, central path, duality gap, etc.)

No feasible start needed.

Complexity : ϵ-solution reached in O(√n ln \frac{1}{ϵ}) iterations (same for linear programming with n variables !)

Applications

• Exact models : Eigenvalue optimization. Convex quadratic optimization. Robust control. Structural optimization. Statistics.

• Relaxations : Nonconvex quadratic optimization. Combinatorial optimization (with bounds !) : max-cut, boolean quadratic optimization. General 0-1 linear programming.

• Very active field

Model

Ellipsoid

E ⊂ ℝ^{n} ≡ {x ∈ ℝ^{n}|(x − c)^{T} D(x − c) ≤ 1}

where c ∈ ℝ^{n} and D ≻ 0 ∈ 𝕊^{n}

Constraints

Let {x_{i}^{+} } be the points to be included in the ellipsoid and {x_{i}^{−}} the points to be excluded. We ask for (x_{i}^{+} − c)^{T} D(x_{i}^{+} − c) ≤ 1 and (x_{i}^{−} − c)^{T} D(x_{i}^{−} − c) ≥ 1 + t and try to maximize t in order to obtain the best separation.

• If the points are separable by an ellipsoid, we find an optimal solution with t > 0

• If the points are not separable by an ellipsoid, we find an optimal solution with t < 0 but minimize the uncertain zone

Formulation

Use a trick : letting

Z = ( \begin{matrix}s & z^{T} \\ z & D \end{matrix} )

it is possible to prove that the problem is equivalent to

min −t s.t. Z • Y_{i}^{+} + r_{i}^{+} = 1 and Z • Y_{i}^{−} − r_{i}^{−} = 1 + t with Z ⪰ 0, r_{i}^{+} ≥ 0, r_{i}^{−} ≥ 0

which is a semidefinite program. We have Y_{i}^{±} = (−1; x_{i}^{±})^{T} (−1; x_{i}^{±}) and we can recover c with D^{−1}z.

N.B. There is an additional constraint to avoid the case D = 0 when points are not separable

Results

Implementation

We used Matlab 5.2 and a semidefinite package, SDPPack 0.9 by F. Alizadeh, J.-P. Haeberly, M.V. Nayakkankuppam, M.L. Overton and S. Schmieta

Benchmark

Data  Cl. Pts dim 10% 50%  Ref
Iris  3 150  4 85.6 92.7
Breast  2 683  9 94.9 96.2 96.9
Housing  2 506  14 85.3 95.6 84.0
Diabetes  2 768  8 67.8 64.7 71.9

Conclusions

• Main idea : use ellipsoids to separate classes

• Compute ellipsoids with semidefinite programming

• Very encouraging results

• Further research – Better handling of infeasibility

– Better exploitation of ellipsoids

– Variable subset selection

– Clustering (nonconvex)