# Duality of Hoffman constants

Javier F. Peña Tepper School of Business, Carnegie Mellon University, USA,
<EMAIL_ADDRESS>Juan C. Vera Department of Econometrics and Operations
Research, Tilburg University, The Netherlands<EMAIL_ADDRESS>Luis F.
Zuluaga Department of Industrial and Systems Engineering, Lehigh University,
USA<EMAIL_ADDRESS>
###### Abstract

Suppose $A\in\mathbb{R}^{m\times n}$ and consider the following canonical
systems of inequalities defined by $A$:

$\begin{array}[]{l}Ax=b\\\ x\geq 0\end{array}\qquad\text{ and }\qquad
A^{\text{\sf T}}y-c\leq 0.$

We establish some novel duality relationships between the Hoffman constants
for the above constraint systems of linear inequalities provided some suitable
Slater condition holds. The crux of our approach is a Hoffman duality
inequality for polyhedral systems of constraints. The latter in turn yields an
interesting duality identity between the Hoffman constants of the following
box-constrained systems of inequalities:

$\begin{array}[]{l}Ax=b\\\ \ell\leq x\leq u\end{array}\qquad\text{ and
}\qquad\ell\leq A^{\text{\sf T}}y-c\leq u$

for $\ell,u\in\mathbb{R}^{n}$ with $\ell<u.$

##  1 Introduction

A number of recent papers show a surge of interest in the central role that
Hoffman bounds and more error bounds play in mathematical programming. In
particular, Hoffman constants play a central role in modern developments of
first-order algorithms for linear programming [1, 13, 18] and also on some
recent advances on the conditional gradient method [12, 29]. Error bounds are
also instrumental for many other results on the convergence of a variety of
optimization algorithms [1, 3, 9, 10, 15, 16, 19, 22, 27, 26].

The now vast literature on error bounds (see [2, 5, 11, 17, 20, 23, 24, 28,
30] and the many references therein) started with the seminal paper of Hoffman
[14], who showed that the distance from a point $v\in\mathbb{R}^{m}$ to a
nonempty polyhedron of the form $\\{y\in\mathbb{R}^{m}:A^{\text{\sf T}}y\leq
c\\}$ can be bounded above in terms of a constant that depends only on $A$ and
the magnitude of the violation of the constraints $A^{\text{\sf T}}v\leq c$.
Hoffman’s result implies that the distance from a point
$u\in\mathbb{R}^{n}_{+}$ to a nonempty polyhedron of the form $\\{x\geq
0:Ax=b\\}$ can also be bounded in terms of a constant that depends only on $A$
and the magnitude of the violation of the constraints $Au=b$.

The renewed interest in Hoffman constants and the central role that duality
plays in optimization have inspired us to investigate the duality properties
of Hoffman constants. More precisely, this paper is concerned with the
following natural, yet seemingly overlooked, duality question concerning
Hoffman constants:

> Is there a relationship between the Hoffman constants of the linear systems
> of inequalities in $\mathbb{R}^{n}$ of the form $Ax=b,x\geq 0$ defined by a
> matrix $A\in\mathbb{R}^{m\times n}$ and those in $\mathbb{R}^{m}$ of the
> form $A^{\text{\sf T}}y\leq c$ defined by $A^{\text{\sf
> T}}\in\mathbb{R}^{n\times m}$?

We show that indeed there is a strong relationship between these Hoffman
constants. More precisely, we show that suitable Slater conditions readily
imply duality inequalities between the Hoffman constants. The direction of the
inequality is determined by the Slater condition that holds. In a nice
parallel fashion, for box-constrained systems of linear inequalities, we show
a stronger duality identity between the Hoffman constants. The crux of our
approach is a Hoffman duality inequality for polyhedral systems of constraints
(Theorem 2). The derivation and proofs of our results rely crucially on some
characterizations of Hoffman constants developed in our previous work [23].
The duality insight that we provide in this paper enhances the
characterizations of Hoffman constants in [23]. The latter characterizations
have led to several interesting developments in variational analysis [8, 7, 6,
21].

We next provide a summary of our main results and introduce some of the
notation and terminology that we use throughout the paper. Suppose
$A\in\mathbb{R}^{m\times n}$ and consider the following canonical systems of
inequalities defined by $A$:

$\begin{array}[]{l}Ax=b\\\ x\geq 0\end{array}\qquad\text{ and }\qquad
A^{\text{\sf T}}y-c\leq 0.$ (1)

Define the solution mappings
$P_{A}:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ and
$Q_{A}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ as follows

$P_{A}(b):=\\{x\geq 0:Ax=b\\},\qquad
Q_{A}(c):=\\{y\in\mathbb{R}^{m}:A^{\text{\sf T}}y\leq c\\}.$ (2)

In other words, $P_{A}(b)\subseteq\mathbb{R}^{n}$ and
$Q_{A}(c)\subseteq\mathbb{R}^{m}$ denote the set of solutions to the first and
to the second linear inequality systems in (1) for $b\in\mathbb{R}^{m}$ and
$c\in\mathbb{R}^{n}$ respectively.

The role of norms and their duals is central to our developments. To that end,
suppose $\mathbb{R}^{n}$ and $\mathbb{R}^{m}$ are endowed with some (primal)
norms $\|\cdot\|$. Let ${\mathrm{dist}}(\cdot,\cdot)$ denote the point-to-set
distance defined by the norm $\|\cdot\|$. Let $\|\cdot\|^{*}$ denote the dual
norms in $\mathbb{R}^{n}$ and $\mathbb{R}^{m}$ and let
${\mathrm{dist}}^{*}(\cdot,\cdot)$ denote the point-to-set distance defined by
the norm $\|\cdot\|^{*}$.

Hoffman’s Lemma [14] implies that there exists a finite constant $H(P_{A})$
such that for all $x\in\mathbb{R}^{n}_{+}$ and $b\in A(\mathbb{R}^{n}_{+})$

${\mathrm{dist}}(x,P_{A}(b))\leq H(P_{A})\cdot\|Ax-b\|.$ (3)

Similarly, Hoffman’s Lemma [14] implies that there exists a finite constant
$H(Q_{A})$ such that for all $y\in\mathbb{R}^{m}$ and
$c\in\mathbb{R}^{n}_{+}+A^{\text{\sf T}}(\mathbb{R}^{m})$

${\mathrm{dist}}^{*}(y,Q_{A}(c))\leq
H(Q_{A})\cdot{\mathrm{dist}}^{*}(c-A^{\text{\sf T}}y,\mathbb{R}^{n}_{+}).$ (4)

Throughout the paper we will write $\mathcal{H}(P_{A})$ to denote the sharpest
constant $H(P_{A})$ that satisfies (3), that is,

$\mathcal{H}(P_{A})=\sup_{b\in A(\mathbb{R}^{n}_{+})\atop
x\in\mathbb{R}^{n}_{+}\setminus
P_{A}(b)}\frac{{\mathrm{dist}}(x,P_{A}(b))}{\|Ax-b\|}.$ (5)

Likewise, we will write $\mathcal{H}(Q_{A})$ to denote the sharpest constant
$H(Q_{A})$ that satisfies (4), that is,

$\mathcal{H}(Q_{A})=\sup_{c\in A^{\text{\sf
T}}(\mathbb{R}^{m})+\mathbb{R}^{n}_{+}\atop y\in\mathbb{R}^{m}\setminus
Q_{A}(c)}\frac{{\mathrm{dist}}^{*}(y,Q_{A}(c))}{{\mathrm{dist}}^{*}(c-A^{\text{\sf
T}}y,\mathbb{R}^{n}_{+})}.$ (6)

We show (Theorem 3) that if the primal Slater condition $Ax=0,x>0$ holds for
some $x\in\mathbb{R}^{n}$ then $\mathcal{H}(P_{A})\leq\mathcal{H}(Q_{A})$. In
nice symmetric fashion, we also show that if the dual Slater condition
$A^{\text{\sf T}}y<0$ holds for some $y\in\mathbb{R}^{m}$ then
$\mathcal{H}(Q_{A})\leq\mathcal{H}(P_{A})$. Furthermore, we show (see Example
3 and Example 4) that in each of these two inequalites the right-hand-side can
be arbitrarily larger than the left-hand-side.

We also show a similar but stronger result for box-constrained systems of
linear inequalities. Suppose $\mathbb{B}:=\\{x\in\mathbb{R}^{n}:\ell\leq x\leq
u\\}$ for some $\ell,u\in\mathbb{R}^{n}$ with $\ell<u,$ and consider the
following pair of box-constrained systems of linear inequalities defined by
$A$ and $\mathbb{B}$:

$\begin{array}[]{ll}Ax=b\\\ x\in\mathbb{B}\end{array}\qquad\text{ and }\qquad
c-A^{\text{\sf T}}y\in\mathbb{B}.$ (7)

Define the solution mappings
$P_{A,\mathbb{B}}:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ and
$Q_{A,\mathbb{B}}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ for the box-
constrained systems of linear inequalities (7) as follows:

$P_{A,\mathbb{B}}(b):=\\{x\in\mathbb{B}:Ax=b\\},\qquad
Q_{A,\mathbb{B}}(c):=\\{y\in\mathbb{R}^{m}:A^{\text{\sf
T}}y-c\in\mathbb{B}\\}.$ (8)

Hoffman’s Lemma [14] implies that there exists a finite constant
$H(P_{A,\mathbb{B}})$ such that for all $x\in\mathbb{B}$ and $b\in
A(\mathbb{B})$

${\mathrm{dist}}(x,P_{A,\mathbb{B}}(b))\leq H(P_{A,\mathbb{B}})\cdot\|Ax-b\|.$
(9)

Similarly, Hoffman’s Lemma [14] implies that there exists a finite constant
$H(Q_{A,\mathbb{B}})$ such that for all $y\in\mathbb{R}^{m}$ and
$c\in\mathbb{B}+A^{\text{\sf T}}(\mathbb{R}^{m})$

${\mathrm{dist}}^{*}(y,Q_{A,\mathbb{B}}(c))\leq
H(Q_{A,\mathbb{B}})\cdot{\mathrm{dist}}^{*}(c-A^{\text{\sf T}}y,\mathbb{B}).$
(10)

Once again, we will write $\mathcal{H}(P_{A,\mathbb{B}})$ to denote the
sharpest constant $H(P_{A,\mathbb{B}})$ that satisfies (9) and
$\mathcal{H}(Q_{A,\mathbb{B}})$ to denote the sharpest constant
$H(Q_{A,\mathbb{B}})$ that satisfies (10). We show (Theorem 5) that
$\mathcal{H}(P_{A,\mathbb{B}})=\mathcal{H}(Q_{A,\mathbb{B}})$.

The above duality results concern Hoffman constants that depend on the matrix
$A$. However, in some contexts the problem of interest is more naturally
stated in terms of the space $L=\ker(A)$ or
$L^{\perp}=\operatorname{Im}(A^{\text{\sf T}})$. Hence we also establish
similar results for the Hoffman constants of the analogous canonical and box-
constrained systems of inequalities stated in terms of the spaces $L=\ker(A)$
and $L^{\perp}=\operatorname{Im}(A^{\text{\sf T}})$. More precisely, consider
the systems of linear inequalities

$\text{ find }x\in(L+b)\cap\mathbb{R}^{n}_{+}\qquad\text{ and }\qquad\text{
find }y\in(L^{\perp}+c)\cap\mathbb{R}^{n}_{+},$ (11)

as well as the box-constrained systems of linear inequalities

