11institutetext: University of British Columbia, Kelowna, Canada
11email<EMAIL_ADDRESS>
# QUBO formulations for NP-Hard spanning tree problems

Ivan Carvalho  0000-0002-8257-2103

###### Abstract

We introduce a novel Quadratic Unconstrained Binary Optimization (QUBO)
formulation method for spanning tree problems. Instead of encoding the
presence of edges in the tree individually, we opt to encode spanning trees as
a permutation problem. We apply our method to four NP-hard spanning tree
variants, namely the $k$-minimum spanning tree, degree-constrained minimum
spanning tree, minimum leaf spanning tree, and maximum leaf spanning tree. Our
main result is a formulation with $\mathcal{O}(|V|k)$ variables for the
$k$-minimum spanning tree problem, beating related strategies that need
$\mathcal{O}(|V|^{2})$ variables.

###### Keywords:

Quadratic unconstrained binary optimization Ising Models Spanning trees Graph
Theory QUBO .

##  1 Introduction

Given an edge-weighted undirected graph $G=(V,E)$, the minimum spanning tree
(MST) of a graph is the subgraph $G_{T}=(V,E_{T})$ such that $G_{T}$ is
connected, acyclic, and the sum of the edge weights, $\sum_{(u,v)\in
E_{T}}W_{u,v}$, is minimized. Finding the MST of a graph can be done in
polynomial time with greedy algorithms such as Kruskal’s algorithm [11] and
Prim’s algorithm [14].

However, adding constraints to the spanning tree or changing the objective
make some variants much harder to solve. Constraints such as limiting the
minimum number of vertices [16, 4] or limiting the maximum degree of vertex
[15] make the problem NP-Hard. The same applies to minimizing (or maximizing)
the number of leaves [17, 6].

In this paper, we focus on using Quadratic Unconstrained Binary Optimization
(QUBO) to solve NP-Hard spanning tree problems. We introduce a novel QUBO
formulation method for spanning tree problems. Instead of encoding the
presence of edges in the tree individually, we opt to encode spanning trees as
a permutation problem. Our main result is a formulation with
$\mathcal{O}(|V|k)$ variables for the $k$-minimum spanning tree problem
(kMST). The method also yields a formulation with $\mathcal{O}(|V|^{2})$
variables for the degree-constrained minimum spanning tree (DCMST), the
minimum leaf spanning tree, and the maximum leaf spanning tree.

##  2 Quadratic Unconstrained Binary Optimization

QUBO instances are relevant because they can be approximately solved using
methods such as simulated annealing [10], quantum annealing [9], digital
annealing [1], and the Quantum Approximate Optimization Algorithm (QAOA) [3].

Solving QUBO instances can be described as minimizing a quadratic polynomial
over binary variables $x_{1},x_{2},\ldots,x_{n}$:

${\arg\\!\min}_{x\in\\{0,1\\}^{n}}\hskip
5.69046ptH=c+\sum_{i=1}^{n}\sum_{j=i+1}^{n}b_{i,j}x_{i}x_{j}+\sum_{i=1}^{n}a_{i}x_{i}$

QUBO formulations are also closely connected to Ising models, that are
described by a quadratic polynomial with variables $\sigma_{i}\in\\{-1,+1\\}$:

${\arg\\!\min}_{\sigma\in\\{-1,+1\\}^{n}}\hskip
5.69046ptH=-\sum_{i=1}^{n}\sum_{j=i+1}^{n}J_{i,j}\sigma_{i}\sigma_{j}-\mu\sum_{i=1}^{n}h_{i}\sigma_{i}$

We highlight that there is a mapping between QUBO and Ising by using the
equation $\sigma_{i}=2x_{i}-1$. Hence we can swap QUBO and Ising formulations
interchangeably. Ising formulations are more common in Physics and are closer
to the way hardware such as quantum annealers represent the problem. QUBO
formulations are more common in the field of Computer Science, and will be the
chosen notation for the remaining equations.

There are two QUBO formulation metrics that are pertinent for the hardware
that can solve the instances, namely the number of variables and the density
of the formulation [5].

Existing hardware such as D-Wave’s quantum annealers or Fujitsu’s digital
annealers can only solve QUBO instances up to a limited number of variables.
Therefore, the best hardware-friendly formulations use the fewest possible
number of variables.

Moreover, the number of interactions among the variables, called density, is
also relevant to the hardware. D-Wave’s quantum annealers do not have full
connectivity among their qubits and often a minor-embedding [2] is required to
map the Ising model to the hardware topology. Minor-embeddings use a chain of
qubits to represent a single variable, which reduces the size of the QUBO
problems that can be solved by hardware. Thus, the best hardware-friendly
formulations also have the smallest possible density.

##  3 Related Work and Contributions

The literature for QUBO formulations is plentiful, with given formulations for
many combinatorial optimization problems [8]. In his work, Lucas proposes QUBO
formulations for many NP problems, including the DCMST problem [12]. Lucas
proposed formulation uses $\mathcal{O}(|V|^{3})$ variables in its worst case,
with the largest number of variables of the formulation being dedicated to
encode the depth of an edge $(u,v)$ in the spanning tree.

In his Master’s thesis, Fowler improves upon Lucas’ works and provides a DCMST
formulation that uses $\mathcal{O}(|V|^{2})$ variables in its worst case [5].
Fowler’s improved formulation relies on encoding edges (which require
$\mathcal{O}(|E|)$ variables) and ordering variable among the vertices (which
require $\mathcal{O}(|V|^{2})$ variables).

Silva et al. also offer a QUBO formulation for another NP-Hard variant of the
spanning tree problem, the minimum loss spanning tree reconfiguration problem
[18]. Their formulation diverges from that of Lucas and Fowler because it
assumes that the input grah is planar, which is valid for the electrical
networks they analyse. Nevertheless, their formulation still encodes the
presence of each vertex in the tree and requires $\mathcal{O}(|E|)$ variables.

###  3.1 Our Contributions

Our new proposed formulations, by contrast, do not encode the presence of
edges in the spanning tree. Instead, we frame the spanning tree problem as a
permutation problem, similarly to Lucas’ formulation for the Travelling
Salesman Problem (TSP) [12] .This novel technique allows us to encode the
$k$-minimum spanning tree problem with $\mathcal{O}(|V|k)$ variables, which
uses fewer variables than the $\mathcal{O}(|V|^{2})$ related formulations for
small $k$. Using fewer varaibles is desirable, as by the hardware limitations
discussion earlier.

Another consequence of adopting the permutation strategy is that advancements
in encoding permutations, generally focused on solving the TSP, will also
benefit our encoding for spanning trees. Techniques such as using Higher Order
Binary Optimization for QAOA [7] or leveraging qudits instead of qubits [19]
could also benefit our proposed encoding.

Our work is the first in literature to introduce QUBO formulations for the
kMST and for the minimum (maximum) leaf spanning tree. Nonetheless, we believe
that Fowler’s DCMST formulation could encode those problems with minor tweaks
while keeping $\mathcal{O}(|V|^{2})$ variables. Hence, for comparison
purposes, we refer to Fowler’s work as a related strategy with
$\mathcal{O}(|V|^{2})$ variables.

##  4 Methods

Our method is based on incrementally building a spanning tree by adding one
vertex at a time. Throughout the building process, the spanning tree always
remains a single connected component. Assume that the vertices are labelled
$1,2,\ldots,|V|$. Then, the order that the vertices are added in the tree can
be treated as a permutation of $\\{1,2,\ldots,|V|\\}$.

Hence, the first type of variable we use in our encoding $x_{v,i}$ is used to
represent the positions of vertices in the permutation (similar to the QUBO
encoding of the TSP):

$x_{v,i}=\begin{cases}1,\hskip 14.22636pt\text{if the vertex }v\text{ is at
the }i\text{-th position}\\\ 0,\hskip 14.22636pt\text{otherwise}\end{cases}$

The method, however, also needs additional variables. One key difference
between a spanning tree and a path is the edge used to connect a vertex $v$.
On a path, it is implied that if the vertex $u$ is at position $i$ and the
vertex $v$ is at position $i+1$, then the edge $(u,v)$ is used to connect the
two. The same does not apply to spanning trees, because a vertex in the tree
might have degree greater than two.

Thus, the second type of variable we use in our encoding $y_{v,i}$ is used to
represent which previous position in the permutation each vertex connects to:

$y_{v,i}=\begin{cases}1,\hskip 14.22636pt\text{if the vertex }v\text{ has an
edge connecting it to the vertex at the }i\text{-th position}\\\ 0,\hskip
14.22636pt\text{otherwise}\end{cases}$

This representation is convenient for two reasons. Firstly, it let us enforce
that a vertex only connects to previous vertices in the sequence. We can add a
constraint that $\sum_{i=1}^{|V|}\sum_{j=i}^{|V|-1}x_{v,i}y_{v,j}=0$ for each
vertex $v$. Secondly, we can test if an edge $(u,v)$ is present in the tree
with the expression $\sum_{i=1}^{|V-1|}x_{u,i}y_{v,i}$.

##  5 Results

###  5.1 $k$-Minimum Spanning Tree

####  5.1.1 Preliminaries

Given an edge-weighted undirected graph $G=(V,E)$ with non-negative edge
weights and a positive integer $k\leq|V|$, the kMST of a graph can be defined
as the MST with at least $k$ vertices. That is, the kMST is the subgraph
$G_{T}=(V_{T},E_{T})$ such that $G_{T}$ is connected and acyclic, the number
of vertices $|V_{T}|$ is greater than or equal to $k$, and the sum of the edge
weights, $\sum_{(u,v)\in E_{T}}W_{u,v}$, is minimized. The kMST problem is
also known as edge-weighted $k$-cardinality tree in literature [4].

For the QUBO formulation, we will exploit the fact that the solution for the
kMST has exactly $k$ vertices [16]. For each vertex $v\in V$, we define
variables $x_{v,i}$ with $1\leq i\leq k$ for encoding the presence of the
vertex in the permutation of size $k$. We also define for each $v\in V$ the
variables $y_{v,i}$ with $1\leq i\leq k-1$ to encode the connections to
previous vertices in the permutation. The formulation uses $2|V|k-|V|$
variables in total.

Our formulation also contains two parameters $\lambda_{A}>0$ and
$\lambda_{B}>0$ to tweak the energy of the hamiltonian. We use $\lambda_{A}$
as a coefficient for the quadratic penalties [8]. QUBO problems are by
definition unconstrained, hence we add penalties such that invalid solutions
cannot be the global minimum of the expression.

####  5.1.2 Formulation

We formulate the Hamiltonian for the kMST using three parts such that
$H_{kMST}=H_{Tree}+H_{Cst}^{(1)}+H_{Cst}^{(2)}$.

The first Hamiltonian represents the cost of the edges in the kMST, by
checking the presence of edges in the tree using the
$\sum_{i=1}^{k}x_{u,i}y_{v,i}$ expression discussed earlier. We also add a
penalty in the Hamiltonian such that no invalid edge $(u,v)\notin E$ is
allowed in a solution to the QUBO.

$H_{Tree}=\lambda_{B}\sum_{(u,v)\in E}W_{u,v}\sum_{i=1}^{k-1}x_{u,i}\cdot
y_{v,i}+\lambda_{A}\sum_{(u,v)\notin E}\sum_{i=1}^{k-1}x_{u,i}\cdot y_{v,i}$

