# Accelerated Algorithms for a Class of Optimization Problems with Constraints
††thanks: The first author was supported by a Siemens Fellowship. This work
was supported in part by Boeing Strategic University Initiative.

Anjali Parashar Priyank Srivastava Anuradha M. Annaswamy A. Parashar, P.
Srivastava and A. M. Annaswamy are with the Department of Mechanical
Engineering, Massachusetts Institue of Technology.
<EMAIL_ADDRESS>
###### Abstract

This paper presents a framework to solve constrained optimization problems in
an accelerated manner based on High-Order Tuners (HT). Our approach is based
on reformulating the original constrained problem as the unconstrained
optimization of a loss function. We start with convex optimization problems
and identify the conditions under which the loss function is convex. Building
on the insight that the loss function could be convex even if the original
optimization problem is not, we extend our approach to a class of nonconvex
optimization problems. The use of a HT together with this approach enables us
to achieve a convergence rate better than state-of-the-art gradient-based
methods. Moreover, for equality-constrained optimization problems, the
proposed method ensures that the state remains feasible throughout the
evolution, regardless of the convexity of the original problem.

##  I Introduction

Several problems in a wide range of fields such as adaptive control, machine
learning, and optimization [1, 2, 3, 4] utilize gradient-descent based
approaches. In adaptive control, decision making in the form of reducing a
performance error as well ensuring that the learning error in parameters
reduces to zero as well as learning the unknown parameters of the system, both
in realtime are the underlying goals. A gradient-descent approach is often
employed to realize both goals, first to obtain a fast convergence of the
performance error and then, to reduce the learning error. In machine learning,
fast and correct training of models such as neural networks is sought after,
which necessitates the reduction of an underlying loss function using a
gradient-based approach. Optimization approaches require the solution of an
augmented Lagrangian in an expedient manner, through a gradient-descent
method. All of these solutions have to be achieved often in the presence of
various constraints. Conservation equations invariably introduces equality
constraints in the form of momentum, mass, or energy balance, while capacity
limits introduce inequality constraints. Given the importance of the fast
convergence in all these problems, there is a need for algorithms that can
lead to an order of magnitude improvement in the speed of convergence, both
performance and learning errors, while retaining stability. This paper
proposes such an algorithm.

Recently, a class of High-order Tuners (HT) was proposed in continuous-time
[5] and in discrete-time [6] for a large class of dynamic systems for the
purpose of estimation of unknown parameters. The estimation problem for this
class of systems can be reformulated as a linear regression problem, where the
underlying regressors correspond to various system variables that can be
measured, including inputs, outputs, and states. Each of these high-order
tuners was shown to result in a stable performance error when the regressors
were time-varying. One of these tuners was extended in [7] for a class of
nonlinear problems where the underlying error model is still based on linear
regression. The motivation for these methods come from adaptive control
perspectives in [8, 9] and optimization perspectives [10, 4]. In [11], these
results were extended to convex functions, and shown that the high-order
tuners are capable of leading to stable performance with a potential for
accelerated convergence of the performance error to zero. However, all the
aforementioned works focus on optimization problems without constraints. The
work [12] proposes a framework to employ Nesterov’s accelerated algorithm for
equality-constrained convex optimization problems.

In this paper, we extend the results of HT in [6] and [11] for optimization in
the presence of both equality and inequality constraints. For equality-
constrained optimization problems, we show both for convex as well as
nonconvex settings, that HT-based algorithms can be derived and shown to lead
to a stable behavior while guaranteeing the feasibility at all times. Our
solution strategy is based on reformulating the original problem as the
unconstrained optimization of a loss function proposed in [13] and identifying
the conditions under which the loss function is convex as well as strongly
convex. We show how these algorithms can be extended to the case when
inequality constraints are present as well. Conditions under which stable
behavior can be guaranteed are clearly delineated in all cases.

The organization of the paper is as follows. Section II outlines the problem
statement and the approach we adopt to find its solution, along with a few
preliminaries on convex analysis and constrained optimization. In Section III,
we first propose a HT-based algorithm for equality-constrained convex
optimization problems and based on that, generalize our treatment to general
convex problems involving inequality constraints. We then extend our approach
for convex optimization to a class of nonconvex problems in Section IV. In
Section V, we summarize the main contributions of the paper and outline a few
future research directions.

##  II Problem Statement

We consider optimization problems of the form

$\displaystyle\min$ $\displaystyle f(x)$ (1) s.t. $\displaystyle h(x)=0$
$\displaystyle g(x)\leq 0,$

where $x\in\operatorname{\mathbb{R}}^{n}$ is the decision variable,
$f:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}$,
$h:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}^{m}$, and
$g:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}^{p}$ are
continuously differentiable functions. Without loss of generality, we assume
that problem (1) is not overdetermined, i.e., $m\leq n$.

Our aim is to design recursive algorithms that solve (1), exhibiting
accelerated convergence as proposed by Nesterov for unconstrained convex
optimization, cf. [10]. Our approach is based on reformulating the original
problem as the unconstrained optimization of a loss function and then using
high-order tuners for accelerated convergence, cf. [11]. To satisfy
constraints closely during the evolution, we employ a constraint-completion
and correction procedure described below. As will become apparent, our
approach will rely on ensuring that an underlying loss function is convex. We
first show that this is indeed the case if the optimization problem is convex
in Section III. We then generalize our treatment to a class of nonconvex
optimization problems in Section IV.

Before proceeding to the technical content of the paper, we present our
notational conventions and review basic concepts from convex analysis and
constrained optimization below.

### Notation

Let $\operatorname{\mathbb{R}}$ denote the set of real numbers. $\|.\|$
denotes the 2-norm of a vector or matrix. For a continuously differentiable
function $f:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}$,
$\nabla f$ denotes its gradient. $(.)^{T}$ denotes the transpose of a vector
or matrix. For vectors $x,y\in\operatorname{\mathbb{R}}^{n}$, $x\geq y$
implies that the inequality holds elementwise. For a vector
$x\in\operatorname{\mathbb{R}}^{n}$, with $1\leq i<j\leq n$, $x_{i:j}$ denotes
the subvector with elements from the $i$-th entry of $x$ to the $j$-th entry.

### Convex analysis

Here we present the basics of convex analysis following [14, 4]. A set
$\Omega\in\operatorname{\mathbb{R}}^{n}$ is convex if for all $x,y\in\Omega$,
$\lambda x+(1-\lambda)y\in\Omega$ for all $\lambda\in(0,1)$.

######  Definition 1.

(Convex functions): A function
$f:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}$ is convex on a
convex set $\Omega$ if for all $x,y\in\Omega$,

$f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y),$

for all $\lambda\in(0,1)$.

######  Definition 2.

(Strongly convex functions): A continuously differentiable function $f$ is
$\mu$-strongly convex on $\Omega$ if there exists a $\mu>0$ such that for all
$x,y\in\Omega$,

$f(\lambda x+(1-\lambda)y)\leq\lambda
f(x)+(1-\lambda)f(y)-\dfrac{1}{2}\mu\lambda(1-\lambda)\|x-y\|^{2},$

for all $\lambda\in(0,1)$.

######  Definition 3.

($\overline{L}$-smooth convex functions): A continuously differentiable
function $f$ is $\overline{L}$-smooth convex on $\Omega$ if it is convex and
there exists an upper bound $\overline{L}>0$ on the Lipschitz constant of its
gradient, i.e.,

$\dfrac{\|\nabla f(x)-\nabla f(y)\|}{\|x-y\|}\leq\overline{L},$

for all $x,y\in\Omega$.

A similar definition could be stated for $\overline{L}$-smooth strongly convex
functions but we omit it here to avoid repetition.

### Nonlinear optimization via constraint-completion and correction

Consider the nonlinear optimization problem (1) and define a loss function
$\operatorname{\mathcal{L}}:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}$,
consisting of the original objective function and soft loss terms penalizing
the constraint violation as

$\operatorname{\mathcal{L}}(x)=f(x)+\lambda_{h}\|h(x)\|^{2}+\lambda_{g}\|\operatorname{\operatorname{softplus}}(g(x))\|^{2},$

where $\lambda_{h},\lambda_{g}>0$ are design parameters. Given
$y\in\operatorname{\mathbb{R}}^{p}$, the function
$\operatorname{\operatorname{softplus}}:\operatorname{\mathbb{R}}^{p}\to\operatorname{\mathbb{R}}^{p}$
is defined as

$\operatorname{\operatorname{softplus}}(y)=\log(1+e^{y}),$

and serves as a smooth approximation to ReLU to ensure that
$\operatorname{\mathcal{L}}$ is continuously differentiable. We employ a
constraint-completion and correction approach to leverage the fact that
equality constraints introduce linear dependencies in the feasible solution
space, as in [13]. Building on this insight and assuming that problem (1) is
not overdetermined, $x$ is partitioned into an independent variable
$\theta\in\operatorname{\mathbb{R}}^{m}$ and a dependent variable
$z\in\operatorname{\mathbb{R}}^{n-m}$,

$x=[\theta^{T}\quad z^{T}]^{T}.$

We assume that $h$ is such that given $m$ entries of $x$, its remaining
$(n-m)$ entries can be computed either in closed form or recursively. In other
words, we assume that we have knowledge of the function
$p:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n-m}$ such that

$h([\theta^{T}\quad p(\theta)^{T}]^{T})=0,$

holds for all $\theta\in\mathbb{R}^{m}$. For all the points where
$\frac{\partial h}{\partial z}\neq 0$, existence and uniqueness of $p$ is
guaranteed from the Implicit Function theorem. The reduction of variable
dimension as explained above ensures that equality constraints are always
satisfied.

Using the function $p(\cdot)$ defined as above, we now define a modified loss
function $l:\mathbb{R}^{m}\rightarrow\mathbb{R}$ as

$l(\theta)=\mathcal{L}([\theta^{T}\quad p(\theta)^{T}]^{T}).$

The optimization problem in (1) is now reformulated as an unconstrained
minimization problem given by

$\min l(\theta),$

with $\theta\in\mathbb{R}^{m}$ as the decision variable. Depending on the
information about the mapping $p$, gradient of the modified loss function
could be computed either explicitly or using the Implicit Function theorem as
in [15].

The above completion procedure takes care of the equality constraints.
However, there is no guarantee associated with the satisfaction of inequality
constraints. As will be shown later, we employ a gradient-based correction
procedure that employs penalty terms using the
$\operatorname{\operatorname{softplus}}$ function above and corrections that
allow the solution to approach the feasible region along the manifold of
points satisfying the equality constraints.

##  III Convex Optimization Problems

In this section, we consider convex optimization problems in the general form

$\displaystyle\min$ $\displaystyle f(x)$ (2) s.t. $\displaystyle Ax=b$
$\displaystyle g(x)\leq 0,$

where $x\in\operatorname{\mathbb{R}}^{n}$ is the decision variable,
$f:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}$ and
$g:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}^{p}$ are
continuously differentiable (strongly) convex functions,
$A\in\operatorname{\mathbb{R}}^{m\times n}$ and
$b\in\operatorname{\mathbb{R}}^{m}$. We start with problems involving just the
equality constraints and then generalize our approach to problems involving
both equality and inequality constraints.

###  III-A Equality-constrained convex optimization

Equality-constrained convex optimization problems have the general structure

$\displaystyle\min$ $\displaystyle f(x)$ (3) s.t. $\displaystyle Ax=b.$

With $\lambda_{h}>0$, the loss function $\operatorname{\mathcal{L}}$ and the
modified loss function $l$ take the following forms:

$\displaystyle\operatorname{\mathcal{L}}(x)=$ $\displaystyle
f(x)+\lambda_{h}\|Ax-b\|^{2},$ (4a) $\displaystyle l(\theta)=$ $\displaystyle
f([\theta^{T}\;p(\theta)^{T}]^{T}).$ (4b)