$\text{ find }x\in(L+b)\cap\mathbb{B}\qquad\text{ and }\qquad\text{ find
}y\in(L^{\perp}+c)\cap\mathbb{B}.$ (12)

We show (Theorem 4 and Theorem 6) that the same kind of duality relationships
hold for the Hoffman constants associated to the pair of problems (11) as well
as to the pair of problems (12).

##  2 Hoffman duality inequality

This section details the key technical tool underlying our developments,
namely the Hoffman duality inequality (Theorem 2 below).

Suppose $\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is a set-valued
mapping, that is, $\Phi(b)\subseteq\mathbb{R}^{n}$ for each
$b\in\mathbb{R}^{m}$. The graph of $\Phi$ is

${\mathrm{graph}}(\Phi)=\\{(b,x)\in\mathbb{R}^{m}\times\mathbb{R}^{n}:x\in\Phi(b)\\}.$

Observe that $\Phi$ is precisely the solution mapping of the following
feasibility problem

$\text{ find }x\in\mathbb{R}^{n}\text{ such that
}(b,x)\in{\mathrm{graph}}(\Phi).$

The domain ${\mathrm{dom}}(\Phi)\subseteq\mathbb{R}^{m}$, and image
$\operatorname{Im}(\Phi)\subseteq\mathbb{R}^{n}$, of $\Phi$ are as follows

${\mathrm{dom}}(\Phi):=\\{b\in\mathbb{R}^{m}:\Phi(b)\neq\emptyset\\},\;\operatorname{Im}(\Phi):=\bigcup_{b\in\mathbb{R}^{m}}\Phi(b).$

The inverse mapping $\Phi^{-1}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$
is defined via $b\in\Phi^{-1}(x)\Leftrightarrow x\in\Phi(b)$. Observe that

${\mathrm{graph}}(\Phi^{-1})=\\{(x,b)\in\mathbb{R}^{n}\times\mathbb{R}^{m}:(b,x)\in{\mathrm{graph}}(\Phi)\\}.$

Suppose each of the spaces $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$ is endowed
with some norm $\|\cdot\|$. Define the Hoffman constant $\mathcal{H}(\Phi)$ as
the sharpest $H(\Phi)$ such that for all $b\in{\mathrm{dom}}(\Phi)$ and all
$x\in\operatorname{Im}(\Phi)$ the following inequality holds

${\mathrm{dist}}(x,\Phi(b))\leq H(\Phi)\cdot{\mathrm{dist}}(b,\Phi^{-1}(x)).$

In other words, the Hoffman constant $\mathcal{H}(\Phi)$ is

$\mathcal{H}(\Phi):=\sup_{b\in{\mathrm{dom}}(\Phi)\atop
x\in\operatorname{Im}(\Phi)\setminus\Phi(b)}\frac{{\mathrm{dist}}(x,\Phi(b))}{{\mathrm{dist}}(b,\Phi^{-1}(x))}.$
(13)

Each of the above ${\mathrm{dist}}(\cdot,\cdot)$ is the point-to-set distance
defined via the norm in the underlying space.

######  Example 1.

Suppose $A\in\mathbb{R}^{m\times n}$ and $P_{A}$ is the first of the solution
mappings defined in (2). Then
${\mathrm{graph}}(P_{A})=\\{(Ax,x):x\in\mathbb{R}^{n}_{+}\\}$. Consequently,
${\mathrm{dom}}(P_{A})=A(\mathbb{R}^{n}_{+})$,
$\operatorname{Im}(P_{A})=\mathbb{R}^{n}_{+},$ and for any
$x\in\mathbb{R}^{n}_{+}$ we have $P_{A}^{-1}(x)=Ax$. According to (13) the
Hoffman constant $\mathcal{H}(P_{A})$ is

$\mathcal{H}(P_{A})=\sup_{b\in A(\mathbb{R}^{n}_{+})\atop
x\in\mathbb{R}^{n}_{+}\setminus
P_{A}(b)}\frac{{\mathrm{dist}}(x,P_{A}(b))}{{\mathrm{dist}}(b,\\{Ax\\})}=\sup_{b\in
A(\mathbb{R}^{n}_{+})\atop x\in\mathbb{R}^{n}_{+}\setminus
P_{A}(b)}\frac{{\mathrm{dist}}(x,P_{A}(b))}{\|Ax-b\|}.$

This is exactly the Hoffman constant $\mathcal{H}(P_{A})$ defined in (5) in
the Introduction.

We should clarify a minor but important detail concerning the notation
$\mathcal{H}(\Phi)$ of the Hoffman constant (13). In our previous article
[23], this constant was denoted $\mathcal{H}(\Phi^{-1})$. Thus our references
to [23], like Theorem 1 below, have been adjusted accordingly. Although this
is only a choice of notation, and thus of no fundamental relevance, the
notation in (13) is more convenient as it emphasizes the role of the solution
mapping $\Phi$. It is also consistent with the notation used in other recent
articles [8, 7].

A set-valued mapping $\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is
sublinear if ${\mathrm{graph}}(\Phi)$ is a convex cone. Define the norm of a
sublinear mapping $\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ as
follows

$\|\Phi\|=\max_{b\in{\mathrm{dom}}(\Phi)\atop\|b\|\leq
1}\min_{x\in\Phi(b)}\|x\|.$ (14)

Our main developments hinge on the characterization of Hoffman constants in
Theorem 1 below. The statement of this result relies on some notation that we
will use throughout the paper. Suppose
$\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is a polyhedral mapping,
that is, ${\mathrm{graph}}(\Phi)\subseteq\mathbb{R}^{m}\times\mathbb{R}^{n}$
is a polyhedron. For $(b,x)\in{\mathrm{graph}}(\Phi)$ or equivalently
$x\in\Phi(b)$, let $T_{(b,x)}(\Phi)$ denote the tangent cone to
${\mathrm{graph}}(\Phi)$ at $(b,x)$, that is,

$T_{(b,x)}(\Phi)=\\{(v,u)\in\mathbb{R}^{m}\times\mathbb{R}^{n}:(b,x)+t(v,u)\in{\mathrm{graph}}(\Phi)\text{
for some }t>0\\}.$

Let $\mathcal{T}(\Phi)$ denote the collection of all tangent cones at points
in ${\mathrm{graph}}(\Phi)$, that is,

$\mathcal{T}(\Phi):=\\{T_{(b,x)}(\Phi):(b,x)\in{\mathrm{graph}}(\Phi)\\},$

and let

${\mathfrak{S}}(\Phi):=\\{T\in\mathcal{T}(\Phi):{\mathrm{dom}}(\Phi_{T})\text{
is a linear subspace}\\}.$

For $T\in\mathcal{T}(\Phi)$ let
$\Phi_{T}:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ be the sublinear
mapping defined via

$x\in\Phi_{T}(b)\Leftrightarrow(b,x)\in T.$

In other words, $\Phi_{T}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is
the sublinear mapping that satisfies ${\mathrm{graph}}(\Phi_{T})=T$. We will
rely on the following characterization of $\mathcal{H}(\Phi)$ from [23,
Theorem 1 and Lemma 1].

######  Theorem 1.

Suppose $\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is a polyhedral
mapping. Then

$\mathcal{H}(\Phi)=\max_{T\in{\mathfrak{S}}(\Phi)}\|\Phi_{T}\|=\max_{T\in\mathcal{\mathcal{T}}(\Phi)}\|\Phi_{T}\|.$
(15)

######  Corollary 1.

Suppose $\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is a polyhedral
mapping and suppose $\mathcal{S}\subseteq\mathcal{T}(\Phi)$ satisfies the
following bounding property: for all $T\in{\mathfrak{S}}(\Phi)$ there exists
$T^{\prime}\in\mathcal{S}$ such that $\|\Phi_{T}\|\leq\|\Phi_{T^{\prime}}\|.$
Then

$\mathcal{H}(\Phi)=\max_{T\in\mathcal{S}}\|\Phi_{T}\|=\max_{T\in\mathcal{S}}\mathcal{H}(\Phi_{T}).$
(16)

In particular, if ${\mathrm{dom}}(\Phi)$ is a linear subspace then
$\mathcal{S}:=\\{{\mathrm{graph}}(\Phi)\\}$ satisfies the bounding property
and thus

$\mathcal{H}(\Phi)=\|\Phi\|.$ (17)

###### Proof.

The bounding property and (15) imply that

$\mathcal{H}(\Phi)=\max_{T\in{\mathfrak{S}}(\Phi)}\|\Phi_{T}\|\leq\max_{T\in\mathcal{S}}\|\Phi_{T}\|\leq\max_{T\in\mathcal{\mathcal{T}}(\Phi)}\|\Phi_{T}\|=\mathcal{H}(\Phi).$

Thus the first identity in (16) follows. For the second identity, first
observe that since ${\mathrm{graph}}(\Phi)$ is polyhedral, we have
$\mathcal{T}(\Phi_{T})\subseteq\mathcal{T}(\Phi)$ for all
$T\in\mathcal{T}(\Phi)$. Therefore (15) implies that
$\|\Phi_{T}\|\leq\mathcal{H}(\Phi_{T})\leq\mathcal{H}(\Phi)$ for all
$T\in\mathcal{T}(\Phi)$. Consequently the first identity in (16) implies that

$\mathcal{H}(\Phi)=\max_{T\in\mathcal{S}}\|\Phi_{T}\|\leq\max_{T\in\mathcal{S}}\mathcal{H}(\Phi_{T})\leq\mathcal{H}(\Phi).$

Hence the second identity in (16) follows as well.

When ${\mathrm{dom}}(\Phi)$ is a subspace, it readily follows that
${\mathrm{dom}}(\Phi)={\mathrm{dom}}(\Phi_{T})$ for all
$T\in\mathcal{T}(\Phi)$ and hence $\mathcal{S}:=\\{{\mathrm{graph}}(\Phi)\\}$
satisfies the bounding property. The latter fact and (16) imply (17). ∎

Suppose $\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is sublinear. The
upper adjoint $\Phi^{*}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is
defined as

$y\in\Phi^{*}(c)\Leftrightarrow\langle y,b\rangle\leq\langle c,x\rangle\text{
for all }(b,x)\in{\mathrm{graph}}(\Phi)$ (18)

To be more accurate, the upper adjoint $\Phi^{*}$ is a mapping between the
dual spaces of $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$. In other words,
$\Phi^{*}:(\mathbb{R}^{m})^{*}\rightrightarrows(\mathbb{R}^{n})^{*}$. Thus
according to (14) the norm of $\Phi^{*}$ is as follows

$\|\Phi\|^{*}=\max_{c\in{\mathrm{dom}}(\Phi^{*})\atop\|c\|^{*}\leq
1}\min_{y\in\Phi^{*}(c)}\|y\|^{*}.$ (19)

Similarly, according to (13) the Hoffman constant $\mathcal{H}(\Phi^{*})$ is

$\mathcal{H}(\Phi^{*}):=\sup_{c\in{\mathrm{dom}}(\Phi^{*})\atop
y\in\operatorname{Im}(\Phi^{*})\setminus\Phi^{*}(c)}\frac{{\mathrm{dist}}^{*}(y,\Phi^{*}(c))}{{\mathrm{dist}}^{*}(c,(\Phi^{*})^{-1}(y))}.$
(20)

where each ${\mathrm{dist}}^{*}(\cdot,\cdot)$ is the distance defined via the
dual norm $\|\cdot\|^{*}$ in the underlying dual space.

The following proposition details some properties of the upper adjoint that we
will use in some of our main developments.

######  Proposition 1.