The second Hamiltonian ensures that three constraints are met. The first
constraint is that no two vertices must occupy the same position in the
permutation. The second constraint is that no vertex may occupy two positions
in the permutation. The third constraint is that for each position
$i\in\\{1,2,\ldots k\\}$, exactly one vertex must occupy such position.

$H_{Cst}^{(1)}=\lambda_{A}\sum_{v=1}^{|V|}\sum_{u=v+1}^{|V|}\sum_{i=1}^{k}x_{u,i}\cdot
x_{v,i}+\lambda_{A}\sum_{i=1}^{k}\sum_{j=i+1}^{k}\sum_{v=1}^{|V|}x_{v,i}\cdot
x_{v,j}+\lambda_{A}\sum_{i=1}^{k}(1-\sum_{v=1}^{|V|}x_{v,i})^{2}$

The third Hamiltonian validates another two constraints related to connections
of each vertex. The first constraint penalizes connections from a vertex to
another vertex ahead of it in the permutation. The second constraint validates
that if a vertex $v$ is present in the permutation and it is not the first
vertex, then exactly one of its $y_{v,i}$ is set to $1$.

$H_{Cst}^{(2)}=\lambda_{A}\sum_{u=1}^{|V|}\sum_{i=2}^{k}(x_{u,i}\cdot\sum_{j=i}^{k-1}y_{u,j})+\lambda_{A}\sum_{v=1}^{|V|}(\sum_{i=2}^{k}x_{v,i}-\sum_{i=1}^{k-1}y_{v,i})^{2}$

Therefore, the Hamiltonian for the kMST is:

$H_{kMST}=H_{Tree}+H_{Cst}^{(1)}+H_{Cst}^{(2)}$

To ensure that the solution that minimizes the energy of the Hamiltonian is a
valid solution to the kMST, we propose a lower bound to the penalty
coefficient of $\lambda_{A}>\lambda_{B}|V|\cdot\max_{(u,v)\in E}(W_{u,v})>0$.

The proposed formulation uses $\mathcal{O}(|V|k)$ variables and contains
$\mathcal{O}(|V|^{2}k+|V|k^{2})$ interactions among the variables.

###  5.2 Degree restricted Minimum Spanning Tree

####  5.2.1 Preliminaries

Given an edge-weighted undirected graph $G=(V,E)$ with non- negative edge
weights and a positive integer $\Delta$, the DCMST of a graph can be defined
as finding a MST such that the degree of every vertex is less than or equal to
$\Delta$. That is, the DCMST is the subgraph $G_{T}=(V,E_{T})$ such that
$G_{T}$ is connected and acyclic, $\deg(v)\leq\Delta$ holds for every $v\in
V$, and the sum of the edge weights, $\sum_{(u,v)\in E_{T}}W_{u,v}$, is
minimized.

The QUBO formulation for the DCMST is similar to the one for the kMST. The
parameters $\lambda_{A}>0$ and $\lambda_{B}>0$ return on the formulation, and
many of the Hamiltonians are similar. However, there are two key differences.
The first difference is that the permutation is of size $|V|$, hence we define
variables $x_{v,i}$ for each $v\in V$ and for each $i$ with $1\leq i\leq|V|$.
Analogously, we also define $y_{v,i}$ for each $v\in V$ and for each $i$ with
$1\leq i\leq|V|-1$.

The second difference is the use of degree-counter slack variables for
encoding the inequality constraints. We use an identical strategy to the one
in Lucas’ and Fowler’s works [12, 5]. Let $M=\lfloor\log_{2}\Delta\rfloor$.
Then, for each position $i\in\\{1,2,\ldots|V|-1\\}$ in the permutation, we
define the expression $\mathcal{Z}_{i}$ that counts how many vertices connect
to the position $i$:

$\mathcal{Z}_{i}=(\sum_{j=0}^{M-1}z_{i,j}2^{j})+z_{i,M}(\Delta+1-2^{M})$

Each variable $z_{i,j}$ can be interpreted as a bit in the binary
representation of $\mathcal{Z}_{i}$, with the exception of $z_{i,M}$ which is
a remainder for when $\Delta$ is not of the form $2^{n}-1$. We point that
$0\leq\mathcal{Z}_{i}\leq\Delta$, hence the degree-counter variable cannot
assume values that are not consistent with a DCMST solution.

The formulation uses
$2|V|^{2}+|V|\lfloor\log_{2}\Delta\rfloor-(\lfloor\log_{2}\Delta\rfloor+1)$
variables in total.

####  5.2.2 Formulation

The Hamiltonian for the DCMST is formulated with four parts such that
$H_{DCMST}=H_{Tree}+H_{Cst}^{(1)}+H_{Cst}^{(2)}+H_{Cst}^{(3)}$.

The first Hamiltonian represents the cost of the edges in the DCMST, by
checking the presence of edges in the tree. Likewise, there is a penalty in
the Hamiltonian for invalid edges. $H_{Tree}$ is almost identical to the one
for the kMST, with the difference being on the sum of the terms going from $1$
to $|V|$ instead of $1$ to $k$.

$H_{Tree}=\lambda_{B}\sum_{(u,v)\in E}W_{u,v}\sum_{i=1}^{|V|-1}x_{u,i}\cdot
y_{v,i}+\lambda_{A}\sum_{(u,v)\notin E}\sum_{i=1}^{|V|-1}x_{u,i}\cdot y_{v,i}$

The second Hamiltonian checks constraints regarding the permutation. The first
constraint is that each vertex must appear exactly once in the permutation.
The second constraint is that for each position, exactly one vertex must be
assigned to it.

$H_{Cst}^{(1)}=\lambda_{A}\sum_{v=1}^{|V|}(1-\sum_{i=1}^{|V|}x_{v,i})^{2}+\lambda_{A}\sum_{i=1}^{|V|}(1-\sum_{v=1}^{|V|}x_{v,i})^{2}$

The third Hamiltonian checks two other constraints concerning the connection
of the nodes. The first constraint penalizes connections from a vertex to
another vertex ahead of it in the permutation. The second constraint ensures
that every vertex connects to exactly one previous vertex, with the exception
of the first vertex does not require such connection.

$H_{Cst}^{(2)}=\lambda_{A}\sum_{u=1}^{|V|}\sum_{i=2}^{|V|}(x_{u,i}\cdot\sum_{j=i}^{|V|-1}y_{u,j})+\lambda_{A}\sum_{v=1}^{|V|}(1-x_{v,1}-\sum_{i=1}^{|V|-1}y_{v,i})^{2}$

The fourth Hamiltonian is for the degree related constraints. For each $i$, we
validate that $\mathcal{Z}_{i}$ and its associated $z_{i,j}$ variables encode
the number of connections of position $i$. Note that for $i\geq 2$, we also
need to subtract one to account for the implicit connection with a previous
vertex in the permutation.

$H_{Cst}^{(3)}=\lambda_{A}(\mathcal{Z}_{1}-\sum_{v=1}^{|V|}y_{v,1})^{2}+\lambda_{A}\sum_{i=2}^{|V|-1}(\mathcal{Z}_{i}-1-\sum_{v=1}^{|V|}y_{v,i})^{2}$

Therefore, the Hamiltonian for the DCMST is:

$H_{DCMST}=H_{Tree}+H_{Cst}^{(1)}+H_{Cst}^{(2)}+H_{Cst}^{(3)}$

We propose again the lower bound for the penalty coefficient of
$\lambda_{A}>\lambda_{B}|V|\cdot\max_{(u,v)\in E}(W_{u,v})>0$, to ensure the
ground state of the Hamiltonian is a valid DCMST solution.

The proposed formulation uses $\mathcal{O}(|V|^{2})$ variables and contains
$\mathcal{O}(|V|^{3})$ interactions among the variables.

###  5.3 Minimum (Maximum) Leaf Spanning Tree

####  5.3.1 Preliminaries

Given a unweighted undirected graph $G=(V,E)$, the minimum leaf spanning tree
(MLST) of a graph can be defined as the spanning tree such that the number of
leaves is minimized. Let $V_{L}=\\{v\in V|\deg(v)=1\\}$ denote the leaves of
the tree. Then, the MLST is the subgraph $G_{T}=(V,E_{T})$ such that $G_{T}$
is connected and acyclic, and the number of leaves $|V_{L}|$ is minimized.

A related problem to the MLST is the maximum leaf spanning tree, which
maximizes the number of leaves $|V_{L}|$. We will show that the QUBO
formulation for the two problems is almost identical, as we can swap
minimizing for maximizing by multiplying by minus one. For the formulation
discussion, we focus on the problem that minimizes leaves for simplicity.

The QUBO formulation for the MLST shares many similarities with the one for
the kMST. The formulation uses the variables $x_{v,i}$, $y_{v,i}$, and the
parameters $\lambda_{A}>0$ and $\lambda_{B}>0$ just like the DCMST. The major
difference is on the slack variables, which instead of just counting the
degree also check if a vertex is a leaf in the tree.

We use a technique similar to the idea from the Max $k$-SAT QUBO formulation
[13] to count leaves in the tree. We add a depth $d$ to the degree-counter
expressions $\mathcal{Z}_{d,i}$ . For $d=1$, $\mathcal{Z}_{1,i}$ counts
$\deg(v)-1$, where $v$ is the vertex such that $x_{v,i}=1$. For $d>1$,
$\mathcal{Z}_{d,i}$ counts how many variables were set to one in
$\mathcal{Z}_{d-1,i}$. For some $D=d$, $\mathcal{Z}_{D,i}$ will eventually be
represented by exactly two binary variables.

Because $\deg(v)-1$ is equal to zero if $v$ is a leaf, $\mathcal{Z}_{1,i}$ has
no variable set to one if the vertex at position $i$ is a leaf. This
propagates to the next depths, as $\mathcal{Z}_{d,i}$ will also have no
variable set to one. Therefore, we can verify that the vertex at position $i$
is a leaf by checking if $\mathcal{Z}_{D,i}=0$.

Let $D=\log_{2}^{\star}|V|$ be the iterated logarithm of the number of
vertices. We define a sequence $M$ such that $M_{0}=|V|-1$ and
$M_{d}=\lfloor\log_{2}(1+M_{d-1})\rfloor$ for $1\leq d\leq D$. Then, we define
the expression $\mathcal{Z}_{d,i}$ for each position
$i\in\\{1,2,\ldots,|V|-1\\}$ and each depth $1\leq d\leq D$:

$\mathcal{Z}_{d,i}=(\sum_{j=0}^{-1+M_{d}}z_{d,i,j}2^{j})+z_{d,i,M_{d}}(M_{d-1}+1-2^{M_{d}})$

Each variable $z_{d,i,j}$ can be interpreted as a bit in the binary
representation of $\mathcal{Z}_{d,i}$, with the exception of $z_{d,i,M_{d}}$
which is a remainder for when $M_{d}$ is not of the form $2^{n}-1$.

For convenience, we also define the expression $\mathcal{B}_{d,i}$ that counts
the number of variables that are set in $\mathcal{Z}_{d,i}$:

$\mathcal{B}_{d,i}=\sum_{j=0}^{M_{d}}z_{d,i,j}$