Here we have used the fact that
$\lambda_{h}\|A[\theta^{T}\;p(\theta)^{T}]^{T}-b\|^{2}=0$. We note that $p$ is
an affine function of $\theta$. Let

$p(\theta)=P\theta+q,$ (5)

where $P\in\operatorname{\mathbb{R}}^{(n-m)\times m}$ and
$q\in\operatorname{\mathbb{R}}^{n-m}$. $\operatorname{\mathcal{L}}$ is convex
by construction. We characterize the convexity properties of $l$ in the
following result.

######  Proposition III.1.

(Convexity of the modified loss function for equality-constrained convex
programs): For the equality-constrained convex optimization problem (3),
assume $f$ is a $\overline{L}$-smooth convex function, and let

$\displaystyle\overline{M}=\sqrt{1+\|P\|}\overline{L}.$ (6)

Then $l$ is $\overline{M}$-smooth convex.

###### Proof.

Convexity of $l$ follows in a straightforward manner from the definitions of
$l$ and $p$ in (4b) and (5) respectively, and the convexity of $f$. For the
$\overline{M}$-smoothness, using the chain rule, we have

$\displaystyle\dfrac{dl}{d\theta}=$ $\displaystyle\dfrac{\partial
l}{\partial\theta}+\dfrac{\partial l}{\partial p(\theta)}\dfrac{\partial
p(\theta)}{\partial\theta}.$

Hence

$\displaystyle\nabla l=\nabla f_{1:m}+P^{T}\nabla f_{m+1:n}.$

Let us consider the gradient of $l$ at
$\theta_{1},\theta_{2}\in\operatorname{\mathbb{R}}^{m}$ and examine the
Lipschitz constant of $l$.

$\displaystyle\dfrac{\|\nabla l(\theta_{1})-\nabla
l(\theta_{2})\|}{\|\theta_{1}-\theta_{2}\|}\leq$ $\displaystyle\dfrac{\|\nabla
f_{1:m}(\theta_{1})-\nabla f_{1:m}(\theta_{2})\|}{\|\theta_{1}-\theta_{2}\|}$
$\displaystyle+$ $\displaystyle\dfrac{\|P^{T}(\nabla
f_{m+1:n}(\theta_{1})-\nabla
f_{m+1:n}(\theta_{2}))\|}{\|\theta_{1}-\theta_{2}\|}$

Since $\|\nabla f_{i:j}\|\leq\|\nabla f\|$ for all $i,j$, we have

$\displaystyle\dfrac{\|\nabla l(\theta_{1})-\nabla
l(\theta_{2})\|}{\|\theta_{1}-\theta_{2}\|}\leq\dfrac{(1+\|P\|)\|\nabla
f(x_{1})-\nabla f(x_{2})\|}{\|\theta_{1}-\theta_{2}\|}$ (7)

To write the denominator of the above expression in terms of $x_{1}$ and
$x_{2}$, remember that

$\displaystyle\|\theta_{1}-\theta_{2}\|^{2}+\|P\theta_{1}-P\theta_{2}\|^{2}=\|x_{1}-x_{2}\|^{2}.$

Using properties of the norm,

$\displaystyle\|\theta_{1}-\theta_{2}\|^{2}+\|P\|\|\theta_{1}-P\theta_{2}\|^{2}\geq$
$\displaystyle\|x_{1}-x_{2}\|^{2}$
$\displaystyle\|\theta_{1}-\theta_{2}\|\geq\dfrac{\|x_{1}-x_{2}\|}{\sqrt{1+\|P\|}}.$
(8)

Using (7) and (8), we have

$\displaystyle\dfrac{\|\nabla l(\theta_{1})-\nabla
l(\theta_{2})\|}{\|\theta_{1}-\theta_{2}\|}\leq$
$\displaystyle\dfrac{\sqrt{1+\|P\|}\|\nabla f(x_{1})-\nabla
f(x_{2})\|}{\|x_{1}-x_{2}\|}$ $\displaystyle\leq$
$\displaystyle\sqrt{1+\|P\|}\overline{L},$

where the last inequality follows from the $\overline{L}$-smoothness property
of $f$. ∎

The next result extends Proposition III.1 to the case of strongly convex
functions.

######  Corollary III.2.

(Strong convexity of the modified loss function for equality-constrained
convex programs): For the equality-constrained convex optimization problem
(3), assume $f$ is a $\overline{L}$-smooth and $\mu$-strongly convex function.
Then $l$ is $\overline{M}$-smooth and $\mu$-strongly convex, where
$\overline{M}$ is defined in equation (6).

###### Proof.

Consider $\theta_{1},\theta_{2}\in\operatorname{\mathbb{R}}^{m}$. Now consider
$x_{1},x_{2}\in\operatorname{\mathbb{R}}^{n}$ defined as
$x_{1}=[\theta_{1}^{T}\;\;p(\theta_{1})^{T}]^{T}$ and
$x_{1}=[\theta_{2}^{T}\;\;p(\theta_{2})^{T}]^{T}$. Then from the properties of
$f$, it follows that

$\displaystyle f(\lambda x_{1}+(1-\lambda)x_{2})\leq$ $\displaystyle\lambda
f(x_{1})+(1-\lambda)f(x_{2})$
$\displaystyle-\dfrac{1}{2}\mu\lambda(1-\lambda)\|x_{1}-x_{2}\|^{2},$

for all $\lambda\in(0,1)$. Using the fact that
$\|\theta_{1}-\theta_{2}\|^{2}\leq\|x_{1}-x_{2}\|^{2}$, we have

$\displaystyle f(\lambda x_{1}+(1-\lambda)x_{2})\leq$ $\displaystyle\lambda
f(x_{1})+(1-\lambda)f(x_{2})$
$\displaystyle-\dfrac{1}{2}\mu\lambda(1-\lambda)\|\theta_{1}-\theta_{2}\|^{2}.$

Rest of the proof follows from the definition of $l$ and the proof of
Proposition III.1. ∎

Now that we have established the convexity and smoothness properties of the
modified loss function $l$, we leverage the properties of high-order tuners
[6, 11] to propose an accelerated algorithm to solve (3). Let
$\mathcal{N}_{k}$ be the normalizing signal defined as

$\mathcal{N}_{k}=1+H_{k},$

where

$H_{k}=\max\\{\zeta:\zeta\in\sigma(\nabla^{2}l(\theta_{k}))\\},$

where $\sigma(\nabla^{2}l(\theta_{k}))$ denotes the spectrum of the Hessian
matrix of the loss function $l$ evaluated at $\theta=\theta_{k}$. Note that it
is also possible to make a more conservative selection for $\mathcal{N}_{k}$
such as $\overline{M}$, i.e., smoothness parameter of the loss function if
accurate information about $\nabla^{2}l$ is not available. Next we introduce
Algorithm 1 to solve problem (3).

Algorithm 1 HT Optimizer for equality-constrained convex optimization

1: Initial conditions $\theta_{0}$, $\nu_{0}$, gains $\gamma$, $\beta$

2: for $k=0$ to $N$ do

3: Compute $\nabla l(\theta)$ and let $\mathcal{N}_{k}=1+H_{k}$

4: $\nabla\overline{q}_{k}(\theta_{k})=\dfrac{\nabla
l(\theta_{k})}{\mathcal{N}_{k}}$

5:
$\overline{\theta}_{k}=\theta_{k}-\gamma\beta\nabla\overline{q}_{k}(\theta_{k})$

6:
$\theta_{k+1}\leftarrow\overline{\theta}_{k}-\beta(\overline{\theta}_{k}-\nu_{k})$

7: Compute $\nabla l(\theta_{k+1})$ and let

8: $\nabla\overline{q}_{k}(\theta_{k+1})=\dfrac{\nabla
l(\theta_{k+1})}{\mathcal{N}_{k}}$

9: $\nu_{k+1}\leftarrow\nu_{k}-\gamma\nabla\overline{q}_{k}(\theta_{k+1})$

10: end for

The following result formally characterizes the convergence properties of
Algorithm 1.

######  Theorem III.3.

(Convergence of the HT algorithm for equality-constrained convex programs): If
the objective function $f$ is $\overline{L}$-smooth convex, then with
$0<\beta<1$ and $0<\gamma<\frac{\beta(2-\beta)}{8+\beta}$, the sequence of
iterates $\\{\theta_{k}\\}$ generated by Algorithm 1 satisfy
$\underset{k\rightarrow\infty}{\lim}l(\theta_{k})=l(\theta^{*})$, where
$l(\theta^{*})=f([\theta^{*T}\quad p(\theta^{*})^{T}]^{T})$ is the optimal
value of (3).

###### Proof.

From Proposition III.1, $\overline{L}$-smoothness of the objective function
$f$ implies that the loss function $l$ is $\overline{M}$-smooth and convex.
Rest of the proof follows from [11, Theorem 2]. ∎

Following Corollary III.2 and [11, Theorem 3], a similar result exists for the
strongly convex case as well.

###  III-B Convex optimization problems with equality & inequality constraints

Here we extend our approach to solve general convex optimization problems
involving equality as well as the inequality constraints in the form (2).
Redefine the loss function and the modified loss functions (4) by including a
penalty term corresponding to the inequality constraints violation as

$\displaystyle\mathcal{L}(x)=$ $\displaystyle
f(x)+\lambda_{h}\|Ax-b\|^{2}+\lambda_{g}\|\operatorname{\operatorname{softplus}}(g(x))\|^{2},$
(9a) $\displaystyle l(\theta)=$ $\displaystyle
f([\theta^{T}\;p(\theta)^{T}]^{T})+\lambda_{g}\|\operatorname{\operatorname{softplus}}(g([\theta^{T}\;p(\theta)^{T}])^{T})\|^{2}.$
(9b)

Since the penalty term corresponding to the inequality constraints is convex,
it follows from Proposition III.1 that the modified loss function (9b) is
convex.

Our approach is based on the inequality correction procedure of [13], briefly
described in Section II. The method involves first implementing the HT
Algorithm 1 on the loss function (9b) ensuring that the equality constraints
are met at all times. Then we apply an additional update that drives the
decision variable towards the feasible region corresponding to the inequality
constraints as well. Let $\alpha>0$ be the stepsize and define
$\rho:\operatorname{\mathbb{R}}^{n}\to\operatorname{\mathbb{R}}^{n}$ as

$\displaystyle\rho\Bigg{(}\begin{bmatrix}\theta\\\ p(\theta)\\\
\end{bmatrix}\Bigg{)}=\begin{bmatrix}\theta-\alpha\Delta\theta\\\
p(\theta)-\alpha\Delta p(\theta)\\\ \end{bmatrix},$ (10)

where

$\begin{aligned}
\Delta\theta=\Bigg{(}\dfrac{d}{d\theta}\|\operatorname{\operatorname{softplus}}\bigg{(}g\bigg{(}\begin{bmatrix}\theta\\\
p(\theta)\\\ \end{bmatrix}\bigg{)}\bigg{)}\|^{2}\Bigg{)}^{T}\end{aligned}.$

Note immediately that the inequality correction step above does not affect the
feasibility with respect to the equality constraints. Hence by implementing
the described method, we obtain Algorithm 2 that satisfies equality
constraints at each step and moves closer towards satisfying the inequality
constraints with each successive iteration.

Algorithm 2 HT optimizer for equality + inequality constrained convex
optimization

1: Initial conditions $x_{0}$, $\overline{x}_{0}$, $\nu_{0}$, gains $\alpha$,
$\gamma$, $\beta$

2: for k=0,1,2,… do

3: Compute $\nabla l(\theta_{k})$ and let $\mathcal{N}_{k}=1+H_{k}$

4: $\nabla\overline{f}_{k}(\theta_{k})=\dfrac{\nabla
l(\theta_{k})}{\mathcal{N}_{k}}$