Let $K\subseteq\mathbb{R}^{n}$ be a closed convex cone and
$K^{*}\subseteq\mathbb{R}^{n}$ its dual, that is,
$K^{*}:=\\{u\in\mathbb{R}^{n}:\langle u,x\rangle\geq 0\text{ for all }x\in
K\\}.$

  * (a)

Suppose $A\in\mathbb{R}^{m\times n}$ and
$\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is the set-valued mapping
$b\mapsto\Phi(b):=\\{x\in K:Ax=b\\}.$ Then
$\Phi^{*}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is the set-valued
mapping

$\displaystyle c\mapsto\Phi^{*}(c)$
$\displaystyle:=\\{y\in\mathbb{R}^{m}:c-A^{\text{\sf T}}y\in K^{*}\\}$
$\displaystyle=\\{y\in\mathbb{R}^{m}:A^{\text{\sf T}}y+s=c\text{ for some
}s\in K^{*}\\}.$

  * (b)

Suppose $L\subseteq\mathbb{R}^{n}$ is a linear subspace and
$\Phi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is the following set-
valued mapping

$b\mapsto\Phi(b):=\\{x\in K:x\in L+b\\}.$

Then $\Phi^{*}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is the following
set-valued mapping

$\displaystyle c\mapsto\Phi^{*}(c)$ $\displaystyle:=\\{y\in L^{\perp}:c-y\in
K^{*}\\}$ $\displaystyle=\\{y\in L^{\perp}:y+s=c\text{ for some }s\in
K^{*}\\}.$

###### Proof.

  * (a)

We have ${\mathrm{graph}}(\Phi)=\\{(Ax,x):x\in K\\}$. Therefore for
$c\in\mathbb{R}^{n}$

$\displaystyle y\in\Phi^{*}(c)$ $\displaystyle\Leftrightarrow\langle
y,Ax\rangle\leq\langle c,x\rangle\text{ for all }x\in K$
$\displaystyle\Leftrightarrow\langle c-A^{\text{\sf T}}y,x\rangle\geq 0\text{
for all }x\in K$ $\displaystyle\Leftrightarrow c-A^{\text{\sf T}}y\in K^{*}.$

  * (b)

We have ${\mathrm{graph}}(\Phi)=\\{(w+x,x):x\in K,w\in L\\}$. Therefore for
$c\in\mathbb{R}^{n}$

$\displaystyle y\in\Phi^{*}(c)$ $\displaystyle\Leftrightarrow\langle
y,w+x\rangle\leq\langle c,x\rangle\text{ for all }x\in K,w\in L$
$\displaystyle\Leftrightarrow\langle c-y,x\rangle+\langle y,w\rangle\geq
0\text{ for all }x\in K,w\in L$ $\displaystyle\Leftrightarrow c-y\in
K^{*}\text{ and }y\in L^{\perp}.$

∎

######  Example 2.

Suppose $A\in\mathbb{R}^{m\times n}$ and $P_{A},Q_{A}$ are the solution
mappings defined in (2). Then Proposition 1(a) implies that

$P_{A}^{*}=Q_{A}.$ (21)

Furthermore, ${\mathrm{graph}}(Q_{A})=\\{(A^{\text{\sf
T}}y+s,y):y\in\mathbb{R}^{m},s\in\mathbb{R}^{n}_{+}\\}$. Consequently,
${\mathrm{dom}}(Q_{A})=A^{\text{\sf T}}(\mathbb{R}^{m})+\mathbb{R}^{n}_{+}$,
$\operatorname{Im}(Q_{A})=\mathbb{R}^{m},$ $Q_{A}^{-1}(y)=A^{\text{\sf
T}}y+\mathbb{R}^{n}_{+}$ for $y\in\mathbb{R}^{m}$, and according to (20) the
Hoffman constant $\mathcal{H}(Q_{A})$ is

$\mathcal{H}(Q_{A})=\sup_{c\in A^{\text{\sf
T}}(\mathbb{R}^{m})+\mathbb{R}^{n}_{+}\atop y\in\mathbb{R}^{m}\setminus
Q_{A}(c)}\frac{{\mathrm{dist}}^{*}(y,Q_{A}(c))}{{\mathrm{dist}}^{*}(c,A^{\text{\sf
T}}y+\mathbb{R}^{n}_{+})}=\sup_{c\in A^{\text{\sf
T}}(\mathbb{R}^{m})+\mathbb{R}^{n}_{+}\atop y\in\mathbb{R}^{m}\setminus
Q_{A}(c)}\frac{{\mathrm{dist}}^{*}(y,Q_{A}(c))}{{\mathrm{dist}}^{*}(c-A^{\text{\sf
T}}y,\mathbb{R}^{n}_{+})}.$

This is exactly the Hoffman constant $\mathcal{H}(Q_{A})$ defined in (6) in
the introduction.

In the special case when ${\mathrm{dom}}(\Phi)$ is a linear subspace, the
following norm duality identity holds [4, 23]

$\|\Phi\|=\max_{u\in{\mathrm{dom}}(\Phi^{*})\atop\|u\|^{*}\leq
1}\max_{y\in\Phi^{*}(u)}\|y\|^{*}.$ (22)

In particular, when ${\mathrm{dom}}(\Phi)$ is a linear subspace, identities
(19) and (22) imply the following norm duality inequality

$\|\Phi\|=\max_{u\in{\mathrm{dom}}(\Phi^{*})\atop\|u\|^{*}\leq
1}\max_{y\in\Phi^{*}(u)}\|y\|^{*}\geq\max_{c\in{\mathrm{dom}}(\Phi^{*})\atop\|c\|^{*}\leq
1}\min_{y\in\Phi^{*}(c)}\|y\|^{*}=\|\Phi^{*}\|^{*}.$

In contrast, the Hoffman constants $\mathcal{H}(\Phi)$ and
$\mathcal{H}(\Phi^{*})$ satisfy an analogous inequality in the reverse
direction, as the next theorem shows.

######  Theorem 2 (Hoffman duality inequality).

Suppose $\Phi:\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is a polyhedral
sublinear mapping. Then

$\|\Phi\|\leq\mathcal{H}(\Phi^{*}).$

In particular, if ${\mathrm{dom}}(\Phi)$ is a linear subspace then

$\mathcal{H}(\Phi)\leq\mathcal{H}(\Phi^{*}).$

###### Proof.

By Theorem 1 and Corollary 1, it suffices to show that there exists
$T\in\mathcal{T}(\Phi^{*})$ such that $\|\Phi^{*}_{T}\|^{*}\geq\|\Phi\|$. To
that end, let $\bar{b}\in{\mathrm{dom}}(\Phi)$ with $\|\bar{b}\|=1$ be such
that

$\|\Phi\|=\min_{x\in\Phi(\bar{b})}\|x\|.$

The existence of such $\bar{b}$ follows from (14). We will show that there
exists $T\in\mathcal{T}(\Phi^{*})$ and
$\bar{u}\in{\mathrm{dom}}(\Phi^{*}_{T})$ with $\|\bar{u}\|^{*}\leq 1$ such
that

$v\in(\Phi^{*}_{T})(\bar{u})\Rightarrow\|v\|^{*}\geq\min_{x\in\Phi(\bar{b})}\|x\|.$
(23)

This will finish the proof because (14) and (23) imply that

$\|\Phi^{*}_{T}\|^{*}=\max_{u\in{\mathrm{dom}}(\Phi_{T}^{*})\atop\|u\|^{*}\leq
1}\min_{v\in(\Phi^{*}_{T})(\bar{u})}\|v\|^{*}\geq\min_{v\in(\Phi^{*}_{T})(\bar{u})}\|v\|^{*}\geq\min_{x\in\Phi(\bar{b})}\|x\|=\|\Phi\|.$

We next construct $T\in\mathcal{T}(\Phi^{*})$ and
$\bar{u}\in{\mathrm{dom}}(\Phi^{*}_{T})$ with $\|\bar{u}\|^{*}\leq 1$ such
that (23) holds. To that end, first observe that

$\min_{x\in\Phi(\bar{b})}\|x\|=\min_{x\in\Phi(\bar{b})}\max_{\|w\|^{*}\leq
1}\langle w,x\rangle.$ (24)

Second, apply Sion’s minimax theorem [25] to get

$\min_{x\in\Phi(\bar{b})}\max_{\|w\|^{*}\leq 1}\langle
w,x\rangle=\max_{\|w\|^{*}\leq 1}\min_{x\in\Phi(\bar{b})}\langle w,x\rangle.$
(25)

Third, since $\Phi$ is a polyhedral sublinear mapping,
$K:={\mathrm{graph}}(\Phi)$ is a polyhedral convex cone and thus convex
duality implies that for and each $w\in\mathbb{R}^{n}$

$\min_{x\in\Phi(\bar{b})}\langle
w,x\rangle=\min_{x\in\mathbb{R}^{n}\atop(\bar{b},x)\in K}\langle
w,x\rangle=\max_{v\in\mathbb{R}^{m}\atop(-v,w)\in K^{*}}\langle
v,\bar{b}\rangle=\max_{v\in\Phi^{*}(w)}\langle v,\bar{b}\rangle.$ (26)

Putting together (24), (25), and (26) we get

$\min_{x\in\Phi(\bar{b})}\|x\|=\min_{x\in\Phi(\bar{b})}\max_{\|w\|^{*}\leq
1}\langle w,x\rangle=\max_{\|w\|^{*}\leq 1\atop v\in\Phi^{*}(w)}\langle
v,\bar{b}\rangle.$ (27)

Let $\bar{x}$ and $(\bar{v},\bar{w})$ be optimal solutions to the left-most
and right-most problems in (27). Then
$\bar{x}\in\Phi(\bar{b}),\;\bar{v}\in\Phi^{*}(\bar{w}),$ and

$\|\bar{x}\|=\langle\bar{w},\bar{x}\rangle=\langle\bar{v},\bar{b}\rangle.$
(28)

Let $T:=T_{(\bar{w},\bar{v})}(\Phi^{*})\in\mathcal{T}(\Phi^{*})$. Observe that
$(-\bar{w},-\bar{v})\in T$. In addition, for all $(-\bar{w},v)\in T$ we have
$\bar{v}+tv\in\Phi^{*}(\bar{w}-t\bar{w})$ for $t>0$ sufficiently small and
hence the construction of the upper adjoint $\Phi^{*}$ and (28) yield

$\langle\bar{v}+tv,\bar{b}\rangle\leq\langle\bar{w}-t\bar{w},\bar{x}\rangle\Rightarrow\langle
v,\bar{b}\rangle\leq-\langle\bar{w},\bar{x}\rangle.$

Thus $\bar{u}:=-\bar{w}\in{\mathrm{dom}}(\Phi_{T}),$
$\|\bar{u}\|^{*}=\|\bar{w}\|^{*}\leq 1$, and for all $v\in\Phi^{*}(\bar{u})$
we have

$\min_{x\in\Phi(\bar{b})}\|x\|=\|\bar{x}\|=\langle\bar{w},\bar{x}\rangle\leq-\langle
v,\bar{b}\rangle\leq\|v\|^{*}\cdot\|\bar{b}\|=\|v\|^{*}.$

Therefore (23) holds.

∎

##  3 Canonical systems of linear inequalities

Suppose $A\in\mathbb{R}^{m\times n}$. Consider the solution mappings
$P_{A},Q_{A}$ for the canonical systems of linear inequalities (1) defined via
(2). Observe that the solution mappings $P_{A},Q_{A}$ are polyhedral sublinear
mappings.

######  Theorem 3.

Suppose $A\in\mathbb{R}^{m\times n}$. Let $P_{A},Q_{A}$ be the solution
mappings defined via (2).

  * (a)

