Duality Theory on Vector Spaces
Dang Van Cuong 111Department of Mathematics, Faculty of Natural Sciences, Duy
Tan University, Da Nang, Vietnam (dvcuong@duytan.edu.vn). , Tuyen
Tran222Department of Mathematics and Statistics, Loyola University Chicago,
Chicago, IL 60660, USA (ttran18@luc.edu).,

Abstract. In this paper, we provide further studies of the Fenchel-Rockafellar
duality and the Lagrange duality in the general frame work of vector spaces
without topological structures. Under the conditions of set extremality for
systems of convex sets in vector spaces on domains of the functions involved,
we establish conjugate calculus rules. Then we develop sufficient conditions
which guarantee the validity of the Fenchel-Rockafellar strong duality. Using
a Slater condition based on core-solidity, we then obtain a sufficient
condition for the Lagrange strong duality. Our new developments continue to
push how far we can go with set-valued and convex analysis without any
topological structure on the underlying space.
Key words. Algebraic interior, algebraic core, Fenchel duality, Lagrangian
duality, calculus rules,
AMS subject classifications. 49J52, 49J53, 90C31

##  1 Introduction

Duality theory has a central role in optimization theory and its applications.
From a _primal optimization problem_ with objective functions defined in a
primal space, a _dual problem_ defined in the dual space is formulated with
the hope that the new problem is easier to solve, while having close relations
with the primal problem. There are two main duality methods in optimization
which are the _Fenchel duality_ and the _Lagrangian duality_. Its important
role in optimization makes the duality theory attractive for extensive
research in optimization theory and applications; see, e.g., [1, 2, 3, 4, 5,
6, 7, 8, 10, 9, 11, 12, 15, 16, 19, 20, 21, 22, 23, 24, 29, 30, 32, 33, 36].

The first branch of duality theory in optimization studies _Fenchel duality_.
Given proper convex functions $\varphi\colon X\to\overline{\mathbb{R}}$,
$\psi\colon Y\to\overline{\mathbb{R}}$ and a linear continuous operator
$A\colon X\to Y$ between vector spaces $X$ and $Y$, consider the following
primal minimization problem:

minimize $\displaystyle\varphi(x)+\psi(Ax)\;\mbox{ subject to }\;x\in X.$
(1.1)

Note that the optimization problem (1.1) is written in the unconstrained
format, while it actually incorporates constraints via the domains of the
extended-real-valued functions $\varphi$ and $\psi$. Using the conjugate
functions of $\varphi,\psi$ and the adjoint operator of $A$, the Fenchel dual
problem of (1.1) is defined in the maximization form as follows:

maximize $\displaystyle-\varphi^{*}(A^{*}g)-\psi^{*}(-g)\;\mbox{ subject to
}\;g\in Y^{\prime}.$ (1.2)

As we know, the conjugate functions $\varphi^{*}\colon
X^{\prime}\to\overline{\mathbb{R}}$ and $\psi^{*}\colon
Y^{\prime}\to\overline{\mathbb{R}}$ are convex while entering (1.2) with the
negative sign, and thus the Fenchel dual problem also belongs to convex
minimization, where $X^{\prime}$ and $Y^{\prime}$ are algebraic dual spaces of
$X$ and $Y$ corresponding.

Define the optimal values in these problems by

$\widehat{p}:=\inf_{x\in X}\big{\\{}\varphi(x)+\psi(Ax)\big{\\}},$
$\widehat{d}:=\sup_{y^{*}\in
Y^{*}}\big{\\{}-\varphi^{*}(A^{*}y^{*})-\psi^{*}(-y^{*})\big{\\}}.$

The main question of the Fenchel duality problem is “When does the Fenchel
strong duality $\widehat{p}=\widehat{d}$ take place?” which is answered by the
Fenchel-Rockafellar theorem. Recently, under qualifications on generalized
interiors, some sufficient conditions have been given to get Fenchel strong
duality on locally convex topological vector spaces; see, e.g., [4, 5, 7, 10,
9, 11, 15, 16, 36]. One of the main goals of this paper is to provide a full
generalization of the Fenchel–Rockafellar theorem to the setting of a vector
space without topology using core qualifications, in line of our recent papers
[13, 14].

The second branch of duality theory in optimization studies _Lagrangian
duality_. Consider a primal optimization problem with the optimal value given
by

$p:=\inf\\{\varphi(x)\ |\ x\in\Omega,\ \psi(x)\in-C,\ Ax=b\\},$

where $\Omega\subset X$ is a nonempty convex set, $b\in Z,$ $X,Y$ and $Z$ are
vector spaces, $Y$ is ordered by a convex cone $C\subset Y$, $\varphi\colon
X\to\mathbb{R}$ is convex, $\psi\colon X\to Y$ is $C$-convex, and $A\colon
X\to Z$ is a continuous linear mapping. The primal problem is studied in
connection with the Lagrangian dual problem

$\qquad\qquad\qquad d:=\sup\\{L^{\prime}(g,h)\ |\ h\in C^{\prime},\;g\in
Z^{\prime}\\},$

where the objective function is defined by

$L^{\prime}(g,h):=\inf_{x\in\Omega}\\{\varphi(x)+\langle
h,\psi(x)\rangle+\langle g,Ax-b\rangle\\},$

with the constraint set

$C^{\prime}:=\\{h\in Y^{\prime}\ |\ 0\leq\langle h,c\rangle\ \text{for all}\
c\in C\\}.$

One of the main goals of Lagrangian duality theory is to obtain sufficient
conditions which guarantee the Lagrangian strong duality $p=d.$ Most of the
known results in this research direction require the Slater conditions. In
locally convex topological vector spaces, Slater conditions based on
generalized interiors were introduced by Borwein and Lewis in [8], and then
were generalized by Jeyakumar and Wolkowicz in [29]. Further significant
results were obtained in [10, 9, 17, 18] and the references therein. In this
paper, in line of our recent papers [13, 14] on vector spaces without
topological structure, we use a core-solid Slater condition to give a
sufficient condition of the Lagrangian strong duality.

Our paper is organized as follows. In Section 2 we present basic definitions
and notions of convex analysis used throughout the paper. Section 3 is devoted
to revisiting the coderivative and subdifferential calculus rules for set-
valued mappings and nonsmooth functions. We develop conjugate calculus rules
and the Fenchel duality for set-valued mappings and nonsmooth functions on
vector spaces in Sections 4. Finally, we provide a core-solid Slater condition
for the Lagrangian strong duality in Section 5.

##  2 Preliminaries

In this section we define the basic notions and present some preliminaries
needed for the formulation and proofs of the main results. The reader is
referred to the books [25, 26, 30, 37] and the papers [13, 14] for related
results and additional material on convex analysis on vector spaces. Our
notation is standard in convex and variational analysis; see, e.g., [30, 31,
34, 35]. All the spaces under consideration are real vector spaces. Given such
a space $X$, its algebraic dual space is denoted by

$X^{\prime}:=\big{\\{}f\colon X\to\mathbb{R}\;\big{|}\ f\;\text{ is a linear
function}\big{\\}}.$

We now recall some basic notions for partially ordered vector spaces. Let $Y$
be a linear space and $C$ be a nonempty convex cone in $Y$. We define a
relation on $Y$ by

$y_{1}\leq_{C}y_{2}\;\text{if and only if}\;y_{2}-y_{1}\in C,$

and this relation is compatible with the vector structure, i.e.

  1. (a)

if $0\leq_{C}x$ and $0\leq_{C}y$, then $0\leq_{C}x+y$,

  2. (b)

if $0\leq_{C}x$, then $0\leq_{C}\lambda x$ for all $\lambda\geq 0$.

This defines a partial ordering on $Y$, and in this case we say that $Y$ is
partially ordered by the nonempty convex cone $C$ and refer to $Y$ as an
ordered vector space. We also define the relation

$y_{1}<_{C}y_{2}\;\text{if and only if}\;y_{2}-y_{1}\in
C\;\text{and}\;y_{1}\neq y_{2}.$

We say that $Y$ is totally ordered by the nonempty convex cone $C$ if for any
$y_{1},y_{2}\in Y$ we have either $y_{1}\leq_{C}y_{2}$ or
$y_{2}\leq_{C}y_{1}.$

It is immediate that $0\leq_{C}y$ if and only if $y\in C$, so we refer to the
points in $C$ as the nonnegative elements and use the notation $Y^{+}$. We
also refer to the supremum and infimum of a subset $U\subset Y$ in the usual
sense, namely $\bar{y}=\sup U$ if $u\leq_{C}\bar{y}$ holds for all $u\in U$
and $\bar{y}\leq_{C}y$ for any other upper bound $y$ for $U$, and similarly
for $\inf U$. If $\\{y_{n}\\}_{n\in\mathbb{N}}$ is a sequence in $Y$, we
naturally refer to it is a decreasing sequence if $y_{n+1}\leq_{C}y_{n}$ for
every $n\in\mathbb{N}$. Finally, a decreasing, nonnegative sequence
$\\{p_{n}\\}_{n\in\mathbb{N}}\subset Y^{+}$ converges in order to 0 if
$0=\inf_{n\in\mathbb{N}}\\{p_{n}\\}$ in which case we write
$p_{n}\downarrow_{C}0$. Such sequences are used to define a general notion of
order convergence $y_{n}\rightarrow_{C}y$ in ordered vector spaces [28,
Theorem 16.1].

An ordered vector space $Y$ by a cone $C$ is said to be Archimedean if
$n^{-1}y\downarrow_{C}0$ whenever $y\in Y^{+}$, and it is said to be
generating if $Y=C-C$.

Let $f\colon X\to Y$ be a function between vector spaces, where $Y$ is
partially ordered by a nonempty convex cone $C$. We define the $C$-domain and
the $C-$epigraph of $f$ as follows:

$\mbox{\rm dom}\,_{C}(f):=\\{x\in X\;\big{|}\;\exists y\in
Y\;\text{with}\;f(x)<_{C}y\\},$ $\mbox{\rm epi}\,_{C}(f):=\\{(x,y)\in X\times
Y\;\big{|}\;x\in\mbox{\rm dom}\,_{C}(f),f(x)\leq_{C}y\\}.$

The function $f$ is said to be $C$-proper if $\mbox{\rm
dom}\,_{C}(f)\neq\emptyset$. We say that $f$ is $C$-convex if for all
$x_{1},x_{2}\in\mbox{\rm dom}\,_{C}(f)$ and $\lambda\in[0,1]$ one has

$f\big{(}\lambda x_{1}+(1-\lambda)x_{2}\big{)}\leq_{C}\lambda
f(x_{1})+(1-\lambda)f(x_{2}).$

###### Definition 2.1

Let $\Omega\subset X$ be a convex set. Then core or algebraic interior of
$\Omega$ is defined by

$\displaystyle\text{core}(\Omega):=\big{\\{}x\in\Omega\;\big{|}\;\forall v\in
X,\;\exists\delta>0,\;\forall t\mbox{ with
}|t|<\delta:\;x+tv\in\Omega\big{\\}}.$

If $X$ is a topological vector space, then ${\rm
int}(\Omega)\subset\text{core}(\Omega)\subset\Omega$, where ${\rm
int}(\Omega)$ stands for the topological interior of $\Omega$. In the general
case of vector spaces, the convexity of the set $\text{core}(\Omega)$ can be
derived from the convexity of $\Omega$.

Recall that a subset $\Omega$ of a vector space $X$ is absorbing if for any
$v\in X$ there exists $\delta>0$ such that $tv\in\Omega$ whenever
$|t|<\delta$. One can see that $\bar{x}\in\text{core}(\Omega)$ if and only if
the set $\Omega-\bar{x}$ is absorbing. We also observe that

$\text{core}\big{(}\text{core}(\Omega)\big{)}=\text{core}(\Omega).$

We next recall the two separation notions for convex sets which will be used
in the paper.

###### Definition 2.2

Nonempty subsets $\Omega_{1},\Omega_{2}\subset X$ are separated by a
hyperplane if there is a nonzero linear function $f\colon X\to\mathbb{R}$ such
that

$\sup\big{\\{}f(x)\;\big{|}\;x\in\Omega_{1}\big{\\}}\leq\inf\big{\\{}f(x)\;\big{|}\;x\in\Omega_{2}\big{\\}}.$
(2.1)

If we have in addition that

$\inf\big{\\{}f(x)\;\big{|}\;x\in\Omega_{1}\big{\\}}<\sup\big{\\{}f(x)\;\big{|}\;x\in\Omega_{2}\big{\\}},$

which means that there exist vectors $x_{1}\in\Omega_{1}$ and
$x_{2}\in\Omega_{2}$ with $f(x_{1})<f(x_{2})$, then the sets $\Omega_{1}$ and
$\Omega_{2}$ are properly separated by a hyperplane.

A set $\Omega\subset X$ is said to be core-solid if
$\text{core}(\Omega)\neq\emptyset$. The following important theorems (see [14,
Therem 3.3, Theorem 3.4]) presents a refined version of the hyperplane
separation of a singleton from a convex set in vector spaces with establishing
the equivalence between separation and proper separation in this case and
deriving a core characterization of these properties.

###### Theorem 2.3

Let $\Omega$ be a convex subset in $X$with $\mbox{\rm
core}\,(\Omega)\neq\emptyset$, and let $x_{0}\notin\Omega$. Then there exists
a hyperplane that separates $\Omega$ and $\\{x_{0}\\}$ properly. In the case
where $\Omega=\mbox{\rm core}\,(\Omega)$, there is a nonzero linear function
$f\colon X\to R$ with $f(x)<f(x_{0})$ for all $x\in\Omega$.

###### Theorem 2.4