5:
$\overline{\theta}_{k}=\theta_{k}-\gamma\beta\nabla\overline{f}_{k}(\theta_{k})$

6:
${\theta}_{k+1}\leftarrow\overline{\theta}_{k}-\beta(\overline{\theta}_{k}-\nu_{k})$

7: $\overline{x}_{k+1}=[\theta^{T}_{k+1}\;\;p(\theta_{k+1})^{T}]^{T}$

8: Compute $x_{k+1}\leftarrow\rho(\overline{x}_{k+1})$

9: Compute $\nabla l(\theta_{k+1})$ and let

10: $\nabla\overline{f}_{k}(\theta_{k+1})=\dfrac{\nabla
l(\theta_{k+1})}{\mathcal{N}_{k}}$

11: $\nu_{k+1}\leftarrow\nu_{k}-\gamma\nabla\overline{q}_{k}(\theta_{k+1})$

12: end for

It is reasonable to expect that if the hypotheses of Theorem III.3 are
satisfied and $\alpha$ is properly selected, Algorithm 2 solves problem (2).

##  IV Convex Optimization for a Class of Nonconvex Problems

In this section, we extend our approach of achieving accelerated convergence
via high-order tuners to a class of nonconvex optimization problems. As with
the convex case, we start with problems involving just the equality
constraints and then generalize our methodology to problems involving
inequality constraints as well. Throughout this section, we consider only the
conditions under which the loss function is convex. The arguments could be
generalized easily to the strongly convex case.

###  IV-A Equality-constrained nonconvex problems

Consider the optimization problem

$\displaystyle\min$ $\displaystyle f(x)$ (11) s.t. $\displaystyle h(x)=0,$

and the associated loss function

$\displaystyle\operatorname{\mathcal{L}}(x)=f(x)+\lambda_{h}\|h(x)\|^{2}.$
(12)

The following result whose proof is immediate and hence skipped, provides the
conditions under which $\operatorname{\mathcal{L}}$ is convex.

######  Lemma IV.1.

(Convexity of the loss function for equality-constrained nonconvex programs):
If $f$ and $h$ are convex, then $\operatorname{\mathcal{L}}$ defined in (12)
is convex.

The modified loss function in this case once again takes the form (4b), albeit
the functional form of $p$ would not be linear anymore. As such, establishing
the convexity of $l$ over the entire domain as in Proposition III.1 may not be
feasible anymore. We therefore search for conditions under which the modified
loss function $l$ is convex over some subset of the domain. We summarize a set
of such conditions in the following result.

######  Proposition IV.2.

(Convexity of the modified loss function for equality-constrained nonconvex
programs): Assume that there exists a convex set
$\Omega_{n}\in\operatorname{\mathbb{R}}^{n}$ such that the functions $f$ and
$h$ are convex on $\Omega_{n}$. Let

$\displaystyle\Omega_{m}=\\{\theta\>|\>\theta=x_{1:m},x\in\Omega_{n}\\}.$ (13)

If either of the following conditions is satisfied:

  1. (i)

$\nabla\operatorname{\mathcal{L}}(x)\geq 0$ for all $x\in\Omega_{n}$, and $p$
is convex on $\Omega_{m}$,

  2. (ii)

$\nabla\operatorname{\mathcal{L}}(x)\leq 0$ for all $x\in\Omega_{n}$, and $p$
is concave on $\Omega_{m}$,

then $l$ is convex on $\Omega_{m}$.

###### Proof.

We present here the arguments for only condition (i). The ensuing treatment
easily generalizes to condition (ii). It is immediate to see that $\Omega_{m}$
is convex. Consider $\theta_{1},\theta_{2}\in\Omega_{m}$. Since $p(\theta)$ is
convex, we have

$p(\lambda\theta_{1}+(1-\lambda)\theta_{2})\leq\lambda
p(\theta_{1})+(1-\lambda)p(\theta_{2}),$

and it follows that

$\begin{bmatrix}\lambda\theta_{1}+(1-\lambda)\theta_{2}\\\
p(\lambda\theta_{1}+(1-\lambda)\theta_{2})\end{bmatrix}\leq\lambda\begin{bmatrix}\theta_{1}\\\
p(\theta_{1})\end{bmatrix}+\ (1-\lambda)\begin{bmatrix}\theta_{2}\\\
p(\theta_{2})\end{bmatrix}.$

Since $\mathcal{L}$ is nondecreasing, it follows that