Suppose the following primal Slater condition holds:

$Ax=0\text{ for some }x>0.$

Then $\mathcal{H}(P_{A})\leq\mathcal{H}(Q_{A})$.

  * (b)

Suppose the following dual Slater condition holds:

$A^{\text{\sf T}}y<0\text{ for some }y\in\mathbb{R}^{m}.$

Then $\mathcal{H}(Q_{A})\leq\mathcal{H}(P_{A})$.

###### Proof.

The proof follows from Theorem 2 and the identity (21) as we next detail.

  * (a)

If $Ax=0$ for some $x>0$ then
${\mathrm{dom}}(P_{A})=A(\mathbb{R}^{n}_{+})=A(\mathbb{R}^{n})$. In
particular, ${\mathrm{dom}}(P_{A})$ is a linear subspace. Therefore, Theorem 2
and (21) imply that
$\mathcal{H}(P_{A})\leq\mathcal{H}(P_{A}^{*})=\mathcal{H}(Q_{A}).$

  * (b)

If $A^{\text{\sf T}}y<0$ for some $y\in\mathbb{R}^{m}$ then
${\mathrm{dom}}(Q_{A})=A(\mathbb{R}^{m})+\mathbb{R}^{n}_{+}=\mathbb{R}^{n}$.
In particular ${\mathrm{dom}}(Q_{A})$ is a linear subspace. Therefore, Theorem
2 and (21) imply that
$\mathcal{H}(Q_{A})\leq\mathcal{H}(Q_{A}^{*})=\mathcal{H}(P_{A}).$

∎

We next consider the canonical systems of linear inequalities (11) defined via
$L=\ker(A)$ and $L^{\perp}=\operatorname{Im}(A^{\text{\sf T}})$. Let
$\overline{P}_{L}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and
$\overline{Q}_{L^{\perp}}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ be
the solution mappings for the canonical systems of linear inequalities (11),
namely:

$\overline{P}_{L}(b):=\\{x\geq 0:x\in
L+b\\},\qquad\overline{Q}_{L^{\perp}}(c):=\\{y\in L^{\perp}:y\leq c\\}.$ (29)

In other words, $\overline{P}_{L}(b)=\mathbb{R}^{n}_{+}\cap(L+b)$ and
$\overline{Q}_{L^{\perp}}(c)=L^{\perp}\cap(c-\mathbb{R}^{n}_{+}).$

Observe that the solution mappings $\overline{P}_{L},\overline{Q}_{L^{\perp}}$
are polyhedral sublinear mappings. Furthermore, the Hoffman constants defined
via (13) for the mappings $\overline{P}_{L}$ and $\overline{Q}_{L^{\perp}}$
are as follows. First, observe that
${\mathrm{dom}}(\overline{P}_{L})=L+\mathbb{R}^{n}_{+},\;\operatorname{Im}(\overline{P}_{L})=\mathbb{R}^{n}_{+}$,
and $\overline{P}_{L}^{-1}(x)=x+L$ for all $x\in\mathbb{R}^{n}_{+}$. Thus

$\mathcal{H}(\overline{P}_{L})=\sup_{b\in L+\mathbb{R}^{n}_{+}\atop
x\in\mathbb{R}^{n}_{+}\setminus\overline{P}_{L}(b)}\frac{{\mathrm{dist}}(x,\overline{P}_{L}(b))}{{\mathrm{dist}}(b,x+L)}.$

Second, observe that
${\mathrm{dom}}(\overline{Q}_{L})=L^{\perp}+\mathbb{R}^{n}_{+},\;\operatorname{Im}(\overline{Q}_{L^{\perp}})=L^{\perp}$,
and $\overline{Q}_{L^{\perp}}^{-1}(y)=y+\mathbb{R}^{n}_{+}$ for all $y\in
L^{\perp}$. Thus

$\mathcal{H}(\overline{Q}_{L^{\perp}})=\sup_{c\in
L^{\perp}+\mathbb{R}^{n}_{+}\atop y\in
L^{\perp}\setminus\overline{Q}_{L^{\perp}}(c)}\frac{{\mathrm{dist}}(y,\overline{Q}_{L^{\perp}}(c))}{{\mathrm{dist}}(c,y+\mathbb{R}^{n}_{+})}.$

Furthermore, Proposition 1(b) implies that

$\overline{P}_{L}^{*}=\overline{Q}_{L^{\perp}}.$ (30)

We have the following analogue of Theorem 3.

######  Theorem 4.

Suppose $A\in\mathbb{R}^{m\times n}$ and $L:=\ker(A)$. Let
$\overline{P}_{L},\overline{Q}_{L^{\perp}}$ be the solution mappings defined
as in (29) above.

  * (a)

Suppose the following primal Slater condition holds:

$L\cap\mathbb{R}^{n}_{++}\neq\emptyset.$

Then $\mathcal{H}(\overline{P}_{L})\leq\mathcal{H}(\overline{Q}_{L^{\perp}})$.

  * (b)

Suppose the following dumal Slater condition holds:

$L^{\perp}\cap\mathbb{R}^{n}_{++}\neq\emptyset.$

Then $\mathcal{H}(\overline{Q}_{L^{\perp}})\leq\mathcal{H}(\overline{P}_{L})$.

###### Proof.

This proof is a straightforward modification of the proof of Theorem 3.

  * (a)

If $L\cap\mathbb{R}^{n}_{++}\neq\emptyset$ then
${\mathrm{dom}}(\overline{P}_{L})=L+\mathbb{R}^{n}_{+}=\mathbb{R}^{n}$. In
particular, ${\mathrm{dom}}(\overline{P}_{L})$ is a linear subspace.
Therefore, Theorem 2 and (30) imply that
$\mathcal{H}(\overline{P}_{L})\leq\mathcal{H}(\overline{P}_{L}^{*})=\mathcal{H}(\overline{Q}_{L^{\perp}})$.

  * (b)

If $L^{\perp}\cap\mathbb{R}^{n}_{++}\neq\emptyset$ then
${\mathrm{dom}}(\overline{Q}_{L^{\perp}})=L^{\perp}+\mathbb{R}^{n}_{+}=\mathbb{R}^{n}$.
In particular, ${\mathrm{dom}}(\overline{Q}_{L^{\perp}})$ is a linear
subspace. Therefore, Theorem 2 and (30) imply that
$\mathcal{H}(\overline{Q}_{L^{\perp}})\leq\mathcal{H}(\overline{Q}_{L^{\perp}}^{*})=\mathcal{H}(\overline{P}_{L})$.

∎

It is easy to see that the primal and dual Slater conditions in parts (a) and
(b) of Theorem 3 cannot both hold. Likewise for the primal and dual Slater
conditions in parts (a) and (b) of Theorem 4. Therefore, there is an inherent
dual asymmetry between the Hoffman constants of the canonical systems (1) and
(11). By contrast, in Section 4 below we show that there is a perfect dual
symmetry between the Hoffman constants of the box-constrained systems (7) and
(12).

The two examples below show that the right-hand-side of each of the
inequalities in Theorem 3 and Theorem 4 can be arbitrarily larger than the
left-hand-side. For ease of computation, the following examples assume that
$\mathbb{R}^{m}$ and $\mathbb{R}^{n}$ are endowed with the $\ell_{2}$-norm and
the $\ell_{1}$-norm respectively and thus the dual spaces
$(\mathbb{R}^{m})^{*}$ and $(\mathbb{R}^{n})^{*}$ are endowed with the
$\ell_{2}$-norm and the $\ell_{\infty}$-norm respectively.

From [23, equations (9) and (18)] it follows that for this choice of norms and
$A\in\mathbb{R}^{m\times n}$ the Hoffman constants $\mathcal{H}(P_{A})$ and
$\mathcal{H}(Q_{A})$ have the following geometric properties.

First, if $Ax=0$ for some $x>0$ then

$\frac{1}{\mathcal{H}(P_{A})}=\frac{1}{\|P_{A}\|}=\inf\\{\|Au\|_{2}:Au\not\in\\{Ax:x\geq
0,\|x\|_{1}=1\\}\\}.$ (31)

In other words, if $Ax=0$ for some $x>0$ then $1/\mathcal{H}(P_{A})$ is the
distance from the origin to the relative boundary of the convex hull of the
columns of $A$.

Second, if $A^{\text{\sf T}}y<0$ for some $y\in\mathbb{R}^{n}$ then

$\displaystyle\frac{1}{\mathcal{H}(Q_{A})}$
$\displaystyle=\frac{1}{\|Q_{A}\|^{*}}$
$\displaystyle=\min\\{\|y\|_{2}:A^{\text{\sf T}}y\geq\mathbf{1}\\}$
$\displaystyle=\min\\{\|Ax\|_{2}:x\geq 0,\|x\|_{1}=1\\}.$ (32)

In other words, if $A^{\text{\sf T}}y<0$ for some $y\in\mathbb{R}^{n}$ then
$1/\mathcal{H}(Q_{A})$ is the distance from the origin to the convex hull of
the columns of $A$.

######  Example 3.

Suppose $m=2,n=4,\theta\in(0,\pi/6)$ and

$A=\begin{bmatrix}0&0&\cos(\theta)&-\cos(\theta)\\\
1&-1&-\sin(\theta)&-\sin(\theta)\end{bmatrix}.$

In this case the primal Slater condition $Ax=0,x>0$ holds at the following
point

$\bar{x}:=\begin{bmatrix}1+2\sin(\theta)&1&1&1\end{bmatrix}^{\text{\sf T}}.$
(33)

Furthermore, (31) and some simple calculations show that

$\mathcal{H}(P_{A})=\frac{1}{\sin\left(\frac{\pi}{4}-\frac{\theta}{2}\right)}<\frac{1}{\sin\left(\frac{\pi}{6}\right)}.$

On the other hand, $\mathcal{H}(Q_{A})\geq 1/\sin(\theta)$ because for
$c=\begin{bmatrix}1/\sin(\theta)&0&-1&-1\end{bmatrix}^{\text{\sf T}}$ and
$v=\begin{bmatrix}0&0\end{bmatrix}^{\text{\sf T}}$ we have
${\mathrm{dist}}^{*}(c-A^{\text{\sf T}}v,\mathbb{R}^{n}_{+})=\|(A^{\text{\sf
T}}v-c)_{+}\|_{\infty}=1$ and

$y\in Q_{A}(c)\Rightarrow\|v-y\|_{2}=\|y\|_{2}\geq
y_{2}\geq\frac{1}{\sin(\theta)}.$

Thus

${\mathrm{dist}}(v,Q_{A}(c))\geq\frac{1}{\sin(\theta)}=\frac{1}{\sin(\theta)}\cdot{\mathrm{dist}}^{*}(c-A^{\text{\sf
T}}v,\mathbb{R}^{n}_{+}).$

Since this holds for any $\theta\in(0,\pi/6)$, it follows that
$\mathcal{H}(Q_{A})$ can be arbitrarily larger than $\mathcal{H}(P_{A})$ by
choosing $\theta$ sufficiently small.