Let $L=\sum_{d=1}^{D}1+M_{d}$ denote the sum of slack variables associated
with a position. Then, the total number of variables for the formulation is
$2|V|^{2}-|V|+L|V|-L$.

####  5.3.2 Formulation

The Hamiltonian for the MLST is formulated with five parts such that
$H_{MLST}=H_{Tree}+H_{Edges}+H_{Cst}^{(1)}+H_{Cst}^{(2)}+H_{Cst}^{(3)}$.

The first Hamiltonian counts the number of leaves. The expression for counting
leaves $(1-z_{D,i,1})(1-z_{D,i,0})$ evaluates to one if the vertex at position
$i$ is a leaf. Otherwise, it evaluates to zero as at least one of the bits
will be set. Notice that the vertex at position $i=|V|$ is always a leaf,
hence we add a constant to account for that.

$H_{Tree}=\lambda_{B}(1+\sum_{i=1}^{|V|-1}(1-z_{D,i,1})(1-z_{D,i,0}))$

The second Hamiltonian is for penalizing invalid edges $(u,v)\notin E$.

$H_{Edges}=\lambda_{A}\sum_{(u,v)\notin E}\sum_{i=1}^{|V|-1}x_{u,i}\cdot
y_{v,i}$

The third Hamiltonian checks constraints regarding the permutation, and is
identical to $H_{Cst}^{(1)}$ from the DCMST formulation.

$H_{Cst}^{(1)}=\lambda_{A}\sum_{v=1}^{|V|}(1-\sum_{i=1}^{|V|}x_{v,i})^{2}+\lambda_{A}\sum_{i=1}^{|V|}(1-\sum_{v=1}^{|V|}x_{v,i})^{2}$

The fourth Hamiltonian checks constraints concerning the connection of the
nodes, and is identical to $H_{Cst}^{(2)}$ from the DCMST formulation.

$H_{Cst}^{(2)}=\lambda_{A}\sum_{u=1}^{|V|}\sum_{i=2}^{|V|}(x_{u,i}\cdot\sum_{j=i}^{|V|}y_{u,j})+\lambda_{A}\sum_{v=1}^{|V|}(1-x_{v,1}-\sum_{i=1}^{|V|}y_{v,i})^{2}$

The fifth Hamiltonian is for the constraints related to $\mathcal{Z}_{d,i}$.
For $d=1$, we ensure that $\mathcal{Z}_{1,i}$ is equal to the degree minus
one. The expression for $i=1$ is slightly different than the one for $i\geq 2$
because the latter ones have an implicit connection to a previous position in
the permutation. For $2\leq d\leq D$, we verify the constraint that
$\mathcal{Z}_{d,i}=\mathcal{B}_{d-1,i}$.

$H_{Cst}^{(3)}=\lambda_{A}((\mathcal{Z}_{1,1}+1-\sum_{v=1}^{|V|}y_{v,1})^{2}+\sum_{i=2}^{|V|-1}(\mathcal{Z}_{1,i}-\sum_{v=1}^{|V|}y_{v,i})^{2})+\lambda_{A}\sum_{d=2}^{D}\sum_{i=1}^{|V|-1}(\mathcal{Z}_{d,i}-\mathcal{B}_{d-1,i})^{2}$

Therefore, the Hamiltonian for the MLST is:

$H_{MLST}=H_{Tree}+H_{Edges}+H_{Cst}^{(1)}+H_{Cst}^{(2)}+H_{Cst}^{(3)}$

We suggest the lower bound for the penalty coefficient of
$\lambda_{A}>\lambda_{B}|V|>0$, to ensure the ground state of the Hamiltonian
is a valid MLST solution.

To solve for the maximum leaf spanning tree, we just swap the sign of
$H_{Tree}$ to $-H_{Tree}$. The sign swap rewards leaves in the tree instead of
adding cost, hence the number of leaves is maximized.

$H_{MaxLeaf}=-H_{Tree}+H_{Edges}+H_{Cst}^{(1)}+H_{Cst}^{(2)}+H_{Cst}^{(3)}$

The proposed formulations use $\mathcal{O}(|V|^{2})$ variables and contain
$\mathcal{O}(|V|^{3})$ interactions among the variables.

##  6 Conclusion

We have provided a novel method to encode NP-Hard spanning tree problems as
QUBO instances. We leveraged the well-known permutation problem method to
encode the TSP as a QUBO, and tweaked it to apply it to spanning trees.

For the kMST, our novel formulation of $\mathcal{O}(|V|k)$ variables yields an
improvement in the number of variables required to encode the problem compared
to related strategies that require $\mathcal{O}(|V|^{2})$ variables. For the
DCMST and for the MLST, our novel formulations use $\mathcal{O}(|V|^{2})$
variables and match related encodings with regards to the number of variables.

Future work on this topic is an invitation to transfer recent improvements
from QUBO research of the TSP into spanning tree problems. In particular, the
use of Higher Order Binary Optimization seems especially promising as it
reduces the number of binary variables and qubits to encode spanning tree
instances.

## References

  * [1] Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., Katzgraber, H.G.: Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics 7 (Apr 2019). https://doi.org/10.3389/fphy.2019.00048
  * [2] Choi, V.: Minor-embedding in adiabatic quantum computation: II. minor-universal graph design. Quantum Information Processing 10(3), 343–353 (Oct 2010). https://doi.org/10.1007/s11128-010-0200-3, https://doi.org/10.1007/s11128-010-0200-3
  * [3] Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm (2014). https://doi.org/10.48550/arXiv.1411.4028
  * [4] Fischetti, M., Hamacher, H.W., Jørnsten, K., Maffioli, F.: Weighted k-cardinality trees: Complexity and polyhedral structure. Networks 24(1), 11–21 (Jan 1994). https://doi.org/10.1002/net.3230240103
  * [5] Fowler, A.: Improved QUBO formulations for D-Wave quantum computing. Master’s thesis, University of Auckland (2017), http://hdl.handle.net/2292/35722
  * [6] Galbiati, G., Maffioli, F., Morzenti, A.: A short note on the approximability of the maximum leaves spanning tree problem. Information Processing Letters 52(1), 45–49 (Oct 1994). https://doi.org/10.1016/0020-0190(94)90139-2
  * [7] Glos, A., Krawiec, A., Zimborás, Z.: Space-efficient binary optimization for variational quantum computing. npj Quantum Information 8(1) (Apr 2022). https://doi.org/10.1038/s41534-022-00546-y
  * [8] Glover, F., Kochenberger, G., Hennig, R., Du, Y.: Quantum bridge analytics i: a tutorial on formulating and using QUBO models. Annals of Operations Research 314(1), 141–183 (Apr 2022). https://doi.org/10.1007/s10479-022-04634-2
  * [9] Johnson, M.W., Amin, M.H.S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Johansson, J., Bunyk, P., Chapple, E.M., Enderud, C., Hilton, J.P., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I., Rich, C., Thom, M.C., Tolkacheva, E., Truncik, C.J.S., Uchaikin, S., Wang, J., Wilson, B., Rose, G.: Quantum annealing with manufactured spins. Nature 473(7346), 194–198 (May 2011). https://doi.org/10.1038/nature10012
  * [10] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (May 1983). https://doi.org/10.1126/science.220.4598.671
  * [11] Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7(1), 48–50 (1956). https://doi.org/10.1090/s0002-9939-1956-0078686-7
  * [12] Lucas, A.: Ising formulations of many NP problems. Frontiers in Physics 2 (2014). https://doi.org/10.3389/fphy.2014.00005
  * [13] Nüßlein, J., Gabor, T., Linnhoff-Popien, C., Feld, S.: Algorithmic QUBO formulations for k-SAT and hamiltonian cycles. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. ACM (Jul 2022). https://doi.org/10.1145/3520304.3533952
  * [14] Prim, R.C.: Shortest connection networks and some generalizations. Bell System Technical Journal 36(6), 1389–1401 (Nov 1957). https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
  * [15] Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., III, H.B.H.: Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica 31(1), 58–78 (Sep 2001). https://doi.org/10.1007/s00453-001-0038-2
  * [16] Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees—short or small. SIAM Journal on Discrete Mathematics 9(2), 178–200 (May 1996). https://doi.org/10.1137/s0895480194266331
  * [17] Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Information Processing Letters 105(5), 164–169 (Feb 2008). https://doi.org/10.1016/j.ipl.2007.08.030
  * [18] Silva, F.F.C., Carvalho, P.M.S., Ferreira, L.A.F.M., Omar, Y.: A qubo formulation for minimum loss spanning tree reconfiguration problems in electric power networks (2021). https://doi.org/10.48550/arXiv.2109.09659
  * [19] Vargas-Calderón, V., Parra-A., N., Vinck-Posada, H., González, F.A.: Many-qudit representation for the travelling salesman problem optimisation. Journal of the Physical Society of Japan 90(11), 114002 (nov 2021). https://doi.org/10.7566/jpsj.90.114002


#  Projections onto hyperbolas or bilinear constraint sets in Hilbert spaces

Heinz H. Bauschke, Manish Krishan Lal, and Xianfu Wang  Mathematics,
University of British Columbia, Kelowna, B.C. V1V 1V7, Canada. E-mail:
<EMAIL_ADDRESS>Mathematics, University of British Columbia, Kelowna,
B.C. V1V 1V7, Canada. E-mail<EMAIL_ADDRESS>Mathematics,
University of British Columbia, Kelowna, B.C. V1V 1V7, Canada. E-mail:
<EMAIL_ADDRESS>
(December 1, 2021)

###### Abstract

Sets of bilinear constraints are important in various machine learning models.
Mathematically, they are hyperbolas in a product space. In this paper, we give
a complete formula for projections onto sets of bilinear constraints or
hyperbolas in a general Hilbert space.

2020 Mathematics Subject Classification: Primary 41A50, 90C26; Secondary
90C20, 46C05.

Keywords: bilinear constraint set, hyperbola, orthogonal projection, nonconvex
minimization, prox-regularity.

##  1 Introduction

Throughout this paper, we assume that

$X$ is a Hilbert space with inner product
$\left\langle{\cdot},{\cdot}\right\rangle\colon X\times X\to\mathbb{R}$,  (1)

and induced norm $\|\cdot\|$. In various learning models [9, 10], Elser
utilizes projections onto the _bilinear constraint_ set:

$C_{\gamma}:=\big{\\{}{(x,y)\in X\times
X}~{}\big{|}~{}{\left\langle{x},{y}\right\rangle=\gamma}\big{\\}}$ (2)

where $\gamma\in\mathbb{R}$ is a fixed constant. Mathematically speaking, up
to a rotation, this is just a hyperbola or quadratic surface in $X\times X$.
Finding projections onto quadratic curves or surfaces algorithmically have
many practical applications; see, e.g., [6, 7, 9, 10]. If $\gamma=0$ in
$C_{\gamma}$, then $C_{0}$ becomes the set ‘cross’ in $X\times X$. The
projection formula for the ‘cross’ has been thoroughly investigated [2]. In
[9, 10], although Elser has provided some results on projections onto
$C_{\gamma}$ only when $X=\mathbb{R}^{n}$, complete mathematical details are
not presented.

_The goal of this paper is to give a complete analysis of the projection onto
the set $C_{\gamma}$ with $\gamma\neq 0$, and extend the results to a general
Hilbert space._