$\displaystyle\mathcal{L}$
$\displaystyle\Bigg{(}\begin{bmatrix}\lambda\theta_{1}+(1-\lambda)\theta_{2}\\\
p(\lambda\theta_{1}+(1-\lambda)\theta_{2})\end{bmatrix}\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\mathcal{L}\Bigg{(}\lambda\begin{bmatrix}\theta_{1}\\\
p(\theta_{1})\end{bmatrix}+\ (1-\lambda)\begin{bmatrix}\theta_{2}\\\
p(\theta_{2})\end{bmatrix}\Bigg{)}.$ (14)

Moreover, it follows from Lemma IV.1 that $\operatorname{\mathcal{L}}$ is
convex, and we have

$\displaystyle\mathcal{L}$
$\displaystyle\Bigg{(}\lambda\begin{bmatrix}\theta_{1}\\\
p(\theta_{1})\end{bmatrix}+\ (1-\lambda)\begin{bmatrix}\theta_{2}\\\
p(\theta_{2})\end{bmatrix}\Bigg{)}$ $\displaystyle\leq$
$\displaystyle\lambda\mathcal{L}\Bigg{(}\begin{bmatrix}\theta_{1}\\\
p(\theta_{1})\end{bmatrix}\Bigg{)}+(1-\lambda)\mathcal{L}\Bigg{(}\begin{bmatrix}\theta_{2}\\\
p(\theta_{2})\end{bmatrix}\Bigg{)}.$ (15)

Combining the inequalities (14) and (15), we get

$\displaystyle\mathcal{L}$
$\displaystyle\Bigg{(}\begin{matrix}\lambda\theta_{1}+(1-\lambda)\theta_{2}\\\
p(\lambda\theta_{1}+(1-\lambda)\theta_{2})\end{matrix}\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\lambda\mathcal{L}\Bigg{(}\begin{bmatrix}\theta_{1}\\\
p(\theta_{1})\end{bmatrix}\Bigg{)}+(1-\lambda)\mathcal{L}\Bigg{(}\begin{bmatrix}\theta_{2}\\\
p(\theta_{2})\end{bmatrix}\Bigg{)}.$

And from the definition of the modified loss function, it follows that

$l(\lambda\theta_{1}+(1-\lambda)\theta_{2})\leq\lambda
l(\theta_{1})+(1-\lambda)l(\theta_{2}),$

completing the proof. ∎

Now that we have established sufficient conditions for the convexity of the
modified loss function, we can use high-order tuners to find an optimizer of
(11). In fact, if the sequence of iterates lie within the set $\Omega_{n}$,
then we can use Algorithm 1, stated earlier for convex programs, to find a
solution of (11). The following result formalizes this.

######  Theorem IV.3.

(Convergence of the HT algorithm for equality-constrained nonconvex programs):
If the objective function $f$ and the equality constraint $h$ are convex over
a set $\Omega_{n}$, In addition, with $0<\beta<1$,
$0<\gamma<\frac{\beta(2-\beta)}{8+\beta}$, and $\theta_{0}\in\Omega_{m}$,
where $\Omega_{m}$ is defined in (13), if the sequence of iterates
$\\{\theta_{k}\\}$ generated by Algorithm 1 satisfy
$\\{\theta_{k}\\}\in\Omega_{m}$, then
$\underset{k\rightarrow\infty}{\lim}l(\theta_{k})=l(\theta^{*})$, where
$l(\theta^{*})=f([\theta^{*T}\quad p(\theta^{*})^{T}]^{T})$ is the optimal
value of (11).

###### Proof.

Convexity of the loss function $l$ follows from Proposition IV.2. Moreover,
since $\\{\theta_{k}\\}\in\Omega_{m}$ for all $k$, there exists a constant
$\overline{S}$ such that

$\displaystyle\dfrac{\|\nabla l(\theta_{1})-\nabla
l(\theta_{2})\|}{\|\theta_{1}-\theta_{2}\|}\leq\overline{S},$

for all $\theta_{1},\theta_{2}\in\Omega_{m}$. Rest of the proof follows from
[11, Theorem 2]. ∎

Theorem IV.3 enables us to leverage Algorithm 1, provided that the state
remains inside the set over which the modified loss function is convex. It is
reasonable to argue that this is always not the case. To overcome this
assumption, we use the projection operator defined as

$\operatorname{\operatorname{proj}_{\Omega_{m}}}(\tilde{\theta})=\text{argmin}\|\tilde{\theta}-\theta\|,\quad\forall\theta\in\Omega_{m}$

to make sure that the state remains inside the set $\Omega_{m}$. Algorithm 3
states this concisely.

Algorithm 3 HT Optimizer for equality-constrained nonconvex optimization

1: Initial conditions $\theta_{0}$, $\nu_{0}$, gains $\gamma$, $\beta$

2:
$\theta_{0}\leftarrow\operatorname{\operatorname{proj}_{\Omega_{m}}}(\theta_{0})$

3: for $k=1$ to $N$ do

4: Compute $\nabla l(\theta)$ and let $\mathcal{N}_{k}=1+H_{k}$

5: $\nabla\overline{q}_{k}(\theta_{k})=\dfrac{\nabla
l(\theta_{k})}{\mathcal{N}_{k}}$

6:
$\overline{\theta}_{k}=\theta_{k}-\gamma\beta\nabla\overline{q}_{k}(\theta_{k})$

7:
$\theta_{k+1}\leftarrow\operatorname{\operatorname{proj}_{\Omega_{m}}}(\overline{\theta}_{k}-\beta(\overline{\theta}_{k}-\nu_{k}))$

8: Compute $\nabla l(\theta_{k+1})$ and let

9: $\nabla\overline{q}_{k}(\theta_{k+1})=\dfrac{\nabla
l(\theta_{k+1})}{\mathcal{N}_{k}}$

10: $\nu_{k+1}\leftarrow\nu_{k}-\gamma\nabla\overline{q}_{k}(\theta_{k+1})$

11: end for

The arguments of this section show how the proposed approach could be applied
to solve nonconvex problems, where a convex objective function needs to be
optimized with respect to nonlinear convex equality constraints. Moreover, the
proposed method ensures that the state remains feasible throughout the
evolution, regardless of the convexity of the original problem.

###  IV-B Nonconvex optimization problems with equality & inequality
constraints

Here we employ the correction procedure described in Section II to extend our
approach to solve problems of the form (1), which includes inequality
constraints in addition to equality constraints. As in the convex case, let us
define the function $\rho$ as in (10) and consider the following algorithm,
obtained from appending Algorithm 3 with a suitable inequality correction
step.

Algorithm 4 HT optimizer for equality + inequality constrained nonconvex
optimization

1: Initial conditions $x_{0}$, $\overline{x}_{0}$, $\nu_{0}$, gains $\alpha$,
$\gamma$, $\beta$

2: $x_{0}\leftarrow\operatorname{\operatorname{proj}_{\Omega_{n}}}(x_{0})$

3: for k=0,1,2,… do

4: Compute $\nabla l(\theta_{k})$ and let $\mathcal{N}_{k}=1+H_{k}$

5: $\nabla\overline{f}_{k}(\theta_{k})=\dfrac{\nabla
l(\theta_{k})}{\mathcal{N}_{k}}$

6:
$\overline{\theta}_{k}=\theta_{k}-\gamma\beta\nabla\overline{f}_{k}(\theta_{k})$

7:
${\theta}_{k+1}\leftarrow\overline{\theta}_{k}-\beta(\overline{\theta}_{k}-\nu_{k})$

8: $\overline{x}_{k+1}=[\theta^{T}_{k+1}\;\;p(\theta_{k+1})^{T}]^{T}$

9: Compute
$x_{k+1}\leftarrow\operatorname{\operatorname{proj}_{\Omega_{n}}}(\rho(\overline{x}_{k+1}))$

10: Compute $\nabla l(\theta_{k+1})$ and let

11: $\nabla\overline{f}_{k}(\theta_{k+1})=\dfrac{\nabla
l(\theta_{k+1})}{\mathcal{N}_{k}}$

12: $\nu_{k+1}\leftarrow\nu_{k}-\gamma\nabla\overline{q}_{k}(\theta_{k+1})$

13: end for

If the hypotheses of Theorem IV.3 are satisfied, then with an appropriate
value of $\alpha$ introduced in (10), we can use Algorithm 4 to find a
solution of (1), without the explicit assumption of states belonging to the
set $\Omega_{n}$.

##  V Conclusions and Future Work

We have presented accelerated algorithms based on high-order tuners for
solving constrained convex optimization problems. Our approach is based on
identifying the conditions under which the reformulated loss function is
convex, guarantees that the equality constraints are satisfied at all times,
and is also applicable to a class of nonconvex optimization problems. Future
work will involve formally characterizing the rate of convergence and
extending our approach to a broader class of nonconvex problems.

## References

  * [1] K. S. Narendra and A. M. Annaswamy, _Stable Adaptive Systems_. NJ: Prentice-Hall, Inc., 1989, (out of print).
  * [2] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2009.
  * [3] E. Hazan, “Introduction to online convex optimization,” _arXiv preprint arXiv:1909.05207_ , 2019.
  * [4] Y. Nesterov, _Lectures on convex optimization_. Springer International Publishing, 2018, vol. 137.
  * [5] J. E. Gaudio, A. M. Annaswamy, M. A. Bolender, E. Lavretsky, and T. E. Gibson, “A Class of High Order Tuners for Adaptive Systems,” _IEEE Control Systems Letters_ , pp. 1–1, 6 2020.
  * [6] J. E. Gaudio, A. M. Annaswamy, J. M. Moreu, M. A. Bolender, and T. E. Gibson, “Accelerated Learning with Robustness to Adversarial Regressors,” _3rd L4DC Conference_ , 2021.
  * [7] N. M. Boffi and J.-J. E. Slotine, “Implicit regularization and momentum algorithms in nonlinear adaptive control and prediction,” _arXiv preprint arXiv:1912.13154_ , 2020.
  * [8] A. S. Morse, “High-order parameter tuners for the adaptive control of linear and nonlinear systems,” in _Systems, models and feedback: Theory and Applications_. Springer, 1992, pp. 339–364.
  * [9] S. Evesque, A. Annaswamy, S. Niculescu, and A. Dowling, “Adaptive control of a class of time-delay systems,” _J. Dyn. Sys., Meas., Control_ , vol. 125, no. 2, pp. 186–193, 2003.
  * [10] Y. E. Nesterov, “A method of solving a convex programming problem with convergence rate ${O}(1/k^{2})$,” _Soviet Mathematics Doklady_ , vol. 27, no. 2, pp. 372–376, 1983.
  * [11] J. M. Moreu and A. M. Annaswamy, “A stable high-order tuner for general convex functions,” _IEEE Control Systems Letters_ , vol. 6, pp. 566–571, 2022.
  * [12] P. Srivastava and J. Cortés, “Nesterov acceleration for equality-constrained convex optimization via continuously differentiable penalty functions,” _IEEE Control Systems Letters_ , vol. 5, no. 2, pp. 415–420, 2021.
  * [13] P. L. Donti, D. Rolnick, and J. Z. Kolter, “DC3: A learning method for optimization with hard constraints,” in _International Conference on Learning Representations_ , 2021.
  * [14] R. T. Rockafellar, _Convex Analysis_. Princeton, NJ, USA: Princeton University Press, 1970.
  * [15] B. Amos and J. Z. Kolter, “OptNet: Differentiable optimization as a layer in neural networks,” in _International Conference on Machine Learning_ , 2017\.


# Constraints for the spectra of generators of quantum dynamical semigroups

Dariusz Chruściński  Ryohei Fujii  Gen Kimura<EMAIL_ADDRESS>Hiromichi
Ohno  Institute of Physics, Faculty of Physics, Astronomy and Informatics
Nicolaus Copernicus University, Grudzia̧dzka 5/7, 87–100 Toruń, Poland
College of Systems Engineering and Science, Shibaura Institute of Technology,
Saitama 330-8570, Japan  Department of Mathematics, Faculty of Engineering,
Shinshu University, 4-17-1 Wakasato, Nagano 380-8553, Japan.

###### Abstract

Motivated by a spectral analysis of the generator of completely positive
trace-preserving semigroup, we analyze a real functional

$A,B\in M_{n}(\mathop{\mathbb{C}}\nolimits)\to
r(A,B)=\frac{1}{2}\Bigl{(}\langle[B,A],BA\rangle+\langle[B,A^{\mathrm{\ast}}],BA^{\mathrm{\ast}}\rangle\Bigr{)}\in\mathop{\mathbb{R}}\nolimits$

where $\langle A,B\rangle:=\tr(A^{\mathrm{\ast}}B)$ is the Hilbert-Schmidt
inner product, and $[A,B]:=AB-BA$ is the commutator. In particular we discuss
the upper and lower bounds of the form $c_{-}\|A\|^{2}\|B\|^{2}\leq r(A,B)\leq
c_{+}\|A\|^{2}\|B\|^{2}$ where $\|A\|$ is the Frobenius norm. We prove that
the optimal upper and lower bounds are given by
$c_{\pm}=\frac{1\pm\sqrt{2}}{2}$. If $A$ is restricted to be traceless, the
bounds are further improved to be
$c_{\pm}=\frac{1\pm\sqrt{2(1-\frac{1}{n})}}{2}$. Interestingly, these upper
bounds, especially the latter one, provide new constraints on relaxation rates
for the quantum dynamical semigroup tighter than previously known constraints
in the literature. A relation with Böttcher-Wenzel inequality is also
discussed.

###### keywords:

Hilbert-Schmidt Inner Product, Frobenius Norm, Commutator, Quantum Dynamical
Semigroup, Complete Positivity

##  1 Introduction

Motivated by a problem in the field of open quantum systems, we introduce the
following real-valued functional:

$r(A,B)=\frac{1}{2}\Bigl{(}\langle[B,A],BA\rangle+\langle[B,A^{\mathrm{\ast}}],BA^{\mathrm{\ast}}\rangle\Bigr{)}$
(1)

for any complex square matrices $A,B\in M_{n}(\mathop{\mathbb{C}}\nolimits)$.
Here, $A^{\mathrm{\ast}}$ is the Hermitian conjugation of $A$, $\langle
A,B\rangle:=\tr(A^{\mathrm{\ast}}B)$ is the Hilbert-Schmidt inner
product111Note that, we are following the convention in quantum physics that
the inner product is linear in the second argument (and anti-linear in the
first argument). , and $[A,B]:=AB-BA$ denotes the commutator. One of the goals
of this paper is to investigate the bounds of the form

$c_{-}(n)\|A\|^{2}\|B\|^{2}\leq r(A,B)\leq c_{+}(n)\|A\|^{2}\|B\|^{2}$ (2)

where $c_{\pm}(n)$ are real constants (possibly dependent on the matrix size
$n$) and the matrix norm is the Frobenius norm
$\|A\|:=\sqrt{\tr(A^{\mathrm{\ast}}A)}$. We will see (in Sec. 3) that these
bounds problem is related to Böttcher-Wenzel inequality [1] on the norm of
commutator.

The origin of the function (1) lies in the field of open quantum system [2, 3,
4, 5, 6]: For a Markovian open quantum dynamics, a time evolution of quantum
state is described by quantum dynamical semigroup, i.e., a semigroup of
completely positive trace-preserving maps [4]. Due to the seminal results [7,
8], any such generator has the following Gorini-Kossakowski-Lindblad-Sudarshan
(GKLS) form

$\mathcal{L}(\rho)=-i[H,\rho]+\sum_{k}\left(L_{k}\rho
L_{k}^{\mathrm{\ast}}-\frac{1}{2}\\{L_{k}^{\mathrm{\ast}}L_{k},\rho\\}\right),$
(3)

where $H=H^{\ast}$ is interpreted as an effective Hamiltonian, and $L_{k}$’s
are the so called jump (or noise) operators. One of the important physical
quantities is a relaxation rate which determines the time scale of the
exponential decaying [4]. For $n$-level quantum system, there are generally
$n^{2}-1$ relaxation rates, which are defined by

$\Gamma_{\alpha}:=-\real\lambda_{\alpha},\ \ \ \ (\alpha=1,\ldots,n^{2}-1),$
(4)

where $\lambda_{\alpha}$ are eigenvalues of generator $\mathcal{L}$ except for
$\lambda_{n^{2}}=0$. (Note that there is always one zero eigenvalue due to the
trace preserving property of $\mathop{\mathcal{L}}\nolimits$.) By using (1)
and GKLS form (3), we observe (in Sec. 5) that any relaxation rate is
expressed as

$\Gamma_{\alpha}=\sum_{k}r(u_{\alpha},L_{k}),$ (5)

where $u_{\alpha}$ is the unit eigenmatrix of $\mathop{\mathcal{L}}\nolimits$
belonging to $\lambda_{\alpha}$, i.e.,
$\mathop{\mathcal{L}}\nolimits(u_{\alpha})=\lambda_{\alpha}u_{\alpha}\
(\|u_{\alpha}\|=1)$. With this in mind, we shall call function (1) a
$r$-function, where “r” stands for a relaxation. Moreover, it is easy to see
that the upper bound in (2) gives the following constraints for relaxation
rates (see Sec. 5 for details):

$\Gamma_{\alpha}\leq\frac{c_{+}(n)}{n}\sum_{\beta=1}^{n^{2}-1}\Gamma_{\beta}\
\ \ \ (\forall\alpha=1,\ldots,n^{2}-1).$ (6)

This is universally satisfied for any quantum dynamical semigroup reflecting
the condition of complete positivity. Therefore, we have a significant
motivation to investigate function (1), especially its upper bound, in open
quantum physics.

In this paper, we show that the best constants for (2) (i.e., the minimum of
$c_{+}(n)$ and the maximum of $c_{-}(n)$) are
$c_{\pm}(n)=\frac{1\pm\sqrt{2}}{2}$ independent of the matrix size $n$.
Namely, we have

###### Theorem 1

For any complex matrices $A,B\in M_{n}(\mathop{\mathbb{C}}\nolimits)$,

$\frac{1-\sqrt{2}}{2}\|A\|^{2}\|B\|^{2}\leq
r(A,B)\leq\frac{1+\sqrt{2}}{2}\|A\|^{2}\|B\|^{2}.$ (7)

Both lower and upper bounds are sharp, i.e., there are matrices $A$ and $B$
that can attain the bounds.

Furthermore, if we restrict the matrix $A$ to be traceless, then the best
constants are further tightened to be
$c_{\pm}(n)=\frac{1\pm\sqrt{2(1-\frac{1}{n})}}{2}$:

###### Theorem 2

For any complex matrices $A,B\in M_{n}(\mathop{\mathbb{C}}\nolimits)$ with
$\tr A=0$,

$\frac{1-\sqrt{2(1-\frac{1}{n})}}{2}\|A\|^{2}\|B\|^{2}\leq
r(A,B)\leq\frac{1+\sqrt{2(1-\frac{1}{n})}}{2}\|A\|^{2}\|B\|^{2}.$ (8)

Both lower and upper bounds are sharp. In particular, for $n=2$, the
inequalities read

$0\leq r(A,B)\leq\|A\|^{2}\|B\|^{2}.$ (9)

Note that the best constants $\frac{1\pm\sqrt{2(1-\frac{1}{n})}}{2}$ in (8)
with the traceless restriction are strictly tighter than the best constants
$\frac{1\pm\sqrt{2}}{2}$ in (7) and converges to the general bounds as
$n\to\infty$. We emphasize that both upper bounds in (7) and (8) give tighter
constraints than any of the previously known constraints [10, 11] (Theorem 3).

The rest of the paper is organized as follows. In Sec. 2, we investigate
general properties of $r$-function. In Sec. 3, we discuss a relation between
our problem and Böttcher-Wenzel inequality on the norm of commutator. In Sec.
4, we prove main results on the sharp bounds of $r$-function. In Sec. 5 an
application to quantum dynamical semigroup is explained. Sec. 6 is devoted to
conclusion and discussion.

##  2 Properties of $r$-function

In this section, we investigate some of general properties of $r$-function
(1). We first observe that there are several equivalent expressions:

$\displaystyle r(A,B)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\tr(A^{\mathrm{\ast}}AB^{\mathrm{\ast}}B+AA^{\mathrm{\ast}}B^{\mathrm{\ast}}B-A^{\mathrm{\ast}}BAB^{\mathrm{\ast}}-BA^{\mathrm{\ast}}B^{\mathrm{\ast}}A),$
(10) $\displaystyle=$
$\displaystyle\frac{1}{2}\tr(\\{A,A^{\mathrm{\ast}}\\}B^{\mathrm{\ast}}B)-\real\tr(A^{\mathrm{\ast}}BAB^{\mathrm{\ast}}),$
(11) $\displaystyle=$ $\displaystyle\frac{1}{2}\Bigl{(}(\|[A,B]\|^{2}+\tr
A^{\mathrm{\ast}}A[B^{\mathrm{\ast}},B]\Bigr{)},$ (12) $\displaystyle=$
$\displaystyle\frac{1}{2}\Bigl{(}(\|[A^{\mathrm{\ast}},B^{\mathrm{\ast}}]\|^{2}+\tr(A^{\mathrm{\ast}}A[B^{\mathrm{\ast}},B])\Bigr{)},$
(13) $\displaystyle=$
$\displaystyle\frac{1}{2}\Bigl{(}(\|[A,B^{\mathrm{\ast}}]\|^{2}+\tr(AA^{\mathrm{\ast}}[B^{\mathrm{\ast}},B])\Bigr{)},$
(14) $\displaystyle=$
$\displaystyle\frac{1}{2}\Bigl{(}(\|[A^{\mathrm{\ast}},B]\|^{2}+\tr(AA^{\mathrm{\ast}}[B^{\mathrm{\ast}},B])\Bigr{)},$
(15) $\displaystyle=$
$\displaystyle\frac{1}{4}\Bigl{(}(\|[A,B]\|^{2}+\|[A^{\mathrm{\ast}},B]\|^{2}+\tr(\\{A,A^{\mathrm{\ast}}\\}[B^{\mathrm{\ast}},B])\Bigr{)},$
(16)

where $\\{A,B\\}:=AB+BA$ denotes the anti-commutator. Indeed, it is
straightforward to see that expansions of (1) and (11) - (16) all reduce to
(10) by noting the cyclic property of trace. The fact that $r$-function is a
real valued is easily seen from these expressions. Note that $r$-function is
asymmetric between $A$ and $B$ in general; for instance, with
$A=\left(\begin{array}[]{cc}0&1\\\ 1&1\\\ \end{array}\right)$ and
$B=\left(\begin{array}[]{cc}0&0\\\ 1&0\\\ \end{array}\right)$, $r(A,B)=1$ and
$r(B,A)=\frac{3}{2}$. It is not bilinear but satisfies

$r(\alpha A,\beta
B)=|\alpha|^{2}|\beta|^{2}r(A,B)\quad(\alpha,\beta\in\mathop{\mathbb{C}}\nolimits).$
(17)

Note also the unitary invariance:

$r(UAU^{\mathrm{\ast}},UBU^{\mathrm{\ast}})=r(A,B)$ (18)

for any unitary matrix $U$. For Cartesian decomposition for $A=A_{R}+iA_{I}$,
where $A_{R}=\frac{A+A^{\ast}}{2}$ and $A_{I}=\frac{A-A^{\ast}}{2i}$ are self-
adjoint real and imaginary parts of $A$, a direct computation shows

$r(A,B)=r(A_{R},B)+r(A_{I},B).$ (19)

Late on, we will see this property plays an important role in showing upper
and lower bounds for general matrices, not necessarily for self-adjoint
matrices.

If $A=B$, $r$-function is shown to be (by using (12) or (13))

$r(A,A)=\frac{1}{2}\tr(A^{\mathrm{\ast}}A[A^{\mathrm{\ast}},A]).$ (20)

For the sake of practice, we shall start from the lower and upper bounds for
this case. Since the eigenvalues of $A^{\mathrm{\ast}}A$ and
$AA^{\mathrm{\ast}}$ are the same, we have
$\|A^{\mathrm{\ast}}A\|=\|AA^{\mathrm{\ast}}\|$. By using Schwarz inequality,

$\displaystyle r(A,A)$
$\displaystyle=\frac{1}{2}\tr(A^{\mathrm{\ast}}AA^{\mathrm{\ast}}A-A^{\mathrm{\ast}}AAA^{\mathrm{\ast}})=\frac{1}{2}\|A^{\mathrm{\ast}}A\|^{2}-\frac{1}{2}\langle
A^{\mathrm{\ast}}A,AA^{\mathrm{\ast}}\rangle$
$\displaystyle\geq\frac{1}{2}\|A^{\mathrm{\ast}}A\|^{2}-\frac{1}{2}\|A^{\mathrm{\ast}}A\|\|AA^{\mathrm{\ast}}\|=0.$

This lower bound is sharp since the equality is always attainable by any
normal matrix $A$. Using the similar idea, one obtains the following upper
bound:

$r(A,A)\leq\frac{1}{2}\|A^{\mathrm{\ast}}A\|^{2}+\frac{1}{2}|\langle
A^{\mathrm{\ast}}A,AA^{\mathrm{\ast}}\rangle|\leq\frac{1}{2}\|A^{\mathrm{\ast}}A\|^{2}+\frac{1}{2}\|A^{\mathrm{\ast}}A\|\|AA^{\mathrm{\ast}}\|\leq\|A\|^{4}.$

Here, we have used the triangle inequality, Schwarz inequality, the norm
inequality $\|AB\|\leq\|A\|\|B\|$ (which holds for any unitary invariant norm
[18]), and $\|A^{\mathrm{\ast}}\|=\|A\|$. However, this is not the tight bound
and can be further sharpened as follows. In what follows, we use the Dirac
notation [12] for vector $\ket{\psi}\in\mathop{\mathbb{C}}\nolimits^{n}$. In
particular, let $\outerproduct{\psi}{\phi}$ denote the linear operator on
$\mathop{\mathbb{C}}\nolimits^{n}$ defined by
$\outerproduct{\psi}{\phi}\ket{\xi}:=\langle\phi|\xi\rangle\ket{\psi}$ where
$\langle\phi|\xi\rangle$ is the inner product between $\ket{\phi}$ and
$\ket{\xi}$. With this notation, the singular value decomposition of $A$ with
its singular values $a_{i}\geq 0$ can be written as
$A=\sum_{i=1}^{n}a_{i}\outerproduct{b_{i}}{\beta_{i}}$ with orthonormal bases
$\\{\ket{b_{i}}\\}_{i=1}^{n},\\{\ket{\beta_{i}}\\}_{i=1}^{n}$ of
$\mathop{\mathbb{C}}\nolimits^{n}$. Then, a direct computation of (20) shows

$\displaystyle
r(A,A)=\frac{1}{2}\Bigl{(}\sum_{i=1}^{n}a^{4}_{i}-\sum_{i,j=1}^{n}a^{2}_{i}a^{2}_{j}|\langle
b_{i}|\beta_{j}\rangle|^{2}\Bigr{)}.$ (21)

Since $\|A\|^{4}=(\sum_{i}a_{i}^{2})^{2}=\sum_{i}a_{i}^{4}+\sum_{i\neq
j}a_{i}^{2}a_{j}^{2}$, we have

$\frac{1}{2}\|A\|^{4}-r(A,A)=\frac{1}{2}\Bigl{(}\sum_{i\neq
j}a_{i}^{2}a_{j}^{2}+\sum_{i,j=1}^{n}a^{2}_{i}a^{2}_{j}|\langle
b_{i}|\beta_{j}\rangle|^{2}\Bigr{)}\geq 0.$

The equality is achieved by a rank $1$ operator $A=a\outerproduct{b}{\beta}$
with orthogonal $\ket{b}$ and $\ket{\beta}$. Hence, we have obtained:

###### Proposition 1

For any $A\in M_{n}(\mathop{\mathbb{C}}\nolimits)$,

$0\leq r(A,A)\leq\frac{1}{2}\|A\|^{4}.$ (22)

Both lower and upper bounds are sharp.

##  3 $r$-function vs. Böttcher–Wenzel inequality

Interestingly, our problem is closely related to Böttcher–Wenzel inequality:

$\|[A,B]\|^{2}\leq 2\|A\|^{2}\|B\|^{2},$ (23)

where the bound is sharp. This inequality was firstly conjectured by Böttcher
and Wenzel in [13] giving a proof for real $2\times 2$ matrices and also
normal matrices. Then, it was proved by Vong and Jin [14], by Lu [15], and
subsequently by Böttcher and Wenzel themselves for general complex matrices
[1]. A simple and conceptually sound proof was given by Audenaert using a
variance bound [16]. For the equality condition, see [1] and [17].

In regard to our problem, if we restrict the matrix $B$ to be normal,
$r$-function reduces to be the norm of commutator:

$r(A,B)=\frac{1}{2}\|[A,B]\|^{2},$ (24)

which is easily observed from the expression (12). Since the equality in (23)
can be attained by a normal matrix $B$ (see Proposition 4.6 in [1]), the best
bound in (2) with the restriction of $B$ being normal is $1$. Therefore, one
observes the following restricted inequality:

$r(A,B)\leq\|A\|^{2}\|B\|^{2}$ (25)

which is satisfied for any complex matrix $A$ and for any normal matrix $B$.
Notice that the situation is completely asymmetric between $A$ and $B$.
Indeed, in the next section, we will see (Proposition 3) that the restriction
for $A$ being normal (and even self-adjoint) does not change the general sharp
bound (7).

Furthermore, Böttcher–Wenzel inequality (23) gives a non-trivial upper bound
for our problem (2):

###### Proposition 2

For any matrices $A,B\in M_{n}(\mathop{\mathbb{C}}\nolimits)$,

$r(A,B)\leq\sqrt{2}\|A\|^{2}\|B\|^{2}.$

[Proof] : Applying the triangle inequality, Schwarz inequality, the norm
inequality $\|AB\|\leq\|A\|\|B\|$, $\|A^{\ast}\|=\|A\|$, and finally
commutator inequality (23) to $r$-function in the form (1), we have

$\displaystyle r(A,B)$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}(|\langle[B,A],BA\rangle|+|\langle[B,A^{\mathrm{\ast}}],BA^{\mathrm{\ast}}\rangle|)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}(\|[B,A]\|\|BA\|+\|[B,A^{\mathrm{\ast}}]\|\|BA^{\mathrm{\ast}}\|)\leq\sqrt{2}\|A\|^{2}\|B\|^{2}.$

$\blacksquare$

Notice that if we apply this result to (6), we recover the following universal
constraints for relaxation rates:

$\Gamma_{\alpha}\leq\frac{\sqrt{2}}{n}\sum_{\beta=1}^{n^{2}-1}\Gamma_{\beta}\
\ \ \ (\forall\alpha=1,\ldots,n^{2}-1).$ (26)

This bound was observed in [10] by one of the authors (G.K.) essentially using
the same reasoning here. However, as we will see in the next section, the
upper bounds are sharpened, and hence giving tighter constraints for
relaxation rates.

##  4 Sharp bounds for $r$-function

In this section, we prove Theorem 1 and Theorem 2. The strategy of the proofs
is as follows. We first show the bounds of $r(A,B)$ for the case where $A$ is
self-adjoint. Then, the decomposition (19) gives the general bounds for
general matrices. (In A, we give direct proofs for the case $n=2$.)

###### Proposition 3

For any complex matrices $A,B\in M_{n}(\mathop{\mathbb{C}}\nolimits)$ with
$A=A^{\mathrm{\ast}}$,

$\frac{1-\sqrt{2}}{2}\|A\|^{2}\|B\|^{2}\leq
r(A,B)\leq\frac{1+\sqrt{2}}{2}\|A\|^{2}\|B\|^{2},$ (27)

where both bounds are sharp.

[Proof] By the unitary invariance of $r$-function, note that the restriction
for $A$ to be self-adjoint is equivalent to the restriction to be real
diagonal. Let $A={\rm diag}[a_{1},a_{2},\ldots,a_{n}]$ be any diagonal matrix
with real elements $a_{i}\in\mathop{\mathbb{R}}\nolimits$ and let
$B=(b_{ij})_{i,j=1}^{n}$ be any complex matrix. A direct computation shows

$r(A,B)=\sum_{i\neq j=1}^{n}|b_{ji}|^{2}(a_{i}^{2}-a_{i}a_{j}).$ (28)

Notice that the constants $c_{\pm}:=\frac{1\pm\sqrt{2}}{2}$ appeared in (27)
are solutions of the quadratic equation $4c(c-1)=1$. Using this, we have

$\displaystyle c_{+}\|A\|^{2}\|B\|^{2}-r(A,B)$ $\displaystyle=$ $\displaystyle
c_{+}(\sum_{k}a_{k}^{2})(\sum_{i,j=1}^{n}|b_{ji}|^{2})-\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}(a_{i}-a_{i}a_{j})$ $\displaystyle\geq$
$\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}((c_{+}-1)a_{i}^{2}+c_{+}a_{j}^{2}+a_{i}a_{j})$
$\displaystyle=$ $\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}\sqrt{(c_{+}-1)}a_{i}+\sqrt{c_{+}}a_{j}\Bigr{)}^{2}\geq
0,$

where the last completing the square follows from
$2\sqrt{c_{+}}\sqrt{c_{+}-1}=1$. This shows the upper bound in (27). Note that
the equality is attained by matrices $A$ and $B$ with e.g.,
$a_{1}=1,a_{2}=-\sqrt{\frac{c_{+}}{(c_{+}-1)}}=-2c_{+}$ and $b_{12}=1$ where
all other elements are zero. (Here, $B$ should be chosen to be non-normal
since for normal $B$ tighter inequality (25) is satisfied.)

Similarly, but noting that $c_{-}<0$, we have

$\displaystyle r(A,B)-c_{-}\|A\|^{2}\|B\|^{2}$ $\displaystyle=$
$\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}(a_{i}^{2}-a_{i}a_{j})+(-c_{-})(\sum_{k}a_{k}^{2})(\sum_{i,j=1}^{n}|b_{ji}|^{2})$
$\displaystyle\geq$ $\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}((1-c_{-})a_{i}^{2}+(-c_{-})a_{j}^{2}-a_{i}a_{j})$
$\displaystyle=$ $\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}\sqrt{(1-c_{-})}a_{i}-\sqrt{-c_{-}}a_{j}\Bigr{)}^{2}\geq
0,$