Let $L=\ker(A)$. The following more involved calculations show that
$\mathcal{H}(\overline{Q}_{L^{\perp}})$ can also be arbitrarily larger than
$\mathcal{H}(\overline{P}_{L})$ by choosing $\theta$ sufficiently small.
Observe that $\bar{x}\in L$ for $\bar{x}$ as in (33). Since all coordinates of
$\bar{x}$ are at least one, it follows that for all $b\in\mathbb{R}^{n}$ with
$\|b\|_{1}\leq 1$ the point $x:=b+\bar{x}$ satisfies $x\geq 0$ and
$\|x\|_{1}\leq\|b\|_{1}+\|\bar{x}\|_{1}=5+2\sin(\theta)$. Consequently
identity (17) in Corollary 1 implies that
$\mathcal{H}(\overline{P}_{L})=\|\overline{P}_{L}\|\leq 5+2\sin(\theta)\leq
7$. On the other hand, $\mathcal{H}(\overline{Q}_{L^{\perp}})\geq
1/\sin(\theta)$ because for
$c=\begin{bmatrix}1/\sin(\theta)&0&-1&-1\end{bmatrix}^{\text{\sf T}}$ and
$v:=0\in L^{\perp}$, we have
${\mathrm{dist}}^{*}(c,(\overline{Q}_{L^{\perp}})^{-1}(v))={\mathrm{dist}}^{*}(c,\mathbb{R}^{n}_{+})=1$
and

$y\in\overline{Q}_{L^{\perp}}(c)\Rightarrow\|y\|_{\infty}\geq|y_{2}|\geq\frac{|y_{4}|}{\sin(\theta)}\geq\frac{1}{\sin(\theta)}.$

Thus

${\mathrm{dist}}^{*}(v,\overline{Q}_{L^{\perp}}(c))\geq\frac{1}{\sin(\theta)}\geq\frac{1}{\sin(\theta)}\cdot{\mathrm{dist}}^{*}(c,(\overline{Q}_{L^{\perp}})^{-1}(v)).$

######  Example 4.

Suppose $m=2,n=3,\theta\in(0,\pi/6)$ and

$A=\begin{bmatrix}\sin(\theta)&0&1\\\ 1&1&0\end{bmatrix}.$

In this case the dual Slater condition $A^{\text{\sf T}}y<0$ holds for
$\bar{y}=-\begin{bmatrix}1&1\end{bmatrix}^{\text{\sf T}}$. Furthermore, (3)
and some simple calculations show that

$\mathcal{H}(Q_{A})=\|Q_{A}\|=\sqrt{2}.$

On the other hand, $\mathcal{H}(P_{A})\geq 2/\sin(\theta)$ because for
$b=\begin{bmatrix}0&1\end{bmatrix}^{\text{\sf T}}$ and
$u=\begin{bmatrix}1&0&0\end{bmatrix}^{\text{\sf T}}$ we have
$\|Au-b\|_{2}=\sin(\theta)$ and

$x\in P_{A}(b)\Rightarrow\|x-u\|_{1}\geq 2.$

Thus

${\mathrm{dist}}(u,P_{A}(b))\geq 2=\frac{2}{\sin(\theta)}\cdot\|Au-b\|_{2}.$

Since this holds for any $\theta\in(0,\pi/6)$, it follows that
$\mathcal{H}(P_{A})$ can be arbitrarily larger than $\mathcal{H}(Q_{A})$ by
choosing $\theta$ sufficiently small.

Let $L=\ker(A)$. The following more involved calculations show that
$\mathcal{H}(\overline{P}_{L})$ can also be arbitrarily larger than
$\mathcal{H}(\overline{Q}_{L^{\perp}})$ by choosing $\theta$ sufficiently
small. First, a simple calculation shows that

$L=\\{\begin{bmatrix}-t&t&t\cdot\sin(\theta)\end{bmatrix}:t\in\mathbb{R}\\}.$
(34)

Next, observe that for all $c\in\mathbb{R}^{n}$ with $\|c\|_{\infty}\leq 1$ we
have $\bar{y}\leq c$ for

$\bar{y}:=-\begin{bmatrix}1+\sin(\theta)&1&1\end{bmatrix}^{\text{\sf T}}\in
L^{\perp}.$

Consequently identity (17) in Corollary 1 implies that
$\mathcal{H}(\overline{Q}_{L^{\perp}})=\|\overline{Q}_{L^{\perp}}\|\leq\|\bar{y}\|_{\infty}=1+\sin(\theta)<2.$
On the other hand, $\mathcal{H}(\overline{P}_{L})\geq 2/\sin(\theta)$ because
for $b=\begin{bmatrix}1/\sin(\theta)&0&-1\end{bmatrix}^{\text{\sf T}}$ and
$u=\begin{bmatrix}1/\sin(\theta)&0&0\end{bmatrix}^{\text{\sf
T}}\in\mathbb{R}^{n}_{+}$ we have

${\mathrm{dist}}(b,(\overline{P}_{L})^{-1}(u))={\mathrm{dist}}(b,u+L)\leq\|b-u\|_{1}=1,$

and the construction of $\overline{P}_{L}$ and (34) imply that

$\displaystyle x\in\overline{P}_{L}(b)$ $\displaystyle\Leftrightarrow
x=\begin{bmatrix}\frac{1}{\sin(\theta)}-t&t&-1+t\cdot\sin(\theta)\end{bmatrix}^{\text{\sf
T}}\geq 0\text{ for some }t\in\mathbb{R}$ $\displaystyle\Leftrightarrow
x=\begin{bmatrix}0&\frac{1}{\sin(\theta)}&0\end{bmatrix}^{\text{\sf T}}.$

Thus

$x\in\overline{P}_{L}(b)\Rightarrow\|u-x\|_{1}=\left\|\begin{bmatrix}\frac{1}{\sin(\theta)}&-\frac{1}{\sin(\theta)}&0\end{bmatrix}^{\text{\sf
T}}\right\|_{1}=\frac{2}{\sin(\theta)},$

and so

${\mathrm{dist}}(u,\overline{P}_{L}(b))=\frac{2}{\sin(\theta)}\geq\frac{2}{\sin(\theta)}\cdot{\mathrm{dist}}(b,(\overline{P}_{L})^{-1}(u)).$

##  4 Box-constrained linear inequality systems

Suppose $A\in\mathbb{R}^{m\times n}$ and $\ell,u\in\mathbb{R}^{n}$ with
$\ell<u$ are fixed. Let $L:=\ker(A)$ and
$\mathbb{B}:=\\{x\in\mathbb{R}^{n}:\ell\leq x\leq u\\}$ and consider the box-
constrained systems of linear inequalities (7).

######  Theorem 5.

Suppose $A\in\mathbb{R}^{m\times n}$ and
$\mathbb{B}:=\\{x\in\mathbb{R}^{n}:\ell\leq x\leq u\\}$ for some
$\ell,u\in\mathbb{R}^{n}$ with $\ell<u.$ Let
$P_{A,\mathbb{B}},\;Q_{A,\mathbb{B}}$ be the solution mappings for the box-
constrained systems of linear inequalities (7) defined in (8). Then
$\mathcal{H}(P_{A,\mathbb{B}})=\mathcal{H}(Q_{A,\mathbb{B}}).$

###### Proof.

To ease notation, throughout this proof let $\Phi:=P_{A,\mathbb{B}}$ and
$\Psi:=Q_{A,\mathbb{B}}$. Before proving the identity
$\mathcal{H}(\Phi)=\mathcal{H}(\Psi)$, we establish the convenient expressions
(35) and (36) below for $\mathcal{H}(\Phi)$ and $\mathcal{H}(\Psi)$.

Observe that ${\mathrm{graph}}(\Phi)=\\{(Ax,x):x\in\mathbb{B}\\}$. Thus it
follows that every $T\in\mathcal{T}(\Phi)$ is of the form
$T=T_{I,J}=\\{(Ax,x):x_{I}\geq 0,x_{J}\leq 0\\}$ for some $I,J\subseteq[n]$
with $I\cap J=\emptyset$. For simplicity, we shall write $\Phi_{I,J}$ as
shorthand for $\Phi_{T_{I,J}}$ and $\Phi_{I}$ as shorthand for
$\Phi_{T_{I,I^{c}}}$.

We claim that the collection $\\{T_{I,I^{c}}:I\subseteq[n]\\}$ satisfies the
bounding property and thus Corollary 1 implies that

$\mathcal{H}(\Phi)=\max_{I\subseteq[n]}\|\Phi_{I}\|=\max_{I\subseteq[n]}\;\mathcal{H}(\Phi_{I}).$
(35)

We next prove the above claim that $\\{T_{I,I^{c}}:I\subseteq[n]\\}$ satisfies
the bounding property. To that end, suppose $I,J\subseteq[n]$ with $I\cap
J=\emptyset$ and let $b\in{\mathrm{dom}}(\Phi_{I,J})$ be such that $\|b\|=1$
and

$\|\Phi_{I,J}\|=\min_{x\in\Phi_{I,J}(b)}\|x\|=\min\\{\|x\|:Ax=b,x_{I}\geq
0,x_{J}\leq 0\\}.$

Suppose $\bar{x}$ is a minimizer of the last expression and let

$I^{\prime}:=I\cup\\{i:\bar{x}_{i}>0\\}.$

This choice of $I^{\prime}$ guarantees that
$b\in{\mathrm{dom}}(\Phi_{I^{\prime}})$ because $(b,\bar{x})\in
T_{I^{\prime},(I^{\prime})^{c}}$. The choice of $I^{\prime}$ also guarantees
that $I\subseteq I^{\prime}$ and $J\subseteq(I^{\prime})^{c}$ because if $j\in
J$ then $j\not\in I$ and $\bar{x}_{j}\leq 0$ so $j\not\in I^{\prime}$.
Therefore $T_{I^{\prime},(I^{\prime})^{c}}\subseteq T_{I,J}$ and

$\|\Phi_{I^{\prime}}\|\geq\min_{x\in\Phi_{I^{\prime}}(b)}\|x\|\geq\min_{x\in\Phi_{I,J}(b)}\|x\|\geq\|\Phi_{I,J}\|.$

Since this holds for all $I,J\subseteq[n]$ with $I\cap J=\emptyset$, it
follows that $\\{T_{I,I^{c}}:I\subseteq[n]\\}$ satisfies the bounding
property.

We can proceed in a similar fashion for $\Psi$. Observe that
${\mathrm{graph}}(\Psi)=\\{(A^{\text{\sf
T}}y+s,y):y\in\mathbb{R}^{m},s\in\mathbb{B}\\}$ and thus it follows that every
$K\in\mathcal{T}(\Psi)$ is of the form $K=K_{I,J}=\\{(A^{\text{\sf
T}}y+s,y):s_{I}\geq 0,s_{J}\leq 0\\}$ for some $I,J\subseteq[n]$ with $I\cap
J=\emptyset$. For simplicity, we shall write $\Psi_{I}$ as shorthand for
$\Psi_{K_{I,I^{c}}}$.

Again the collection $\\{K_{I,I^{c}}:I\subseteq[n]\\}$ satisfies the bounding
property and thus Corollary 1 implies that

$\mathcal{H}(\Psi)=\max_{I\subseteq[n]}\|\Psi_{I}\|^{*}=\max_{I\subseteq[n]}\;\mathcal{H}(\Psi_{I}).$
(36)

Next, observe that for each $I\subseteq[n]$ the mappings $\Phi_{I}$ and $\Psi$
can be defined via

$\displaystyle b$
$\displaystyle\mapsto\Phi_{I}(b)=\\{x\in\mathbb{R}^{n}:Ax=b,x_{I}\geq
0,x_{I^{c}}\leq 0\\}$ $\displaystyle c$
$\displaystyle\mapsto\Psi_{I}(c)=\\{y\in\mathbb{R}^{m}:A^{\text{\sf
T}}y+s=c,s_{I}\geq 0,s_{I^{c}}\leq 0\\}.$

