Dual Cones & Quadratic Modules: The Geometry of Global Optimality

Table of Links

Abstract and 1. Introduction

2. Related Works

3. Convex Relaxation Techniques for Hyperbolic SVMs

   3.1 Preliminaries

   3.2 Original Formulation of the HSVM

   3.3 Semidefinite Formulation

   3.4 Moment-Sum-of-Squares Relaxation

4. Experiments

   4.1 Synthetic Dataset

   4.2 Real Dataset

5. Discussions, Acknowledgements, and References

A. Proofs

B. Solution Extraction in Relaxed Formulation

C. On Moment Sum-of-Squares Relaxation Hierarchy

D. Platt Scaling [31]

E. Detailed Experimental Results

F. Robust Hyperbolic Support Vector Machine

C On Moment Sum-of-Squares Relaxation Hierarchy

In this section, we provide necessary background on moment-sum-of-squares hierarchy. We start by considering a general Polynomial Optimization Problem (POP) and introduce the sparse version. This section borrows substantially from the course note [4].

C.1 Polynomial Optimization and Dual Cones

Polynomial optimization problem (POP) in the most generic form can be presented as

where 𝑝(𝑥) is our polynomial objective and ℎ𝑖(𝑥), 𝑔𝑖(𝑥) are our polynomial equality and inequality constraints respectively. However, in general, solving such POP to global optimality is NP-hard [9, 29]. To address this challenge, we leverage methods from algebraic geometry [9, 21], allowing us to approximate global solutions using convex optimization methods.

To start with, we define sum-of-squares (SOS) polynomials as polynomials that could be expressed as a sum of squares of some other polynomials, and we define Σ[𝑥] to be the collection of SOS polynomials. More formally, we have

where R[𝑥] denotes the polynomial ring over R.

Next, we recall the definitions of quadratic module and its dual. Given a set of polynomials g = [𝑔1, 𝑔2, ..., 𝑔𝑙], the quadratic module generated by g is defined as

and its degree 2𝑑-truncation is defined as,

Similarly, given a set of polynomials h = [ℎ1, ℎ2, ..., ℎ𝑚], the ideal generated by h is defined as,

and its degree 2𝑑-truncation is defined as,

where 𝜆𝑖 ’s are also called polynomial multipliers. Interestingly, it is shown that we can perfectly characterize the dual of the sum of ideal and quadratic module,

(Ideal[h]2𝑑 + Qmodule[g]2𝑑) ∗ = 𝒵[ℎ]2𝑑 ∩ ℳ[𝑔]2𝑑 ,

With these notions setup, we can reformulate the POP above into the following SOS program for arbitrary 𝜅 ∈ N as the relaxataion order,

C.2 Sparse Polynomial Optimization

Definition 1. Correlated Sparsity for an objective 𝑝 ∈ R[𝑥] and associated set of constraints means

With correlated sparsity and data regularity (Putinar’s Positivestellentz outlined in Nie [9]), we are able to decompose the Qmodule generated by the entire set of decision variables into the Minkowski sum of Qmodules generated by each sparsity group of variables, effectively reducing the number of decision variables in the implementations. For a problem with only inequality constraints, which is our case for HSVM, the sparse POP for our problem reads as

and we could derive its dual accordingly and present the SDP form for implementation in Equation (14).

[4] Chapter 5 Moment Relaxation: https://hankyang.seas.harvard.edu/Semidefinite/Moment.html