where the last equality follows from $2\sqrt{-c_{-}}\sqrt{1-c_{-}}=1$. Thus,
the lower bound in (27) is shown. The equality is attained by matrices $A$ and
$B$ with e.g., $a_{1}=1,a_{2}=\sqrt{\frac{-c_{-}}{(1-c_{-})}}=-2c_{-}$ and
$b_{12}=1$ where all other elements are zero. $\blacksquare$

Now we are ready to prove Theorem 1.

[Proof of Theorem 1] Just use decomposition (19) for the Cartesian
decomposition $A=A_{R}+iA_{I}$: $r(A,B)=r(A_{R},B)+r(A_{I},B)$. Noting that
$\|A\|^{2}=\|A_{R}\|^{2}+\|A_{I}\|^{2}$, the application of Proposition 3 for
the self-adjoint $A_{R}$ and $A_{I}$ shows that the same bounds (27) follow
for any $A$ and $B$. Moreover, the equalities are attained by choosing $A_{R}$
and $A_{I}$ to attain the bounds of (27). $\blacksquare$

The proof for Theorem 2 goes similarly.

###### Proposition 4

For any complex matrices $A,B\in M_{n}(\mathop{\mathbb{C}}\nolimits)$ with
$\tr A=0$ and $A^{\ast}=A$,