Let $\Omega$ be a convex subset of $X$ with
$\text{core}(\Omega)\neq\emptyset$, and let $x_{0}\in X$. Then the following
assertions are equivalent:
(a) $\Omega$ and $\\{x_{0}\\}$ are separated.
(b) $\Omega$ and $\\{x_{0}\\}$ are properly separated.
(c) $x_{0}\notin\mbox{\rm core}(\Omega)$.

We now revisit the extremality notion for arbitrary sets in vector spaces.

###### Definition 2.5

Let $\Omega_{1}$ and $\Omega_{2}$ be nonempty subset of a vector space $X$.
The set system $\\{\Omega_{1},\Omega_{2}\\}$ is extremal in $X$ if there
exists $x_{0}\in X$ such that for all $\delta>0$ we can find
$t_{0}\in\mathbb{R}$ with $|t_{0}|<\delta$ satisfying

$\big{(}\Omega_{1}+t_{0}x_{0}\big{)}\cap\Omega_{2}=\emptyset.$

It follows directly from the definition that if two sets $\Omega_{1}$ and
$\Omega_{2}$ are disjoint (i.e., $\Omega_{1}\cap\Omega_{2}=\emptyset$), then
they form an extremal system. In addition, two sets $\Omega_{1}$ and
$\Omega_{2}$ do not form an extremal system in $X$ if for any $x_{0}\in X$
there exists $\delta>0$ such that for all $t\in\mathbb{R}$ with $|t|<\delta$
we have the condition

$\big{(}\Omega_{1}+tx_{0}\big{)}\cap\Omega_{2}\neq\emptyset.$

For the next theorem we require another definition, consider a nonempty convex
subset $\Omega$ of a vector space $X$ and define the normal cone to $\Omega$
at $\bar{x}\in\Omega$ by

$N(\bar{x};\Omega):=\big{\\{}f\in X^{\prime}\;\big{|}\;f(x-\bar{x})\leq
0\;\text{ for all }\;x\in\Omega\big{\\}}$

with $N(\bar{x};\Omega):=\emptyset$ for $\bar{x}\notin\Omega$. The next
theorem provides characterizations of set extremality for systems of convex
sets and relationships with convex separation. The proof can be found in [13,
Theorem 3.2].

###### Theorem 2.6

Given two nonempty convex sets $\Omega_{1},\Omega_{2}\subset X$, we have the
following assertions:
(i) The system $\\{\Omega_{1},\Omega_{2}\\}$ is extremal system in $X$ if and
only if $0\notin\text{core}(\Omega_{1}-\Omega_{2})$, which implies that
$\text{core}(\Omega_{1})\cap\Omega_{2}=\emptyset$ and
$\text{core}(\Omega_{2})\cap\Omega_{1}=\emptyset$.
(ii) If the set system $\\{\Omega_{1},\Omega_{2}\\}$ is extremal and the set
difference $\Omega_{1}-\Omega_{2}$ is core-solid, then the sets $\Omega_{1}$
and $\Omega_{2}$ are separated by a hyperplane, i.e., (2.1) holds.
(iii) If $\bar{x}\in\Omega_{1}\cap\Omega_{2}$, then the latter is equivalent
to

$N(\bar{x};\Omega_{1})\cap\big{(}-N(\bar{x};\Omega_{2})\big{)}\neq\\{0\\}.$

(iv) The separation property (2.1) yields the set extremality.

The following result (see [13, Theorem 3.3]) gives us an important rule, a
representation of the normal cone to the intersection of two convex sets.

###### Theorem 2.7

Let $\Omega_{1}$ and $\Omega_{2}$ be convex sets in $X$ with the nonempty
intersection under the fulfillment of the following basic qualification
condition:

$\text{core}(\Omega_{1})\cap\Omega_{2}\neq\emptyset.$

Then the normal cone to $\Omega_{1}\cap\Omega_{2}$ at any point
$\bar{x}\in\Omega_{1}\cap\Omega_{2}$ is represented by

$N(\bar{x};\Omega_{1}\cap\Omega_{2})=N(\bar{x};\Omega_{1})+N(\bar{x};\Omega_{2}).$

##  3 Revisiting Coderivative Calculus in Vector Spaces