The remainder of the paper is organized as follows. Section 2 gives some
general properties of bilinear constraint sets. In Section 3 we focus on full
mathematical details for the existence and explicit formula of projections
onto hyperbolas. Using results from Section 3, in Sections 4–5 we provide
explicit formulas for projections onto sets of bilinear constraints. Our
notation is standard and follows largely [1, 13].

##  2 General properties of $C_{\gamma}$

In an infinite-dimensional space, the existence of projection onto a set often
requires the weak closedness of the set. Our first result says that although
the set $C_{\gamma}$ is norm closed it is not weakly closed in $X\times X$.

######  Proposition 2.1.

The set $C_{\gamma}$ is closed in the norm topology but not closed in the weak
topology in $X\times X$. In fact, $\overline{C_{\gamma}}^{\rm weak}=X\times
X$.

Proof. Evidently, $C_{\gamma}$ is norm closed. We show that
$\overline{C_{\gamma}}^{\rm weak}=X\times X$. Let $(x,y)\in X\times X$.
Consider $S=\mbox{span}\\{x,y\\}$. The orthogonal decomposition theorem gives
$X=S\oplus S^{\perp}$. Because $X$ is infinite-dimensional and $S$ is at most
two-dimensional, $S^{\perp}$ is infinite dimensional, so any orthonormal base
of $S^{\perp}$ must have a sequence $(e_{n})_{{n\in{\mathbb{N}}}}$ which
converges weakly to $0$, i.e., $e_{n}\rightharpoonup 0$; see, e.g., [11]. Also
$e_{n}\perp x$ and $e_{n}\perp y.$ Set $\xi=\gamma-\langle x,y\rangle$. Then

$\displaystyle\left\langle{x-\xi e_{n}},{y-e_{n}}\right\rangle$
$\displaystyle=\left\langle{x},{y}\right\rangle-\left\langle{x},{e_{n}}\right\rangle-\xi\left\langle{e_{n}},{y}\right\rangle+\xi\left\langle{e_{n}},{e_{n}}\right\rangle$
(3) $\displaystyle=\left\langle{x},{y}\right\rangle+\xi=\gamma,$ (4)

so $(x-\xi e_{n},y-e_{n})\in C_{\gamma}$. Since $(x-\xi
e_{n},y-e_{n})\rightharpoonup(x,y)$, we have
$(x,y)\in\overline{C_{\gamma}}^{\rm weak}$. Because $(x,y)\in X\times X$ was
arbitrary, we conclude that $X\times X\subseteq\overline{C}^{\rm weak}$.
$\hfill\quad\blacksquare$

Proposition 2.1 indicates that finding $P_{C_{\gamma}}$, i.e., projections
onto $C_{\gamma}$, might be complicated in a general Hilbert space. This
seemingly difficult issue can be completely avoided by utilizing the
structures of the optimization problem. See Subsection 3.1 below.

Our next result says that when $\gamma\neq 0$, locally around the set
$C_{\gamma}$ the projection onto the set is always single-valued.

######  Proposition 2.2.

Let $\gamma\neq 0$, and $C_{\gamma}=\big{\\{}{(x,y)\in X\times
X}~{}\big{|}~{}{\left\langle{x},{y}\right\rangle=\gamma}\big{\\}}.$ For every
$(x,y)\in C_{\gamma}$, the the following hold:

  1. (i)

$C_{\gamma}$ is prox-regular at $(x,y)$.

  2. (ii)

There exists a neighborhood of $(x,y)$ on which the projection mapping onto
$C_{\gamma}$ is monotone and Lipschitz continuous.

Proof. (i): Write $\iota_{C_{\gamma}}(x,y)=\iota_{\\{\gamma\\}}(h(x,y))$ where
$h(x,y)=\left\langle{x},{y}\right\rangle$. Let $(x,y)\in C_{\gamma}$. Then
$\nabla h(x,y)=(y,x)\neq(0,0)$ because of $\gamma\neq 0$. Being a composition
of a convex function $\iota_{\\{\gamma\\}}$ and a twice differentiable
function $h$ that is qualified at $(x,y)$, [3, Proposition 2.4] shows that
$\iota_{C_{\gamma}}$ is prox-regular at $(x,y)$, so is $C_{\gamma}$.

(ii): Apply (i) and [3, Proposition 4.4]. $\hfill\quad\blacksquare$

Observe that Proposition 2.2 also follow from [13, Proposition 13.32] and [13,
Exercise 13.38] when $X=\mathbb{R}^{n}$; and that when $\gamma=0$, $C_{0}$ is
not prox-regular at $(0,0)$. Although the projection exists locally around
$C_{\gamma}$, it is still not clear for the global existence.

##  3 Projections onto hyperbolas

For ease of analysis, we start with

$C_{\gamma}:=\big{\\{}{(x,y)\in X\times
X}~{}\big{|}~{}{h(x,y):=\left\langle{x},{y}\right\rangle-\gamma=0}\big{\\}}$

where $\gamma>0$. Our goal is to find the projection formula
$P_{C_{\gamma}}(x_{0},y_{0})$ for every $(x_{0},y_{0})\in X\times X$. That is,

$\text{minimize}\quad
f(x,y):=\|x-x_{0}\|^{2}+\|y-y_{0}\|^{2}\quad\text{subject to}\quad(x,y)\in
C_{\gamma}.$ (P)

###  3.1 Auxiliary problems and existence of projections

To determine the projection operator ${\thinspace
P\thinspace}_{\negthinspace\negthinspace C_{\gamma}}$ of the set $C_{\gamma}$,
we shall introduce two equivalently reformulated problems. First, for every
$(u_{0},v_{0})\in X\times X$, we solve the problem

$\text{minimize}\quad
f_{1}(u,v):=\|u-u_{0}\|^{2}+\|v-v_{0}\|^{2}\quad\text{subject
to}\quad(u,v)\in\tilde{C}_{1},$ ($\tilde{P}_{1}$)

where
$\tilde{C}_{1}:=\big{\\{}{(u,v)\in{X}\times{X}}~{}\big{|}~{}{h_{1}(u,v):=\norm{u}^{2}-\norm{v}^{2}-2=0}\big{\\}}.$
Next, for every $(\tilde{u}_{0},\tilde{v}_{0})\in X\times X$ we solve the
problem

$\text{minimize}\quad
f_{\gamma}(\tilde{u},\tilde{v}):=\|\tilde{u}-\tilde{u}_{0}\|^{2}+\|\tilde{v}-\tilde{v}_{0}\|^{2}\quad\text{subject
to}\quad(\tilde{u},\tilde{v})\in\tilde{C}_{\gamma},$ ($\tilde{P}_{\gamma}$)

where
$\tilde{C}_{\gamma}:=\big{\\{}{(\tilde{u},\tilde{v})\in{X}\times{X}}~{}\big{|}~{}{h_{\gamma}(\tilde{u},\tilde{v}):=\norm{\tilde{u}}^{2}-\norm{\tilde{v}}^{2}-2\gamma=0}\big{\\}}$.
Both $\tilde{C}_{1}$ and $\tilde{C}_{\gamma}$ are hyperbolas. $\tilde{P}_{1}$
and $\tilde{P}_{\gamma}$ solve for projections $P_{\tilde{C}_{1}}$ and
$P_{\tilde{C}_{\gamma}}$ respectively, and their connections to
$P_{C_{\gamma}}$ are given by the Proposition 3.2 below. Recall

######  Definition 3.1 (Rotation with an angle $\phi$).

A change of coordinates $(u,v)\in{X}\times{X}$, by rotation through an angle
$\phi$, is defined by

$\begin{bmatrix}x\\\
y\end{bmatrix}=\begin{bmatrix}\cos\phi\operatorname{Id}&-\sin\phi\operatorname{Id}\\\
\sin\phi\operatorname{Id}&\cos\phi\operatorname{Id}\end{bmatrix}\begin{bmatrix}u\\\
v\end{bmatrix}.$

Put

$A_{\phi}:=\begin{bmatrix}\cos\phi\operatorname{Id}&-\sin\phi\operatorname{Id}\\\
\sin\phi\operatorname{Id}&\cos\phi\operatorname{Id}\end{bmatrix}.$

Then $A_{\phi}A_{-\phi}=\operatorname{Id}=A_{-\phi}A_{\phi}$ and
$A^{-1}_{\phi}=A_{-\phi}$. The relationships among
$P_{C_{\gamma}},P_{\tilde{C}_{\gamma}}$ and $P_{\tilde{C}_{1}}$ are summarized
below.

######  Proposition 3.2.

The following hold:

  1. (i)

$P_{\tilde{C}_{\gamma}}=\sqrt{\gamma}P_{\tilde{C}_{1}}(\operatorname{Id}/\sqrt{\gamma}).$

  2. (ii)

$P_{C_{\gamma}}=A_{\pi/4}P_{\tilde{C}_{\gamma}}A_{-\pi/4}.$

Proof. (i): $(\tilde{P}_{1})$ is equivalent to $(\tilde{P}_{\gamma})$ by a
change of variables of scaling $\operatorname{Id}/\sqrt{\gamma}$. Indeed,
using

$\begin{bmatrix}u\\\
v\end{bmatrix}=\frac{1}{\sqrt{\gamma}}\begin{bmatrix}\tilde{u}\\\
\tilde{v}\end{bmatrix},\text{ and }\begin{bmatrix}u_{0}\\\
v_{0}\end{bmatrix}=\frac{1}{\sqrt{\gamma}}\begin{bmatrix}\tilde{u}_{0}\\\
\tilde{v}_{0}\end{bmatrix}$

$h_{\gamma}(\tilde{u},\tilde{v})=0$ becomes $h_{1}(u,v)=0$, and
$f_{\gamma}(\tilde{u},\tilde{v})$ becomes $\gamma
f_{1}(u,v)=\gamma(\|u-u_{0}\|^{2}+\|v-v_{0}\|^{2})$.

(ii): $(P)$ is equivalent to $(\tilde{P}_{\gamma})$ by a change of variables
of rational $A_{\pi/4}$. Indeed, with

$\begin{bmatrix}x\\\ y\end{bmatrix}=A_{\pi/4}\begin{bmatrix}\tilde{u}\\\
\tilde{v}\end{bmatrix},\text{ and }\begin{bmatrix}x_{0}\\\
y_{0}\end{bmatrix}=A_{\pi/4}\begin{bmatrix}\tilde{u}_{0}\\\
\tilde{v}_{0}\end{bmatrix}$

the objective
$f(x,y)=\|x-x_{0}\|^{2}+\|y-y_{0}\|^{2}=\|(x,y)-(x_{0},y_{0})\|^{2}$ can be
rewritten as

$\displaystyle f(x,y)$
$\displaystyle=\norm{A_{\frac{\pi}{4}}\begin{bmatrix}\tilde{u}-\tilde{u}_{0}\\\
\tilde{v}-\tilde{v}_{0}\end{bmatrix}}^{2}=\begin{bmatrix}\tilde{u}-\tilde{u}_{0}\\\
\tilde{v}-\tilde{v}_{0}\end{bmatrix}^{T}A_{\frac{\pi}{4}}^{T}A_{\frac{\pi}{4}}\begin{bmatrix}\tilde{u}-\tilde{u}_{0}\\\
\tilde{v}-\tilde{v}_{0}\end{bmatrix}$
$\displaystyle=\norm{\tilde{u}-\tilde{u}_{0}}^{2}+\norm{\tilde{v}-\tilde{v}_{0}}^{2},$