Thus Proposition 1(a) implies that $\Phi_{I}^{*}=\Psi_{I}$ for all
$I\subseteq[n]$. Theorem 2 in turn implies that

$\|\Phi_{I}\|\leq\mathcal{H}(\Psi_{I})\text{ and
}\|\Psi_{I}\|^{*}\leq\mathcal{H}(\Phi_{I})$

for all $I\subseteq[n]$. The latter inequalities together with (35) and (36)
imply that $\mathcal{H}(\Phi)=\mathcal{H}(\Psi)$.

∎

We next consider the box-constrained systems of linear inequalities (12)
defined via $L=\ker(A)$ and $L^{\perp}=\operatorname{Im}(A^{\text{\sf T}})$.
Let
$\overline{P}_{L,\mathbb{B}}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$
and
$\overline{Q}_{L^{\perp},\mathbb{B}}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$
be the analogous solution mappings for the box-constrained systems of linear
inequalities (12), namely

$\overline{P}_{L,\mathbb{B}}(b):=\\{x\in\mathbb{B}:x\in
L+b\\},\qquad\overline{Q}_{L^{\perp},\mathbb{B}}(c):=\\{y\in
L^{\perp}:y\in\mathbb{B}+c\\}.$ (37)

We have the following analogue of Theorem 5.

######  Theorem 6.

Suppose $A\in\mathbb{R}^{m\times n}$, $L:=\ker(A)$, and
$\mathbb{B}:=\\{x\in\mathbb{R}^{n}:\ell\leq x\leq u\\}$ for some
$\ell,u\in\mathbb{R}^{n}$ with $\ell<u.$ Let
$\overline{P}_{L,\mathbb{B}},\;\overline{Q}_{L^{\perp},\mathbb{B}}$ be the
solution mappings for the box-constrained systems of linear inequalities (12)
defined via (37). Then
$\mathcal{H}(\overline{P}_{L,\mathbb{B}})=\mathcal{H}(\overline{Q}_{L^{\perp},\mathbb{B}}).$

###### Proof.

This proof is a straightforward modification of the proof of Theorem 5. To
highlight the similarities between the two proofs, throughout this proof let
$\Phi:=\overline{P}_{L,\mathbb{B}}$ and
$\Psi:=\overline{Q}_{L^{\perp},\mathbb{B}}$. Before proving the identity
$\mathcal{H}(\Phi)=\mathcal{H}(\Psi)$, we establish the convenient expressions
(38) and (39) below for $\mathcal{H}(\Phi)$ and $\mathcal{H}(\Psi)$.

Observe that ${\mathrm{graph}}(\Phi)=\\{(w+x,x):x\in\mathbb{B},w\in L\\}$.
Thus it follows that every $T\in\mathcal{T}(\Phi)$ is of the form
$T=T_{I,J}=\\{(w+x,x):x_{I}\geq 0,x_{J}\leq 0,w\in L\\}$ for some
$I,J\subseteq[n]$ with $I\cap J=\emptyset$. For simplicity, we shall write
$\Phi_{I}$ as shorthand for $\Phi_{T_{I,I^{c}}}$.

Proceeding as in the proof of Theorem 5, it follows that

$\mathcal{H}(\Phi)=\max_{I\subseteq[n]}\|\Phi_{I}\|=\max_{I\subseteq[n]}\;\mathcal{H}(\Phi_{I}).$
(38)

Similarly, observe that ${\mathrm{graph}}(\Psi)=\\{(y+s,y):y\in
L^{\perp},s\in\mathbb{B}\\}$ and thus it follows that every
$K\in\mathcal{T}(\Psi)$ is of the form $K=K_{I,J}=\\{(y+s,y):y\in
L^{\perp},s_{I}\geq 0,s_{J}\leq 0\\}$ for some $I,J\subseteq[n]$ with $I\cap
J=\emptyset$. For simplicity, we shall write $\Psi_{I}$ as shorthand for
$\Psi_{K_{I,I^{c}}}$.

Proceeding as in the proof of Theorem 5, it follows that

$\mathcal{H}(\Psi)=\max_{I\subseteq[n]}\|\Psi_{I}\|^{*}=\max_{I\subseteq[n]}\;\mathcal{H}(\Psi_{I}).$
(39)

The proof can be completed by proceeding exactly as in the proof of Theorem 5.
∎

Corollary 2 below shows the following interesting connection between box-
constrained and canonical systems of linear inequalities: the Hoffman
constants of the box-constrained systems of inequalities (7) and (12) are
precisely signed versions of the Hoffman constants of the canonical systems of
inequalities (1) and (11) provided the norm in $\mathbb{R}^{n}$ is sign
invariant as explained below.

The statement of Corollary 2 relies on the following set of signature matrices
$\SS\subseteq\mathbb{R}^{n\times n}$:

$\SS:=\\{\operatorname{Diag}(d):d\in\\{-1,1\\}^{n}\\}.$

We say that the norm $\|\cdot\|$ in $\mathbb{R}^{n}$ is sign invariant if for
all $x\in\mathbb{R}^{n}$ and $D\in\SS$

$\|Dx\|=\|x\|.$

Equivalently, $\|\cdot\|$ is sign invariant if
$|x|=|y|\Rightarrow\|x\|=\|y\|$.

It is easy to see that many popular norms, including all $\|\cdot\|_{p}$ norms
for $p\in[1,\infty]$ are sign invariant.

######  Corollary 2.

Suppose $A\in\mathbb{R}^{m\times n}$, $L:=\ker(A)$, and
$\mathbb{B}:=\\{x\in\mathbb{R}^{n}:\ell\leq x\leq u\\}$ for some
$\ell,u\in\mathbb{R}^{n}$ with $\ell<u$. In addition, suppose the norm
$\|\cdot\|$ in $\mathbb{R}^{n}$ is sign invariant. Then

$\mathcal{H}(P_{A,\mathbb{B}})=\max_{S\in\SS}\mathcal{H}(P_{AS})=\max_{S\in\SS}\mathcal{H}(Q_{AS})=\mathcal{H}(Q_{A,\mathbb{B}}),$
(40)

and

$\mathcal{H}(\overline{P}_{L,\mathbb{B}})=\max_{S\in\SS}\mathcal{H}(\overline{P}_{SL})=\max_{S\in\SS}\mathcal{H}(\overline{Q}_{SL^{\perp}})=\mathcal{H}(\overline{Q}_{L^{\perp},\mathbb{B}}).$
(41)

In particular, the constants
$\mathcal{H}(P_{A,\mathbb{B}})=\mathcal{H}(Q_{A,\mathbb{B}})$ and
$\mathcal{H}(\overline{P}_{L,\mathbb{B}})=\mathcal{H}(\overline{Q}_{L^{\perp},\mathbb{B}})$
are independent of the specific values of $\ell,u\in\mathbb{R}^{n}$ as long as
$\ell<u$.

###### Proof.

There is a natural one-to-one correspondence between the subsets of $[n]$ and
the set of signature matrices $\SS$, namely

$I\subseteq[n]\leftrightarrow
S_{I}=\\{\operatorname{Diag}(d_{I}):d_{i}=1\text{ for }i\in I\text{ and
}d_{i}=-1\text{ for }i\not\in I\\}.$

This correspondence and the sign invariance of the norm $\|\cdot\|$ in
$\mathbb{R}^{n}$ allows us to restate the identities (35), (36) in the proof
of Theorem 5 as follows

$\mathcal{H}(P_{A,\mathbb{B}})=\max_{S\in\SS}\mathcal{H}(P_{AS})$

and

$\mathcal{H}(Q_{A,\mathbb{B}})=\max_{S\in\SS}\mathcal{H}(Q_{AS}).$

Theorem 5 thus yields (40). The proof of (41) follows in the same fashion from
(38), (39) and Theorem 6.

∎

## References

  * [1] D. Applegate, O. Hinder, H. Lu, and M. Lubin.  Faster first-order primal-dual methods for linear programming using restarts and sharpness.  Mathematical Programming, pages 1–52, 2022.
  * [2] D. Azé and J. Corvellec.  On the sensitivity analysis of Hoffman constants for systems of linear inequalities.  SIAM Journal on Optimization, 12(4):913–927, 2002.
  * [3] A. Beck and S. Shtern.  Linearly convergent away-step conditional gradient for non-strongly convex functions.  Mathematical Programming, 164(1):1–27, 2017.
  * [4] J. Borwein.  Norm duality for convex processes and applications.  Journal of Optimization Theory and Applications, 48(1):53–64, 1986\.
  * [5] J. Burke and P. Tseng.  A unified analysis of Hoffman’s bound via Fenchel duality.  SIAM Journal on Optimization, 6(2):265–282, 1996.
  * [6] J. Camacho, M. Cánovas, M. López, and J. Parra.  Robust and continuous metric subregularity for linear inequality systems.  Computational Optimization and Applications, 86(3):967–988, 2023\.
  * [7] J. Camacho, M.J. Cánovas, H. Gfrerer, and J. Parra.  Hoffman constant of the argmin mapping in linear optimization.  arXiv preprint arXiv:2307.01034, 2023.
  * [8] J. Camacho, M.J. Cánovas, and J. Parra.  From calmness to Hoffman constants for linear semi-infinite inequality systems.  SIAM Journal on Optimization, 32(4):2859–2878, 2022.
  * [9] D. Dadush, B. Natura, and L. Végh.  Revisiting tardos’s framework for linear programming: faster exact solutions using approximate solvers.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 931–942. IEEE, 2020.
  * [10] Y. Gao and C. Kroer.  First-order methods for large-scale market equilibrium computation.  Advances in Neural Information Processing Systems, 33:21738–21750, 2020.
  * [11] O. Güler, A. Hoffman, and U. Rothblum.  Approximations to solutions to systems of linear inequalities.  SIAM Journal on Matrix Analysis and Applications, 16(2):688–696, 1995.
  * [12] D. Gutman and J. Pena.  The condition number of a function relative to a set.  Mathematical Programming, 188:255–294, 2021.
  * [13] O. Hinder.  Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs.  arXiv preprint arXiv:2309.03988, 2023.
  * [14] A. Hoffman.  On approximate solutions of systems of linear inequalities.  Journal of Research of the National Bureau of Standards, 49(4):263–265, 1952.
  * [15] S. Lacoste-Julien and M. Jaggi.  On the global linear convergence of Frank-Wolfe optimization variants.  In Advances in Neural Information Processing Systems (NIPS), 2015\.
  * [16] D. Leventhal and A. Lewis.  Randomized methods for linear constraints: Convergence rates and conditioning.  Math. Oper. Res., 35:641–654, 2010.
  * [17] W. Li.  The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program.  Linear algebra and its applications, 187:15–40, 1993.
  * [18] S. Lu and J. Yang.  On the geometry and refined rate of primal-dual hybrid gradient for linear programming.  arXiv preprint arXiv:2307.03664, 2023.
  * [19] Z. Luo and P. Tseng.  Error bounds and convergence analysis of feasible descent methods: a general approach.  Annals of Operations Research, 46(1):157–178, 1993.
  * [20] O. Mangasarian and T-H Shiau.  Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems.  SIAM Journal on Control and Optimization, 25(3):583–595, 1987.
  * [21] J. Peña.  An easily computable upper bound on the Hoffman constant for homogeneous inequality systems.  Computational Optimization and Applications, pages 1–13, 2023.
  * [22] J. Peña and D. Rodriguez.  Polytope conditioning and linear convergence of the Frank-Wolfe algorithm.  Math. Oper. Res., 44(1):1–18, 2019.
  * [23] J. Peña, J. Vera, and L. Zuluaga.  New characterizations of Hoffman constants for systems of linear constraints.  Math. Program., 187(1):79–109, 2021.
  * [24] S. Robinson.  Bounds for error in the solution set of a perturbed linear program.  Linear Algebra and its applications, 6:69–81, 1973.
  * [25] M. Sion.  On general minimax theorems.  Pacific Journal of Mathematics, 8(1):171–176, 1958.
  * [26] P. Wang and C. Lin.  Iteration complexity of feasible descent methods for convex optimization.  Journal of Machine Learning Research, 15(1):1523–1548, 2014.
  * [27] J. Ye, X. Yuan, S. Zeng, and J. Zhang.  Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems.  Set-Valued and Variational Analysis, pages 1–35, 2021.
  * [28] C. Zalinescu.  Sharp estimates for Hoffman’s constant for systems of linear inequalities and equalities.  SIAM Journal on Optimization, 14(2):517–533, 2003.
  * [29] R. Zhao.  An away-step Frank-Wolfe method for minimizing logarithmically-homogeneous barriers.  arXiv preprint arXiv:2305.17808, 2023.
  * [30] X. Zheng and K. Ng.  Hoffman’s least error bounds for systems of linear inequalities.  Journal of Global Optimization, 30(4):391–403, 2004.