$\frac{1-\sqrt{2(1-\frac{1}{n})}}{2}\|A\|^{2}\|B\|^{2}\leq
r(A,B)\leq\frac{1+\sqrt{2(1-\frac{1}{n})}}{2}\|A\|^{2}\|B\|^{2},$ (29)

where both bounds are sharp.

[Proof] As before, it is enough to prove for any real diagonal matrix $A={\rm
diag}[a_{1},a_{2},\ldots,a_{n}]$ ($a_{i}\in\mathop{\mathbb{R}}\nolimits$), but
this time with the traceless condition $\sum_{k}a_{k}=0$, and for arbitrary
$B=(b_{ij})_{i,j=1}^{n}$.

The case $n=2$ is straightforward: Letting $A={\rm diag}[a,-a]$ with
$a\in\mathop{\mathbb{R}}\nolimits$, one finds
$r(A,B)=2a^{2}(|b_{12}|^{2}+|b_{21}|^{2})$. This immediately shows the bounds
(29) and the bounds are sharp. Let $n\geq 3$. Note that constants
$c^{\prime}_{\pm}:=\frac{1\pm\sqrt{2(1-\frac{1}{n})}}{2}$ appeared in (29) are
the solutions of the quadratic equation
$4(c^{\prime}+\frac{c^{\prime}}{n-2}-1)(c^{\prime}+\frac{c^{\prime}}{n-2})=(1+\frac{2c^{\prime}}{n-2})^{2}$.
Using general expression (28), one has

$\displaystyle c^{\prime}_{+}\|A\|^{2}\|B\|^{2}-r(A,B)$ $\displaystyle=$
$\displaystyle
c^{\prime}_{+}(\sum_{k}a_{k}^{2})(\sum_{i,j=1}^{n}|b_{ji}|^{2})-\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}(a_{i}^{2}-a_{i}a_{j})$ $\displaystyle\geq$
$\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}(c^{\prime}_{+}-1)a_{i}^{2}+c^{\prime}_{+}a_{j}^{2}+a_{i}a_{j}+c^{\prime}_{+}\sum_{k\neq
i,j}a_{k}^{2}\Bigr{)}.$

Applying Schwartz inequality $(n-2)\sum_{k\neq i,j}a_{k}^{2}\geq|\sum_{k\neq
i,j}a_{k}|^{2}$ and the traceless condition $\sum_{k\neq
i,j}a_{k}=-(a_{i}+a_{j})$, the last term can be further lower bounded by

$\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}(c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2}-1)a_{i}^{2}+(c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2})a_{j}^{2}+(1+\frac{2c^{\prime}_{+}}{n-2})a_{i}a_{j}\Bigr{)}$
$\displaystyle=$ $\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}\sqrt{c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2}-1}a_{i}+\sqrt{c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2}}a_{j}\Bigr{)}^{2}\geq
0.$

The last completing the square is due to the fact that
$c^{\prime}_{+}=\frac{1+\sqrt{2(1-\frac{1}{n})}}{2}$ is the solution of
$2\sqrt{c^{\prime}+\frac{c^{\prime}}{n-2}-1}\sqrt{c^{\prime}+\frac{c^{\prime}}{n-2}}=1+\frac{2c^{\prime}}{n-2}$.

The equality is also attained by a real diagonal matrix $A$ and $B$ with e.g.,
$a_{1}=\sqrt{c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2}}$,
$a_{2}=-\sqrt{c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2}-1}$,
$a_{k}=\frac{1}{n-2}\left(\sqrt{c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2}-1}-\sqrt{c^{\prime}_{+}+\frac{c^{\prime}_{+}}{n-2}}\right)$
$(3\leq k\leq n)$ and $b_{21}=1$ where all other elements are zero.

The lower bound is shown similarly. Note that $c^{\prime}_{-}\leq 0$. Applying
Schwartz inequality $(n-2)\sum_{k\neq i,j}a_{k}^{2}\geq|\sum_{k\neq
i,j}a_{k}|^{2}$ and the traceless condition $\sum_{k\neq
i,j}a_{k}=-(a_{i}+a_{j})$, we obtain

$\displaystyle r(A,B)-c^{\prime}_{-}\|A\|^{2}\|B\|^{2}$ $\displaystyle=$
$\displaystyle-c^{\prime}_{-}(\sum_{k}a_{k}^{2})(\sum_{i,j=1}^{n}|b_{ji}|^{2})+\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}(a_{i}^{2}-a_{i}a_{j})$ $\displaystyle\geq$
$\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}(1-c^{\prime}_{-})a_{i}^{2}-c^{\prime}_{-}a_{j}^{2}-a_{i}a_{j}-c^{\prime}_{-}\sum_{k\neq
i,j}a_{k}^{2}\Bigr{)}$ $\displaystyle\geq$ $\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}(1-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2})a_{i}^{2}+(-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2})a_{j}^{2}-(1+\frac{2c^{\prime}_{-}}{n-2})a_{i}a_{j}\Bigr{)}$
$\displaystyle=$ $\displaystyle\sum_{i\neq
j=1}^{n}|b_{ji}|^{2}\Bigl{(}\sqrt{1-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2}}a_{i}-\sqrt{-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2}}a_{j}\Bigr{)}^{2}\geq
0.$

The last completing the square follows from
$2\sqrt{1-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2}}\sqrt{-c^{\prime}-\frac{c^{\prime}_{-}}{n-2}}=1+\frac{2c^{\prime}_{-}}{n-2}$.
The equality is attained by a real diagonal matrix $A$ and $B$ with e.g.,
$a_{1}=\sqrt{-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2}}$,
$a_{2}=\sqrt{1-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2}}$,
$a_{k}=\frac{1}{n-2}\left(-\sqrt{1-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2}}-\sqrt{-c^{\prime}_{-}-\frac{c^{\prime}_{-}}{n-2}}\right)$
$(3\leq k\leq n)$ and $b_{21}=1$ where all other elements are zero.
$\blacksquare$

[Proof of Theorem 2] Similar to the proof of Theorem 1, this follows from
Proposition 4 and the decomposition (19) just by noting that both the real and
imaginary parts are also traceless for a traceless matrix $A$. The sharpness
of the bounds also follows similarly. $\blacksquare$

##  5 Application to quantum dynamical semigroup

Note that the trivial condition that any relaxation rate (4) is positive can
be guaranteed by the positive preserving property of the dynamical map.
However, it is known that the condition of complete positivity imposes a
strong constraint on the relaxation rates [7, 9, 10, 11]: Simply put, any
relaxation rate cannot be too large compared to other relaxation rates. This
is quantitatively described by the following constraint:

$\Gamma_{\alpha}\leq
r(n)\sum_{\beta=1}^{n^{2}-1}\Gamma_{\beta}\quad(\forall\alpha=1,\ldots,n^{2}-1)$
(30)