and $h(x,y)=\left\langle{x},{y}\right\rangle-\gamma=0$ becomes
$h_{\gamma}(\tilde{u},\tilde{v})=\|\tilde{u}\|^{2}-\|\tilde{v}\|^{2}-2\gamma=0$.
$\hfill\quad\blacksquare$

In view of Proposition 3.2(ii), to see that
$P_{C_{\gamma}}(x,y)\neq\varnothing$ for every $(x,y)\in X\times X$, the
following observation is crucial.

######  Proposition 3.3.

For every $(\tilde{u}_{0},\tilde{v}_{0})\in{X}\times{X}$, the minimization
problem

minimize $\displaystyle\quad
f_{\gamma}(\tilde{u},\tilde{v})=\|\tilde{u}-\tilde{u}_{0}\|^{2}+\|\tilde{v}-\tilde{v}_{0}\|^{2}$
(5) subject to $\displaystyle\quad
h_{\gamma}(\tilde{u},\tilde{v})=\norm{\tilde{u}}^{2}-\norm{\tilde{v}}^{2}-2\gamma=0$
(6)

always has a solution, i.e.,
$P_{\tilde{C}_{\gamma}}(\tilde{u}_{0},\tilde{v}_{0})\neq\varnothing$.

Proof. We shall illustrate only the case $\tilde{u}_{0}\neq
0,\tilde{v}_{0}\neq 0$, since the other cases are similar. We claim that the
optimization problem is essentially $2$-dimensional. To this end, we expand

$\displaystyle f_{\gamma}(\tilde{u},\tilde{v})$
$\displaystyle=\underbrace{\|\tilde{u}\|^{2}-2\left\langle{\tilde{u}},{\tilde{u}_{0}}\right\rangle+\|\tilde{u}_{0}\|^{2}}+\underbrace{\|\tilde{v}\|^{2}-2\left\langle{\tilde{v}},{\tilde{v}_{0}}\right\rangle+\|\tilde{v}_{0}\|^{2}}.$
(7)

The constraint

$h_{\gamma}(\tilde{u},\tilde{v}):=\norm{\tilde{u}}^{2}-\norm{\tilde{v}}^{2}-2\gamma=0$

means that only the norms $\|\tilde{u}\|$ and $\|\tilde{v}\|$ matter. With
$\|\tilde{u}\|$ fixed, the Cauchy-Schwarz inequality in a Hilbert space, see,
e.g., [11], shows that
$\tilde{u}\mapsto\left\langle{\tilde{u}},{\tilde{u}_{0}}\right\rangle$ will be
larger so that the first underlined part in $f_{\gamma}$ will be smaller when
$\tilde{u}$ and $\tilde{u}_{0}$ are positively co-linear, i.e,
$\tilde{u}=\alpha\tilde{u}_{0}$ for some $\alpha\geq 0$. Similarly, for fixed
$\|v\|$ the second underlined part in $f_{\gamma}$ will be smaller when
$\tilde{v}=\beta\tilde{v}_{0}$ for some $\beta\geq 0$. It follows that the
optimization problem given by (5)-(6) is equivalent to

minimize $\displaystyle\quad
g(\alpha,\beta):=(1-\alpha)^{2}\|\tilde{u}_{0}\|^{2}+(1-\beta)^{2}\|\tilde{v}_{0}\|^{2}$
(8) subject to $\displaystyle\quad
g_{1}(\alpha,\beta):=\alpha^{2}\norm{\tilde{u}_{0}}^{2}-\beta^{2}\norm{\tilde{v}_{0}}^{2}-2\gamma=0,\alpha\geq
0,\beta\geq 0.$ (9)

Because $g:\mathbb{R}^{2}\rightarrow\mathbb{R}$ is continuous and coercive,
and $g_{1}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ is continuous, we conclude
that the optimization problem given by (8)-(9) has a solution.
$\hfill\quad\blacksquare$

We are now ready for the investigation of projections onto
$\tilde{C}_{1},\tilde{C}_{\gamma}$ and $C_{\gamma}$.

###  3.2 Finding the projection $P_{\tilde{C}_{1}}$

Note that

$\nabla f_{1}(u,v)=(2(u-u_{0}),2(v-v_{0}))\quad\text{and}\quad\nabla
h_{1}(u,v)=(2u,-2v).$ (10)

By [4, Proposition 4.1.1], every solution of ($\tilde{P}_{1}$) satisfies the
necessarily conditions, i.e., the KKT system of ($\tilde{P}_{1}$), given by

$\displaystyle(1+\lambda)u=u_{0}$ (11) $\displaystyle(1-\lambda)v=v_{0}$ (12)
$\displaystyle\|u\|^{2}-\|v\|^{2}-2=0.$ (13)

######  Lemma 3.4.

Let $u_{0}\neq 0,v_{0}\neq 0$. If $(u,v,\lambda)$ verifies (11)–(13) and
$(u,v)$ is an optimal solution of problem ($\tilde{P}_{1}$), then the Lagrange
multiplier $\lambda$ satisfies $|\lambda|<1$.

Proof. The constraint set

$\|u\|^{2}-\|v\|^{2}=2,$

has a special structure: replacing $u$ by $-u$, or $v$ by $-v$ the constraint
is still verified. Also consider

$f(u,v)=\|u-u_{0}\|^{2}+\|v-v_{0}\|^{2}=\|u_{0}\|^{2}-2\left\langle{u_{0}},{u}\right\rangle+\|u\|^{2}+\|v_{0}\|^{2}-2\left\langle{v_{0}},{v}\right\rangle+\|v\|^{2},$

Given $u_{0}\text{ and }v_{0}$, for fixed $\|u\|$ and $\|v\|$, $f(u,v)$
becomes smaller if one choose $\left\langle{u_{0}},{u}\right\rangle\geq 0$,
and $\left\langle{v_{0}},{v}\right\rangle\geq 0$. Indeed, one can do so by
replacing $u$ by $-u$ or $v$ by $-v$ if needed. Now by (11) and (12),

$(1+\lambda)\left\langle{u_{0}},{u}\right\rangle=\|u_{0}\|^{2},\text{ and
}(1-\lambda)\left\langle{v_{0}},{v}\right\rangle=\|v_{0}\|^{2}.$

Because $u_{0}\neq 0,v_{0}\neq 0$, we have
$\left\langle{u_{0}},{u}\right\rangle>0,\left\langle{v_{0}},{v}\right\rangle>0$
so that $1+\lambda>0,1-\lambda>0$. Hence $|\lambda|<1.$
$\hfill\quad\blacksquare$

######  Proposition 3.5.

Let $u_{0}\neq 0,v_{0}\neq 0$. Define
$p\coloneqq\norm{u_{0}}^{2}-\norm{v_{0}}^{2}$ and
$q\coloneqq\norm{u_{0}}^{2}+\norm{v_{0}}^{2}$. Suppose that $u,v\in{X}$ and
$\lambda\in\mathbb{R}$ verify (11)-(13) and $(u,v)$ is an optimal solution to
($\tilde{P}_{1}$). Then the following hold:

  1. (i)

$u=\frac{u_{0}}{(1+\lambda)}$, $v=\frac{v_{0}}{(1-\lambda)}$, and
$(1-\lambda)^{2}\norm{u_{0}}^{2}-(1+\lambda)^{2}\norm{v_{0}}^{2}=2(1-\lambda^{2})^{2}$.

  2. (ii)

The objective function has
$f_{1}(u,v)=\lambda^{2}\bigg{(}\frac{\|u_{0}\|^{2}}{(1+\lambda)^{2}}+\frac{\|v_{0}\|^{2}}{(1-\lambda)^{2}}\bigg{)}.$

  3. (iii)

$\lambda$ is the unique solution of

$H(\lambda)\coloneqq\frac{(\lambda^{2}+1)p-2\lambda
q}{2(1-\lambda^{2})^{2}}-1=0$ (14)