# On thermodynamic stability and ensemble equivalence at coexistence

Jozismar Rodrigues Alves<EMAIL_ADDRESS>Vera Bohomoletz
Henriques<EMAIL_ADDRESS>Instituto de Física - Universidade de São Paulo.

###### Abstract

Numerical simulations of systems at coexistence are known to yield unstable
fields in some regions of the density parameters, as well as inequivalence of
ensembles. The ‘Van der Waals-like’ loops are attributed to effects of the
interface between the coexisting phases, but the question of convexity remains
unresolved. We recover the theory developed by Hill in the 1960’s, and adapt
it to include the interface free energy. Our adapted theory is verified
through carefully planned simulations, and give a thermodynamic description of
the interface behaviour inside the coexistence region which restores the
proper convexity of the thermodynamic potentials, as well as yields
convergence of grandcanonical and canonical results. As a bonus, our
interpretation allows direct calculation of surface tension in very good
accordance with Onsager’s analytic prediction.

††preprint: APS/123-QED

The XIXth century experimental study of the coexisting gas-liquid phases [1]
showed that the system pressure-volume isotherms present a horizontal plateau
which signals the presence of phase separation. The first successful theory of
Andrews [1] results was proposed by Van der Waals [2]: it had the advantage of
presenting two densities for the same pressure, as in coexistence. However,
instead of the plateau, it presented loops. Loops are present in all
”classical” mean-field theories [3, 4] for phase transitions, instability
arising from a mathematical treatment which does not include description of
phase separation, since the system is treated as homogeneous all the way
through the coexistence region.

In the absence of exact treatment for most systems, numerical simulations
constitute the only resource for exploring thermodynamic properties of many
statistical or molecular models which take into account correlations. However,
it has been known for a few decades [5, 6, 7], that the numerical simulations
of molecular or statistical models in fixed density ensembles present ”Van der
Waals-like” loops on the sides of the plateaus (see Figure 1). The second law
of Thermodynamics imposes strict conditions on the thermodynamic state
variables. Fields must present a definite convexity in relation to their
conjugate densities, thus loops would imply violation of thermodynamic
stability. Several studies have attributed loops to interface effects in
finite systems, which should disappear in the thermodynamic limit [7, 7]. The
de-escalating of loops with size has been indicated very clearly in several
numerical studies [6]. As to fixed field ensembles, instead of loops one sees
a region of ”hystheresis”, wich has been interpreted in terms of
metastability. Thus, numerical simulations of phase-separating systems in the
coexistence region seem to yield both thermodynamic instability as well as the
nonequivalence of ensembles. Both features have been reputed to be a
consequence of the finiteness of the simulated systems.

In this paper, we recover a theory proposed by Hill [7] for the
thermostatistics of different ensembles of systems at coexistence, presented
by the author at the dawn of numerical studies of statistical models. We add a
new interpretation to Hill’s approach, by introducing the thermodynamics of
the interface between coexisting phases. Our proposal points to the recovery
of proper thermodynamic stability, as well as to the equivalence of ensembles,
as we illustrate for the case of the square lattice fluid model.

Figure 1: Lattice gas chemical potential vs. density isotherm below
criticality obtained from MC simulations in the $(T,V,N)$ canonical ensemble.
Insets correspond to system snapshots for densities in the +-loop, plateau and
in the -loop, respectively. The dashed line is an extension of the plateau
region and its intersections with the isotherm correspond to the phase
coexistence densities (see text). Data are for $L=40$ and temparature $t=0.5$.

What is the precise origin of loops in numerical simulations? In the 1960’s,
Hill [7] presented a theory aimed at answering this question, which we
describe briefly. Let $Y$ represent a thermodynamic field and $X$ the
respective conjugate density. At a particular density $X$, a system at
coexistence presents two different densities, say $X_{1}$ and $X_{2}$, which
represent the densities of the two coexisting phases. If one runs simulations
for fixed conjugate field $Y$, density $X$ fluctuate around the two values
$X_{1}$ and $X_{2}$. Thus, if one plots the distribution probability density
$P(X|Y$), one obtains a two-peak function, with peaks centered on $X_{1}$ and
$X_{2}$, separated by a minimum at $X_{min}$.

For clearness of argument, let us consider a simple fluid at the gas-liquid
coexistence. The grand-canonical probability of finding $N$ particles in the
system at $(T,V,\mu)$ is given by

$P(N;T,V,\mu)=\frac{e^{\beta\mu N}Z(T,V,N)}{\Xi(T,V,\mu)}$ (1)

where $Z(T,V,N)$ and $\Xi(T,V,\mu)$ are, respectively, the canonical and the
grand canonical partition functions of the system.

According to Hill’s proposal, the maximum of the distribution
$\left[\frac{dP(N;T,V,\mu)}{dN}\right]_{N_{gas},N_{min},N_{liq}}=0$ should
yield the chemical potential in the canonical ensemble:

$\beta\mu+\frac{1}{Z(T,V,N)}\frac{\partial Z(T,V,N)}{\partial N}=0$ (2)

in accordance with the corresponding equation of state in the Helmholtz free-
energy representation

$\left(\frac{\partial F}{\partial N}\right)_{T,V}=\mu(T,V,N)$ (3)

.

Liquid-gas coexistence would be signaled by a two-peaked distribution of
particle number $N$ for the system in the chemical potential bath, thus
yielding three values for particle density, corresponding to $N_{gas}$,
$N_{min}$, $N_{liq}$, at the same chemical potential $\mu$. At coexistence,
probability distribution $p(N)$ should present two maxima of the same height,
while the minimum would run over a continuous set of values of the abcissa
$N$.

We argue that the theory proposed by Hill [7] is in fact correct for the
homogeneous phases, but must be modified in its application to the coexistence
region, because of the additional dependence of free-energy on the
thermodynamics of the interface between the two phases. For a simple fluid,
the free-energy for the system at coexistence, $F_{cx}$, must be written as

$F_{cx}(T,V,N)=F_{bulk}(T,V,N)+F_{int}(T,V,N)$ (4)

with the free-energy of the interface given by
$F_{int}=\gamma(T)A_{int}(T,V,N)$, where $\gamma$ describes surface tension,
while $A_{int}$ is the area of the interface [8, 9]. As for the equation of
state related to variation of the number of particles, we have:

$\left(\frac{\partial F_{cx}}{\partial
N}\right)_{T,V}=\mu_{coex}(T,V,N)+\gamma\left(\frac{\partial A_{int}}{\partial
N}\right)_{T,V},$ (5)

where chemical potential is obtained from the bulk free-energy as

$\mu(T,V,N)=\left(\frac{\partial F_{bulk}}{\partial
N}\right)_{T,V}=\left(\frac{\partial F_{cx}}{\partial
N}\right)_{T,V,A_{int}(T,V,N)}.$ (6)