In this section we revisit coderivative calculus rules in vector spaces. The
reader can refer to [13] for more details. We first recall that a set-valued
mapping $F\colon X\;{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Y$ between vector spaces is associated with its
graph

$\text{gph}\,(F):=\big{\\{}(x,y)\in X\times Y\;\big{|}\;y\in F(x)\big{\\}},$

and it is called convex if its graph is a convex subset of the product space
$X\times Y$. We also consider the domain and range of $F$ defined by

$\mbox{\rm dom}\,(F):=\big{\\{}x\in
X\;\big{|}\;F(x)\neq\emptyset\big{\\}},\;\mbox{\rm rge}\,(F):=\bigcup_{x\in
X}F(x),$

respectively. It is easy to see that if $F$ is a convex set-valued mapping,
then $\mbox{\rm rge}\,(F)$ is a convex subset of $Y$.

Recall that the coderivative of $F$ at $(\bar{x},\bar{y})\in\text{gph}\,(F)$
is a set-valued mapping $D^{*}F(\bar{x},\bar{y})\colon Y^{\prime}\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;X^{\prime}$ defined by

$D^{*}F(\bar{x},\bar{y})(g):=\big{\\{}f\in X^{\prime}\;\big{|}\;(f,-g)\in
N\big{(}(\bar{x},\bar{y});\text{gph}\,(F)\big{)}\big{\\}},\quad g\in
Y^{\prime}.$ (3.1)

Now we define the composition of two mappings $F\colon X\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Y$ and $G\colon Y\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Z$ by

$(G\circ F)(x)=\bigcup_{y\in F(x)}G(y):=\\{z\in G(y)\;|\;y\in F(x)\\},\quad
x\in X,$

and observe that $G\circ F$ is convex provided that both $F$ and $G$ are
convex. Given $\bar{z}\in(G\circ F)(\bar{x})$, we consider the set

$M(\bar{x},\bar{z}):=F(\bar{x})\cap G^{-1}(\bar{z}).$

The following theorem establishes the coderivative chain rule for set-valued
mappings in vector spaces. In this version, we use the core qualification
condition on domains and ranges replacing the one on graphs known from [13,
Theorem 5.1].

###### Theorem 3.1

Let $F\colon X\;{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Y$ and $G\colon Y\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Z$ be convex set-valued mappings. Suppose that the
qualification condition is satisfied

$\mbox{\rm core}\,\big{(}\mbox{\rm rge}\,(F)\big{)}\cap\mbox{\rm
core}\,\big{(}\mbox{\rm dom}\,(G)\big{)}\neq\emptyset;$ (3.2)

Then for any $(\bar{x},\bar{z})\in\text{gph}\,(G\circ F)$ and $h\in
Z^{\prime}$ we have the coderivative chain rule

$D^{*}(G\circ F)(\bar{x},\bar{z})(h)=\bigcap_{\bar{y}\in
M(\bar{x},\bar{z})}D^{*}F(\bar{x},\bar{y})\circ D^{*}G(\bar{y},\bar{z})(h).$
(3.3)

Proof. Picking $f\in D^{*}(G\circ F)(\bar{x},\bar{z})(h)$ and $\bar{y}\in
M(\bar{x},\bar{z})$ gives us the inclusion $(f,-h)\in
N((\bar{x},\bar{z});\text{gph}\,(G\circ F))$, which means that

$\langle f,x-\bar{x}\rangle-\langle h,z-\bar{z}\rangle\leq 0\;\mbox{\rm for
all }\;(x,z)\in\text{gph}\,(G\circ F).$

Define two convex subsets of $X\times Y\times Z$ by

$\Omega_{1}:=\text{gph}\,(F)\times Z\;\mbox{ and
}\;\Omega_{2}:=X\times\text{gph}\,(G).$

It is easy to see that

$\Omega_{1}-\Omega_{2}=X\times\big{(}\mbox{\rm rge}\,(F)-\mbox{\rm
dom}\,(G)\big{)}\times Z.$ (3.4)

Using (3.4), we have the representation

$\mbox{\rm core}\,(\Omega_{1}-\Omega_{2})=X\times\mbox{\rm
core}\,\big{(}\mbox{\rm rge}\,(F)-\mbox{\rm dom}\,(G)\big{)}\times Z.$

Applying [14, Lemma 5.1] gives us

$\mbox{\rm core}\,(\Omega_{1}-\Omega_{2})=X\times\big{(}\mbox{\rm
core}\,\big{(}\mbox{\rm rge}\,(F)\big{)}-\mbox{\rm core}\,\big{(}\mbox{\rm
dom}\,(G)\big{)}\big{)}\times Z.$

It follows from (3.2) and the definitions of the sets $\Omega_{1}$ and
$\Omega_{2}$

$0\in\mbox{\rm core}\,(\Omega_{1}-\Omega_{2}),\;\mbox{ and so }\;\mbox{\rm
core}\,(\Omega_{1})\cap\mbox{\rm core}\,(\Omega_{2})\neq\emptyset.$ (3.5)

We can see that $(\bar{x},\bar{y},\bar{z})\in\Omega_{1}\cap\Omega_{2}$. Hence,
from the definitions

$(f,0,-h)\in N((\bar{x},\bar{y},\bar{z});\Omega_{1}\cap\Omega_{2}).$

Applying [14, Theorem 5.4] with qualification (3.5) tells us that

$(f,0,-h)\in
N((\bar{x},\bar{y},\bar{z});\Omega_{1}\cap\Omega_{2})=N((\bar{x},\bar{y},\bar{z});\Omega_{1})+N((\bar{x},\bar{y},\bar{z});\Omega_{2}),$

and thus there exists a vector $g\in Y^{\prime}$ such that we have the
representation

$(f,0,-h)=(f,-g,0)+(0,g,-h)$

with $(f,-g)\in N((\bar{x},\bar{y});\text{gph}\,(F)),\;(g,-h)\in
N((\bar{y},\bar{z});\text{gph}\,(G)).$ Using the coderivative definition (3.1)
we obtain

$f\in D^{*}F(\bar{x},\bar{y})(g)\;\mbox{\rm and }\;g\in
D^{*}G(\bar{y},\bar{z})(h),$

and hence the inclusion “$\subset$” in (3.3) is verified. The opposite
inclusion is trivial. $\hfill\square$

Let $F\colon X\;{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Y$ be a set-valued mapping and let $\Theta\subset
Y$ be a given set. The preimage or inverse image of $\Theta$ under the mapping
$F$ is given by

$F^{-1}(\Theta):=\\{x\in X\ |\ F(x)\cap\Theta\neq\emptyset\\}.$

The next result gives us a representation of the normal cone to
$F^{-1}(\Theta)$ via the normal cone of $\Theta$ and the coderivative of $F$.

###### Proposition 3.2

Let $F\colon X\;{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Y$ be a convex set-valued mapping and let
$\Theta\subset Y$ be a convex set, where $X,Y$ are vector spaces. Suppose that

$\mbox{\rm core}\,\big{(}\mbox{\rm rge}\,(F)\big{)}\cap\mbox{\rm
core}\,(\Theta)\neq\emptyset.$ (3.6)

Then for any $\bar{x}\in F^{-1}(\Theta)$ and $\bar{y}\in F(\bar{x})\cap\Theta$
we have the representation

$N(\bar{x};F^{-1}(\Theta))=D^{*}F(\bar{x},\bar{y})\big{(}N(\bar{y};\Theta)\big{)}.$

Proof. The set $F^{-1}(\Theta)$ is clearly convex. Fix $f\in
N(\bar{x};F^{-1}(\Theta))$ we get

$\langle f,x-\bar{x}\rangle\leq 0\ \text{ for all}\ x\in F^{-1}(\Theta),\
\text{i.e.},\ F(x)\cap\Theta\neq\emptyset.$

Consider the two convex sets

$\Omega_{1}:=\text{gph}\,(F)\;\mbox{ and }\;\Omega_{2}:=X\times\Theta$

and easily check that

$\Omega_{1}-\Omega_{2}=X\times\big{(}\mbox{\rm rge}\,(F)-\Theta\big{)}.$

Using (3.6), we have the equalities

$0\in\mbox{\rm core}\,(\Omega_{1})-\mbox{\rm core}\,(\Omega_{2})=\mbox{\rm
core}\,(\Omega_{1}-\Omega_{2})=X\times\big{(}\mbox{\rm core}\,(\mbox{\rm
rge}\,(F))-\mbox{\rm core}\,(\Theta)\big{)},$

and hence $\mbox{\rm core}\,(\Omega_{1})\cap\mbox{\rm
core}\,(\Omega_{2})\neq\emptyset$. Applying [14, Theorem 5.4] gives us that

$\begin{array}[]{ll}(f,0)\in
N((\bar{x},\bar{y});\Omega_{1}\cap\Omega_{2})&=N((\bar{x},\bar{y});\Omega_{1})+N((\bar{x},\bar{y});\Omega_{2})\\\
&=N((\bar{x},\bar{y});\text{gph}\,(F))+[\\{0\\}\times
N(\bar{y};\Theta)]\end{array}$

and allows us to conclude that

$(f,0)=(f,-g)+(0,g)\ \text{with}\ (f,-g)\in
N((\bar{x},\bar{y});\text{gph}\,(F))\ \text{and}\ g\in N(\bar{y};\Theta).$

Hence $f\in D^{*}F(\bar{x},\bar{y})(g)$ and $g\in N(\bar{y};\Theta)$, which
brings us to the inclusion

$N(\bar{x};F^{-1}(\Theta))\subset
D^{*}F(\bar{x},\bar{y})\big{(}N(\bar{y};\Theta)\big{)}.$

The opposite inclusion is trivial, and thus we complete the proof.
$\hfill\square$

The next result addresses the exact coderivative representation for parametric
constraint systems defined as follows. Let $\Omega\subset X\times Y$ and
$\Theta\subset Z$ be convex sets, and let $\varphi\colon X\times Y\to Z$ be
such that both sets $\varphi^{-1}(\Theta)$ and $\mbox{\rm rge}\,(\varphi)$ are
convex, where $X,Y,$ and $Z$ are vector spaces. Consider the set-valued
mapping $F\colon X\;{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Y$ given by

$F(x):=\\{y\in Y\ |\ (x,y)\in\Omega,\ \varphi(x,y)\in\Theta\\}$ (3.7)

and observe that the graph of $F$ is a convex set. The following result
presents the coderivative of a parametric constraint systems

###### Theorem 3.3

Let $\varphi,\Theta,$ and $\Omega$ be as above, and let $F$ be defined in
(3.7). Suppose that

$\mbox{\rm core}\,\big{(}\mbox{\rm rge}\,(\varphi)\big{)}\cap\mbox{\rm
core}\,(\Theta)\neq\emptyset.$

If either $\mbox{\rm
core}\,\big{(}\varphi^{-1}(\Theta)\big{)}\cap\Omega\neq\emptyset\;\text{or}\;\varphi^{-1}(\Theta)\cap\mbox{\rm
core}\,(\Omega)\neq\emptyset$, then for any
$(\bar{x},\bar{y})\in\text{gph}\,(F)$ with
$\bar{z}=\varphi(\bar{x},\bar{y})\in\Theta$ any $g\in Y^{\prime}$, we have

$D^{*}F(\bar{x},\bar{y})(g)=\\{f\in X^{\prime}\ |\ (f,-g)\in
D^{*}\varphi(\bar{x},\bar{y},\bar{z})(N(\bar{z};\Theta))+N((\bar{x},\bar{y});\Omega)\\}.$

Proof. It follows from the definition that

$\text{gph}\,(F)=\varphi^{-1}(\Theta)\cap\Omega,$

and hence the coderivative of (3.7) is represented as

$D^{*}F(\bar{x},\bar{y})(g)=\\{f\in X^{\prime}\ |\ (f,-g)\in
N((\bar{x},\bar{y});\varphi^{-1}(\Theta)\cap\Omega)\\}.$

Using the imposed assumptions on the initial data and employing the normal
intersection rule from Theorem 2.7 give us the equality

$N((\bar{x},\bar{y});\text{gph}\,(F))=N((\bar{x},\bar{y});\varphi^{-1}(\Theta))+N((\bar{x},\bar{y});\Omega).$

Finally, applying Proposition 3.2, we arrive at

$N\big{(}(\bar{x},\bar{y});\varphi^{-1}(\Theta)\big{)}=D^{*}\varphi(\bar{x},\bar{y},\bar{z})(N(\bar{z};\Theta))$

and hence complete the proof of the theorem. $\hfill\square$

Let $F_{1},F_{2}\colon X\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
2.0pt\hbox{$\rightarrow$}}\;Y$ be set-valued mappings. We define

$(F_{1}\cap F_{2})(x):=F_{1}(x)\cap F_{2}(x),\;x\in X.$

The following result gives us a presentation of the coderivative for the
intersection of two set-valued mapping.

###### Theorem 3.4

Let $F_{1},F_{2}\colon X\rightrightarrows Y$ be convex set-valued mappings and

$\text{core}(\text{gph}\,F_{1})\cap\text{gph}\,F_{2}\neq\emptyset.$

Then for any $\bar{y}\in(F_{1}\cap F_{2})(\bar{x})$ and any $g\in Y^{\prime}$
we have

$D^{*}(F_{1}\cap
F_{2})(\bar{x},\bar{y})(g)=\bigcup_{g_{1}+g_{2}=g}\big{(}D^{*}F_{1}(\bar{x},\bar{y})(g_{1})+D^{*}F_{2}(\bar{x},\bar{y})(g_{2})\big{)}.$
(3.8)

Proof. We first verify the inclusion “$\subset$” in (3.8). Let
$\bar{y}\in(F_{1}\cap F_{2})(\bar{x})$, $g\in Y^{\prime}$, and $f\in
D^{*}(F_{1}\cap F_{2})(\bar{x},\bar{y})(g)$ we have

$(f,-g)\in N\big{(}(\bar{x},\bar{y});{\text{gph}\,}(F_{1}\cap
F_{2})\big{)}=N\big{(}(\bar{x},\bar{y});(\text{gph}\,F_{1})\cap(\text{gph}\,F_{2})\big{)}.$

Then applying Theorem 2.7 under the corresponding assumptions tells us that

$\displaystyle(f,-g)\in N\big{(}(\bar{x},\bar{y});{\rm gph}(F_{1}\cap
F_{2})\big{)}=N\big{(}(\bar{x},\bar{y});\text{gph}\,F_{1}\big{)}+N\big{(}(\bar{x},\bar{y});\text{gph}\,F_{2}\big{)}.$

Thus, $(f,-g)=(f_{1},-g_{1})+(f_{2},-g_{2})$ with some $(f_{i},-g_{i})\in
N((\bar{x},\bar{y});\text{gph}\,F_{i}))$ for $i=1,2$. Therefore, $f\in
D^{*}F_{1}(\bar{x},\bar{y})(g_{1})+D^{*}F_{2}(\bar{x},\bar{y})(g_{2})$ and
$g=g_{1}+g_{2}$, which justify the inclusion “$\subset$” in (3.8).

To verify the opposite inclusion in (3.8), take $g_{1},g_{2}\in Y^{\prime}$
with $g_{1}+g_{2}=g$. Choosing $f\in
D^{*}F_{1}(\bar{x},\bar{y})(g_{1})+D^{*}F_{2}(\bar{x},\bar{y})(g_{2})$, we get
$f=f_{1}+f_{2}$ for some $f_{1}\in D^{*}F_{1}(\bar{x},\bar{y})(g_{1})$ and
$f_{2}\in D^{*}F_{2}(\bar{x},\bar{y})(g_{2})$. This shows that

$\displaystyle(f,-g)=(f_{1},-g_{1})+(f_{2},-g_{2})$ $\displaystyle\in
N\big{(}(\bar{x},\bar{y});\text{gph}\,F_{1}\big{)}+N\big{(}(\bar{x},\bar{y});\text{gph}\,F_{2}\big{)}$
$\displaystyle=N\big{(}(\bar{x},\bar{y});{\rm gph}(F_{1}\cap F_{2})\big{)},$

and thus $f\in D^{*}(F_{1}\cap F_{2})(\bar{x},\bar{y})(g)$, which completes
the proof of the theorem. $\hfill\square$

##  4 Conjugate Calculus and Duality in Vector Spaces

In this section we first develop refined calculus rules for Fenchel conjugates
of convex functions in vector spaces with relaxed qualification conditions
under the convex set extremality. Then we use these results to establish a new
duality theorem in vector spaces.

Let $\Omega$ be a nonempty subset of a vector space $X$. We recall that the
support function $\sigma_{\Omega}\colon X^{\prime}\to\bar{\mathbb{R}}$ of
$\Omega$ is defined by

$\sigma_{\Omega}(f):=\sup\\{\langle f,x\rangle\;\big{|}\;x\in\Omega\\},\;f\in
X^{\prime}.$

The following theorem gives us a presentation for the support function of the
intersection of two convex sets in vector spaces.

###### Theorem 4.1

Let $\Omega_{1}$ and $\Omega_{2}$ be nonempty and convex subsets of a vector
space $X$. Suppose that

$\text{core}(\Omega_{1})\cap\Omega_{2}\neq\emptyset.$

Then the support function of the intersection $\Omega_{1}\cap\Omega_{2}$ is
represented as

$\big{(}\sigma_{\Omega_{1}\cap\Omega_{2}}\big{)}(f)=\big{(}\sigma_{\Omega_{1}}\square\sigma_{\Omega_{2}}\big{)}(f)\;\;\mbox{
for all }\;f\in X^{\prime}.$ (4.1)

Furthermore, for any $f\in\mbox{\rm dom}\,(\sigma_{\Omega_{1}\cap\Omega_{2}})$
there exist dual elements $f_{1},f_{2}\in X^{\prime}$ such that
$f=f_{1}+f_{2}$ and

$(\sigma_{\Omega_{1}\cap\Omega_{2}})(f)=\sigma_{\Omega_{1}}(f_{1})+\sigma_{\Omega_{2}}(f_{2}).$
(4.2)

Proof. The proof of inequality “$\leq$” in (4.1) is straightforward.

Now we prove the inequality “$\geq$” in (4.1) under the given assumptions. To
proceed, fix any $f\in\mbox{\rm dom}\,(\sigma_{\Omega_{1}\cap\Omega_{2}})$,
denote $\alpha:=\sigma_{\Omega_{1}\cap\Omega_{2}}(f)\in\mathbb{R}$, for which
by definition

$\langle f,x\rangle\leq\alpha\;\;\mbox{\rm whenever
}\;x\in\Omega_{1}\cap\Omega_{2},$

and define the nonempty convex subsets of $X\times\mathbb{R}$ by

$\displaystyle\begin{array}[]{ll}&\Theta_{1}:=\big{\\{}(x,\lambda)\in
X\times\mathbb{R}\;\big{|}\;x\in\Omega_{1},\;\lambda\leq\langle
f,x\rangle-\alpha\big{\\}},\\\
&\Theta_{2}:=\Omega_{2}\times[0,\infty).\end{array}$

It is easy to see from the constructions of $\Theta_{1}$ and $\Theta_{2}$ that

$\text{core}(\Theta_{1})=\\{x\in\text{core}(\Omega_{1}),\;\lambda<\langle
f,x\rangle-\alpha\\}$

and hence

$\text{core}(\Theta_{1})\cap\Theta_{2}=\emptyset.$

Applying Theorem 2.6 ensures the existence of $(0,0)\neq(g,\beta)\in
X^{\prime}\times\mathbb{R}$ for which

$\langle g,x\rangle+\beta\lambda_{1}\leq\langle
g,y\rangle+\beta\lambda_{2}\;\mbox{ whenever
}\;(x,\lambda_{1})\in\Theta_{1},\;(y,\lambda_{2})\in\Theta_{2}.$ (4.4)

In addition, there are $(\tilde{x},\tilde{\lambda}_{1})\in\Theta_{1}$ and
$(\tilde{y},\tilde{\lambda}_{2})\in\Theta_{2}$ satisfying

$\langle g,\tilde{x}\rangle+\tilde{\lambda}_{1}\beta<\langle
g,\tilde{y}\rangle+\tilde{\lambda}_{2}\beta.$ (4.5)

If $\beta=0$ we can reduce (4.5) to

$\langle g,\tilde{x}\rangle<\langle g,\tilde{y}\rangle.$

Using $(\bar{x},\langle f,x\rangle-\alpha)\in\Theta_{1}$ and
$(\bar{x},0)\in\Theta_{2}$ yields $\beta\geq 0$. Now we will show that
$\beta>0$. By contradiction, suppose $\beta=0$, from (4.4) and (4.5),
$\Omega_{1}$ and $\Omega_{2}$ can be properly separated which is a
contradiction to $\text{core}(\Omega_{1})\cap\Omega_{2}\neq\emptyset$. Thus,
$\beta>0$.

Taking now the pairs $(x,\langle f,x\rangle-\alpha)\in\Theta_{1}$ in (4.4) and
$(y,0)\in\Theta_{2}$, we get

$\langle g,x\rangle+\beta(\langle f,x\rangle-\alpha)\leq\langle
g,y\rangle\;\;\mbox{\rm with }\;\beta>0,$

which leads us to the estimate

$\big{\langle}g/\beta+f,x\big{\rangle}+\big{\langle}-g/\beta,y\big{\rangle}\leq\alpha\;\mbox{
for all }\;x\in\Omega_{1},\;y\in\Omega_{2}.$

Letting $f_{1}:=g/\beta+f$ and $f_{2}:=-g/\beta$, we arrive at the inequality
“$\geq$” in (4.1) and thus get the representation (4.2). $\hfill\square$

Let $\varphi\colon X\to\overline{\mathbb{R}}$ be a convex function. We recall
that the convex Fenchel conjugate of $\varphi$ is the function
$\varphi^{*}\colon X^{\prime}\to[-\infty,\infty]$ given by

$\varphi^{*}(f):=\sup\\{\langle f,x\rangle-\varphi(x)\ |\ x\in X\\},\;f\in
X^{\prime}.$

Note that if $\mbox{\rm dom}\,(\varphi)\neq\emptyset$, then $\varphi^{*}\colon
X^{\prime}\to(-\infty,\infty]$ is a convex function and

$\varphi^{*}(f):=\sup\\{\langle f,x\rangle-\varphi(x)\ |\ x\in\mbox{\rm
dom}\,(\varphi)\\},\;f\in X^{\prime}.$

The next observation makes a bridge between the conjugate of an arbitrary
function and the support function of its epigraph. It is essential in the
implementation of our geometric approach to conjugate calculus.

###### Lemma 4.2

For any proper function $\varphi\colon X\to\overline{\mathbb{R}}$ we have

$\varphi^{*}(f)=\sigma_{{\rm\small epi}(\varphi)}(f,-1)\;\mbox{ whenever
}\;f\in X^{\prime}.$

Proof. It follows from the definitions that

$\displaystyle\begin{array}[]{ll}\varphi^{*}(f)=\sup\big{\\{}\langle
f,x\rangle-\varphi(x)\;\big{|}\;x\in\mbox{\rm
dom}\,(\varphi)\big{\\}}&=\sup\big{\\{}\langle
f,x\rangle-\lambda\;\big{|}\;(x,\lambda)\in\mbox{\rm
epi}\,(\varphi)\big{\\}}\\\ \\\ &=\sigma_{{\rm\small
epi}(\varphi)}(f,-1),\end{array}$

which therefore verifies the claimed formula. $\hfill\square$

Here is the conjugate sum rule in vector spaces.

###### Theorem 4.3

Let $\varphi_{1},\varphi_{2}\colon X\to\overline{\mathbb{R}}$ be proper convex
functions on a vector space $X$. Suppose that

$\text{core}\big{(}\mbox{\rm dom}\,(\varphi_{1})\big{)}\cap\mbox{\rm
dom}\,(\varphi_{2})\neq\emptyset.$

Then we have the conjugate sum rule

$(\varphi_{1}+\varphi_{2})^{*}(f)=\big{(}\varphi_{1}^{*}\square\varphi_{2}^{*}\big{)}(f)\;\mbox{
for all }\;f\in X^{\prime}.$ (4.7)

Moreover, the infimum in $(\varphi_{1}^{*}\square\varphi_{2}^{*})(f)$ is
attained, i.e., for any $f\in\mbox{\rm dom}\,(\varphi_{1}+\varphi_{2})^{*}$
there exist $f_{1},f_{2}\in X^{\prime}$ for which

$\displaystyle(\varphi_{1}+\varphi_{2})^{*}(f)=\varphi_{1}^{*}(f_{1})+\varphi_{2}^{*}(f_{2}),\quad
f=f_{1}+f_{2}.$

Proof. Fixing any $f_{1},f_{2}\in X^{\prime}$ with $f_{1}+f_{2}=f$, we get

$\displaystyle\begin{array}[]{ll}\varphi_{1}^{*}(f_{1})+\varphi_{2}^{*}(f_{2})&=\sup\big{\\{}\langle
f_{1},x\rangle-\varphi_{1}(x)\;\big{|}\;x\in X\big{\\}}+\sup\big{\\{}\langle
f_{2},x\rangle-\varphi_{2}(x)\;\big{|}\;x\in X\big{\\}}\\\
&\geq\sup\big{\\{}\langle f_{1},x\rangle-\varphi_{1}(x)+\langle
f_{2},x\rangle-\varphi_{2}(x)\;\big{|}\;x\in X\big{\\}}\\\
&=\sup\big{\\{}\langle f,x\rangle-(\varphi_{1}+\varphi_{2})(x)\;\big{|}\;x\in
X\big{\\}}=(\varphi_{1}+\varphi_{2})^{*}(f).\end{array}$

Note that this inequality does not require the given assumption.

Let us prove that
$(\varphi_{1}^{*}\square\varphi_{2}^{*})(f)\leq(\varphi_{1}+\varphi_{2})^{*}(f)$.
We only need to consider the case where
$(\varphi_{1}+\varphi_{2})^{*}(f)<\infty$. Define two convex sets by

$\displaystyle\begin{array}[]{ll}&\Omega_{1}:=\big{\\{}(x,\lambda_{1},\lambda_{2})\in
X\times\mathbb{R}\times\mathbb{R}\;\big{|}\;\lambda_{1}\geq\varphi_{1}(x)\big{\\}}=\mbox{\rm
epi}\,(\varphi_{1})\times\mathbb{R},\\\
&\Omega_{2}:=\big{\\{}(x,\lambda_{1},\lambda_{2})\in
X\times\mathbb{R}\times\mathbb{R}\;\big{|}\;\lambda_{2}\geq\varphi_{2}(x)\big{\\}}.\end{array}$
(4.11)

Similarly to Lemma 4.2 we get the representation

$(\varphi_{1}+\varphi_{2})^{*}(f)=\sigma_{\Omega_{1}\cap\Omega_{2}}(f,-1,-1).$
(4.12)

We can show that $\Omega_{1}$ and $\Omega_{2}$ satisfy the support function
intersection rule requirements. Applying this theorem to the right-hand side
of (4.12) gives us triples $(f_{1},-\alpha_{1},-\alpha_{2})\in
X^{\prime}\times\mathbb{R}\times\mathbb{R}$ and
$(f_{2},-\beta_{1},-\beta_{2})\in X^{\prime}\times\mathbb{R}\times\mathbb{R}$
such that
$(f,-1,-1)=(f_{1},-\alpha_{1},-\alpha_{2})+(f_{2},-\beta_{1},-\beta_{2})$ and

$(\varphi_{1}+\varphi_{2})^{*}(f)=\sigma_{\Omega_{1}\cap\Omega_{2}}(f,-1,-1)=\sigma_{\Omega_{1}}(f_{1},-\alpha_{1},-\alpha_{2})+\sigma_{\Omega_{2}}(f_{2},-\beta_{1},-\beta_{2}).$

If $\alpha_{2}\neq 0$, then
$\sigma_{\Omega_{1}}(f_{1},-\alpha_{1},-\alpha_{2})=\infty$, which is not
possible. Thus $\alpha_{2}=0$ and similarly $\beta_{1}=0$. Employing now Lemma
4.2 and taking into account the structures of the sets $\Omega_{1}$ and
$\Omega_{2}$ in (4.11) imply that

$\displaystyle\begin{array}[]{ll}(\varphi_{1}+\varphi_{2})^{*}(f)&=\sigma_{\Omega_{1}\cap\Omega_{2}}(f,-1,-1)=\sigma_{\Omega_{1}}(f_{1},-1,0)+\sigma_{\Omega_{2}}(f_{2},0,-1)\\\
&=\sigma_{{\rm\small epi}(\varphi_{1})}(f,-1)+\sigma_{{\rm\small
epi}(\varphi_{2})}(f_{2},-1)\\\
&=\varphi_{1}^{*}(f_{1})+\varphi_{2}^{*}(f_{2})\geq\big{(}\varphi_{1}^{*}\square\varphi_{2}^{*}\big{)}(f).\end{array}$

This justifies the sum rule (4.7) and hence the infimum is attained.
$\hfill\square$

###### Theorem 4.4

Let $A\colon X\to Y$ be a continuous linear mapping between vector spaces and
$\varphi:Y\to\overline{\mathbb{R}}$ be convex function. Suppose that one of
two following conditions is satisfied:

  1. (a)

Graph of $A$ is core-solid and

$AX\cap\mbox{\rm dom}\,\varphi\neq\emptyset;$ (4.14)

  2. (b)

Graph of $\varphi$ is core-solid and

$AX\cap\text{core}(\mbox{\rm dom}\,\varphi)\neq\emptyset.$ (4.15)

Then we have the conjugate chain rule

$(\varphi\circ
A)^{*}(f)=\inf\\{\varphi^{*}(g)\;\big{|}\;g\in(A^{*})^{-1}(f)\\},\;f\in
X^{\prime}.$

Furthermore, for any $f\in\mbox{\rm dom}\,(\varphi\circ A)^{*}$ there exists
$g\in(A^{*})^{-1}(f)$ such that

$(\varphi\circ A)^{*}(f)=\varphi^{*}(g).$

Proof. Picking $g\in(A^{*})^{-1}(f)$ gives us by definition that

$\displaystyle\begin{array}[]{ll}\varphi^{*}(g)&=\sup\big{\\{}\langle
g,y\rangle-\varphi(y)\;\big{|}\;y\in Y\big{\\}}\\\ &\geq\sup\big{\\{}\langle
g,Ax\rangle-\varphi(Ax)\;\big{|}\;x\in X\big{\\}}\\\ &=\sup\big{\\{}\langle
A^{*}g,x\rangle-(\varphi\circ A)(x)\;\big{|}\;x\in X\big{\\}}\\\
&=\sup\big{\\{}\langle f,x\rangle-(\varphi\circ A)(x)\;\big{|}\;x\in
X\big{\\}}=(\varphi\circ A)^{*}(f).\end{array}$

This implies the inequality

$\inf\big{\\{}\varphi^{*}(g)\;\big{|}\;g\in(A^{*})^{-1}(f)\big{\\}}\geq(\varphi\circ
A)^{*}(f).$

Note that this inequalities holds obviously if $(A^{*})^{-1}(f)=\emptyset$.

Let us show that the opposite inequality is also satisfied. We can assume that
$f\in\mbox{\rm dom}\,((\varphi\circ A)^{*})$ and then define the convex sets

$\;\Omega_{1}:=\text{gph}\,(A)\times\mathbb{R}\mbox{ and
}\;\Omega_{2}:=X\times\mbox{\rm epi}\,(\varphi)\subset X\times
Y\times\mathbb{R}.$ (4.17)

It follows directly from the above constructions that

$(\varphi\circ A)^{*}(f)=\sigma_{\Omega_{1}\cap\Omega_{2}}(f,0,-1)<\infty.$

We can see that
$\text{core}(\Omega_{1})=\text{core}(\text{gph}\,(A))\times\mathbb{R}$.
Applying [14, Theorem 4.2], condition (a) gives us that

$\text{core}(\text{gph}\,A)=\\{(x,y)\;\big{|}\;x\in\text{core}(\mbox{\rm
dom}\,A),y\in\text{core}\\{Ax\\}\\}=\\{(x,y)\;\big{|}\;x\in
X,y=Ax\\}=\text{gph}\,A,$

while condition (b) shows that

$\text{core}(\text{gph}\,\varphi)=\\{(y,\lambda)\;\big{|}\;y\in\text{core}(\mbox{\rm
dom}\,\varphi),\varphi(y)<\lambda\\}.$

Therefore, identity (4.14) gives us the qualification

$\text{core}(\Omega_{1})\cap\Omega_{2}\neq\emptyset,$

while identity (4.15) gives us the qualification

$\Omega_{1}\cap\text{core}(\Omega_{2})\neq\emptyset.$

Then, Theorem 4.1 applied and there exist triples $(f_{1},g_{1},\alpha_{1})$
and $(f_{2},g_{2},\alpha_{2})$ in the space $X^{\prime}\times
Y^{\prime}\times\mathbb{R}$ satisfying

$(f,0,-1)=(f_{1},g_{1},\alpha_{1})+(f_{2},g_{2},\alpha_{2})\;\mbox{ and}$
$\sigma_{\Omega_{1}\cap\Omega_{2}}(f,0,-1)=\sigma_{\Omega_{1}}(f_{1},g_{1},\alpha_{1})+\sigma_{\Omega_{2}}(f_{2},g_{2},\alpha_{2}).$

It follows from the structures of $\Omega_{1}$ and $\Omega_{2}$ in (4.17) that
$\alpha_{1}=0$ and $f_{2}=0$. This gives us the representation

$\sigma_{\Omega_{1}\cap\Omega_{2}}(f,0,-1)=\sigma_{\Omega_{1}}(f,g_{2},0)+\sigma_{\Omega_{2}}(0,-g_{2},-1)$

for some $g_{2}\in Y^{\prime}$. Thus we arrive at the equalities

$\displaystyle\begin{array}[]{ll}\sigma_{\Omega_{1}\cap\Omega_{2}}(f,0,-1)&=\sup\big{\\{}\langle
f,x\rangle-\langle g_{2},Ax\rangle\;\big{|}\;x\in
X\big{\\}}+\sigma_{{\rm\small epi}(\varphi)}(g_{2},-1)\\\
&=\sup\big{\\{}\langle f-A^{*}g_{2},x\rangle\;\big{|}\;x\in
X\big{\\}}+\varphi^{*}(g_{2}),\end{array}$

which allow us to conclude that $f=A^{*}g_{2}$. Therefore

$\sigma_{\Omega_{1}\cap\Omega_{2}}(f,0,-1)=\varphi^{*}(g_{2})\geq\inf\big{\\{}\varphi^{*}(g)\;\big{|}\;g\in(A^{*})^{-1}(f)\big{\\}}.$

This justifies both statements of the theorem. $\hfill\square$

The following theorem gives us the version of Fenchel strong duality in vector
spaces under core qualifications.

###### Theorem 4.5

Let $\varphi,\psi\colon X\to\overline{\mathbb{R}}$ be convex functions.
Suppose that

$\text{core}\big{(}\mbox{\rm dom}\,(\varphi)\big{)}\cap\mbox{\rm
dom}\,(\psi)\neq\emptyset.$

Then

$\inf\\{\varphi(x)+\psi(x)\ |\ x\in X\\}=\sup\\{-\varphi^{*}(-f)-\psi^{*}(f)\
|\ f\in X^{\prime}\\}$

Proof. The inequality $``\geq$” follows directly from the definition.

We next prove the inequality $``\leq$”. Since the this inequality is obvious
when

$\inf\\{\varphi(x)+\psi(x)\;\big{|}\;x\in X\\}=-\infty,$

it suffices to consider the case where
$\alpha:=\inf\\{\varphi(x)+\psi(x)\;\big{|}\;x\in X\\}\in\mathbb{R}$. It is
easy to see that

$\alpha=\inf\\{\varphi(x)+\psi(x)\;\big{|}\;x\in X\\}=-\sup\\{\langle
0,x\rangle-(\varphi+\psi)(x)\;\big{|}\;x\in X\\}=-(\varphi+\psi)^{*}(0).$

Using conjugate sum rule from Theorem 4.3, we can find $f\in X^{\prime}$ such
that

$\alpha=-(\varphi+\psi)^{*}(0)=-\varphi^{*}(-f)-\psi^{*}(f).$

Therefore, we arrive the inequality $``\leq$” and hence the Theorem has been
proved. $\hfill\square$

We now investigate the composite convex optimization framework of Fenchel
duality in general vector spaces with specifying the results in vector spaces
and infinite-dimensional settings. The following result establishes an
inequality relationship between optimal values of the problem (1.1) and dual
problems (1.2). This relationship, which is sometimes called weak duality,
holds with no convexity assumptions of $\varphi$ and/or $\psi$, and its proof
is a consequence of the definitions.

###### Proposition 4.6

Consider the optimization problem (1.1) and its dual (1.2) in vector spaces,
where the functions $\varphi$ and $\psi$ are not assumed to be convex. Define
the optimal values in these problems by

$\displaystyle\begin{array}[]{ll}&\displaystyle\widehat{p}:=\inf_{x\in
X}\big{\\{}\varphi(x)+\psi(Ax)\big{\\}},\\\
&\displaystyle\widehat{d}:=\sup_{g\in
Y^{*}}\big{\\{}-\varphi^{*}(A^{*}g)-\psi^{*}(-g)\big{\\}}.\end{array}$

Then we always have $\widehat{p}\geq\widehat{d}$.

Proof. Directly from the definitions of conjugate functions and adjoint
operators, for any $g\in Y^{\prime}$ we have

$\displaystyle-\varphi^{*}(A^{*}g)-\psi^{*}(-g)$ $\displaystyle=-\sup_{x\in
X}\\{\langle A^{*}g,x\rangle-\varphi(x)\\}-\sup_{y\in
Y}\\{\langle-g,y\rangle-\psi(y)\\}$ $\displaystyle=\inf_{x\in
X}\\{\varphi(x)-\langle g,Ax\rangle\\}+\inf_{y\in Y}\\{\psi(y)+\langle
g,y\rangle\\}$ $\displaystyle\leq\inf_{x\in X}\\{\varphi(x)-\langle
g,Ax\rangle\\}+\inf_{x\in X}\\{\psi(Ax)+\langle g,Ax\rangle\\}$
$\displaystyle\leq\inf_{x\in X}\\{\varphi(x)-\langle
g,Ax\rangle+\psi(Ax)+\langle g,Ax\rangle\\}$ $\displaystyle=\inf_{x\in
X}\\{\varphi(x)+\psi(Ax)\\}=\widehat{p}.$

Taking the supremum with respect to all $g\in Y^{\prime}$ yields
$\widehat{d}\leq\widehat{p}$. $\hfill\square$

The following result gives us a version of Fenchel-Rockafellar theorem on
vector spaces under core qualification.

###### Theorem 4.7

Consider the optimization problem (1.1) and its dual (1.2). Suppose that one
of two conditions in Theorem 4.4 is satisfied. In addition to the standing
assumptions on $\varphi,\psi$, and $A$ in the formulation of the problem, and
either

$\mbox{\rm dom}\,(\psi\circ A)\cap\text{core}\big{(}\mbox{\rm
dom}\,(\varphi)\big{)}\neq\emptyset$ (4.20)

or

$\text{core}\big{(}\mbox{\rm dom}\,(\psi\circ A)\big{)}\cap\mbox{\rm
dom}\,(\varphi)\neq\emptyset$

Then we have the equality $\widehat{p}=\widehat{d}$. Furthermore, if the
number $\widehat{p}$ is finite, then the supremum in the definition of
$\widehat{d}$ is attained.

Proof. Due to Proposition 4.6, it remains to show that
$\widehat{p}\leq\widehat{d}$. Since the latter inequality is obvious when
$\widehat{p}=-\infty$, it suffices to consider the case where
$\widehat{p}\in\mathbb{R}$. We clearly have the equalities

$\displaystyle\begin{array}[]{ll}\widehat{p}&:=\displaystyle\inf_{x\in
X}\big{\\{}\varphi(x)+\psi(Ax)\big{\\}}=-\displaystyle\sup_{x\in
X}\big{\\{}\langle 0,x\rangle-[\varphi+(\psi\circ A)](x)\big{\\}}\\\
&=-[\varphi+(\psi\circ A)]^{*}(0).\end{array}$

By the conjugate sum rule from Theorem 4.3, we find $f\in X^{\prime}$ such
that

$\widehat{p}=-[\varphi+(\psi\circ A)]^{*}(0)=-\varphi^{*}(f)-(\psi\circ
A)^{*}(-f).$

The conjugate chain rule from Theorem 4.4 gives us $g\in Y^{\prime}$
satisfying

$A^{*}g=f,\;\;\mbox{ and }\;(\psi\circ A)^{*}(f)=\psi^{*}(g).$

Therefore, we arrive at the relationships

$\widehat{p}=-\varphi^{*}(A^{*}g)-\psi^{*}(-g)\leq\widehat{d},$

which also ensure that the supremum in the definition of $\widehat{d}$ is
attained. $\hfill\square$

###### Corollary 4.8

The qualification condition (4.20) is satisfied if

$\mbox{\rm dom}\,(\psi)\cap A(\text{core}(\mbox{\rm
dom}\,(\varphi))\neq\emptyset.$

Proof. Choose $y_{0}\in\mbox{\rm dom}\,(\psi)$ such that $y_{0}=A(x_{0})$ for
some $x_{0}\in\text{core}(\mbox{\rm dom}\,(\varphi))$. Then $x_{0}\in\mbox{\rm
dom}\,(\psi\circ A)\cap\text{core}(\mbox{\rm dom}\,(\varphi))$.
$\hfill\square$

##  5 Lagrangian Duality in Vector Spaces

In this section we consider the primal optimization problem discussed in the
introduction without the equality constraints. The general framework we work
under is described below:

$\left\\{\begin{aligned} &X\;\text{is a vector space},\;\Omega\;\text{is a
nonempty convex subset of}\;X,\\\ &Y\;\text{is an Archimedean and generating
partially ordered vector space by a cone}\;C\subset Y,\\\ &\varphi\colon
X\to\mathbb{R},\;\psi\colon X\to Y,\\\ &\varphi\;\text{is
convex},\;\psi\;\text{is}\;C-\text{convex},\\\ &C^{\prime}=\\{f\in
Y^{\prime}\;|\;0\leq\langle f,c\rangle\;\text{for all}\;c\in C\\},\\\
&\\{x\in\Omega\;|\;\psi(x)\in-C\\}\neq\emptyset,\\\
&L^{\prime}(f)=\inf_{x\in\Omega}\\{\varphi(x)+\langle
f,\psi(x)\rangle\\}.\end{aligned}\right.$

We consider the constrained optimization problem

$\displaystyle\begin{array}[]{ll}&\mbox{\rm minimize }\varphi(x),\\\
&\mbox{\rm subject to }x\in\Omega,\;\psi(x)\in-C,\end{array}$ (5.3)

and its Lagrange dual problem

$\displaystyle\begin{array}[]{ll}&\mbox{\rm maximize }L^{\prime}(f),\\\
&\mbox{\rm subject to }f\in C^{{}^{\prime}}.\end{array}$ (5.6)

Set

$\Lambda=\\{x\in\Omega\;|\;\psi(x)\in-C\\},$

and then define the optimal values in problems (5.3) and (5.6) by

$p:=\inf\\{\varphi(x)\;|\;x\in\Lambda\\},d:=\sup\\{L^{\prime}(f)\;|\;f\in
C^{\prime}\\}.$

One of the main goals of Lagrangian duality theory is to obtain sufficient
conditions which guarantee the Lagrangian strong duality $p=d.$ Most of the
known results in this research direction require the Slater conditions. In
LCTV spaces, some Slater conditions based on the quasi-relative interior was
introduced by Borwein and Lewis in [8], and then it was generalized by
Jeyakumar and Wolkowicz in [29]. Further significant results were obtained in
[9, 10, 17, 18] and the references therein.

The Slater condition/constraint for (5.3) postulates that

$\displaystyle\begin{array}[]{ll}\exists\widehat{x}\in\Omega\;\mbox{\rm such
that}\;\psi(\widehat{x})\in-\mbox{\rm core}\,(C).\end{array}$ (5.8)

To proceed, we consider a system of inequalities with the unknown $x\in X$:

$\left\\{\begin{aligned} &\varphi(x)<0,\\\ &\psi(x)\in-C,\\\
&x\in\Omega.\end{aligned}\right.$ (5.9)

We also consider a system of inequalities with unknowns $h\in Y^{\prime}$:

$\left\\{\begin{aligned} &\varphi(x)+\langle h,\psi(x)\rangle\geq 0\;\mbox{\rm
for all }x\in\Omega,\\\ &h\in C^{\prime}.\end{aligned}\right.$ (5.10)

The next lemma reveals relationships between the constraint systems (5.9) and
(5.10) under the Slater constraint (5.8).

###### Lemma 5.1

Let the Slater condition (5.8) be satisfied for problem (5.3). Then (5.9) has
a solution if and only if (5.10) has no solution.

Proof. Suppose that (5.9) admits a solution $x_{0}$ and show that (5.10) has
no solution. By a contradiction, suppose that (5.10) has a solution
$\kappa_{0}\in C^{\prime}$. Then for the solution $x_{0}$ of (5.9) one has

$\varphi(x_{0})+\langle\kappa_{0},\psi(x_{0})\rangle\leq\varphi(x_{0})<0,$

which is a clear contradiction. Note that the Slater condition (5.8) is not
required in this part.

Now suppose that (5.10) has no solution then show that (5.9) has a solution.
By a contradiction, suppose that (5.9) has no solution. Consider the set

$\Theta:=\\{(\gamma_{0},\gamma)\in\mathbb{R}\times
Y\;|\;\varphi(x)<\gamma_{0},\;\psi(x)\leq_{C}\gamma,\;\mbox{\rm for some
}x\in\Omega\\}.$

We first show that $\Theta$ is a nonempty like-convex set and
$(0,0)\notin\Theta$. Since (5.10) is not solvable, there exists
$x_{0}\in\Omega$ such that for all $\kappa\in C^{\prime}$ we have the strict
inequality

$\varphi(x_{0})+\langle\kappa,\psi(x_{0})\rangle<0.$

Fix $\overline{\kappa}\in C^{\prime}$, denote $\overline{\gamma}=\psi(x_{0})$
and $\overline{\gamma}_{0}=-\langle\overline{\kappa},\psi(x_{0})\rangle$. Then
$(\overline{\gamma}_{0},\overline{\gamma})\in\Theta$ and hence $\Theta$ is
nonempty. Since (5.9) has no solution, it follows that $(0,0)\notin\Theta$.
Furthermore, the like-convexity of $\Theta$ is implied by the convexity of
$\varphi$ and $C$-convexity of $\psi$.

We next show that $\mbox{\rm core}\,(\Theta)\neq\emptyset$. By the Slater
condition (5.8) there exists $\hat{x}\in\Omega$ such that
$\psi(\hat{x})\leq_{C}0$ and observe that

$\displaystyle\Theta\supset\\{(\gamma_{0},\gamma)\in\mathbb{R}\times Y\;|\;$
$\displaystyle\varphi(\hat{x})<\gamma_{0},\;\psi(\hat{x})\leq_{C}\gamma\\}$
$\displaystyle=\\{\gamma_{0}\in\mathbb{R}\;|\;\varphi(\hat{x})<\gamma_{0}\\}\times\\{\gamma\in
Y\;|\;\psi(\hat{x})\leq_{C}\gamma\\}.$

Note that as $\psi(\hat{x})\leq_{C}0$, we have $C\subset\\{\gamma\in
Y\;|\;\psi(\hat{x})\leq_{C}\gamma\\}$ and so

$\Theta\supset\\{\gamma_{0}\in\mathbb{R}\;|\;\varphi(\hat{x})<\gamma_{0}\\}\times
C.$

Now $\mbox{\rm
core}\,(\\{\gamma_{0}\in\mathbb{R}\;|\;\varphi(\hat{x})<\gamma_{0}\\})$ is
trivially non-empty due to being an open interval in $\mathbb{R}$. Therefore,
using the Slater condition

$\displaystyle\mbox{\rm
core}\,(\\{\gamma_{0}\in\mathbb{R}\;|\;\varphi(\hat{x})<\gamma_{0}\\}\times
C)$ $\displaystyle=\mbox{\rm
core}\,(\\{\gamma_{0}\in\mathbb{R}\;|\;\varphi(\hat{x})<\gamma_{0}\\})\times\mbox{\rm
core}\,(C)\neq\emptyset.$

Hence $\emptyset\neq\mbox{\rm
core}\,(\\{\gamma_{0}\in\mathbb{R}\;|\;\varphi(\hat{x})<\gamma_{0}\\}\times
C)\subset\mbox{\rm core}\,(\Theta)$.

Since $(0,0)\notin\Theta$ and $\mbox{\rm core}\,(\Theta)\neq\emptyset$,
Theorem 2.3 shows that the sets $\Theta$ and $\\{(0,0)\\}$ can be properly
separated. This gives us multipliers
$\widetilde{\lambda}_{0}\in\mathbb{R},\widetilde{\kappa}^{*}_{0}\in
Y^{\prime}$, not all zeros, such that

$\widetilde{\lambda}_{0}\gamma_{0}+\langle\widetilde{\kappa}_{0}^{*},\gamma\rangle\geq
0$ (5.11)

whenever $(\gamma_{0},\gamma)\in\Theta$. In addition, there exists
$(\widetilde{\gamma}_{0},\widetilde{\gamma})\in\Theta$ satisfying the strict
inequality

$\widetilde{\lambda}_{0}\widetilde{\gamma}_{0}+\langle\widetilde{\kappa}^{*}_{0},\widetilde{\gamma}\rangle>0.$
(5.12)

By passing to the limit, observe that the inequality (5.11) also holds for any
$(\gamma_{0},\gamma)\in\overline{\Theta}$. We will show that
$\widetilde{\gamma}_{0}>0$ and $\widetilde{\kappa}_{0}^{*}\in C^{\prime}$. By
the Slater condition (5.8), there exists $\widehat{x}\in\Omega$ such that
$\psi(\widehat{x})\leq_{C}0$. Fix any $\gamma_{0}>0$ such that
$\gamma_{0}>\varphi(\widehat{x}),$ one has $(\gamma_{0},0)\in\Theta$ and
(5.11) shows that $\widetilde{\lambda}_{0}\gamma_{0}\geq 0.$ If
$\widetilde{\lambda}_{0}<0,$ then $\gamma_{0}\leq 0,$ and hence $\widehat{x}$
is a solution of (5.9). This contradiction shows that
$\widetilde{\lambda}_{0}\geq 0.$ To show $\widetilde{\kappa}_{0}^{*}\in
C^{\prime}$, by a contradiction, suppose that
$\widetilde{\kappa}_{0}^{*}\notin C^{\prime}$. It means that there exists
$u_{0}\in C$, and hence $0\leq_{C}u_{0}$, such that
$\langle\widetilde{\kappa}_{0}^{*},u_{0}\rangle<0$. If
$\widetilde{\lambda}_{0}=0$, then we can see that
$(\gamma_{0},u_{0})\in\Theta$ while (5.11) fails. If
$\widetilde{\lambda}_{0}>0,$ set
$u_{1}=(1-\frac{\widetilde{\lambda}_{0}\gamma_{0}}{\langle\widetilde{\kappa}_{0}^{*},u_{0}\rangle})u_{0}$.
Since $\widetilde{\lambda}_{0}\gamma_{0}\geq 0$ and
$\langle\widetilde{\kappa}_{0}^{*},u_{0}\rangle<0$, one has $u_{1}\in C$ and
hence $\psi(\widehat{x})\leq_{C}0\leq_{C}u_{1}$. We can see that
$(\gamma_{0},u_{1})\in\Theta$ but (5.11) is not satisfied. This contradiction
verifies that $\widetilde{\lambda}_{0}\geq 0$ and
$\widetilde{\kappa}_{0}^{*}\in C^{\prime}$.

Since $\widetilde{\kappa}_{0}^{*}\in C^{\prime}$ and $\psi(\widehat{x})\in-C$,
one has

$\langle\widetilde{\kappa}_{0}^{*},\psi(\widehat{x})\rangle\leq
0\leq\langle\widetilde{\kappa}_{0}^{*},c\rangle\;\text{for all}\;c\in C.$
(5.13)

Fix any $x\in\Omega$ and see that

$(\varphi(x),\psi(x))\in\overline{\Theta}$

Thus,

$\widetilde{\lambda}_{0}\varphi(x)+\langle\widetilde{\kappa}_{0}^{*},\psi(x)\rangle\geq
0.$ (5.14)

We are going to show that $\widetilde{\lambda}_{0}>0$. By a contradiction,
suppose that $\widetilde{\lambda}_{0}=0$. Then, (5.14) shows that
$\langle\widetilde{\kappa}_{0}^{*},\psi(\widehat{x})\rangle\geq 0$ and hence
$\langle\widetilde{\kappa}_{0}^{*},\psi(\widehat{x})\rangle=\langle\widetilde{\kappa}_{0}^{*},-\psi(\widehat{x})\rangle=0$
followed from (5.13). Therefore, (5.13) can be written as

$\langle\widetilde{\kappa}_{0}^{*},-\psi(\widehat{x})\rangle=0\leq\langle\widetilde{\kappa}_{0}^{*},c\rangle\;\text{for
all}\;c\in C.$ (5.15)

Using (5.12) gives us that
$\langle\widetilde{\kappa}_{0}^{*},\widetilde{\gamma}\rangle>0$. Since $Y$ is
generating partially ordered by $C$ and $\widetilde{\gamma}\in Y$, [38,
Proposition 1.2] shows that there exists $\widetilde{c}\in C$ such that
$\widetilde{\gamma}\leq_{C}\widetilde{c}$. So,
$\widetilde{c}-\widetilde{\gamma}\in C$ and hence

$\langle\widetilde{\kappa}_{0}^{*},-\psi(\widehat{x})\rangle=0<\langle\widetilde{\kappa}_{0}^{*},\widetilde{\gamma}\rangle\leq\langle\widetilde{\kappa}_{0}^{*},\widetilde{c}\rangle.$
(5.16)

The inequalities (5.15) and (5.16) show that the sets $C$ and
$\\{-\psi(\widehat{x})\\}$ can be properly separated and hence
$\psi(\widehat{x})\notin-\mbox{\rm core}\,(C)$, which contradicts with the
Slater condition (5.8). Therefore, $\widetilde{\lambda}_{0}>0$. Dividing both
sides of (5.14) by $\widetilde{\lambda}_{0}$ shows that (5.10) has a solution.
This is a contradiction, with completes the proof. $\hfill\square$

###### Theorem 5.2

Let $X,Y$ be vector spaces. Let $x$ be a feasible solution of the primal
problem (5.3), and let $f$ be a feasible solution of its dual problem (5.6).
Then $\varphi(x)\geq L^{\prime}(f).$

Proof. The conclusion is implied directly from the definitions of the
problems. $\hfill\square$

Applying Lemma 5.1 and Theorem 5.2, we next state and prove the Lagrangian
strong duality in vector spaces without equality constraints.

###### Theorem 5.3

Consider the primal problem (5.3) and its dual problem (5.6). Suppose that the
Slater condition (5.8) is satisfied. Then the Lagrangian duality holds, i.e.,
$p=d$.

Proof. If $p=-\infty$, then $d=-\infty$ by Theorem 5.2. Thus, we can assume
that $p\in\mathbb{R}$. Then the system (5.9) can be extended to

$\varphi(x)-p<0,\psi(x)\in-C\;,x\in\Omega$

and it has no solution. Thus, the extension system of (5.10) has a solution,
i.e., there exist $h\in C^{\prime}$ such that

$\varphi(x)-p+\langle h,\psi(x)\rangle\geq 0\;\mbox{\rm for all }x\in\Omega.$

This implies that

$d=\inf_{x\in\Omega}\left\\{\varphi(x)+\langle h,\psi(x)\rangle\right\\}\geq
p.$

Combining the above inequality with Theorem 5.2 yields the result.
$\hfill\square$

## References

  * [1] M.S. Bazaraa, H.D. Sherali and C.M. Shetty, Nonlinear Programming: Theory and Algorithms, Wiley, New York, 2006
  * [2] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York, 2011.
  * [3] D.P. Bertsekas, A. Nedić and A.E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 2003.
  * [4] J.M. Borwein and A.S. Lewis, Partially finite convex programming, Part I: quasi-relative interiors and duality theory, Math. Program. 57, 15–48 (1992).
  * [5] J. M. Borwein, and A. S. Lewis, Partially finite convex programming, Part II: qExplicit lattice models , Math. Program. 57, 49–83 (1992).
  * [6] J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization, 2nd edition, Springer, New York, 2006.
  * [7] J. M. Borwein, and H. Wolkowicz, A simple constrain qualification in infinite dimensional programming, Math. Program. 35, 83–96 (1986).
  * [8] J. M. Borwein, and A. S. Lewis, Partially finite convex programming, Research report, Dalhousite University, Halifax, NS, 1987.
  * [9] R.I. Boţ, E.R. Csetnek and A. Modovan, Revisiting some duality theorems via the quasirelative interior in convex optimization, J. Optim. Theory Appl. 139, 67-84 (2008).
  * [10] R. I. Boţ, E. R. Csecnet and G. Wanka, Regularity condition via quasi-relative interior in convex programming, SIAM J. Optim. 19, 217–233 (2008).
  * [11] R. I. Boţ, Conjugate Duality in Convex Optimization, Springer-Verlag Berlin Heidelberg, 2010.
  * [12] R. I. Boţ and E. R. Csecnek, Regularity conditions via generalized interiority notions in convex optimization: New achievements and their relation to some classical statements, Optimization. 61, 35-65 (2012).
  * [13] D.V. Cuong, B.S. Mordukhovich and N.M. Nam, Extremal principle and convex calculus in vector spaces, Pure Appl. Funct. Anal. 6, 1139-1155 (2021).
  * [14] D.V. Cuong, B.S. Mordukhovich, N.M. Nam and A. Cartmell, Algebraic core and convex calculus without topology, Optimization. 71, 309-335 (2021).
  * [15] D.V. Cuong, B.S. Mordukhovich, N.M. Nam and G. Sandine, Fenchel-Rockafellar theorem in infinite dimensions via generalized relative interiors, Optimization. 72, 135-162 (2023).
  * [16] D.V. Cuong, B.S. Mordukhovich, N.M. Nam and G. Sandine, Generalized Differentiation and Duality in Infinite Dimensions under Polyhedral Convexity, Set-Valued Var. Anal. 30, 1503-1526 (2022).
  * [17] P. Daniele, S. Giuffré, G. Idone and A. Maugeri, Infinite dimensional duality and applications, Math. Ann. 339 , 221–239 (2007).
  * [18] P. Daniele, S. Giuffré, General infinite dimensional duality and applications to evolutionary network equilibrium problems, Optim. Lett. 1, 227-243 (2019).
  * [19] M. Durea, J. Dutta and C. Tammer, Lagrange multipliers and $\varepsilon$-Pareto solutions in vector optimization with nonsolid cones in Banach spaces, J. Optim. Theory Appl. 145, 196–211 (2010).
  * [20] F. Giannessi, Constrained Optimization and Image Space Analysis, I: Separation of Sets and Optimality Conditions, Springer, Berlin, 2005.
  * [21] M. S. Gowda and M. Teboulle, A comparison of constraint qualifications in infinite-dimensional convex programming, SIAM J. Control Optimization. 28, 925-935 (1990) .
  * [22] A. Grad, Quasi-relative interior-type constraint qualifications ensuring strong Lagrange duality for optimization problems with cone and affine constraints, J. Math. Anal. Appl. 351, 86-95 (2010).
  * [23] J. B. Hiriart-Urruty, $``\varepsilon$-subdifferential calculus”, in Convex Analysis and Optimization (eds. J. P. Aubin and R. B. Vinter) Research Notes in Mathematics. 57, 43-92 (Pitman, 1982).
  * [24] J. B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms, I: Fundamentals, Springer, Berlin, 1993.
  * [25] R. B. Holmes, Geometric Functional Analysis and Its Applications, Springer, New York, 1975.
  * [26] A. A. Khan, C. Tammer and C. Zălinescu, Set-Valued Optimization. An Introduction with Applications, Springer, Berlin, 2015.
  * [27] D.T. Luc, Theory of Vector Optimization, Springer, Berlin, 1989.
  * [28] W.A.J. Luxemburg and A.C. Zaanen, Riesz Spaces I, North-Holland, Amsterdam-London, 1971.
  * [29] V. Jeyakumar and H. Wolkowicz, Generalizations of Slater’s constraint qualiﬁcation for inﬁnite convex programs, Math. Program. 57, 85–101 (1992).
  * [30] B. S. Mordukhovich and N.M. Nam, Convex Analysis and Bayond, Volume I: Basic Theory, Springer, Berlin, 2022.
  * [31] B. S. Mordukhovich, Variational Analysis and Applications, Springer, Cham, Switzerland, 2018.
  * [32] B. S. Mordukhovich, N. M. Nam, B. Rector and T. Tran, Variational geometric approach to generalized differential and conjugate calculus in convex analysis, Set-Valued Var. Anal. 25, 731–755 (2017).
  * [33] K.F. Ng and W. Song, Fenchel duality in infnite-dimensional setting and its applications, Nonlinear Anal., 55, 845–858 (2003).
  * [34] R. T. Rockafellar and R. J-B. Wets, Variational Analysis, Springer, Berlin, 1998.
  * [35] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.
  * [36] C. Zălinescu, A comparision of constraint qualifications in infinite-dimensional convex programing revisited, J. Austral. Math. Soc. Sen B 40, 353–378 (1999).
  * [37] C. Zălinescu, Convex Analysis in General Vector Spaces, World Scientific, Singapore, 2002.
  * [38] Y.C. Wong and K.F. Ng, Partially Ordered Topological Vector Spaces, Oxford, 1973.


# Target Identification and Bayesian Model Averaging with Probabilistic
Hierarchical Factor Probabilities

Bill Basener  Professor of Data Science
University of Virginia, School of Data Science
Charlottesville, VA
<EMAIL_ADDRESS>
###### Abstract

Target detection in hyperspectral imagery is the process of locating pixels
from an image which are likely to contain target, typically done by comparing
one or more spectra for the desired target material to each pixel in the
image. Target identification is the process of target detection incorporating
an additional process to identify more specifically the material that is
present in each pixel that scored high in detection. Detection is generally a
2-class problem of target vs. background, and identification is a many class
problem including target, background, and additional know materials. The
identification process we present is probabilistic and hierarchical which
provides transparency to the process and produces trustworthy output. This
process of target identification is central to the NINJA near real time
hyperspectral image processing software, which is currently being incorporated
for automated processing of images on board a UAS using GPUs.

In this paper we show that target identification has a much lower false alarm
rate than detection alone, and provide a detailed explanation of a robust
identification method using probabilistic hierarchical classification that
handles the vague categories of materials that depend on users which are
different than the specific physical categories of chemical constituents. It
should be no surprise that target identification outperforms target detection
because the identification process can include spectra for correlated
materials that can cause false alarms in detection, directly eliminating false
alarms if suitable spectra and methods are used.

Identification is often done by comparing mixtures of materials including the
target spectra to mixtures of materials that do not include the target
spectra, possibly with other steps. (band combinations, feature checking,
background removal, etc.) Standard linear regression does not handle these
problems well because the number of regressors (identification spectra) is
greater than the number of feature variables (bands), and there are multiple
correlated spectra. Our proposed method handles these challenges efficiently
and provides additional important practical information in the form of
hierarchical probabilities computed from Bayesian model averaging

###### Index Terms:

Machine Learning, Bayesian Model Averaging, Regression, Unmixing, Target
Identification, UAS

##  I Introduction

Target detection is the process of determining pixels in an image that contain
evidence of a target spectrum. Typically, this is done as a 2 class problem
with a target class and a non-target class. A common detection algorithm is
the ACE (Adaptive Cosine Estimator) which involves whitening each image pixel
and target spectrum and then computing the correlation between the whitened
pixel and target (equivalently, angle between these whitened spectra)
described in [1]. Identification is a more complex process, usually done using
a form of unmixing, or regression, to determine the mixture of material
spectra present in a pixel. This identification via unmixing is done by using
linear regression to determine the best mixture of known material spectra
(called a model) that approximates the observed pixel spectrum.

This target identification process was introduced in automated processing in
[2, 3], and has become an integral element of automated processing for example
on board a UAS such as the GeoReplay-Lite and HyPert [4] software. A major
challenge in the identification by regression process is that there the
libraries used can be extremely large, as the goal is to identify combination
the material(s) present in the pixel out of thousands of known materials. With
many more regressor variables (spectra) than features (bands), this is an
underdetermined regression problem. One method proposed to deal with this is
merging groups of similar spectra using a hierarchical clustering [5, 6], and
find the best unmxing model using spectral cluster means. An alternative is to
compute probabilities for many models which leads to probabilities for
individual spectra or classes of spectra [7], a process called model averaging
which is the method we focus on in this paper.

Bayesian model averaging is an important method for averaging results for a
variety of models with variation. Used in multivariate linear regression, it
provides a robust form of model selection which captures the uncertainty about
model selection, providing a regularized regression model that is the average
of the top models rather than picking a single best model along with a
probability of inclusion for each input variable. In this setting, each model
is a least squares linear regression model and the models differ by the choice
of subset of input variables, although of course different forms of variation
in models could be used.

The fundamentals of Bayeisan model averaging are straightforward. For a
multivariate linear regression problem, let $M_{i}$ denote a model; that is a
subset of the input variable used for linear regression. Let $BIC_{i}$ be the
Bayesian Information Criterion associated with this regression model. Then the
likelihood for this model is approximately

$l(M_{i})=e^{-BIC_{i}/2}$ (1)

From Bayes Theorem the posterior probability for this model is then

$P(M_{i})=\frac{l(M_{i})Pr(M_{i})}{\sum_{k}l(M_{k})}.$ (2)

If our input variables are $X_{1},...,X_{n}$ then the probability that $X_{k}$
should be included is equal to the sum of probabilities for all models that
contain $X_{k}$,

$P(X_{k})=\sum_{M|X_{k}\in M}P(M).$ (3)

Note that this sum is over all models $M$ which contain $X_{k}$ as an input
variable. This is the Bayesian posterior probability for including $X_{k}$ in
the model; the probability that the coefficient for $X_{k}$ is nonzero given
the data. The model averaged coefficient for $X_{k}$ is then

$\beta^{\textrm{avg}}_{k}=\sum_{M|X_{k}\in M}P(M)\beta^{M}_{k},$ (4)

where $\beta^{M}_{k}$ is the coefficient of $X_{k}$ in model $M$. These model
averaged coefficients are weighted by model probabilities, and this process is
a form of regularization creating the averaged model using these coefficients.

If the number of input variables is significant, it can (often is)
computationally impossible or infeasible to compute these probabilities for
every possible model. The two main approaches to sampling are a Markov Chain
Monte Carlo model composition ($MC^{3}$) approach using MCMC random sampling
and an Occam’s window approach where models are iteratively constructed and
rejected when their likelihood is low relatively to the best previous model
(details in [8]). Implementations are available in R [9].

In this paper, we address the issue where multiple input variables represent
the same underlying factor or cause. If multiple variables are measuring the
same underlying factor, their probabilities can compete giving results that
are misleading or require manual interpretation which is not always possible.
It is often important to use multiple variables measuring the same underlying
factor/cause, and the problem cannot generally be solved by choosing just one
representative. We give a first example in a classic context of crime data,
and then focus on regression models for the important application of
identifying materials our of mixtures in hyperspectral data.

We will refer to input variables that represent the same underlying factor
cause
information as overlapping variables. The definition is subjective, dependent
on the goals of the regression analysis, an issue we will deal with
particularly in the spectral data.

##  II Overlapping Variables in Crime Data

A classic paper in the area is Bayesian Model Averaging for Linear Regression
Models [8]. This paper used a classic (often criticized) dataset and model
that historically influenced the question of whether crime is deviant behavior
linked to the offender’s psychological social, and family circumstances, or
whether criminal activity is determined by rational choices based on costs and
benefits of alternative opportunities. This dataset includes 15 demographic
factors from each state in the U.S. along with the crime rate for that state
in 1960.

The posterior probability for inclusion from [8] for each input variable in
the Erlich crime data is shown in Table I.

TABLE I: Posterior Probability of Inclusion for input predictor variables in crime data for 1960, expressed as a percentage. (UR = Unemployment Rate, PR = Participation Rate) Predictor | Occam’s | $MC^{3}$
---|---|---
| Window |
% of males age $14-24$ | 73 | 79
South state indicator | 2 | 17
Mean years schooling | 99 | 98
Police expenditure, 1960 | 64 | 72
Police expenditure, 1959 | 36 | 50
Labor Force PR | 0 | 6
Males per 1,000 females | 0 | 7
State population | 12 | 23
nonwhites per 1,000 | 53 | 62
UR urban males $14-24$ | 0 | 11
UR urban males $35-39$ | 43 | 45
Wealth | 1 | 30
Income Inequality | 100 | 100
Prob. of Imprisonment | 83 | 83
Avg time served in prison | 0 | 22

Our focus on situations where multiple input variables represent the same
underlying factor or cause is illustrated in the police expenditure in 1959
and in 1960 variables. Observe that the sum of probabilities for these two
separate variables is one, and it seems these are two distinct variables
capturing the same underly factor or information. Raftery et al [8] discuss
the problem as follows.

> The model averaging results for the predictors for police expenditures lead
> to an interesting interpretation. Police expenditure was measured in two
> successive years, adn the measures are highly correlated ($r=.993$). The
> data show clearly that the 1960 crime rate is associated with police
> expenditures, and that only one of the two measures ($X_{4}$ and $X_{5}$) is
> needed, but the do not say which measure should be used. Each model in
> Occam’s window contains one predictor or the other, but not both. For both
> Occam’s window and $MC^{3}$ $Pr[(\beta_{4}\neq 0)\cup(\beta_{5}\neq
> 0)|D]=1$, so the data provide very strong evidence with police expenditure.

##  III Overlapping Variables in Hyperspectral Data

A hyperspectral image is a digital image in which each pixel has not just the
usual three (red, green, blue) colors, but many, usually more than one
hundred, bands. Each band is a measurement of light across a small range of
wavelengths. Some of our data will come from the NASA AVIRIS sensor whch has
480 bands ranging from 380nm to 2510nm, and each band collects light from a
range of about 5nm. The data can be ‘binned’ combining neighboring bands to
reduce noise and some bands are removed where the atmosphere (particularly
water) blocks most or all of the light, and our AVIRIS data as a resulting 168
bands. The data is converted to reflectance units, meaning that the value for
each band in each pixel is the percent of light at the wavelengths for that
band that were reflected off the ground at the location of the pixel. The
reflectance varies with wavelength due to interactions of the photons with
molecular constituents and bonds in the material, and thus the reflectance
spectrum provides information about the material present. Spectra for five
different polymer materials are shown in Figre 1.

Figure 1: Spectra for five different polymer materials.

Each pixel in a hyperspectral image collected from an aircraft is the
measurement of light from a relatively large region on the ground - typically
ranging from a 2m$\times$2m up to 10m$\times$10m depending on the altitude of
the sensor. Thus, there are usually multiple materials present in the ground
region and the measured spectrum is a mixture of the spectra for those
materials. This phenomenology results in what is called linear mixing; if
$x_{1},...,x_{n}$ are the spectra (vectors whose length is the number of
bands) for the materials present on the ground, the measured pixel spectrum
will be

$p=\sum_{i}a_{i}x_{i}+\textrm{err}$ (5)

where $a_{i}$ represents the abundance of the material in the pixel;
physically the fraction of light reflecting off that material out off all the
light that reflected off the ground region for the pixel. This is known as the
linear mixing model. There are factors that can create nonlinear mixing of
spectra, for example translucent materials like plant leaves resulting in
light passing through a leaf and reflecting off the ground, geometry of
objects where light reflects off two or more materials, or intimate mixtures
powder coatings), for example. However, the linear mixture model is usually a
good practical approximation.

The other phenomenology that we care specifically about is that of variation
of spectra within a material class. This variation depends on what is being
considered a class; all of the materials whose spectra are shown in 1 could be
considered part of a ’polymer’ class, but they are clearly spectrally
distinct. In figure 2, we show multiple spectra from HDPE (high-density
polyethylene) and can observe a consistency in the features.

Figure 2: Spectra for five different polymer materials.

The general material identification problem in hyperspectral imaging can be
posed as follows. We have a pixel from an image and want to know what
material(s) is/are present. We also have a library of spectra of known
materials. The library may have say 1,000 spectra in it. The observed pixel
spectrum is assumed to be a linear mixture of the materials from our library,
making this a model selection problem. We can simplify the problem by assuming
that the mixture contains only a few, say four, materials from the library in
quantities large enough to be observable, but the problem still has clear
challenges.

##  IV methods

A great simplifying component of the identification problem is that we usually
do not need the exact set of all materials present in the pixel. Usually, the
question of greatest interest is is there material from class ‘X’ present in
the pixel. The class of interest may the class of all polymers; for example
searching for lost hikers in a national forest. The class may be a specific
polymer, for example looking for PETE (Polyethylene terephthalate) because
this material is commonly used for home greenhouses. The problem may be less
well-defined: is there a fabric in the pixel, or is there a vehicle present?

Our method for solving this problem is to compute the probability for the
class of interest by summing the probabilities for every model that contains a
spectrum from that class. Furthermore, if we label all our spectra into
classes, and then select spectra in each class into subclasses, and so on,
summing probabilities gives us a probability for every class and subclass,
which we call hierarchical probabilistic classification. Typically, not all
spectra are of interest. If the question is “Is there a polymer present, and
if so what are the probabilities for each different polymer type” then we just
need class and subclass labels for the polymer spectra. If the question is “Is
there a military-related object in the pixel, then is it a fabric or vehicle,
then depending on that get probabilities for further subclassses” then we need
class-subclass-subsubclass labels for all of the military related material
spectra.

For a simple example, suppose that we have two spectra, Spectrum 1 and
Spectrum 2. Suppose also that we have a library with 8 spectra: two nylon
spectra labeled $N1$ and $N2$, two polyester spectra labeled $P1$ and $P2$,
two cotton spectra labeled $C1$ and $C2$, and two vegetation spectra labeled
$V1$ and $V2$. Suppose we compute the probabilities for each spectrum and get
the results shown in Table II.

TABLE II: Individual probabilities for a toy example. | Fabric | Vegetation
---|---|---
| Polymer | Cotton |
| Nylon | Polyester |  |
| N1 | N2 | P1 | P2 | C1 | C2 | V1 | V2
Spec 1 | .4 | .3 | .2 | .1 | 0 | 0 | 0 | 0
Spec 2 | 0 | 0 | 0 | 0 | .1 | 0 | .4 | .5

In Table II, we organized the column headers to show the material name for
each pair of spectra, and higher level groups such as polymer, which includes
the nylon and polyester, and fabrics, which includes the polymer and cotton
fabrics.

The purpose of using the probabilities is that for two mutually exclusive
events, the probability that one of the events will occur is the sum of the
individual probabilities. Using this, from this table can compute that the
probability that Spectrum 1 is a nylon is $0.4+0.3=0.7$. The probability that
Spectrum 1 is polyester is $0.2+0.1=0.3$. We can compute probabilities for
higher level classes: the probability that Spectra 1 is a polymer fabric (eg.
nylon or polyester) is $1$, and the probability that Spectrum 1 is a fabric is
$1$, and the probability that Spectrum 1 is vegetation is $0$. These
probabilities can be organized in a tree diagram as shown in Figures 4 and 4.
Assuming that the spectra in the library include all possible materials for
these two spectra, we could be confident that Spectrum 1 is a polymer fabric,
and more likely a nylon than a polyester. We could be confident that Spectrum
2 is vegetation.

[.1

Library .0.0

Vegetation [.1.0

Fabric 0.0

Cotton [.1.0

Polymer Polyester

0.3 Nylon

0.7 ] !40pt ] !40pt ]

Figure 3: The material identification tree for Spectrum 1 for the example
data. At each branch in the tree the possible subclasses are listed with
probabilities ordered from least likely to most likely.

[.1

Library 0.1

Fabric [.0.9

Vegetation ] !40pt ]

Figure 4: The material identification tree for Spectrum 2 for the example
data. At each branch in the tree the possible subclasses are listed with
probabilities ordered from least likely to most likely.

##  V results

In this section we provide results from summing probabilities for classes and
subclasses. We first start with a group of pixels from an AVIRIS image and
then some targets from the Forest Radiance dataset [10].

In Figure 5, we show a detection from an AVIRIS image that was over an area
west of Washington DC. The upper left image is a small ‘chip’ from the image
centered on the location, shown as an visual color image by combining the RGB
bands from the hyperspectral image. This location was selected initially
selected from the larger image because it scored high with a target detection
algorithm [11, 1]. Below the RGB chip is a grayscale image with the specific
pixels used indicated in red. (There is a group of pixels that scored high,
and we take the average of these spectra as our pixel spectrum for the
object.) The large visual image (right, top) is a high resolution image over
this location from Google Earth. In this image, we can see that there are hay
bales wrapped in an LDPE-based material, stacked in lines. These are likely
the source of the detection. Below these visual images are spectra from this
location along with spectra that are known to be from HDPE and LDPE materials
for comparison.

Figure 5: A group so of pixels from the AVIRIS image.

In the plots of spectra in Figure 5, the left-hand plot shows the pixel
spectrum along with the HDPE and LDPE for comparison. A standard way to try to
confirm materials is to visually examine the spectra and look for features in
the pixel that match the know library spectra. In this plot, it looks like
there are some features (small dips or sharp rises) present in this pixel at
wavelength locations of the library spectra, but there is not an overall
precise match. This is because the pixel spectrum is a mixture of the material
from the wrap as well as other nearby materials, for example the grass, trees,
and soil. In the right-hand plot, these same library HDPE and LDPE spectra are
shown, but with these is a plot of the background-removed pixel. This pixel is
computed by selecting a number background spectra from the image near but not
on the detected object of interest $s_{1},s_{2},...,s_{n}$, computing a linear
regression using these background spectra and the spectrum that caused the
detection (i.e. the target spectrum),

$p=a_{t}s_{t}+\sum_{i}a_{i}s_{i}$ (6)

where $p$ is the pixel spectrum, $s_{t}$ is the target, and the $a$ are scaler
coefficients. The background-removed spectrum, denoted by Bkg-R, is then

$\textrm{Bkg-R}=p-\sum_{i}a_{i}s_{i}.$ (7)

This background removed spectrum is described in more detail in [2]. We can
now see that the background removed pixel spectrum is a good match to both of
the polyethylene spectra, but there is a precise match with LDPE among the
features in the 2.0-2.5 micrometer range. (The match depends on the wavelength
location where the dips and rises occur, not particularly with overall value.)

The probabilities of inclusion in the model for spectra from a library of
about 200 materials, about 50 of which are polymers, are shown in Table III.
These were computed from Bayesian model averaging using an Occam’s razor
search strategy limiting up to 4 elements per model. It is clear from this
table that the LDPE spectra get the highest probabilities, and that the
probabilities are spread across these spectra with no one spectrum getting a
high probability. In our terminology, these are overlapping input variables.

TABLE III: Probabilities for polymers computed from the AVIRIS pixels. Material Spectrum | Probability
---|---
LDPE | 0.21
LDPE - foam packaging 9 | 0.21
LDPE - foam packaging 6 | 0.17
LDPE - foam packaging 3 | 0.12
LDPE - foam packaging 2 | 0.11
LDPE - foam packaging 8 | 0.1
LDPE - foam packaging 5 | 0.09
LDPE - foam packaging 4 | 0.09
LDPE - foam packaging 7 | 0.07
HDPE | 0.07
HDPE - white bottle 10 | 0.06
HDPE - white bottle 1 | 0.05
HDPE - white bottle 3 | 0.05
HDPE - white bottle 9 | 0.05
HDPE - white bottle 2 | 0.05
PVC - soft inflatable (white) 2 | 0
PVC | 0
PVC - soft extnesion cord 7 | 0
PVC - soft extnesion cord 3 | 0
PVC - soft extnesion cord 1 | 0

To compute the probabilities for the polymer class, we add the probabilities
for all models that included a polymer spectrum, which is 1.0 (there were no
models constructed without polymers that passed Occam’s window). To compute
probability of PVC vs probability of polyethylene, we added the probabilities
of all models that included PVC and all models that included polyethylene,
resulting in 0.00 and 1.00 respectively. Continuing, we arrive with a
probability of 0.83 for LDPE and 0.19 for HDPE. This hierarchal probabilistic
identification is depicted as a tree in Figure 6.

[.1
Polymer 0.0
PVC [.1.00
Polyethylene [0.19
HDPE 0.83
LDPE ] ] ]

Figure 6: The class identification tree the pixels detected in the AVIRIS
image shown in Figure 5. At each branch in the tree the possible subclasses
are listed with probabilities ordered from least likely to most likely.

The next dataset we used is the Forest Radiance image run09m99 acquired in
1995 as part of the HYperspectral Data Imagery Collection Experiment (HYDICE)
sensor [10, 12], shown in Figure 7. The image was converted to reflectance
using the empirical line method computed using the in scene calibration
panels. The image was acquired at approximately 20,000 ft above ground level
with a spatial GSD of 3 meters. Atmospheric and noisy bands were removed
leaving 159 bands. Unlike our AVIRIS example, this image was part of a
collection with a number of known target materials placed on the ground with
multiple spectra collected for each target.

A number of target vehicles and fabric panels were placed in the image as part
of the experiment. As part of the experiment 577 spectra were collected off of
the targets and background materials. We will refer to the spectral library
consisting of these spectra as the canonical forest radiance library. The
vehicles are designated in 3 classes, V, VF, or DV. The V class includes
vehicles V1 through V7, the VF class includes vehicles VF1 through VF6, and
the DV class includes vehicles DV1 through DV4. Out of the V vehicles, V1-V3
are the same vehicle type and spectra in the library treat this group as a
single material class. The same is true for vehicles VF1-VF3. The fabric
target materials include F1 through F14, T1, T2, and fabrics with other
designations. Fabric materials F1-F14, T1, and T2 are emplaced in the image as
three square panels each of sizes 1m, 2m, and 3m, arranged in rows. The
fabrics can further be subdivided by material type: F3 is a green cotton
material, T1 and T2 and others are green nylon. The specific objects selected
for testing in this paper are the vehicles V3 and VF3 and fabrics F3, T1, and
T2, shown in Figure 7.

Figure 7: The image forest radiance run09m99 with the selected targets.

At the highest level, one would like to determine if an object is a fabric or
a vehicle. If the determination can be made at that level, we want to
determine if a more specific class be designated within vehicle and fabric
subclasses.

We first consider the vehicle V3. The tree diagram shown in Figure 9. At the
highest level, we assume with probability 1 that the spectra for the selected
object is in the library. This is a basic assumption intrinsic to model
averaging. At the next level, it is determined that the probability that the
target is a fabric is 0.0150 while the probability that the target is a
vehicle is 0.9850. Continuing down the tree, we see that there is
approximately a 95% probability that this target is in the class V1-V3, which
is the most specific class assignment that can be made with this library.

[.1

Library 0.0150

Fabric [.0.9850

Vehicle 0.0000

DV 0.0018

VF [.0.9834

V notV1-V3

0.0420 V1-V3

0.9580 !40pt ] !40pt ] !40pt ]

Figure 8: The class identification tree for V3. At each branch in the tree the
possible subclasses are listed with probabilities ordered from least likely to
most likely.

[.1

Library 0.1217

Fabric [.0.8891

Vehicle 0.0000

V 0.3175

DV [.0.5716

VF notVF1-VF3

0.1687 VF1-VF3

0.4029 ] !40pt ] !40pt ]

Figure 9: The class identification tree for VF3. At each branch in the tree
the possible subclasses are listed with probabilities ordered from least
likely to most likely.

The class identification tree for vehicle VF3 is shown in Figure 9. Observe
that for VF3, it was possible to determine with confidence that this object is
a vehicle, and either a DF or VF class vehicle. After that, the designation
becomes less certain. We can tell that this object is about twice as likely to
be a VF than DV, and if it is a VF then it is twice as likely to be a VF1-VF3
than one of the other vehicles. But this designations within the vehicle
classes cannot be made with as much certainty as was possible with V3.

The class identification tree for fabrics T1 and T2 are shown in Figures 11
and 11. Observe that for both targets, we can be definitively certain that the
fabrics is either T1 or T2. However, with the T1 target the information is
insufficient to determine which of the T-fabrics is correct. But with the T2
fabric target, we can be confident that the fabric is T2.

[.1

Library 0.0000

Vehicle [.1.0000

Fabric 0.0000

Cotton [.1.0000

Nylon 0.0344

notT1-2 [.0.96556

T1-2 0.4759

T2 0.4898

T1 ] !40pt ] !40pt ] !40pt ]

Figure 10: The class identification tree for T1. At each branch in the tree
the possible subclasses are listed with probabilities ordered from least
likely to most likely.

[.1

Library 0.0000

Vehicle [.1.0000

Fabric 0.0000

Cotton [.1.0000

Nylon 0.0268

notT1-2 [.0.9732

T1-2 0.0155

T1 0.9576

T2 ] !40pt ] !40pt ] !40pt ]

Figure 11: The class identification tree for T2. At each branch in the tree
the possible subclasses are listed with probabilities ordered from least
likely to most likely.

The class identification tree for the cotton fabric is shown in Figure 12. The
final branching only has one branch because F3 is the only known cotton fabric
in the library.

[.1
Library 0.0125
Vehicle [.0.9836
Fabric 0.0014
Nylon [.0.9812
Cotton [.0.9812
F3 ] ] ] ]

Figure 12: The class identification tree for F3, a cotton fabric. At each
branch in the tree the possible subclasses are listed with probabilities
ordered from least likely to most likely.

##  VI conclusions

In this paper we present a method for computing hierarchical probabilistic
classification based on computed probabilities for classes of input regressor
variables that represent the same underlying cause or factor in a linear
regression problem. We started by discussing a classical example where police
expenditure for two different years is considered in Bayesian model averaging,
resulting in the probabilities being distributed over the two years, and
leading to manual analysis to understand the general relationship between
police expenditure and crime. We define the term overlapping variables to
describe variables that capture the same underlying information, while
recognizing that this term is subjective depending on application.

We then provided example computations using hyperspectral imagery. In this
data, the regression problem is determining the linear mixture with abundances
of materials present in the pixel of a hyperpsectral image. However, a given
material has multiple different spectra with some variation that might be
observed. Moreover, we might be interested in knowing if any of a class of
similar materials is present. Any two spectra that are measurements for the
same material, or for the same class of materials, would be considered
overlapping variables.

In our example from the AVIRIS hyperspectral image, we compute the probability
that a polymer of any type is present, then the probability between PVC and
polyethylene, and then final between high density polyethylene (HDPE) vs low
density polyethylene (LDPE). The computation indicates that the material is a
polyethylene with probability 1, and more likely LDPE (p=0.83) rather than
HDPE (p=0.19). We then produce examples using imagery from the HYDICE sensor
in the Forest Radiance dataset.

This method provides certainly more information than a pick-a-winner method
for model selection that simply chooses a single best model. Pick-a-winner
approaches ignore the uncertainty present with multiple good models. Bayesian
model averaging estimates the uncertainty among models in the probabilities
for individual regressor variable, but as we observed that overlapping
variables can create a situation when the individual variable probabilities
can underestimate the probability for a single underlying factor/cause that is
represented by multiple different variables. Our method computes probabilities
for underlying factors/causes, and can do so simultaneously at multiple levels
of class resolution (classes, subclasses, etc.). We display the results in
trees with class labels and probabilities at each branch point.

## References

  * [1] William F Basener, Brian Allen, and Kristen Bretney,  “Geometry of statistical target detection,”  Journal of Applied Remote Sensing, vol. 11, no. 1, pp. 015012, 2017\.
  * [2] W. Basener,  “An automated method for identification and ranking of hyperspectral target detections,”  2011, vol. 8048, 80480D of Proc. SPIE.
  * [3] William Basener,  “Methods for object-based identification, sorting and ranking of target detections and apparatuses thereof,” U.S. Patent US20120070033A1, March. 2012.
  * [4] Steven Adler-Golden,  “Fast data processing for hyperspectral sensors on small platforms,”  .
  * [5] Yuri Owechko,  “Hyperspectral demixing using foveated compressive projections,” U.S. Patent US10094713B2, Oct. 2016.
  * [6] Cooper Loughlin, Michael Pieper, Dimitris Manolakis, Randall Bostick, Andrew Weisner, and Thomas Cooley,  “Efficient hyperspectral target detection and identification with large spectral libraries,”  IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 13, pp. 6019–6028, 2020.
  * [7] William F. Basener,  “Ensemble learning and model averaging for material identification in hyperspectral imagery,”  in Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery XXIII, Miguel Velez-Reyes and David W. Messinger, Eds. International Society for Optics and Photonics, 2017, vol. 10198, pp. 452 – 459, SPIE.
  * [8] D. Madigan A. E. Raftery and J. A. Hoeting,  “Bayesian model averaging for linear regression models,”  Journal of the American Statistical Association, vol. 92, pp. 179–191, 1997.
  * [9] Shahram Amini and Christopher F. Parmeter,  “Bayesian model averaging in r,”  Journal of Economic and Social Measurement, vol. 36, no. 4, pp. 253–287, 2011.
  * [10] S. Bergman R. Olsen and R. Resmini,  “Target detection in a forest environment using spectral imagery,”  1997, vol. 3118, 46 of Proc. SPIE.
  * [11] C. Siracusa D. Manolakis and G. Shaw,  “Hyperspectral subpixel target detection using the linear mixing model,”  Geoscience and Remote Sensing, IEEE Transactions on, vol. 39, no. 7, pp. 1392 –1409, jul 2001.
  * [12] A. Mariano and J. Grossmann,  “Hyperspectral material identification on radiance data using single-atmosphere or multiple-atmosphere modelingn,”  J. Appl. Remote Sens, Nov.