with some positive constant $r(n)$ dependent on the level $n$. Note that the
condition $r(n)<1$ yields a non-trivial constraint for relaxation rates and
the smaller the constant is the tighter the constraint becomes. Therefore, it
is an important problem to find the minimum constant $r_{\rm opt}(n)$ where
the constraint (30) holds for any GKLS generator. In light of the universality
of the property, the constraint will give a physical manifestation of a
mathematical condition of complete positivity [11].

For $n=2$ (i.e., qubit system), we have shown [7, 9] that for any GKLS
generator $r(2)=\frac{1}{2}$ is correct for the bound (30). The constraint can
be rephrased as

$\Gamma_{i}\leq\Gamma_{j}+\Gamma_{k}\quad(i,j,k=1,2,3).$

Interestingly, in the case where two of the relaxation rates are equal, say
$\Gamma_{2}=\Gamma_{3}$, the relation coincides with the famous relation
between the longitudinal relaxation time $T_{L}(=1/\Gamma_{1})$ and the
transverse relaxation time $T_{T}(=1/\Gamma_{2}=\Gamma_{3})$:

$T_{L}\geq 2T_{T},$ (31)

which is experimentally demonstrated to be true [4, 23]. For a general $n$,
not much is known. Applying the result from [22], one finds
$r(n)\leq\frac{2}{n}$ but only for the restricted class of purely dissipative
generator. In [10], we have shown that $r(n)=\frac{\sqrt{2}}{n}$ is correct
for any GKLS generator with general $n$ by using BW-inequality. On the other
hand, we have shown that the best constant is lower bounded by $\frac{1}{n}$
[11]. Combining these results, we can conclude

$r_{\rm opt}(2)=\frac{1}{2}.$ (32)

But, for larger $n\geq 3$, we only know

$\frac{1}{n}\leq r_{\rm opt}(n)\leq\frac{\sqrt{2}}{n}.$ (33)

We show here that the bound problem (2) of $r$-function can be used to tackle
on this problem. Let us first show the general expression (5) for relaxation
rate. Applying GKLS form (3) into the eigenvalue equation
$\mathop{\mathcal{L}}\nolimits(u_{\alpha})=\lambda_{\alpha}u_{\alpha}$ with
unit eigenmatrix $u_{\alpha}$, and multiplying $u^{\mathrm{\ast}}_{\alpha}$ to
the equation from the left, and finally taking the trace, we obtain

$\lambda_{\alpha}=\tr\Bigl(u^{\mathrm{\ast}}_{\alpha}(-i[H,u_{\alpha}]+\frac{1}{2}\sum_{k}(2L_{k}u_{\alpha}L_{k}^{\mathrm{\ast}}-L_{k}^{\mathrm{\ast}}L_{k}u_{\alpha}-u_{\alpha}L_{k}^{\mathrm{\ast}}L_{k}))\Bigr{missing}).$

Taking the real part of this equation and noting
$\Gamma_{\alpha}=-\real\lambda_{\alpha}$, one arrives at the expression (5)
especially if one uses the form (10). On the other hand, we know the relation
(see [10, 11]):

$\sum_{\alpha=1}^{n^{2}-1}\Gamma_{\alpha}=n\sum_{k}\|L_{k}\|^{2}.$

In showing this, we need to use the traceless condition for $L_{k}$. However,
this can be assumed without loss of generality as the trace part of $L_{k}$
can be renormalized into the Hamiltonian part in the generator (3). Combining
these results, the bound of the form (2) gives a non trivial constraint (6)
for relaxation rate. Moreover, the trace of $u_{\alpha}$ for non-zero
eigenvalue $\lambda_{\alpha}$ is traceless. This is easily shown by using the
fact ${\rm tr}(\mathop{\mathcal{L}}\nolimits(A))=0$ for any matrix $A$.
Therefore, the bound (2) with the restriction of $A$ being traceless also
gives a non-trivial constraint for the relaxation rates. Finally, by applying
results of Theorem 1 and 2, we obtain

###### Theorem 3

For $n$-level quantum system, the optimal bound for relaxation rates for any
quantum dynamical semigroup satisfies

$r_{\rm
opt}(n)\leq\frac{1+\sqrt{2(1-\frac{1}{n})}}{2n}\leq\frac{1+\sqrt{2}}{2n}.$
(34)

We emphasize that the right inequality due to Theorem 1 already gives tighter
constraint than previously known bound (33).

##  6 Conclusion and discussion

In this paper, we have introduced a $r$-function (1) with which any relaxation
rate of quantum dynamical semigroup is expressed by (5). We discussed the
upper and lower bounds of form (2) and found the best bounds are given by
$c_{\pm}=\frac{1\pm\sqrt{2}}{2}$ independent of the matrix size (Theorem 1).
If we restrict the matrix $A$ to be traceless, the bounds are reduced to be
$c_{\pm}=\frac{1\pm\sqrt{2(1-\frac{1}{n})}}{2}$ (Theorem 2). As an
application, we obtained tighter universal constraints on relaxation rates
than any of previously known constraints (Theorem 3).

In [11], we raised a conjecture that $r_{\rm opt}(n)=\frac{1}{n}$ for any
$n\geq 2$. The present result, especially the upper bound
$\frac{1+\sqrt{2(1-\frac{1}{n})}}{2n}$ is close to this and indeed attained
for $2$-level (i.e., qubit) system. Unfortunately, for $n\geq 3$, this is
strictly larger than $\frac{1}{n}$, hence still leaves this problem open.

Acknowledgements

We would like to thank Prof. Andrzej Kossakowski for his fruitful comments and
advices. During the preparation of this manuscript, he passed away on 1th FEB
2021. We would like to dedicate this paper to his memory. D.C. is supported by
the National Science Center project 2018/30/A/ST2/00837. G. K. is supported in
part by JSPS KAKENHI Grants No. 17K18107.

##  Appendix A Direct proofs of Theorems 1 and 2 for $n=2$.

In this appendix, we present direct proofs for Theorem 1 and Theorem 2 for the
case $n=2$ only for instructive purpose. Namely, for any complex matrices
$A,B\in M_{2}(\mathop{\mathbb{C}}\nolimits)$,

$\frac{1-\sqrt{2}}{2}\|A\|^{2}\|B\|^{2}\leq
r(A,B)\leq\frac{1+\sqrt{2}}{2}\|A\|^{2}\|B\|^{2}.$ (35)

If $A$ is restricted to be traceless,

$0\leq r(A,B)\leq\|A\|^{2}\|B\|^{2}.$ (36)

In both cases, the bounds are sharp.

In the following, we use standard notations (in vector analysis) for complex
vectors ${\bm{a}},{\bm{b}}\in\mathop{\mathbb{C}}\nolimits^{3}$ such as
${\bm{a}}\cdot{\bm{b}}:=\sum_{i=1}^{3}\overline{a_{i}}b_{i}$ (dot product),
$|{\bm{a}}|=\sqrt{{\bm{a}}\cdot{\bm{a}}}=\sum_{i=1}^{3}|a_{i}|^{2}$, and
${\bm{a}}\times{\bm{b}}$ (cross product) which is defined by
$({\bm{a}}\times{\bm{b}})_{i}=\sum_{j,k=1}^{3}\epsilon_{ijk}a_{j}b_{k}\
(i=1,2,3)$ where $\epsilon_{ijk}$ is the Levi-Civita symbol. We start from the
following elementary lemmas: As in the main text, let
$c_{\pm}:=\frac{1\pm\sqrt{2}}{2}$ which are the solutions of $4c(c-1)=1$.

###### Lemma 1

Let ${\bm{a}}=(a_{1},a_{2},a_{3})$ and ${\bm{b}}=(b_{1},b_{2},b_{3})$ be
complex vectors in $\mathop{\mathbb{C}}\nolimits^{3}$ with
${\bm{b}}={\bm{b}}_{R}+i{\bm{b}}_{I}$ (the real and the imaginary parts).
Then, for any $x\in\mathop{\mathbb{R}}\nolimits$, we have

$c_{+}(x^{2}+|{\bm{a}}|^{2})|{\bm{b}}|^{2}\geq|{\bm{a}}|^{2}|{\bm{b}}|^{2}+2x|{\bm{a}}||{\bm{b}}_{R}||{\bm{b}}_{I}|.$
(37)

In case ${\bm{b}}\neq 0$, the equality is attained at
$x=(\sqrt{2}-1)|{\bm{a}}|$ if $|{\bm{b}}_{R}|=|{\bm{b}}_{I}|$.

[Proof] If ${\bm{b}}=0$, the inequality trivially holds. Assuming
${\bm{b}}\neq 0$, inequality (37) is simply the following quadratic inequality
for $x$:

$c_{+}|{\bm{b}}|^{2}x^{2}-2|{\bm{a}}||{\bm{b}}_{R}||{\bm{b}}_{I}|x+(c_{+}-1)|{\bm{a}}|^{2}|{\bm{b}}|^{2}\geq
0,$

hence is equivalent to the negative semi-definiteness of its discriminant:

$0\geq(2|{\bm{a}}||{\bm{b}}_{R}||{\bm{b}}_{I}|)^{2}-|{\bm{b}}|^{2}|{\bm{a}}|^{2}|{\bm{b}}|^{2},$

where we used the fact that $c_{+}$ is one of the solutions of $4c(c-1)=1$.
Since $|{\bm{b}}|^{2}=|{\bm{b}}_{R}|^{2}+|{\bm{b}}_{I}|^{2}$, the right hand
side is $-|{\bm{a}}|^{2}(|{\bm{b}_{R}}|^{2}-|{\bm{b}_{I}}|^{2})^{2}\leq 0$.
This proves the inequality (37) for all $x$. Finally, the discriminant is zero
when $|{\bm{b}_{R}}|=|{\bm{b}_{I}}|$. Thus, the equality for (37) is satisfied
at the point
$x=\frac{2|{\bm{a}}||{\bm{b}}_{R}||{\bm{b}}_{I}|}{2c_{+}|{\bm{b}}|^{2}}=\frac{|{\bm{a}}|}{2c_{+}}=(\sqrt{2}-1)|{\bm{a}}|$.
$\blacksquare$

###### Lemma 2

For any $x\in\mathop{\mathbb{R}}\nolimits$,
${\bm{y}},{\bm{z}},{\bm{w}}\in\mathop{\mathbb{C}}\nolimits^{3}$, we have

$(|{\bm{y}}|^{2}+|{\bm{z}}|^{2})(c_{+}|{\bm{w}}|^{2}-c_{-}x^{2})\geq
2|{\bm{w}}||{\bm{y}}||{\bm{z}}|x.$ (38)

In case $|{\bm{y}}|^{2}+|{\bm{z}}|^{2}\neq 0$, the equality is attained if
$x=(\sqrt{2}+1)|{\bm{w}}|$ if $|{\bm{y}}|^{2}=|{\bm{z}}|$.

[Proof] If ${\bm{y}}={\bm{z}}=0$, inequality (38) trivially holds. Assuming
$|{\bm{y}}|^{2}+|{\bm{z}}|^{2}\neq 0$, the inequality is the following
quadratic inequality:

$-c_{-}(|{\bm{y}}|^{2}+|{\bm{z}}|^{2})x^{2}-2|{\bm{w}}||{\bm{y}}||{\bm{z}}|x+c_{+}(|{\bm{y}}|^{2}+|{\bm{z}}|^{2})|{\bm{w}}|^{2}\geq
0,$

which is equivalent to the non-positivity of the discriminant:

$4|{\bm{w}}|^{2}|{\bm{y}}|^{2}|{\bm{z}}|^{2}+4c_{+}c_{-}(|{\bm{y}}|^{2}+|{\bm{z}}|^{2})^{2}|{\bm{w}}|^{2}\leq
0.$