Thus it is clear that computing the partial derivative of the free energy with
respect to particle number, at fixed temperature and volume, does not yield
the chemical potential (Eq.3, but, instead, the sum of the chemical potential
with a term proportional to the variation of the interface area with particle
number (Eq.6).

This special form of the free-energy at coexistence must be associated to a
modified grand-partition function which takes into account the interface area
$A_{int}$. Thus, the probability distribution for the number of particles in
the grand-canonical ensemble (Eq. 1) in the coexistence region must be
rewritten as

$P(N;T,V,\mu)=\frac{e^{\beta(\mu N+\gamma(T)A_{int})}Z(T,V,N)}{\Xi(T,V,\mu)}$
(7)

Extrema with respect to particle number $N$ of the the distribution function
at coexistence $P(N;T,V,\mu)$ are given by:

$\beta\mu+\gamma\left(\frac{\partial A_{int}}{\partial
N}\right)_{T,V}+\frac{1}{Z(T,V,N)}\frac{\partial Z(T,V,N)}{\partial N}=0$ (8)

. The corresponding equation of state is then given by Eq. 6, instead of Eq.
3.

What are the implications of our proposal on the interpretation of simulation
results?

In canonical ensemble simulations, the numerical chemical potential is
obtained through Widom’s insertion method [9]. From discretization of Eq.3 for
homogeneous systems, a numerical chemical potential $\mu_{num}$ may be shown
to be a function of an average of the Boltzman factor of the energy added to
the system upon insertion of a ’virtual’ particle:

$\mu_{num}(T,V,N)\equiv-
k_{B}T\ln\frac{Z(T,V,N+1)}{Z(T,V,N)}=k_{B}T\ln\left[\frac{\rho}{\langle\exp\left(\frac{e_{additionalparticle}}{k_{B}T}\right)\rangle_{T,V,N}}\right].$
(9)

As we discussed above, Eq. 3, and thus also Eq. 9, in the case of simulations,
yield the chemical potential only for the case of homogeneous phases. In the
coexistence region, numerical simulations in the canonical ensemble yield non-
homogeneous phases, and the true chemical potential $\mu$ is no longer given
by the discretized partial derivative of the canonical free-energy. Rather,
the latter is really a combination of chemical potential and a term
proportional to the gradient of the area of the interface. Thus, at
coexistence, Widom’s insertion (9) yields a pseudo-chemical potential, which
we design $\tilde{\mu}$, related to the true chemical potential $\mu$ through

$\tilde{\mu}(T,V,N)=\mu(T,V,N)+\gamma\left(\frac{\partial{\tilde{A}_{int}}}{\partial
N}\right)_{T,V}.$ (10)

Note that at coexistence, $\tilde{\mu}$ must rise above the true chemical
potential $\mu$, as the area of the interface increases with particle number
$N$, whereas the opposite is true if adding particles brings down the
interface area. Also, if interface area is maintained constant, as particles
are added to the system, the pseudo chemical potential equals the true
chemical potential,$\tilde{\mu}$ = $\mu$.

In order to check our modified Hill’s theory, we have carried out very careful
simulations for the lattice fluid on the square lattice, under periodic
boundary conditions. For the chosen model, analytical results by Onsager are
available [10], which serve as good test on the theory. Our procedure is as
follows: (i) in the grand-canonical ensemble $(T,V,\mu)$, we calculate the
full particle density probability distributions $P(N)$, whose extrema yield
precise pseudo chemical-potential vs density $rho$ relations; (ii) we obtain
the pseudo chemical potential isotherms directly from usual canonical ensemble
$(T,V,N)$ simulations, through eq 9; (iii) Results from the two different
ensembles are compared.

In the grand-canonical ensemble $(T,V,\mu)$ description, the probability
distribution function $P(N;T,V,\mu$), at different chemical potentials, is
obtained via a combination of multicanonical and Wang-Landau techniques, as
proposed in references [11, 12, 13]. The use of these techniques is central to
our results, because they allow us to probe events of very low probability, in
between the gas and liquid densities, thus yielding the full $\mu$ vs $\rho$
isotherms. The N probability distributions are represented in Fig 2, for
different values of the pseudo chemical potential $\tilde{\mu}$ (see equation
7). It can be seen that there are two equal peaks for the coexistence chemical
potential $\mu/\epsilon=-2$ (corresponding to zero magnetic field for the
Ising model). As the chemical potentials rises above the coexistence value,
the small density peak diminishes while the large density peak increases. The
opposite is true if the chemical potential is lowered below its coexistence
value.

Figure 2: Probability distribution function $P(N;T,V,\mu)$ for different
values of the chemical potential $\mu$, obtained from $(T,V,\mu)$ grand-
canonical ensemble. The left curve displays $P(N)$ for decreasing values of
the chemical potential from coexistence and below, while the right curve
displays $P(N)$ for increasing chemical potential values above coexistence.
Circles indicate extrema of the distributions. Data are for $L=40$ and
temperature $t=0.5$.

In the canonical $(T,V,N)$ ensemble, the usual Metropolis algorithm [6] was
used to obtain $\tilde{\mu}$ from the equation of state represented by Eq. 10.

Our numerical results for both ensembles are illustrated in the bottom Fig. 3.
Upper plots show grand-canonical probability distributions $P(N)$ and lower
plots display canonical pseudo-chemical potential $\tilde{\mu}$. The results
in the different ensembles may be compared in the folowing terms: (i) on the
left pannel, extrema of the grand-canonical distribution function $P(N)$ for a
given particular $\tilde{\mu}$ are in correspondence with the density values
at the same $\tilde{\mu}$ of the canonical isotherms in the loop region; (ii)
a small plateau for the canonical $\tilde{\mu}$, seen at intermediate
densities, is in correspondence with the set of minima of the $P(N)$
probability distribution, while a ’plus’ loop is seen near low densities and a
’minus’ loop is seen near large densities. Let us analyse these results in the
light of state equation 5 (or Eq. 10). In the plateau region of intermediate
densities, pseudo and true chemical potential converge, and interface area
should be stationary under increase in particle number. This means we can
identify the coexistence potential with the plateau value, and extract the
coexisting densities from the intersection points of the extension of the
plateau with the $\tilde{\mu}$ curve (see Fig.1). Note that the plateau occurs
at the value predicted by the exact Onsager theory,
$\frac{\mu_{cx}}{\epsilon}=-2$. How can we interpret the effects of variation
in interface area? As one goes over the lower density limit for coexistence,
an interface area appears and increases as particles are added, and
$\tilde{\mu}>\mu$. In a planar system, a circular dense phase is formed, but
as particle number increases, it deforms towards a rectangular strip accross
the lattice, because of periodic boundary conditions. The interface area of
the rectangular strip is independent of its width, and thus remains constant
as new particles are inserted into the system. This is true up to the point,
at higher densities, at which the strip initiates deformation, as the low
density phase contracts to a circle whose perimeter decreases as particle
number decreases. In this region, interface area decreases, and pseudo
potential falls below true chemical potential.

If the modified theory of Hill is fulfilled (even for finite systems), we
expect the $(\rho,\tilde{\mu})$ values at the loops (Fig. 3) to be given by
the extrema of the distribution functions $P(N)$ of the grandcanonical
ensemble (Fig. 2). In Fig 4, we compare function $\tilde{\mu}(\rho)$ obtained
from the canonical ensemble simulations (Fig 3) with $\rho(\tilde{\mu})$
obtained from the extrema of the distribution functions in the grand-canonical
ensemble (Fig 3). It can be seen that results coincide entirely in the whole
coexistence region. The coincidence of both curves constitutes a good check on
our modified version of Hill’s theory.

Figure 3: Comparison between results obtained from $(T,V,N)$ and $(T,V,\mu)$
simulations. Figures (a) and (b) display distribution probability functions
$P(N;T,V,\mu)$ for $\mu=-2.0$ and for $\mu=-1.98$, respectively. In Figures
(c) and (d), the same chemical potential isotherm (for $t=0.5$) obtained from
$(T,V,N)$ simulations is displayed, in order to facilitate comparison with the
$(T,V,\mu)$ results. The dashed vertical lines connect the extreme points of
$P(N$) at fixed $\mu$ with the corresponding densities on the chemical
potential $(T,V,N$) isotherm. Note the correspondence between chemical
potentials in each of the two sets of data. Data points are for $L=40$ and
temperature $t=0.5$. Figure 4: Comparison between thermodynamics obtained from
different ensembles. Results for the pseudo-chemical potential $\tilde{\mu}$
isotherm are displayed as a line for the $(T,V,N)$ data, and as circles for
the $(T,V,\mu)$ data. $L=40$ and $t=0.5$.

An important and definite check on our proposal is possible. In the case of
the 2d lattice gas, an analytic expression for the interface tension was
presented in Onsager’s paper [10], which, for the lattice interacting gas, is
given by

$\frac{\gamma}{\epsilon}=\frac{1}{2}-t\ln\left[\frac{1+e^{-\frac{1}{2t}}}{1-e^{-\frac{1}{2t}}}\right],$
(11)

with $t\equiv k_{B}T/\epsilon$.

Usually [14, 15, 16] surface tension is calculated from the grandcanonical
probability distribution function $P(N)$. In our proposal, numerical results
for the function $\tilde{\mu}$ allow direct calculation of surface tension
$\gamma$ from the integration of Eq 10. The interface has zero area at the gas
density $\rho_{gas}$, increases as density is increased, accompanying the
formation of a spherical liquid bubble which increases, deforms and becomes
flat. As density is further increased, $\tilde{\mu}$ remains constant, since
$\left(\frac{\partial A_{int}}{\partial N}\right)_{T,V}=0$ as long as the
interface remains flat, with $A_{int}=2L^{d-1}$, in spite of the growth of the
volume of the liquid phase. The integral over particle number of Eq 4 may be
written as

$I\equiv\int_{\rho_{gas}}^{0.5}(\tilde{\mu}-\mu_{cx})d\left(\frac{N}{V}\right)=\gamma\int_{0}^{A_{plateau-
int}}\frac{dA_{int}}{V}.$ (12)

From numerical integration, interface tension can be obtained from
$\gamma=\frac{I\times L}{2}$, for the case of the 2d lattice gas.

Figure 5 displays true and pseudo chemical potentials.The effect of interface
area on the isotherms is substracted and true $\mu$ vs density isotherms are
obtained. The figure also illustrates our procedure for the obtention of
surface tension. Fig 6 shows our numerical results for $\gamma(t)$ as compared
to the analytical prediction by Onsager [10].

Figure 5: True vs pseudo chemical potential isotherms. Extension of the
plateau in $\tilde{\mu(\rho)}$ identifies limits of coexistence and gas and
liquid densities $\rho$. The thick line represents the true chemical potential
isotherm $\tilde{\mu(\rho)}$. Integration of $\tilde{\mu}$ positive loop
allows for calculation of surface tension $\gamma(t)$. See text. Data are for
$L=40$ and temperature $t=0.5$.  Figure 6: Lattice gas surface tension
$\gamma(t)$. In the left figure our $L=40$ data for $\gamma(t)$ are displayed
as circles, and can be compared to Onsager’s exact result (dashed line). The
right figure displays behaviour with size $L$ for temperatures $t=0.45$ and
$t=0.5$. The exact results, corresponding to $L\rightarrow\infty$ are
indicated with the diamond symbol. For $t=0.46$, fitting yields
$\gamma(t,L\rightarrow\infty)=0.1135$, compared to exact
$\gamma(t=0.46)=0.1140$. For $t=0.5$, fitting yields
$\gamma(t,L\rightarrow\infty)=0.1770$, compared to exact
$\gamma(t=0.5)=0.1771$.

In summary, we have found an interpretation for loops of thermodynamic fields
encountered in numerical simulations in the corresponding density ensembles.
We have given proof that the numerical results are not in fact results for the
fields, but results for the sum of the thermodynamic field and the gradient of
the interface area that arises in the coexistence region. The true
thermodynamic fields maintain their proper convexity, and the numerical
results in the phase coexistence region in the two ensembles are identical. As
a side product of our analysis, we propose a much simpler method for the
calculation of surface tension, turning unnecessary the non-trivial
calculation of the full grand-canonical distribution probability function.

## References

  * Andrews [1869] T. Andrews, The bakerian lecture: On the continuity of the gaseous and liquid states of matter, Philosophical Transactions of the Royal Society of London 159, 575 (1869).
  * Van der Waals [1873] J. Van der Waals,  _Over de Continuiteit van den Gas-en Vloeistoftoestand (On the Continuity of the Gas and Liquid State)_ , Ph.D. thesis, University of Leiden, Leiden (1873).
  * Callen [1985] H. B. Callen,  _Thermodynamics and an introduction to thermostatistics; 2nd ed._ (Wiley, New York, NY, 1985).
  * Huang [1987] K. Huang,  _Statistical Mechanics; 2nd ed._ (Wiley, New York, NY, 1987).
  * Furukawa and Binder [1982] H. Furukawa and K. Binder, Two-phase equilibria and nucleation barriers near a critical point, Physical Review A 26, 556 (1982).
  * Block  _et al._ [2010] B. J. Block, S. K. Das, M. Oettel, P. Virnau, and K. Binder, Curvature dependence of surface free energy of liquid drops and bubbles: A simulation study, The Journal of Chemical Physics 133, 154702 (2010).
  * Hill [1987] T. L. Hill,  _Statistical mechanics: principles and selected applications_ (Dover, 1987).
  * Rowlinson and Widom [1982] J. S. Rowlinson and B. Widom,  _Molecular Theory of Capillarity_ (Oxford, 1982).
  * Widom [1963] B. Widom, Some topics in the theory of fluids, The Journal of Chemical Physics 39, 2808 (1963).
  * Onsager [1944] L. Onsager, Crystal statistics. i. a two-dimensional model with an order-disorder transition, Phys. Rev. 65, 117 (1944).
  * Berg and Neuhaus [1991] B. A. Berg and T. Neuhaus, Multicanonical algorithms for first order phase transitions, Physics Letters B 267, 249 (1991).
  * Berg and Neuhaus [1992] B. A. Berg and T. Neuhaus, Multicanonical ensemble: A new approach to simulate first-order phase transitions, Phys. Rev. Lett. 68, 9 (1992).
  * Wang and Landau [2001] F. Wang and D. P. Landau, Efficient, multiple-range random walk algorithm to calculate the density of states, Phys. Rev. Lett. 86, 2050 (2001).
  * Tröster  _et al._ [2012] A. Tröster, M. Oettel, B. Block, P. Virnau, and K. Binder, Numerical approaches to determine the interface tension of curved interfaces from free energy calculations, The Journal of Chemical Physics 136, 064709 (2012).
  * Binder [1982] K. Binder, Monte carlo calculation of the surface tension for two- and three-dimensional lattice-gas models, Phys. Rev. A 25, 1699 (1982).
  * Schrader  _et al._ [2009] M. Schrader, P. Virnau, and K. Binder, Simulation of vapor-liquid coexistence in finite volumes: A method to compute the surface free energy of droplets, Phys. Rev. E 79, 061104 (2009).