in $\left]-1,1\right[$.

Proof. (i): Because $u_{0}\neq 0,v_{0}\neq 0$, we obtain $|\lambda|<1$,
$u=\frac{u_{0}}{(1+\lambda)}$ and $v=\frac{v_{0}}{(1-\lambda)}$ by Lemma 3.4
and (11)-(12). Then we have the following equivalences

$\displaystyle\norm{u}^{2}-\norm{v}^{2}=2$
$\displaystyle\Leftrightarrow\frac{\norm{u_{0}}^{2}}{(1+\lambda)^{2}}-\frac{\norm{v_{0}}^{2}}{(1-\lambda)^{2}}=2$
(15)
$\displaystyle\Leftrightarrow(1-\lambda)^{2}\norm{u_{0}}^{2}-(1+\lambda)^{2}\norm{v_{0}}^{2}=2(1-\lambda)^{2}(1+\lambda)^{2}$
(16)
$\displaystyle\Leftrightarrow(1-\lambda)^{2}\norm{u_{0}}^{2}-(1+\lambda)^{2}\norm{v_{0}}^{2}=2(1-\lambda^{2})^{2}.$
(17)

(ii): Substitute $u=\frac{u_{0}}{(1+\lambda)}$ and
$v=\frac{v_{0}}{(1-\lambda)}$ in $f_{1}$.
(iii): By (i), we have

$(1-\lambda)^{2}\norm{u_{0}}^{2}-(1+\lambda)^{2}\norm{v_{0}}^{2}=2(1-\lambda^{2})^{2}.$
(18)

Since

$\displaystyle(1-\lambda)^{2}\norm{u_{0}}^{2}-(1+\lambda)^{2}\norm{v_{0}}^{2}$
(19)
$\displaystyle=\big{(}1+\lambda^{2}-2\lambda\big{)}\|u_{0}\|^{2}-\big{(}1+\lambda^{2}+2\lambda\big{)}\|v_{0}\|^{2}$
(20)
$\displaystyle=\lambda^{2}\big{(}\|u_{0}\|^{2}-\|v_{0}\|^{2}\big{)}+\big{(}\|u_{0}\|^{2}-\|v_{0}\|^{2}\big{)}-2\lambda\big{(}\|u_{0}\|^{2}+\|v_{0}\|^{2}\big{)}$
(21) $\displaystyle=\lambda^{2}p+p-2\lambda q,$ (22)

using 22 on left side of 18, we obtain $\lambda^{2}p+p-2\lambda
q=2(1-\lambda^{2})^{2}$, a univariate quartic equation in $\lambda$,
equivalently,

$\displaystyle H(\lambda)\coloneqq\frac{(\lambda^{2}+1)p-2\lambda
q}{2(1-\lambda^{2})^{2}}-1=0.$ (23)

We show that 23 has a unique solution in $]-1,1[$. Because $u_{0}\neq
0,v_{0}\neq 0$, we know that $q>|p|$, and using it along-with $|\lambda|<1$
from Lemma 3.4, we get $p\lambda\leq|p||\lambda|\leq q|\lambda|$, and

$\displaystyle H^{\prime}(\lambda)$
$\displaystyle=\frac{1}{(1-\lambda^{2})^{3}}\big{(}-q(1+3\lambda^{2})+p(\lambda^{3}+3\lambda)\big{)}$
(24)
$\displaystyle\leq\frac{1}{(1-\lambda^{2})^{3}}\big{(}-q(1+3\lambda^{2})+|p||\lambda|(\lambda^{2}+3)\big{)}$
(25)
$\displaystyle\leq\frac{1}{(1-\lambda^{2})^{3}}\big{(}-q(1+3\lambda^{2})+q|\lambda|(\lambda^{2}+3)\big{)}$
(26)
$\displaystyle=\frac{q}{(1-\lambda^{2})^{3}}\big{(}(|\lambda|-1)^{3}\big{)}$
(27)
$\displaystyle=\frac{-q}{((1-|\lambda|)(1+|\lambda|))^{3}}\big{(}(1-|\lambda|)^{3}\big{)}$
(28) $\displaystyle=\frac{-q}{(1+|\lambda|)^{3}}.$ (29)

Since $q=\|u_{0}\|^{2}+\|v_{0}\|^{2}>0$ and $(1+|\lambda|)^{3}>0$, we have
$H^{\prime}(\lambda)<0$ on $]-1,1[$, which implies $H(\lambda)$ is strictly
decreasing on $]-1,1[$. Notice that $\lambda=\pm 1$ are vertical asymptotes
because at $\lambda=\pm 1$ the numerator of $H(\lambda)$ is,
$H(-1)=2(p+q)=4\|u_{0}\|^{2}>0$ and $H(1)=2(p-q)=-4\|v_{0}\|^{2}<0$, so that
$\lim_{\lambda\to 1^{-}}H(\lambda)=-\infty$ and
$\lim_{\lambda\to-1^{+}}H(\lambda)=+\infty$. Since $H$ is continuous, strictly
decreasing, and its range is $]-\infty,\infty[$, we conclude that
$H(\lambda)=0$ has a unique zero in $]-1,1[$. $\hfill\quad\blacksquare$

######  Remark 3.6.

As indicated in [9], an approximate solution to (14) can be found by the
Bisection method, Newton’s method, or a combined version. See also [5, 8].

######  Theorem 3.7.

Let $u_{0},v_{0}\in{X}$, $u_{0}\neq 0,v_{0}\neq 0$. Then ${\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}(u_{0},v_{0})$ is a
singleton, and

${\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}(u_{0},v_{0})=\left\\{\begin{bmatrix}\frac{u_{0}}{1+\lambda}\\\
\frac{v_{0}}{1-\lambda}\end{bmatrix}\right\\}$

in which $\lambda$ is the unique root of $H(\lambda)=0$ in $]-1,1[$ where

$\displaystyle H(\lambda)=\frac{(\lambda^{2}+1)p-2\lambda
q}{2(1-\lambda^{2})^{2}}-1,\text{ and }$ $\displaystyle
p=\norm{u_{0}}^{2}-\norm{v_{0}}^{2},\quad
q=\norm{u_{0}}^{2}+\norm{v_{0}}^{2}.$

Proof. Apply Proposition 3.5. $\hfill\quad\blacksquare$

######  Theorem 3.8.

Let $u_{0},v_{0}\in{X}$ with either $u_{0}=0$ or $v_{0}=0$.

  1. (i)

When $u_{0}=0,$ we have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}(0,v_{0})=\left\\{\begin{bmatrix}u\\\
\frac{v_{0}}{2}\end{bmatrix}\bigg{|}\
\|u\|^{2}=2+\frac{\|v_{0}\|^{2}}{4}\right\\}.$ (30)

  2. (ii)

a) When $v_{0}=0$ and $\|u_{0}\|\geq 2\sqrt{2}$, we have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}(u_{0},0)=\left\\{\begin{bmatrix}\frac{u_{0}}{2}\\\
v\end{bmatrix}\bigg{|}\ \|v\|^{2}=\frac{\|u_{0}\|^{2}}{4}-2\right\\}.$ (31)

b) When $v_{0}=0$ and $0<\|u_{0}\|<2\sqrt{2}$, we have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}(u_{0},0)=\left\\{\begin{bmatrix}\sqrt{2}\frac{u_{0}}{\|u_{0}\|}\\\
0\end{bmatrix}\right\\}.$ (32)

Proof. By (11)–(13), $(u,v)\in{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}(u_{0},v_{0})$
satisfies:

$\displaystyle(1+\lambda)u=u_{0}$ (33) $\displaystyle(1-\lambda)v=v_{0}$ (34)
$\displaystyle\|u\|^{2}-\|v\|^{2}=2,$ (35)

for some $\lambda\in\mathbb{R}$.

(i): $u_{0}=0,v_{0}\neq 0$. (33) yields $(1+\lambda)u=0\Rightarrow$ either
$1+\lambda=0$ or $u=0$. We consider two cases.

Case 1: $1+\lambda=0$, i.e., $\lambda=-1$. By (34), $2v=v_{0}\Rightarrow
v=\frac{v_{0}}{2}$ and then by (35),
$\|u\|^{2}-\|\frac{v_{0}}{2}\|^{2}=2\Rightarrow\|u\|^{2}=2+\frac{\|v_{0}\|^{2}}{4}$.
So, $(u,v)=\left(u,\frac{v_{0}}{2}\right)$ and
$\|u\|^{2}=2+\frac{\|v_{0}\|^{2}}{4}$. The objective function is

$\displaystyle
f(u,v)=\|u-u_{0}\|^{2}+\|v-v_{0}\|^{2}=\|u\|^{2}+\norm{\frac{v_{0}}{2}}^{2}=2+\frac{\|v_{0}\|^{2}}{4}+\frac{\|v_{0}\|^{2}}{4}=2+\frac{\|v_{0}\|^{2}}{2}.$

Case 2: $u=0$. By (35), $(0-\|v\|^{2})=2$, which is impossible.
Combining both cases we have the formula (30).

(ii): $u_{0}\neq 0$, but $v_{0}=0$, which implies $(1-\lambda)v=0$ by (34). We
consider two cases:

Case 1: $1-\lambda=0$, i.e., $\lambda=1$. By (33), $2u=u_{0}\Rightarrow
u=\frac{u_{0}}{2}$ and then by (35),
$\|v\|^{2}=\frac{\|u_{0}\|^{2}}{4}-2\Rightarrow\frac{\|u_{0}\|^{2}}{4}-2\geq
0\Rightarrow\|u_{0}\|^{2}\geq 8$. Thus, $(u,v)=\left(\frac{u_{0}}{2},v\right)$
with $\|v\|^{2}=\frac{\|u_{0}\|^{2}}{4}-2$, where the objective is

$\displaystyle
f(u,v)=\|u-u_{0}\|^{2}+\|v-v_{0}\|^{2}=\frac{\|u_{0}\|^{2}}{4}+\frac{\|u_{0}\|^{2}}{4}-2=\frac{\|u_{0}\|^{2}}{2}-2.$

Note that Case 1 needs $\|u_{0}\|\geq 2\sqrt{2}$.

Case 2: $v=0$. Then $\|u\|^{2}=2\Rightarrow\|u\|=\sqrt{2}$ by (35). By (33),
$|1+\lambda|\|u\|=\|u_{0}\|\Rightarrow|1+\lambda|=\frac{\|u_{0}\|}{\sqrt{2}}\Rightarrow
1+\lambda=\pm\frac{\|u_{0}\|}{\sqrt{2}}.$
Subcase 1: $1+\lambda=-\frac{\|u_{0}\|}{\sqrt{2}}$. By (33),
$u=\frac{u_{0}}{(-\frac{\|u_{0}\|}{\sqrt{2}})}=-\frac{\sqrt{2}u_{0}}{\|u_{0}\|}$.
Then

$f(u,0)=\|u-u_{0}\|^{2}+\|0-v_{0}\|^{2}=\norm{-\frac{\sqrt{2}u_{0}}{\|u_{0}\|}-u_{0}}^{2}=(\|u_{0}\|+\sqrt{2})^{2}.$

Subcase 2: $1+\lambda=\frac{\|u_{0}\|}{\sqrt{2}}.$ By (33),
$u=\frac{\sqrt{2}u_{0}}{\|u_{0}\|}$. Then

$f(u,0)=\|u-u_{0}\|^{2}+\|0-v_{0}\|^{2}=\norm{u_{0}-\frac{\sqrt{2}u_{0}}{\|u_{0}\|}}^{2}=(\|u_{0}\|-\sqrt{2})^{2}.$

Comparing Subcase 1 and Subcase 2, we obtain
$|\|u_{0}\|-\sqrt{2}|<\|u_{0}\|+\sqrt{2}$ because $\|u_{0}\|\neq 0$. That is,
Subcase 2 gives a smaller value at $(u,0)$ with
$u=\sqrt{2}\frac{u_{0}}{\|u_{0}\|}$. We need to compare it to Case 1 whenever
it happens. Note that

$\frac{\|u_{0}\|^{2}}{2}-2<(\|u_{0}\|-\sqrt{2})^{2}\quad\text{whenever}\quad\|u_{0}\|\neq
2\sqrt{2}.$

Indeed, we have

$\frac{\|u_{0}\|^{2}}{2}-2<\|u_{0}\|^{2}-2\sqrt{2}\|u_{0}\|+2\Longleftrightarrow\frac{\|u_{0}\|^{2}}{2}-2\sqrt{2}\|u_{0}\|+4>0\\\
\Longleftrightarrow(\|u_{0}\|-2\sqrt{2})^{2}>0,$

which always holds if $\|u_{0}\|\neq 2\sqrt{2}$. Hence, the nearest points are
given by

$\displaystyle\left(\frac{u_{0}}{2},v\right)\quad\text{with}\quad\|v\|^{2}=\frac{\|u_{0}\|^{2}}{4}-2,\quad\text{
when}\quad\|u_{0}\|\neq 2\sqrt{2}$ (36)
$\displaystyle\left(\frac{u_{0}}{2},0\right)=\left(\sqrt{2}\frac{u_{0}}{\|u_{0}\|},0\right),\quad\text{
when}\quad\|u_{0}\|=2\sqrt{2}.$ (37)

However, Case 1 occurs only when $\|u_{0}\|\geq 2\sqrt{2}$. Hence, when
$\|u_{0}\|\geq 2\sqrt{2}$ the nearest points are given by

$\left(\frac{u_{0}}{2},v\right)\quad\text{with}\quad\|v\|^{2}=\frac{\|u_{0}\|^{2}}{4}-2.$

When $\|u_{0}\|<2\sqrt{2}$, Case 1 is impossible. Then we only need to compare
Subcase 1 and Subcase 2. Hence, the nearest point is

$\left(\sqrt{2}\frac{u_{0}}{\|u_{0}\|},0\right)\quad\text{when}\quad\|u_{0}\|<2\sqrt{2}.$