However, noting $c_{+}c_{-}=-\frac{1}{4}$, the left hand side is
$-|{\bm{w}}|^{2}(|{\bm{y}}|^{2}-|{\bm{z}}|^{2})^{2}$, hence the non-positivity
is satisfied. In particular, the discriminant is zero if
$|{\bm{y}}|=|{\bm{z}}|$ and the equality is attained at
$x=-\frac{|{\bm{w}}|}{2c_{-}}=(\sqrt{2}+1)|{\bm{w}}|$. $\blacksquare$

[Proofs of (35) and (36)] We use the orthonormal basis
$F_{0}=\mathop{\mathbb{I}}\nolimits/\sqrt{2},F_{i}=\sigma_{i}/\sqrt{2}\
(i=1,2,3)$ of $M_{2}(\mathop{\mathbb{C}}\nolimits)$ where
$\sigma_{1},\sigma_{2},\sigma_{3}$ are Pauli matrices:

$\sigma_{1}=\left(\begin{array}[]{cc}0&1\\\ 1&0\\\
\end{array}\right),\sigma_{2}=\left(\begin{array}[]{cc}0&-i\\\ i&0\\\
\end{array}\right),\sigma_{3}=\left(\begin{array}[]{cc}1&0\\\ 0&-1\\\
\end{array}\right).$

Arbitrary $2\times 2$ matrices $A$ and $B$ are written by
$A=\sum_{\mu=0}^{3}a_{\mu}F_{\mu}$ and $B=\sum_{\mu=0}^{3}b_{\mu}F_{\mu}$ with
$a_{\mu},b_{\mu}\in\mathop{\mathbb{C}}\nolimits$. Note that, for the case of
(36), one simply uses $a_{0}=0$ for traceless condition for $A$. One has
$\|A\|^{2}=|a_{0}|^{2}+|{\bm{a}}|^{2},\|B\|^{2}=|b_{0}|^{2}+|{\bm{b}}|^{2}$. A
direct computation shows

$r(A,B)=|{\bm{a}}|^{2}|{\bm{b}}|^{2}-\frac{1}{2}(|{\bm{a}}\cdot{\bm{b}}|^{2}+|\overline{{\bm{a}}}\cdot{\bm{b}}|^{2})-{\rm
Im}(\overline{a_{0}}{\bm{a}}\cdot(\overline{\bm{b}}\times{\bm{b}})),$ (39)

where ${\bm{a}}=(a_{1},a_{2},a_{3})$ and ${\bm{b}}=(b_{1},b_{2},b_{3})$ are
complex three dimensional vectors. Therefore, if we restrict $A$ to be
traceless, i.e., $a_{0}=0$, the third terms in (39) vanishes:

$r(A,B)=|{\bm{a}}|^{2}|{\bm{b}}|^{2}-\frac{1}{2}(|{\bm{a}}\cdot{\bm{b}}|^{2}+|\overline{{\bm{a}}}\cdot{\bm{b}}|^{2}).$

By Scwarz inequality, this is lower bounded by $0$. Also, one has

$r(A,B)\leq|{\bm{a}}|^{2}|{\bm{b}}|^{2}\leq(|a_{0}|^{2}+|{\bm{a}}|^{2})(|b_{0}|^{2}+|{\bm{b}}|^{2})=\|A\|^{2}\|B\|^{2}.$
(40)

Moreover, it is easy to construct matrices $A$ and $B$ to attain all the above
equalities: For the lower bound, take parallel real vectors ${\bm{a}}$ and
${\bm{b}}$. For the upper bound, generally, any $A$ and $B$ with
$a_{0}=b_{0}=0$ and orthogonal conditions
${\bm{a}}\cdot{\bm{b}}=\overline{{\bm{a}}}\cdot{\bm{b}}=0$ attain the bound.
In particular, if we use real ${\bm{a}}$, the equality is achieved by a self-
adjoint matrix $A$. This completes the proof of (36).

To show the general bounds (35), let ${\bm{b}}={\bm{b}}_{R}+i{\bm{b}}_{I}$, so
that $\overline{\bm{b}}\times{\bm{b}}=2i{\bm{b}}_{R}\times{\bm{b}}_{I}$, and
therefore

$r(A,B)=|{\bm{a}}|^{2}|{\bm{b}}|^{2}-\frac{1}{2}(|{\bm{a}}\cdot{\bm{b}}|^{2}+|\overline{{\bm{a}}}\cdot{\bm{b}}|^{2})-2{\rm
Re}(\overline{a_{0}}{\bm{a}}\cdot({\bm{b}}_{R}\times{\bm{b}}_{I})).$ (41)

Using this expression, one observes
$\frac{1+\sqrt{2}}{2}\|A\|^{2}\|B\|^{2}-r(A,B)\geq\frac{1+\sqrt{2}}{2}(|a_{0}|^{2}+|{\bm{a}}|^{2})|{\bm{b}}|^{2}-|{\bm{a}}|^{2}|{\bm{b}}|^{2}-2|a_{0}||{\bm{a}}||{\bm{b}}_{R}||{\bm{b}}_{I}|$
where use has been made of Schwarz inequality and
$|{\bm{b}}_{R}\times{\bm{b}}_{I}|\leq|{\bm{b}}_{R}||{\bm{b}}_{I}|$. However,
by Lemma 1 (for $x=|a_{0}|$), this is non-negative, hence, one has the upper
bound in (35). It is easy to construct matrices $A$ and $B$ to achieve the
equality. For instance, let $\\{{\bm{a}},{\bm{b}_{R}},{\bm{b}_{I}}\\}$ form a
left-handed orthonormal base of $\mathop{\mathbb{R}}\nolimits^{3}$. Then,
using the equality condition in Lemma 1, all equalities in the above
inequalities are attained by taking $a_{0}=\sqrt{2}-1$ and $b_{0}=0$.

Finally, to show the lower bound in (35), let $V={\rm
span}_{\mathbb{C}}\\{{\bm{b}}_{R},{\bm{b}}_{I}\\}$ and $P$ be a projection
onto $V$, and let $P^{\perp}=I-P$. Then, $P{\bm{b}}={\bm{b}}$,
$P\overline{\bm{b}}=\overline{\bm{b}}$ and
$P^{\perp}({\bm{b}}_{R}\times{\bm{b}}_{I})={\bm{b}}_{R}\times{\bm{b}}_{I}$.
Therefore, $|{\bm{a}}\cdot{\bm{b}}|=|{\bm{a}}\cdot
P{\bm{b}}|=|P{\bm{a}}\cdot{\bm{b}}|\quad{\rm
and}\quad|\overline{\bm{a}}\cdot{\bm{b}}|=|{\bm{a}}\cdot\overline{\bm{b}}|=|P{\bm{a}}\cdot\overline{\bm{b}}|$,
and
${\bm{a}}\cdot({\bm{b}}_{R}\times{\bm{b}}_{I})=P^{\perp}{\bm{a}}\cdot({\bm{b}}_{R}\times{\bm{b}}_{I})$.
Considering $|{\bm{a}}|^{2}=|P{\bm{a}}|^{2}+|P^{\perp}{\bm{a}}|^{2}$, we have
$r(A,B)-\frac{1-\sqrt{2}}{2}\|A\|^{2}\|B\|^{2}\geq\frac{\sqrt{2}-1}{2}|{a}_{0}|^{2}|{\bm{b}}|^{2}+\frac{\sqrt{2}+1}{2}|P^{\perp}{\bm{a}}|^{2}|{\bm{b}}|^{2}-2{\rm
Re}(\overline{a_{0}}(P^{\perp}{\bm{a}})\cdot({\bm{b}}_{R}\times{\bm{b}}_{I}))\geq\frac{\sqrt{2}-1}{2}|{a}_{0}|^{2}|{\bm{b}}|^{2}+\frac{\sqrt{2}+1}{2}|P^{\perp}{\bm{a}}|^{2}|{\bm{b}}|^{2}-2|a_{0}||P^{\perp}{\bm{a}}||{\bm{b}}_{R}||{\bm{b}}_{I}|$.
This is shown to be non-negative by using Lemma 2 for
$x=|a_{0}|,{\bm{y}}={\bm{b}}_{R},{\bm{z}}={\bm{b}}_{I},{\bm{w}}=P^{\perp}{\bm{a}}$,
hence we have the lower bound in (35). It is also easy to construct matrices
$A$ and $B$ to achieve the equality. For instance, again let
$\\{{\bm{a}},{\bm{b}_{R}},{\bm{b}_{I}}\\}$ form a left-handed orthonormal base
of $\mathop{\mathbb{R}}\nolimits^{3}$. Then, using the equality condition in
Lemma 2, all equalities in the above inequalities are attained by taking
$a_{0}=\sqrt{2}+1$ and $b_{0}=0$.

$\blacksquare$

## References

  * [1] A. Böttcher, D. Wenzel, The Frobenius norm and the commutator, Linear Algebra Appl. 429, 1864 (2008).
  * [2] H. P. Breuer and F. Petruccione, The Theory of Open Quantum Systems (Oxford Univ. Press, Oxford, 2007).
  * [3] E. B. Davies, Quantum Theory of Open Systems (Academic Press, London, 1976).
  * [4] R. Alicki and K. Lendi, Quantum Dynamical Semigroups and Applications (Springer, Berlin, 1987).
  * [5] C. W. Gardiner and P. Zoller, Quantum Noise, 2nd ed. (Springer-Verlag, Heidelberg, 2000).
  * [6] G. Kimura, Elementary mathematical framework for open quantum $d$-level systems: Decoherence Overview, in: M. Nakahara, R. Rahimi, A. SaiToh (eds.), Decoherence Suppression in Quantum Systems 2008, World Scientific Publishers, 2009, 1.
  * [7] V. Gorini, A. Kossakowski, and E. C. G. Sudarshan, J. Math. Phys. 17, 821 (1976).
  * [8] G. Lindblad, Comm. Math. Phys. 48, 119 (1976).
  * [9] G. Kimura, Phys. Rev. A 66, 062113 (2002).
  * [10] G. Kimura, S. Ajisaka, K. Watanabe, Universal Constraints on Relaxation Times for $d$-Level GKLS Master Equations, Open Syst. Inform. Dynam. 24, 1 (2017).
  * [11] D. Chruscinski, G. Kimura, A. Kossakowski, Y. Shishido, On the universal constraints for relaxation rates for quantum dynamical semigroup, arXiv:2011.10159.
  * [12] P. A. M. Dirac, The Principles of Quantum Mechanics (Clarendon Press; 1982).
  * [13] A. Böttcher, D. Wenzel, How big can the commutator of two matrices be and how big is it typically? Linear Algebra Appl. 403, 216 (2005).
  * [14] S. W. Vong, X. Q. Jin, Proof of Böttcher and Wenzel’s conjecture, Oper. Matrices, 2, 435 (2008).
  * [15] Z. Lu, Normal Scalar Curvature Conjecture and its applications, J. Funct. Anal., 261, 1284 (2007).
  * [16] K. M. R. Audenaert, Variance bounds, with an application to norm bounds for commutators, Linear Algebra Appl. 432, 1126 (2009).
  * [17] C. M. Cheng, S. W. Vong, D. Wenzel, Commutators with maximal Frobenius norm, Linear Algebra Appl. 432, 292 (2010).
  * [18] R. Bhatia, Matrix Analysis (Springer 1997).
  * [19] K. Kraus, States, Effects, and Operations (Springer, 1983).
  * [20] M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information (Cambridge, England, 2000).
  * [21] M. Hayashi, S. Ishizaka, A. Kawachi, G. Kimura, T. Ogawa, Introduction to Quantum Information Science (Springer, 2015).
  * [22] M. M. Wolf, J. I. Cirac, Commun. Math. Phys. 279, 147 (2008).
  * [23] A. Abragam,  Principles of Nuclear Magnetism (Oxford University Press, 1961); C. P. Slichter,  Principles of Magnetic Resonance (Springer-Verlag, 1990).