Finally, since $\|u_{0}\|=2\sqrt{2}\Rightarrow\|v\|^{2}=2-2=0$, (36) gives
$\left(\frac{u_{0}}{2},0\right)$. Also
$\frac{\sqrt{2}}{\|u_{0}\|}=\frac{1}{2}$, therefore
$\sqrt{2}\frac{u_{0}}{\|u_{0}\|}=\tfrac{1}{2}u_{0}$. It follows that
$\left(\frac{u_{0}}{2},0\right)=\left(\sqrt{2}\frac{u_{0}}{\|u_{0}\|},0\right)$
when $\|u_{0}\|=2\sqrt{2}$, which implies that (37) can be obtained from (36)
when $\|u_{0}\|=2\sqrt{2}$. Hence formulas (31) and (32) hold.
$\hfill\quad\blacksquare$

###  3.3 Finding the projection $P_{\tilde{C}_{\gamma}}$

${\thinspace P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}$ can
be found via ${\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}$.

######  Theorem 3.9.

Let $\gamma>0,\tilde{u}_{0},\tilde{v}_{0}\in{X}$, and
$\tilde{C}_{\gamma}=\big{\\{}{(\tilde{u},\tilde{v})\in{X}\times{X}}~{}\big{|}~{}{\norm{\tilde{u}}^{2}-\norm{\tilde{v}}^{2}=2\gamma}\big{\\}}$.
Then the following hold:

  1. (i)

When $\tilde{u}_{0}\neq 0$ and $\tilde{v}_{0}\neq 0$, we have

${\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\tilde{u}_{0},\tilde{v}_{0})=\left\\{\begin{bmatrix}\frac{\tilde{u}_{0}}{1+\lambda}\\\
\frac{\tilde{v}_{0}}{1-\lambda}\end{bmatrix}\right\\},$

in which $\lambda$ is the unique root of $H(\lambda)=0$ in
$\left]-1,1\right[$, where

$\displaystyle H(\lambda)=\frac{(\lambda^{2}+1)p-2\lambda
q}{2(1-\lambda^{2})^{2}}-\gamma,~{}p=\norm{\tilde{u}_{0}}^{2}-\norm{\tilde{v}_{0}}^{2},~{}q=\norm{\tilde{u}_{0}}^{2}+\norm{\tilde{v}_{0}}^{2}.$

  2. (ii)

When $\tilde{u}_{0}=0,$ we have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(0,\tilde{v}_{0})=\left\\{\begin{bmatrix}\tilde{u}\\\
\frac{\tilde{v}_{0}}{2}\end{bmatrix}\bigg{|}\
\|\tilde{u}\|^{2}=2\gamma+\frac{\|\tilde{v}_{0}\|^{2}}{4}\right\\}.$ (38)

  3. (iii)

a) When $\tilde{v}_{0}=0$ and $\|\tilde{u}_{0}\|\geq 2\sqrt{2\gamma}$, we have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\tilde{u}_{0},0)=\left\\{\begin{bmatrix}\frac{\tilde{u}_{0}}{2}\\\
\tilde{v}\end{bmatrix}\bigg{|}\
\|\tilde{v}\|^{2}=\frac{\|\tilde{u}_{0}\|^{2}}{4}-2\gamma\right\\}.$ (39)

b) When $\tilde{v}_{0}=0$ and $0<\|\tilde{u}_{0}\|<2\sqrt{2\gamma}$, we have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\tilde{u}_{0},0)=\left\\{\begin{bmatrix}\sqrt{2\gamma}\frac{\tilde{u}_{0}}{\|\tilde{u}_{0}\|}\\\
0\end{bmatrix}\right\\}.$ (40)

Proof. Proposition 3.2(i) states

${\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\tilde{u}_{0},\tilde{v}_{0})=\sqrt{\gamma}{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{1}}\left(\frac{\tilde{u}_{0}}{\sqrt{\gamma}},\frac{\tilde{v}_{0}}{\sqrt{\gamma}}\right).$

Apply Theorem 3.7 and Theorem 3.8. $\hfill\quad\blacksquare$

##  4 Projections onto bilinear constraint set $C_{\gamma}$ when $\gamma>0$

$P_{C_{\gamma}}$ can be found via $P_{\tilde{C}_{\gamma}}$, which is the main
result of this section.

######  Theorem 4.1.

Let $\gamma>0,~{}x_{0},y_{0}\in X$, and $C_{\gamma}=\big{\\{}{(x,y)\in X\times
X}~{}\big{|}~{}{\left\langle{x},{y}\right\rangle=\gamma}\big{\\}}$. Then the
following hold:

  1. (i)

When $x_{0}\neq\pm y_{0}$, the projection is a singleton:

$\displaystyle{\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},y_{0})=\left\\{\begin{bmatrix}\frac{x_{0}-\lambda
y_{0}}{1-\lambda^{2}}\\\ \frac{y_{0}-\lambda
x_{0}}{1-\lambda^{2}}\end{bmatrix}\right\\},$

in which $\lambda$ is the unique solution of $H(\lambda)=0$ in
$\left]-1,1\right[$, where

$\displaystyle H(\lambda)=\frac{(\lambda^{2}+1)p-2\lambda
q}{2(1-\lambda^{2})^{2}}-\gamma,~{}p=2\left\langle{x_{0}},{y_{0}}\right\rangle,~{}\text{
and }q=\norm{x_{0}}^{2}+\norm{y_{0}}^{2}.$

  2. (ii)

When $x_{0}=-y_{0}$, the projection is a set:

${\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},-x_{0})=\left\\{\begin{bmatrix}\frac{x_{0}}{2}+\frac{\tilde{u}}{\sqrt{2}}\\\
-\frac{x_{0}}{2}+\frac{\tilde{u}}{\sqrt{2}}\end{bmatrix}\bigg{|}\
\|\tilde{u}\|^{2}=2\gamma+\frac{\|x_{0}\|^{2}}{2},~{}~{}\tilde{u}\in
X\right\\}.$

  3. (iii)

a) When $x_{0}=y_{0}$ and $\|x_{0}\|\geq 2\sqrt{\gamma}$, the projection is a
set:

${\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},x_{0})=\left\\{\begin{bmatrix}\frac{x_{0}}{2}-\frac{\tilde{v}}{\sqrt{2}}\\\
\frac{x_{0}}{2}+\frac{\tilde{v}}{\sqrt{2}}\end{bmatrix}\bigg{|}\
\|\tilde{v}\|^{2}=\frac{\|x_{0}\|^{2}}{2}-2\gamma,~{}~{}\tilde{v}\in
X\right\\}.$

b) When $x_{0}=y_{0}$ and $0<\|x_{0}\|<2\sqrt{\gamma}$, the projection is a
singleton:

${\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},x_{0})=\left\\{\sqrt{\gamma}\begin{bmatrix}\frac{x_{0}}{\|x_{0}\|}\\\
\frac{x_{0}}{\|x_{0}\|}\end{bmatrix}\right\\}.$

Proof. Proposition 3.2(ii) states

${\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},y_{0})=A_{\frac{\pi}{4}}{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}A_{-\frac{\pi}{4}}(x_{0},y_{0}).$
(41)

It suffices to apply Theorem 3.9. Indeed, with

$\begin{bmatrix}\tilde{u}_{0}\\\
\tilde{v}_{0}\end{bmatrix}=A_{-\pi/4}\begin{bmatrix}x_{0}\\\
y_{0}\end{bmatrix}=\begin{bmatrix}\frac{x_{0}+y_{0}}{\sqrt{2}}\\\
\frac{-x_{0}+y_{0}}{\sqrt{2}}\end{bmatrix},$ (42)

using (41) and (42) Theorem 3.9 gives:

(i): When $x_{0}\neq\pm y_{0}$, we have $\tilde{u}_{0}\neq 0,\tilde{v}_{0}\neq
0$. By Theorem 3.9(i), we get ${\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\tilde{u}_{0},\tilde{v}_{0})=[\frac{\tilde{u}_{0}}{(1+\lambda)},\frac{\tilde{v}_{0}}{(1-\lambda)}]^{T}$,
so

$\displaystyle{\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},y_{0})$
$\displaystyle=\left[{\begin{array}[]{cc}\frac{1}{\sqrt{2}}\operatorname{Id}&-\frac{1}{\sqrt{2}}\operatorname{Id}\\\
\frac{1}{\sqrt{2}}\operatorname{Id}&\frac{1}{\sqrt{2}}\operatorname{Id}\\\
\end{array}}\right]\left[{\begin{array}[]{cc}\frac{1}{1+\lambda}\operatorname{Id}&0\\\
0&\frac{1}{1-\lambda}\operatorname{Id}\\\
\end{array}}\right]\left[{\begin{array}[]{cc}\frac{1}{\sqrt{2}}\operatorname{Id}&\frac{1}{\sqrt{2}}\operatorname{Id}\\\
-\frac{1}{\sqrt{2}}\operatorname{Id}&\frac{1}{\sqrt{2}}\operatorname{Id}\\\
\end{array}}\right]\begin{bmatrix}x_{0}\\\ y_{0}\end{bmatrix}$
$\displaystyle=\left[{\begin{array}[]{cc}\frac{1}{1-\lambda^{2}}\operatorname{Id}&\frac{-\lambda}{1-\lambda^{2}}\operatorname{Id}\\\
\frac{-\lambda}{1-\lambda^{2}}\operatorname{Id}&\frac{1}{1-\lambda^{2}}\operatorname{Id}\\\
\end{array}}\right]\left[{\begin{array}[]{cc}x_{0}\\\
y_{0}\end{array}}\right].$

Also,
$\|p\|=\|\tilde{u}_{0}\|^{2}-\|\tilde{v}_{0}\|^{2}=2\left\langle{x_{0}},{y_{0}}\right\rangle,$
and
$\|q\|=\|\tilde{u}_{0}\|^{2}+\|\tilde{v}_{0}\|^{2}=\|x_{0}\|^{2}+\|y_{0}\|^{2}$.

(ii): For $x_{0}=-y_{0}$, we have
$\tilde{u}_{0}=0,\tilde{v}_{0}=-\sqrt{2}x_{0}$, so

$\displaystyle{\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},-x_{0})$ $\displaystyle=A_{\frac{\pi}{4}}{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(0,-\sqrt{2}x_{0})$
$\displaystyle=\left\\{A_{\frac{\pi}{4}}\begin{bmatrix}\tilde{u}\\\
\frac{-x_{0}}{\sqrt{2}}\end{bmatrix}\bigg{|}\|\tilde{u}\|^{2}=2\gamma+\frac{\|-\sqrt{2}x_{0}\|^{2}}{4}=2\gamma+\frac{\|x_{0}\|^{2}}{2},\tilde{u}\in
X\right\\}.$

(iii): When $x_{0}\neq-y_{0}$, and $x_{0}=y_{0}$, we have $x_{0}\neq
0,(x_{0},y_{0})=(x_{0},x_{0})$, so that $\tilde{v}_{0}=0$ and
$\tilde{u}_{0}=\frac{x_{0}+y_{0}}{\sqrt{2}}=\sqrt{2}x_{0}.$ Then
$\|\tilde{u}_{0}\|\geq 2\sqrt{2\gamma}\Leftrightarrow\|x_{0}\|\geq
2\sqrt{\gamma}.$

a) When $\|x_{0}\|\geq 2\sqrt{\gamma}$, we have

$\displaystyle{\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},x_{0})$ $\displaystyle=A_{\frac{\pi}{4}}{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\sqrt{2}x_{0},0)$
$\displaystyle=A_{\frac{\pi}{4}}\left\\{\begin{bmatrix}\frac{x_{0}}{\sqrt{2}}\\\
\tilde{v}\end{bmatrix}\bigg{|}\
\|\tilde{v}\|^{2}=\frac{\|\sqrt{2}x_{0}\|^{2}}{4}-2\gamma=\frac{\|x_{0}\|^{2}}{2}-2\gamma,\tilde{v}\in
X\right\\}.$

b) When $0<\|x_{0}\|<2\sqrt{\gamma}$, we have
$\|\tilde{u}_{0}\|<2\sqrt{2\gamma}$, so

$\displaystyle{\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},x_{0})$ $\displaystyle=A_{\frac{\pi}{4}}{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\sqrt{2}x_{0},0)=A_{\frac{\pi}{4}}\begin{bmatrix}\sqrt{2\gamma}\frac{\sqrt{2}x_{0}}{\|\sqrt{2}x_{0}\|}\\\
0\end{bmatrix}=A_{\frac{\pi}{4}}\begin{bmatrix}\sqrt{2\gamma}\frac{x_{0}}{\|x_{0}\|}\\\
0\end{bmatrix}.$

$\hfill\quad\blacksquare$

##  5 Projections onto hyperbola $\tilde{C}_{\gamma}$ and bilinear constraint
set $C_{\gamma}$ when $\gamma<0$

Armed with the results in Sections 3 and 4, we can study
$P_{\tilde{C}_{\gamma}}$ and $P_{C_{\gamma}}$ when $\gamma<0$. Define

$T_{1}:X\times X\rightarrow X\times X:(x,y)\mapsto(y,x),\text{ and }$
$T_{2}:X\times X\rightarrow X\times X:(x,y)\mapsto(x,-y).$

######  Theorem 5.1.

Let $\gamma<0,\tilde{u}_{0},\tilde{v}_{0}\in{X}$, and
$\tilde{C}_{\gamma}=\big{\\{}{(u,v)\in{X}\times{X}}~{}\big{|}~{}{\norm{u}^{2}-\norm{v}^{2}=2\gamma}\big{\\}}$.
Then the following hold:

  1. (i)

When $\tilde{u}_{0}\neq 0,\tilde{v}_{0}\neq 0$, we have

${\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\tilde{u}_{0},\tilde{v}_{0})=\left\\{\begin{bmatrix}\frac{\tilde{u}_{0}}{1-\lambda}\\\
\frac{\tilde{v}_{0}}{1+\lambda}\end{bmatrix}\right\\}$

in which $\lambda$ is the unique root of $H(\lambda)=0$ in
$\left]-1,1\right[$, where

$\displaystyle H(\lambda)=\frac{(\lambda^{2}+1)p-2\lambda
q}{2(1-\lambda^{2})^{2}}+\gamma,~{}p=\norm{\tilde{v}_{0}}^{2}-\norm{\tilde{u}_{0}}^{2},~{}\text{
and }q=\norm{\tilde{u}_{0}}^{2}+\norm{\tilde{v}_{0}}^{2}.$

  2. (ii)

When $\tilde{v}_{0}=0$, we have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(\tilde{u}_{0},0)=\left\\{\begin{bmatrix}\frac{\tilde{u}_{0}}{2}\\\
\tilde{v}\end{bmatrix}\bigg{|}\
\|\tilde{v}\|^{2}=\frac{\|\tilde{u}_{0}\|^{2}}{4}-2\gamma\right\\}.$ (43)

  3. (iii)

a) When $\tilde{u}_{0}=0$ and $\|\tilde{v}_{0}\|\geq 2\sqrt{2(-\gamma)}$, we
have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(0,\tilde{v}_{0})=\left\\{\begin{bmatrix}\tilde{u}\\\
\frac{\tilde{v}_{0}}{2}\end{bmatrix}\bigg{|}\
\|\tilde{u}\|^{2}=\frac{\|\tilde{v}_{0}\|^{2}}{4}+2\gamma\right\\}.$ (44)

b) When $\tilde{u}_{0}=0$ and $0<\|\tilde{v}_{0}\|<2\sqrt{2(-\gamma)}$, we
have

$\displaystyle{\thinspace
P\thinspace}_{\negthinspace\negthinspace\tilde{C}_{\gamma}}(0,\tilde{v}_{0})=\left\\{\begin{bmatrix}0\\\
\sqrt{2(-\gamma)}\frac{\tilde{v}_{0}}{\|\tilde{v}_{0}\|}\end{bmatrix}\right\\}.$
(45)

Proof. Since

$\underset{\begin{subarray}{c}{~{}}\end{subarray}}{\mathrm{minimize}}\;\;\|\tilde{u}-\tilde{u}_{0}\|^{2}+\|\tilde{v}-\tilde{v}_{0}\|^{2}\quad\text{subject
to}\quad\norm{\tilde{u}}^{2}-\norm{\tilde{v}}^{2}=2\gamma$

is equivalent to

$\underset{\begin{subarray}{c}{~{}}\end{subarray}}{\mathrm{minimize}}\;\;\|\tilde{v}-\tilde{v}_{0}\|^{2}+\|\tilde{u}-\tilde{u}_{0}\|^{2}\quad\text{subject
to}\quad\norm{\tilde{v}}^{2}-\norm{\tilde{u}}^{2}=2(-\gamma),$

we have $P_{\tilde{C}_{\gamma}}=T_{1}P_{\tilde{C}_{-\gamma}}T_{1}.$ It
suffices to apply Theorem 3.9. $\hfill\quad\blacksquare$

######  Theorem 5.2.

Let $\gamma<0,~{}x_{0},y_{0}\in X$, and $C_{\gamma}=\big{\\{}{(x,y)\in X\times
X}~{}\big{|}~{}{\left\langle{x},{y}\right\rangle=\gamma}\big{\\}}$. Then the
following hold:

  1. (i)

When $x_{0}\neq\pm y_{0}$, the projection is a singleton:

$\displaystyle{\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},y_{0})=\left\\{\begin{bmatrix}\frac{x_{0}+\lambda
y_{0}}{1-\lambda^{2}}\\\ \frac{y_{0}+\lambda
x_{0}}{1-\lambda^{2}}\end{bmatrix}\right\\}$

in which $\lambda$ is the unique solution of $H(\lambda)=0$ in
$\left]-1,1\right[$, where

$\displaystyle H(\lambda)=\frac{(\lambda^{2}+1)p-2\lambda
q}{2(1-\lambda^{2})^{2}}+\gamma,~{}p=-2\left\langle{x_{0}},{y_{0}}\right\rangle,~{}\text{
and }q=\norm{x_{0}}^{2}+\norm{y_{0}}^{2}.$

  2. (ii)

When $x_{0}=y_{0}$, the projection is a set:

${\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},x_{0})=\left\\{\begin{bmatrix}\frac{x_{0}}{2}+\frac{\tilde{u}}{\sqrt{2}}\\\
\frac{x_{0}}{2}-\frac{\tilde{u}}{\sqrt{2}}\end{bmatrix}\bigg{|}\
\|\tilde{u}\|^{2}=-2\gamma+\frac{\|x_{0}\|^{2}}{2},~{}~{}\tilde{u}\in
X\right\\}.$

  3. (iii)

a) When $x_{0}=-y_{0}$ and $\|x_{0}\|\geq 2\sqrt{-\gamma}$, the projection is
a set:

${\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{\gamma}}(x_{0},-x_{0})=\left\\{\begin{bmatrix}\frac{x_{0}}{2}-\frac{\tilde{v}}{\sqrt{2}}\\\
\frac{-x_{0}}{2}-\frac{\tilde{v}}{\sqrt{2}}\end{bmatrix}\bigg{|}\
\|\tilde{v}\|^{2}=\frac{\|x_{0}\|^{2}}{2}+2\gamma,~{}~{}\tilde{v}\in
X\right\\}.$

b) When $x_{0}=-y_{0}$ and $0<\|x_{0}\|<2\sqrt{-\gamma}$, the projection is a
singleton:

${\thinspace P\thinspace}_{\negthinspace\negthinspace
C_{1}}(x_{0},-x_{0})=\left\\{\sqrt{-\gamma}\begin{bmatrix}\frac{x_{0}}{\|x_{0}\|}\\\
\frac{-x_{0}}{\|x_{0}\|}\end{bmatrix}\right\\}.$

Proof. Since

$\underset{\begin{subarray}{c}{~{}}\end{subarray}}{\mathrm{minimize}}\;\;\|x-x_{0}\|^{2}+\|y-y_{0}\|^{2}\quad\text{subject
to}\quad\left\langle{x},{y}\right\rangle=\gamma$

is equivalent to

$\underset{\begin{subarray}{c}{~{}}\end{subarray}}{\mathrm{minimize}}\;\;\|x-x_{0}\|^{2}+\|z-(-y_{0})\|^{2}\quad\text{subject
to}\quad\left\langle{x},{z}\right\rangle=-\gamma,$

we have $P_{C_{\gamma}}=T_{2}P_{C_{-\gamma}}T_{2}$. It remains to apply
Theorem 4.1. $\hfill\quad\blacksquare$

## Acknowledgments

HHB and XW were supported by NSERC Discovery grants. MKL was supported by
SERB-UBC fellowship and HHB and XW’s NSERC Discovery grants. This work was
presented at the SIAM Conference on Optimization in July 20–23, 2021 by MKL.

## References

  * [1] H.H. Bauschke and P.L. Combettes, _Convex Analysis and Monotone Operator Theory in Hilbert Spaces_ , second edition, Springer, 2017.
  * [2] H.H. Bauschke, M. Krishan Lal, and X. Wang, The projection onto the cross, (2021), https://arxiv.org/abs/2108.04382.
  * [3] F. Bernard and L. Thibault, Prox-regular functions in Hilbert spaces, _Journal of Mathematical Analysis and Applications_ 303 (2005), 1–14.
  * [4] D.P. Bertsekas, _Nonlinear Programming_ , third edition, Athena Scientific, Belmont, Massachusetts, USA, 2016.
  * [5] R.L. Burden, J.D. Faires, and A.M. Burden, _Numerical Analysis_ , 10th edition, 2016.
  * [6] N. Chernov and H. Ma, Least squares fitting of quadratic curves and surfaces, In _Computer Vision_ , Editor S.R. Yoshida, Nova Science Publishers 2011; pp. 285–302.
  * [7] N. Chernov and S. Wijewickrema, Algorithms for projecting points onto conics, _Journal of Computational and Applied Mathematics_ 251 (2013), 8–21.
  * [8] D. Eberly, _Robust and Error-free Geometric Computing_ , CRC Press, 2021.
  * [9] V. Elser, Learning without loss, _Fixed Point Theory and Algorithms for Sciences and Engineering_ 2021, Paper No. 12, 51 pp.. https://doi.org/10.1186/s13663-021-00697-1
  * [10] V. Elser, Matrix product constraints by projection methods, _Journal of Global Optimization_ 68 (2017), 329–355.
  * [11] E. Kreyszig, _Introductory Functional Analysis with Applications_ , John Wiley & Sons, Inc., New York, 1989.
  * [12] D.G. Luenberger, _Optimization by Vector Space Methods_ , Wiley, 1969.
  * [13] R.T. Rockafellar and R. J-B Wets, _Variational Analysis_ , Springer-Verlag, New York, 1998.