∎

11institutetext: Nguyen Ngoc Luan 22institutetext: Department of Mathematics
and Informatics, Hanoi National University of Education
136 Xuan Thuy, Hanoi, Vietnam
<EMAIL_ADDRESS>33institutetext: Do Sang Kim 44institutetext: Department of
Applied Mathematics, Pukyong National University
Busan, Korea
<EMAIL_ADDRESS>55institutetext: Nguyen Dong Yen 66institutetext: Institute
of Mathematics, Vietnam Academy of Science and Technology
18 Hoang Quoc Viet, Hanoi 10307, Vietnam
<EMAIL_ADDRESS>
# Two Optimal Value Functions in Parametric Conic Linear
Programming111Dedicated to Professor Franco Giannessi on the occasion of his
85th birthday.

Nguyen Ngoc Luan  Do Sang Kim  Nguyen Dong Yen

(Received: date / Accepted: date)

###### Abstract

We consider the conic linear program given by a closed convex cone in an
Euclidean space and a matrix, where vector on the right-hand-side of the
constraint system and the vector defining the objective function are subject
to change. Using the strict feasibility condition, we prove the locally
Lipschitz continuity and obtain some differentiability properties of the
optimal value function of the problem under right-hand-side perturbations. For
the optimal value function under linear perturbations of the objective
function, similar differentiability properties are obtained under the
assumption saying that both primal problem and dual problem are strictly
feasible.

###### Keywords:

Conic linear programming Primal problem Dual problem Optimal value function
Lipschitz continuity Differentiability properties Increment estimates

###### MSC:

49K40 90C31 90C25 90C30

##  1 Introduction

If the feasible region or the objective function of a mathematical programming
problem depends on a parameter, then the optimal value of the problem is a
function of the parameter. In general, the optimal value function is a fairly
complicated function. Continuity properties (resp., differentiability
properties) of the optimal value function in parametric mathematical
programming are usually classified as results on stability (resp., on
differential stability) of optimization problems. Many results in this
direction can be found in the books (Bonnans_Shapiro_2000, , Chapters 4,5),
(Mordukhovich_Book_I, , Chapter 4) and (Mordukhovich_Book_II, , Chapter 5),
the papers [4-13], the dissertation An_Thesis , and the references therein.

In 2001, Gauvin Gauvin_2001  investigated the sensitivity of the optimal value
of a parametric linear programming problem. He gave separated formulas for the
increment of the optimal value with respect to perturbations of the right-
hand-side vector in the constraint system, the cost vector, and the
coefficients of the matrix defining the linear constraint system. In 2016,
Thieu Thieu_2016  established some lower and upper bounds for the increment of
the optimal value of a parametric linear program, where both objective vector
and right-hand-side vector in the constraint system are subject to
perturbations. He showed that the appearance of an extra second-order term in
these estimates is a must.

Conic linear programming is a natural extension of linear programming. In a
linear program, a feasible point usually has nonnegative components, i.e., it
belongs to the nonnegative orthant of an Euclidean space. In addition, the
constraints are written as linear inequalities. Meanwhile, in a conic linear
program, the constraint is written as an inequality with the ordering cone
being a closed convex cone in an Euclidean space. Conic linear programs can be
used in many applications that cannot be simulated by linear programs (see,
e.g., (BN_2001, , Section 2.2) and (Luenberger_Ye_2016, , Chapter 6)). This is
the reason why these special convex optimization problems have attracted much
attention from researchers (see Ben-Tal and Nemirovski BN_2001 , Bonnans and
Shapiro Bonnans_Shapiro_2000 , Luenberger and Ye Luenberger_Ye_2016 , Chuong
and Jeyakumar Chuong_Jeyakumar_2017 , and the references therein).

It is of interest to know whether results similar to those of Gauvin
Gauvin_2001  and Thieu Thieu_2016  can be obtained for conic linear programs,
or not. The aim of this paper is to show that the results of Gauvin_2001
admit certain generalizations in conic linear programming, and some
differentiability properties, as well as a locally Lipschitz continuity
property, can be established for the two related optimal value functions. The
obtained results are analyzed via four concrete examples which show that the
optimal value functions in a conic linear program are more complicated than
that of the corresponding optimal value functions in linear programming.

The remaining part of our paper has six sections. Section 2 contains some
definitions, a strong duality theorem in conic linear programming, and a
lemma. Section 3 is devoted to the locally Lipschitz continuity property of
the optimal value function of a conic linear program under right-hand-side
perturbations. Differentiability properties of this optimal value function are
studied in Section 4. Some increment formulas for the function are established
in Section 5. The optimal value function of a conic linear program under
linear perturbations of the objective function is studied in Section 6. The
final section presents some concluding remarks.

##  2 Preliminaries

One says that a nonempty subset $K$ of the Euclidean space $\mathbb{R}^{m}$ is
a cone if $tK\subset K$ for all $t\geq 0$. The (positive) dual cone $K^{*}$ of
a cone $K\subset\mathbb{R}^{m}$ is given by
$K^{*}=\\{v\in\mathbb{R}^{m}\;:\;v^{T}y\geq 0\quad\forall y\in K\\}$, where T
denotes the matrix transposition. Herein, vectors of Euclidean spaces are
written as rows of real numbers in the text, but they are interpreted as
columns of real numbers in matrix calculations. The closed ball centered at
$a\in\mathbb{R}^{m}$ with radius $\varepsilon>0$ is denoted by
$\bar{B}(a,\varepsilon)$. By $\overline{\mathbb{R}}$ we denote the set
$\mathbb{R}\cup\\{\pm\infty\\}$ of extended real values.

Let $f:\mathbb{R}^{k}\to\overline{\mathbb{R}}$ be a proper convex function and
$\bar{x}\in\mathbb{R}^{k}$ be such that $f(\bar{x})$ is finite. According to
Theorem 23.1 in Rockafellar_1970 , the directional derivative

$f^{\prime}(\bar{x};h):=\displaystyle\lim\limits_{t\to
0^{+}}\frac{f(\bar{x}+th)-f(\bar{x})}{t}$

of $f$ at $\bar{x}$ w.r.t. a direction $h\in\mathbb{R}^{k}$, always exists (it
can take values $-\infty$ or $+\infty$), and one has
$f^{\prime}(\bar{x};h)=\inf\limits_{t>0}\dfrac{f(\bar{x}+th)-f(\bar{x})}{t}.$
The subdifferential of $f$ at $\bar{x}$ is defined by $\partial
f(\bar{x})=\big{\\{}p\in\mathbb{R}^{k}\;:\;p^{T}(x-\bar{x})\leq
f(x)-f(\bar{x})\ \,\forall x\in\mathbb{R}^{k}\big{\\}}.$

For a convex set $C$ in an Euclidean space $\mathbb{R}^{k}$, the normal cone
of $C$ at $\bar{x}\in C$ is given by
$N(\bar{x};C)=\left\\{p\in\mathbb{R}^{k}\;:\;p^{T}(x-\bar{x})\leq 0\ \,\forall
x\in C\right\\}.$

Let $F:\mathbb{R}^{k}\rightrightarrows\mathbb{R}^{\ell}$ be a multifunction.
The domain and the graph of $F$ are given, respectively, by the formulas
${\rm{dom}}\,F=\\{x\in\mathbb{R}^{k}\;:\;F(x)\not=\emptyset\\}$ and

${\rm{gph}}\,F=\left\\{(x,y)\in\mathbb{R}^{k}\times\mathbb{R}^{\ell}\;:\;y\in
F(x)\right\\}.$

If ${\rm gph}\,F$ is a convex set in $\mathbb{R}^{k}\times\mathbb{R}^{\ell}$,
then $F$ is said to be a convex multifunction. In that case, the coderivative
of $F$ at $(\bar{x},\bar{y})\in{\rm{gph}}\,F$ is the multifunction
$D^{*}F(\bar{x},\bar{y}):\mathbb{R}^{\ell}\rightrightarrows\mathbb{R}^{k}$
with

$D^{*}F(\bar{x},\bar{y})(v):=\left\\{u\in\mathbb{R}^{k}\;:\;(u,-v)\in
N\big{(}(\bar{x},\bar{y});{\rm{gph}}\,F\big{)}\right\\}$

for all $v\in\mathbb{R}^{\ell}$ (see, e.g., (Mordukhovich_Book_I, , Section
1.2) and An_Yen_2015 ).

From now on, let $K$ be a closed convex cone in $\mathbb{R}^{m}$. For any
$y^{1},y^{2}$ from $\mathbb{R}^{m}$, one writes $y^{1}\geq_{K}y^{2}$ if
$y^{1}-y^{2}\in K$. Similarly, one writes $y^{1}>_{K}y^{2}$ if
$y^{1}-y^{2}\in{\rm int}K$, where ${\rm int}K$ denotes the interior of $K$.

Given a matrix $A\in\mathbb{R}^{m\times n}$, vectors $b\in\mathbb{R}^{m}$ and
$c\in\mathbb{R}^{n}$, we consider the primal conic linear optimization problem

$\min\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b\\}.$ (P)

Following Bental and Nemirovski (BN_2001, , p. 52), we call

$\max\\{b^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0\\}$ (D)

the dual problem of (P). The feasible region, and the solution set, and the
optimal value of (P) are denoted respectively by $\mathcal{F}{\rm(P)}$,
$\mathcal{S}{\rm(P)}$, and $v{\rm(P)}$. The feasible region, the solution set,
and the optimal value of (D) are denoted respectively by
$\mathcal{F}{\rm(D)}$, $\mathcal{S}{\rm(D)}$, and $v({\rm D})$. By
definitions, one has

$v({\rm P})=\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b\\}$

and $v({\rm
D})=\sup\\{b^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0\\}.$ By a
standard convention, $\inf\emptyset=+\infty$ and $\sup\emptyset=-\infty$.

Thanks to the weak duality theorem in conic linear programming (BN_2001, ,
Proposition 2.3.1), one has $c^{T}x\geq b^{T}y$ for any
$x\in\mathcal{F}{\rm(P)}$ and $y\in\mathcal{F}{\rm(D)}$. Hence, $v({\rm
P})\geq v({\rm D})$. By constructing suitable examples, we can show that the
strict inequality $v({\rm P})>v({\rm D})$ is possible, i.e., a conic linear
program may have a duality gap. Thus, the equality $v({\rm P})=v({\rm D})$ is
guaranteed only if one imposes a certain regularity condition. In what
follows, we will rely on the regularity condition called strict feasibility,
which was intensively employed by Bental and Nemirovski BN_2001 .

###### Definition 1

(See (BN_2001, , Section 2.4)) If there exists a point
$x^{0}\in\mathbb{R}^{n}$ satisfying $Ax^{0}>_{K}b$, then one says that problem
(P) is strictly feasible. If there is some $y^{0}\in\mathbb{R}^{m}$ satisfying
$A^{T}y^{0}=c$ and $y^{0}>_{K^{*}}0$, then the dual problem (D) is said to be
strictly feasible.

The main assertion of the strong duality theorem in conic linear programming
can be stated as follows.

###### Lemma 1

(See (BN_2001, , Theorem 2.4.1 (assertions 3a and 3b))) If (P) is strictly
feasible and $v({\rm P})>-\infty$, then (D) has a solution and $v({\rm
D})=v({\rm P})$. If (D) is strictly feasible and one has $v({\rm D})<+\infty$,
then (P) has a solution and $v({\rm D})=v({\rm P})$.

The following analogues of the Farkas lemma (Rockafellar_1970, , p. 200) will
be used repeatedly in the sequel.

###### Lemma 2

Let there be given a closed convex cone $K$ in $\mathbb{R}^{m}$, a matrix $A$
in $\mathbb{R}^{m\times n}$, vectors $b\in\mathbb{R}^{m}$ and
$c\in\mathbb{R}^{n}$, and a real number $\alpha$.
(a) Suppose that there exists a point $x^{0}\in\mathbb{R}^{n}$ satisfying
$Ax^{0}>_{K}b$. Then, the inequality $c^{T}x\geq\alpha$ is a consequence of
the conic-linear inequality $Ax\geq_{K}b$ iff there exists a vector $y\in
K^{*}$ satisfying $A^{T}y=c$ and $b^{T}y\geq\alpha$.
(b) Suppose that there exists a point $y^{0}\in\mathbb{R}^{m}$ satisfying
$A^{T}y^{0}=c$ and $y^{0}>_{K^{*}}0$. Then, the inequality $b^{T}y\leq\alpha$
is a consequence of the system

$A^{T}y=c,\ y\geq_{K^{*}}0$

iff there exists a vector $x\in\mathbb{R}^{n}$ satisfying $Ax\geq_{K}b$ and
$c^{T}x\leq\alpha$.

Proof To prove assertion (a), suppose that $Ax\geq_{K}b$ and there exists a
vector $y\in K^{*}$ satisfying $A^{T}y=c$ and $b^{T}y\geq\alpha$. Then we have

$\displaystyle c^{T}x-b^{T}y=x^{T}c-b^{T}y$
$\displaystyle=x^{T}(A^{T}y)-b^{T}y$ (1) $\displaystyle=(Ax)^{T}y-b^{T}y$
$\displaystyle=(Ax-b)^{T}y\geq 0,$

where the last inequality in (1) is valid because $Ax\geq_{K}b$ and
$y>_{K^{*}}0$. Combining this with the assumption $b^{T}y\geq\alpha$, yields
$c^{T}x\geq\alpha$. Conversely, suppose that $c^{T}x\geq\alpha$ for all $x$
satisfying $Ax\geq_{K}b$. It is clear that (P) is strictly feasible and
$v({\rm P})\geq\alpha$. By the first assertion of Lemma 1, (D) has a solution
and one has $v({\rm P})=v({\rm D})$. Let $y$ be a solution of (D). Then we
have $y\in K^{*}$, $A^{T}y=c$ and $b^{T}y=v({\rm D})=v({\rm P})\geq\alpha$.
So, assertion (a) holds true.

Now, to prove assertion (b), suppose that $A^{T}y=c,\,y\geq_{K^{*}}0$ and
there exists a vector $x\in\mathbb{R}^{n}$ satisfying $Ax\geq_{K}b$ and
$c^{T}x\leq\alpha$. Then, we have

$\displaystyle b^{T}y-c^{T}x=b^{T}y-x^{T}c$
$\displaystyle=b^{T}y-x^{T}(A^{T}y)$ (2) $\displaystyle=b^{T}y-(Ax)^{T}y$
$\displaystyle=-(Ax-b)^{T}y\leq 0,$

where the last inequality in (2) is valid because $Ax\geq_{K}b$ and
$y\geq_{K^{*}}0$. Since $c^{T}x\leq\alpha$, this yields $b^{T}y\leq\alpha$.
Conversely, suppose that $b^{T}y\leq\alpha$ for all $y$ satisfying
$A^{T}y=c,\,y\geq_{K^{*}}0$. So, (D) is strictly feasible by our assumption
and $v({\rm D})\leq\alpha$. By the second assertion of Lemma 1, (P) has a
solution and $v({\rm P})=v({\rm D})$. Let $x$ be a solution of (P). Then we
have $Ax\geq_{K}b$ and $c^{T}x=v({\rm P})=v({\rm D})\leq\alpha$. This
justifies the validity of (b). $\hfill\Box$

###### Remark 1

The result in Lemma 2(a) is a known one (see (BN_2001, , Proposition 2.4.3)).
The assertions of Lemma 1 and Lemma 2(a) may be false if the assumption on the
strict feasiblity of the conic-linear inequality $Ax\geq_{K}b$ is removed (see
(BN_2001, , Example 2.4.2)). Similarly, the assertion of Lemma 2(b) may be
false if the assumption on the strict feasiblity of the conic-linear
inequality $y\geq_{K^{*}}0$ is removed.

The optimal value $v({\rm P})$ depends on the parameters $A$, $b$, and $c$.
Following Gauvin Gauvin_2001 , who studied differential stability properties
of linear programming problems, we consider the functions
$\varphi(b):=\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b\\}$ and
$\psi(c):=\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b\\}.$ Note that
$\varphi(\cdot)$ is the optimal value function of (P) under right-hand-side
perturbations of the constraint set and $\psi(\cdot)$ is the optimal value
function of (P) under perturbations of the objective function.

##  3 Locally Lipschitz Continuity of $\varphi(\cdot)$

According to a remark given in the paper of An and Yen (An_Yen_2015, , p.
113), we know that $\varphi(\cdot)$ is a convex function. The next proposition
presents additional continuity properties of $\varphi$.

###### Theorem 3.1

Suppose that (P) is strictly feasible and $v(\rm P)>-\infty$. Then, there
exists $\varepsilon>0$ such that $\varphi(b^{\prime})$ is finite for every
$b^{\prime}\in\bar{B}(b,\varepsilon)$ and $\varphi$ is Lipschitz on
$\bar{B}(b,\varepsilon)$.

Proof On one hand, since (P) is strictly feasible, one selects a point
$x^{0}\in\mathbb{R}^{n}$ satisfying $Ax^{0}>_{K}b$, i.e., $Ax^{0}-b\in{\rm
int}K$. Then there exists a convex open neighborhood of $b$ satisfying
$Ax^{0}-b^{\prime}\in{\rm int}K$ for every $b^{\prime}\in V$. So, $x^{0}$ is a
feasible point of the problem

$\min\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b^{\prime}\\}$ (${\rm
P}_{b^{\prime}}$)

for all $b^{\prime}\in V$. Moreover $\varphi(b^{\prime})\leq
c^{T}x^{0}<+\infty$. On the other hand, applying the weak duality theorem
(BN_2001, , Proposition 2.3.1) for the problems (${\rm P}_{b^{\prime}}$) and

$\max\\{(b^{\prime})^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0\\}$
(${\rm D}_{b^{\prime}}$)

one has $c^{T}x\geq(b^{\prime})^{T}y$ for all $x\in\mathbb{R}^{n}$ satisfying
$Ax\geq_{K}b^{\prime}$ and for every $y\in\mathbb{R}^{m}$ satisfying
$A^{T}y=c$, $y\geq_{K^{*}}0$. Therefore,

$\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b^{\prime}\\}\geq\sup\\{(b^{\prime})^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0\\}.$

This means that

$\varphi(b^{\prime})\geq\sup\\{(b^{\prime})^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0\\}.$

So, we have $\varphi(b^{\prime})>-\infty$ because

$\begin{array}[]{rl}&\sup\\{(b^{\prime})^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0\\}\\\
&\geq\sup\\{(b^{\prime})^{T}y\;:\;y\in\mathcal{S}({\rm
D})\\}>-\infty,\end{array}$ (3)

where the last inequality in (3) is valid as $\mathcal{S}({\rm D})$ is
nonempty (see Lemma 1). It follows that $\varphi(b^{\prime})$ is finite for
every $b^{\prime}\in V$, i.e., $V\subset{\rm int}({\rm dom}\varphi)$.
Combining this with the convexity of $\varphi$, by (Rockafellar_1970, ,
Theorem 24.7) we can asserts that $\varphi$ is locally Lipschitz on $V$.
$\hfill\Box$

##  4 Differentiability Properties of $\varphi(\cdot)$

First, let us show that the solution set of (D) possesses a remarkable
stability property, provided that the assumptions of Theorem 3.1 are
satisfied.

###### Proposition 1

Suppose that (P) is strictly feasible and $v(\rm P)>-\infty$. Then there
exists $\varepsilon>0$ such that $\mathcal{S}({\rm D}_{b^{\prime}})$ is
nonempty and compact for every $b^{\prime}$ in $B(b,\varepsilon)$.

Proof Since (P) is strictly feasible, there is $x^{0}\in\mathbb{R}^{n}$
satisfying $Ax^{0}-b\in{\rm int}K$. Therefore, there is a real number
$\varepsilon>0$ satisfying $Ax^{0}-b^{\prime}\in{\rm int}K$ for all
$b^{\prime}\in B(b,\varepsilon)$. According to Theorem 3.1, without loss of
generality we can assume that $\varphi(b^{\prime})$ is finite for all
$b^{\prime}\in B(b,\varepsilon)$. Fix a vector $b^{\prime}\in
B(b,\varepsilon)$. Then, the problem (${\rm P}_{b^{\prime}}$) is strictly
feasible and $v\eqref{P_b'}>-\infty$. So, applied for the pair problems (${\rm
P}_{b^{\prime}}$) and (${\rm D}_{b^{\prime}}$) Lemma 1 asserts that
$\mathcal{S}\eqref{D_b'}$ is nonempty and

$\mathcal{S}\eqref{D_b'}=\big{\\{}y\in\mathcal{F}\eqref{D_b'}\;:\;(b^{\prime})^{T}y=\varphi(b^{\prime})\big{\\}}.$

Since $\mathcal{F}\eqref{D_b'}=\mathcal{F}({\rm D})$, this implies
$\mathcal{S}\eqref{D_b'}=\big{\\{}y\in\mathcal{F}({\rm
D})\;:\;(b^{\prime})^{T}y=\varphi(b^{\prime})\big{\\}}.$ Clearly,
$\mathcal{S}\eqref{D_b'}$ is a closed set. To prove that
$\mathcal{S}\eqref{D_b'}$ is compact by contradiction, let us suppose that
$\mathcal{S}\eqref{D_b'}$ is unbounded. Select a sequence $\\{y^{k}\\}$ in
$\mathcal{S}\eqref{D_b'}$ satisfying the condition
$\lim\limits_{k\to\infty}\|y^{k}\|=+\infty$. Define
$\widetilde{y}^{k}=\|y^{k}\|^{-1}y^{k}$. Since $\|\widetilde{y}^{k}\|=1$,
without loss of generality we can assume that the sequence
$\\{\widetilde{y}^{k}\\}$ converges to a vector $\widetilde{y}$ with
$\|\widetilde{y}\|=1$. Since the sequence $\\{y^{k}\\}$ is contained in the
closed cone $K^{*}$, one has $\widetilde{y}\in K^{*}$. Observe that

$\displaystyle
A^{T}\widetilde{y}=\lim\limits_{k\to\infty}A^{T}\widetilde{y}^{k}$
$\displaystyle=\lim\limits_{k\to\infty}\dfrac{A^{T}y^{k}}{\|y^{k}\|}$
$\displaystyle=\lim\limits_{k\to\infty}\dfrac{c}{\|y^{k}\|}=0$

and

$\displaystyle(b^{\prime})^{T}\widetilde{y}=\lim\limits_{k\to\infty}(b^{\prime})^{T}\widetilde{y}^{k}$
$\displaystyle=\lim\limits_{k\to\infty}\dfrac{(b^{\prime})^{T}y^{k}}{\|y^{k}\|}$
$\displaystyle=\lim\limits_{k\to\infty}\dfrac{\varphi(b^{\prime})}{\|y^{k}\|}=0.$

It follows that
$(Ax^{0}-b^{\prime})^{T}\widetilde{y}={(x^{0})}^{T}A^{T}\widetilde{y}-(b^{\prime})^{T}\widetilde{y}=0$.
Meanwhile, since $Ax^{0}-b^{\prime}\in{\rm int}K$ and $\widetilde{y}\in
K^{*}\setminus\\{0\\}$, $(Ax^{0}-b^{\prime})^{T}\widetilde{y}>0$. We have
obtained a contradiction. Thus, $\mathcal{S}\eqref{D_b'}$ is bounded; hence it
is compact. $\hfill\Box$

The following question arises naturally from Proposition 1: If (D) is strictly
feasible and $v(\rm D)<+\infty$, then the solution set $\mathcal{S}({\rm P})$
is nonempty and compact, or not? By the second assertion of Lemma 1, if (D) is
strictly feasible and $v(\rm D)<+\infty$, then $\mathcal{S}({\rm P})$ is
nonempty. However, $\mathcal{S}({\rm P})$ may not be a compact set. The next
example is an illustration for this statement.

###### Example 1

Consider the problem (P) with $n=m=2$, $K=\mathbb{R}^{2}_{+}$,
$A=\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}$, $b=(1,-1)^{T}$, $c=(1,0)^{T}$.
Here we have $K^{*}=K=\mathbb{R}^{2}_{+}$. For $y^{0}:=(1,1)^{T}$, one has
$A^{T}y^{0}=c$ and $y^{0}>_{K^{*}}0$. Thus, (D) is strictly feasible.
Meanwhile, $\mathcal{S}({\rm P})=\\{1\\}\times\mathbb{R}$ is unbounded.

The following result gives a formula for the directional derivative of
$\varphi$ at $b$ in a direction $d$.

###### Theorem 4.1

Suppose that (P) is strictly feasible and (P) has a solution. Then, for every
direction $d\in\mathbb{R}^{m}$, one has

$\varphi^{\prime}(b;d)=\max\limits_{y\in\mathcal{S}({\rm D})}y^{T}d.$ (4)

Proof Fix a direction $d\in\mathbb{R}^{m}$, consider the function
$g:\mathbb{R}\to\overline{\mathbb{R}}$ given by

$g(t)=\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b+td\\},$

where $t\in\mathbb{R}$. Let $f(x,t)=c^{T}x$ for all
$(x,t)\in\mathbb{R}^{n}\times\mathbb{R}$. Clearly, $f$ is convex and
continuous on $\mathbb{R}^{n}\times\mathbb{R}$. Define the multifunction
$G:\mathbb{R}\rightrightarrows\mathbb{R}^{n}$ by setting

$G(t)=\big{\\{}x\in\mathbb{R}^{n}\;:\;Ax\geq_{K}b+td\big{\\}}.$

Note that $G$ is a convex multifunction. Consider the parametric convex
optimization problem $\min\\{f(x,t)\;:\;x\in G(t)\\},$ which depends on the
parameter $t\in\mathbb{R}$, and observe that $g(\cdot)$ is the optimal value
function of this problem. By a remark given in (An_Yen_2015, , p. 113) we know
that $g(\cdot)$ is a convex function. Applying a result of An and Yen
(An_Yen_2015, , Theorem 4.2) for $\bar{t}:=0$ and for a solution $\bar{x}$ of
$({\rm P})$, we have

$\partial g(0)=\bigcup\limits_{(x^{*},t^{*})\in\partial
f(\bar{x},\bar{t})}\big{\\{}t^{*}+D^{*}G(\bar{t},\bar{x})(x^{*})\big{\\}}.$

Since $\partial f(x,t)=\left\\{\begin{bmatrix}c\\\ 0\end{bmatrix}\right\\}$,
this equality yields

$\partial g(0)=D^{*}G(0,\bar{x})(c).$ (5)

By the definition of coderivative for convex multifunctions,

$\displaystyle D^{*}G(0,\bar{x})(c)$
$\displaystyle=\\{t^{*}\in\mathbb{R}\;:\;(t^{*},-c)\in
N((0,\bar{x}),\rm{gph}\,G)\\}$ (6)
$\displaystyle=\big{\\{}t^{*}\in\mathbb{R}\;:\;t^{*}t-c^{T}(x-\bar{x})\leq 0\
\,\forall(t,x)\in\rm{gph}\,G\big{\\}}$
$\displaystyle=\big{\\{}t^{*}\in\mathbb{R}\;:\;c^{T}x-t^{*}t\geq c^{T}\bar{x}\
\,\forall(t,x)\textrm{ with }Ax\geq_{K}b+td\big{\\}}$
$\displaystyle=\big{\\{}t^{*}\in\mathbb{R}\;:\;c^{T}x-t^{*}t\geq c^{T}\bar{x}\
\,\forall(x,t)\textrm{ with }Ax-td\geq_{K}b\big{\\}}.$

Let

$\widetilde{c}:=\begin{bmatrix}c\\\
-t^{*}\end{bmatrix},\quad\widetilde{A}:=\begin{bmatrix}A\quad-d\end{bmatrix},\quad\widetilde{x}:=\begin{bmatrix}x\\\
t\end{bmatrix},\quad\alpha:=c^{T}\bar{x}.$

Clearly, the inequality $Ax-td\geq_{K}b$ is equivalent to
$\widetilde{A}\widetilde{x}\geq_{K}b$. So, from (6) one gets

$\displaystyle
D^{*}G(0,\bar{x})(c)=\big{\\{}t^{*}\in\mathbb{R}\;:\;\widetilde{c}^{T}\widetilde{x}\geq\alpha\
\,\forall\widetilde{x}\in\mathbb{R}^{n}\times\mathbb{R}\textrm{ with
}\widetilde{A}\widetilde{x}\geq_{K}b\big{\\}}.$ (7)

Since (P) is strictly feasible, there exists $x^{0}\in\mathbb{R}^{n}$
satisfying $Ax^{0}>_{K}b$. Setting $\widetilde{x}^{0}=\begin{bmatrix}x^{0}\\\
0\end{bmatrix}$, we have $\widetilde{A}\widetilde{x}^{0}>_{K}b$. Then,
applying the Farkas-type result in Lemma 2(a) to the inequality system
$\widetilde{A}\widetilde{x}\geq_{K}b$ and the vector $\widetilde{c}$, we can
assert that $\widetilde{c}^{T}\widetilde{x}\geq\alpha$ for all
$\widetilde{x}\in\mathbb{R}^{n}\times\mathbb{R}$ such that
$\widetilde{A}\widetilde{x}\geq_{K}b$ iff there exists a vector $y\in K^{*}$
satisfying $\widetilde{A}^{T}y=\widetilde{c}$ and $b^{T}y\geq\alpha$. Since

$\widetilde{A}^{T}y=\begin{bmatrix}A^{T}\\\
-d^{T}\end{bmatrix}y=\begin{bmatrix}A^{T}y\\\ -d^{T}y\end{bmatrix},$

the equality $\widetilde{A}^{T}y=\widetilde{c}$ is equivalent to the
conditions $A^{T}y=c$ and $d^{T}y=t^{*}$. Therefore, combining (7) with the
description of the feasible region of the dual problem (D), we have

$\displaystyle D^{*}G(0,\bar{x})(c)$
$\displaystyle=\big{\\{}t^{*}\in\mathbb{R}\;:\;\exists y\in
K^{*}\;\textrm{s.t.}\;\widetilde{A}^{T}y=\widetilde{c},\;b^{T}y\geq\alpha\big{\\}}$
(8) $\displaystyle=\big{\\{}t^{*}\in\mathbb{R}\;:\;\exists y\in
K^{*}\;\textrm{s.t.}\;A^{T}y=c,\;d^{T}y=t^{*},\;b^{T}y\geq
c^{T}\bar{x}\big{\\}}$ $\displaystyle=\big{\\{}d^{T}y\;:\;y\in
K^{*},\;A^{T}y=c,\;b^{T}y\geq c^{T}\bar{x}\big{\\}}$
$\displaystyle=\big{\\{}d^{T}y\;:\;y\in\mathcal{F}({\rm D}),\;b^{T}y\geq
c^{T}\bar{x}\big{\\}}$ $\displaystyle=\big{\\{}d^{T}y\;:\;y\in\mathcal{F}({\rm
D}),\;b^{T}y\geq v({\rm P})\big{\\}}.$

Since (P) is strictly feasible and (P) has a solution, by the strong duality
theorem in Lemma 1, (D) has a solution and $v({\rm D})=v({\rm P})$. Hence, by
(8),

$\displaystyle D^{*}G(0,\bar{x})(c)$
$\displaystyle=\big{\\{}d^{T}y\;:\;y\in\mathcal{F}({\rm D}),\;b^{T}y\geq
v({\rm D})\big{\\}}$ (9)
$\displaystyle=\big{\\{}d^{T}y\;:\;y\in\mathcal{F}({\rm D}),\;b^{T}y=v({\rm
D})\big{\\}}$ $\displaystyle=\big{\\{}d^{T}y\;:\;y\in\mathcal{S}({\rm
D})\big{\\}}.$

Combining (9) with (5) gives $\partial g(0)=\\{d^{T}y\;:\;y\in\mathcal{S}({\rm
D})\\}.$ Then, by the well-known result on the relationships between the
directional derivative of a convex function (Rockafellar_1970, , Theorem
23.4), we obtain

$g^{\prime}(0;1)=\sup\limits_{s\in\partial
g(0)}s=\sup\limits_{y\in\mathcal{S}({\rm
D})}y^{T}d=\max\limits_{y\in\mathcal{S}({\rm D})}y^{T}d,$ (10)

where the last equality in (10) is valid because $\mathcal{S}({\rm D})$ is
compact. Finally, using (10) and the fact that
$\varphi^{\prime}(b;d)=g^{\prime}(0;1)$, we get the desired formula (4).
$\hfill\Box$

Based on Theorem 4.1, the next proposition provides us with a formula for the
subdifferential of $\varphi$ at $b$.

###### Proposition 2

If (P) is strictly feasible and (P) possesses a solution, then
$\partial\varphi(b)=\mathcal{S}({\rm D})$.

Proof Take a vector $p\in\partial\varphi(b)$. For any $d\in\mathbb{R}^{m}$ and
$t>0$, from the inequality $\varphi(b+td)-\varphi(b)\geq p^{T}(td)$ it follows
that $\dfrac{1}{t}\left(\varphi(b+td)-\varphi(b)\right)\geq p^{T}d.$ Letting
$t\to 0^{+}$, one has $\varphi^{\prime}(b;d)\geq p^{T}d.$ Combining this with
the equation (4) gives

$\max\limits_{y\in\mathcal{S}({\rm D})}y^{T}d\geq p^{T}d.$ (11)

To show that $p$ belongs to $\mathcal{S}({\rm D})$, suppose the contrary:
$p\notin\mathcal{S}({\rm D})$. By $\mathcal{S}({\rm D})$ is a nonempty convex
set, by the strongly separation theorem (see, e.g., (Rockafellar_1970, ,
Corollary 11.4.2)), there exists a vector $d\in\mathbb{R}^{m}$ such that
$\max\limits_{y\in\mathcal{S}({\rm D})}y^{T}d<p^{T}d$. This contradicts with
(11). We have thus proved that $\partial\varphi(b)\subset\mathcal{S}({\rm
D})$. To obtain the opposite inclusion, take any $p\in\mathcal{S}({\rm D})$.
For all $d\in\mathbb{R}^{m}$, by (4),

$\varphi^{\prime}(b;d)=\max\limits_{y\in\mathcal{S}({\rm D})}y^{T}d\geq
p^{T}d.$ (12)

Besides, by (Rockafellar_1970, , Theorem 23.1) one gets

$\varphi(b+d)-\varphi(b)\geq\varphi^{\prime}(b;d).$ (13)

Combining (12) with (13) we have $\varphi(b+d)-\varphi(b)\geq p^{T}d$ for all
$p\in\mathbb{R}^{m}$. So, $p\in\partial\varphi(b)$. The proof is complete.
$\hfill\Box$

##  5 Increment Estimates for $\varphi(\cdot)$

Roughly speaking, the following statement gives an analogue of (Gauvin_2001, ,
Theorem 1) for conic linear programs.

###### Theorem 5.1

Suppose that (P) is strictly feasible and $v{\rm(P)}>-\infty$. Then, for every
$d\in\mathbb{R}^{n}$ and $t>0$, one has

$\varphi(b+td)\geq\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathbb{R}^{m},\
\,A^{T}y=c,\ y\geq_{K^{*}}0,\ b^{T}y=\varphi(b)\\}.$

In addition, for every $d\in\mathbb{R}^{n}$, there exists $\tau>0$ such that

$\varphi(b+td)\leq\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathcal{F}{\rm(D)}\\}$
(14)

for all $t\in(0,\tau]$.

Proof By Lemma 1, (D) has a solution and $v({\rm D})=v({\rm P})$; hence
$v({\rm D})=\varphi(b)$. On one hand, applying the weak duality theorem
(BN_2001, , Proposition 2.3.1) for the problems

$\min\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b+td\\}$ (${\rm P}_{t}$)

and

$\max\\{(b+td)^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0\\}$
(${\rm D}_{t}$)

one has $c^{T}x\geq(b+td)^{T}y$ for all $x\in\mathbb{R}^{n}$ satisfying
$Ax\geq_{K}b+td$ and for every $y\in\mathbb{R}^{m}$ satisfying $A^{T}y=c$,
$y\geq_{K^{*}}0$. Consequently,

$\begin{array}[]{rl}&\inf\big{\\{}c^{T}x\;:\;x\in\mathbb{R}^{n},Ax\geq_{K}b+td\big{\\}}\\\
&\geq\sup\big{\\{}(b+td)^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0\big{\\}}.\end{array}$
(15)

On the other hand, it is clear that

$\sup\\{(b+td)^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0\\}\\\
\geq\sup\\{(b+td)^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0,b^{T}y=\varphi(b)\\}.$
(16)

Combining (15) and (16), one gets

$\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},Ax\geq_{K}b+td\\}\\\
\geq\sup\\{(b+td)^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0,b^{T}y=\varphi(b)\\}.$

It follows that

$\begin{array}[]{rl}\varphi(b+td)&\geq\sup\\{(b+td)^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0,b^{T}y=\varphi(b)\\}\\\
&=\sup\\{b^{T}y+td^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0,b^{T}y=\varphi(b)\\}\\\
&=\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0,b^{T}y=\varphi(b)\\}.\end{array}$
(17)

Combining (17) with the fact that $\varphi(b)=v({\rm P})>-\infty$, one has
$\varphi(b+td)>-\infty$.

Since (P) is strictly feasible, there is a point $x^{0}\in\mathbb{R}^{n}$
satisfying $Ax^{0}>_{K}b$. Then one can find $\tau>0$ such that
$Ax^{0}>_{K}b+td$ for all $t\in[0,\tau]$. Hence, (${\rm P}_{t}$) is strictly
feasible. Applying Lemma 1 for a pair problems (${\rm P}_{t}$) and (${\rm
D}_{t}$), where $t\in[0,\tau]$, we have

$\displaystyle\varphi(b+td)$
$\displaystyle=\sup\\{(b+td)^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0\\}$
$\displaystyle\leq\sup\\{b^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0\\}$
$\displaystyle\hskip
14.22636pt+\sup\\{td^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0\\}$
$\displaystyle=\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathbb{R}^{m},A^{T}y=c,y\geq_{K^{*}}0\\}.$

Thus, the inequality (14) has been proved for all $t\in[0,\tau]$. $\hfill\Box$

We now consider the case where $K$ is a polyhedral convex cone.

###### Theorem 5.2

Suppose that $K$ is a polyhedral convex cone and $\varphi(b)$ is finite. Then
for every $d\in\mathbb{R}^{n}$, there exists $\tau>0$ such that

$\varphi(b+td)=\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c,\,y\geq_{K^{*}}0,b^{T}y=\varphi(b)\\}$
(18)

for all $t\in]0,\tau]$.

Proof Since $K$ is a polyhedral convex cone in $\mathbb{R}^{m}$, there exists
a matrix $B\in\mathbb{R}^{k\times m}$ satisfying
$K=\\{y\in\mathbb{R}^{m}\;:\;By\geq_{\mathbb{R}^{k}_{+}}0\\}.$ Then, the
problem (P) can be written in the form

$\min\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,BAx\geq_{\mathbb{R}^{k}_{+}}Bb\\}.$
(P’)

The dual problem of (P’) is the problem

$\max\\{(Bb)^{T}z\;:\;z\in\mathbb{R}^{k},\,(BA)^{T}z=c,z\geq_{\mathbb{R}^{k}_{+}}0\\}.$
(D’)

Since $\varphi(b)$ is finite, the (P’) has a solution. Moreover, both of two
problems (P’) and (D’) have solutions and the optimal values are equal. Then,
for every $d\in\mathbb{R}^{m}$, by using Theorem 1 in Gauvin_2001  for the
problem (P’), one gets

$\displaystyle\varphi(b+td)$
$\displaystyle=\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b+td\\}$
$\displaystyle=\inf\\{c^{T}x\;:\;x\in\mathbb{R}^{n},\,BAx\geq_{\mathbb{R}^{k}_{+}}Bb+tBd\\}$
$\displaystyle=\varphi(b)+t\sup\\{(Bd)^{T}z\;:\;z\in\mathbb{R}^{k}_{+},(BA)^{T}z=c,(Bb)^{T}z=\varphi(b)\\}$
$\displaystyle=\varphi(b)+t\sup\\{d^{T}(B^{T}z)\;:\;z\in\mathbb{R}^{k}_{+},A^{T}(B^{T}z)=c,b^{T}(B^{T}z)=\varphi(b)\\}$

for any $t>0$ sufficiently small. Denote $B^{T}z=y$, we have

$\varphi(b+td)=\varphi(b)+t\sup\\{d^{T}y\;:\;y\in
B^{T}(\mathbb{R}^{k}_{+}),A^{T}y=c,b^{T}y=\varphi(b)\\}.\\\ $ (19)

In the other hand, since $K=\\{y\in\mathbb{R}^{m}\;:\;\langle
B_{i}^{T},y\rangle\geq 0,\ i=1,2,\dots,k\\}$ where $B_{i}$ is the $i$-row of
matrix $B$, one has

$K^{*}=\left\\{\sum\limits_{i=1}^{k}\lambda_{i}B^{T}_{i}\;:\;\lambda_{i}\geq
0,\,i=1,2,\dots,k\right\\}$

by Proposition 2.42 in Bonnans_Shapiro_2000 ; hence
$K^{*}=B^{T}(\mathbb{R}^{k}_{+})$. Combining the later and the equation (19),
we can assert that (18) holds. $\hfill\Box$

###### Remark 2

Theorem 5.2 is a generalization of Theorem 1 in Gauvin_2001 , where the case
$K=\mathbb{R}^{m}_{+}$ was treated.

The following two examples are designed as illustrations for Theorem 5.1.

###### Example 2

Consider the conic problem (P) with $x=(x_{1},x_{2})^{T}\in\mathbb{R}^{2}$,
$K$ is the 3D ice cream cone in $\mathbb{R}^{3}$, i.e.,
$K=\left\\{(y_{1},y_{2},y_{3})^{T}\in\mathbb{R}^{3}\;:\;y_{3}\geq\sqrt{y_{1}^{2}+y_{2}^{2}}\right\\}$,
$A=\begin{bmatrix}0&0\\\ 0&1\\\ 1&0\end{bmatrix}$, $b=(-1,0,0)^{T}$,
$c=(1,0)^{T}$. We have

$\mathcal{F}({\rm
P})=\Big{\\{}x\in\mathbb{R}^{2}\;:\;x_{1}\geq\sqrt{1+x_{2}^{2}}\Big{\\}}.$
(20)

Clearly, $\varphi(b)=1$ and $\mathcal{S}({\rm
P})=\big{\\{}(1,0)^{T}\big{\\}}.$ Note that $A^{T}y=c$ iff $y_{2}=0$ and
$y_{3}=1$. In addition $K^{*}=K$. It follows that

$\mathcal{F}({\rm D})=\\{y=(y_{1},0,1)^{T}\in\mathbb{R}^{3}\;:\;-1\leq
y_{1}\leq 1\\}.$

Obviously, $\mathcal{S}({\rm D})=\\{(-1,0,1)^{T}\\}$. Given
$d\in\mathbb{R}^{3}$ with $d_{1}>0$, and for every $t>0$, one has
$Ax\geq_{K}b+td$ iff
$x_{1}\geq\sqrt{(1-td_{1})^{2}+(x_{2}-td_{2})^{2}}+td_{3}$. On one hand, for
$t$ small enough,

$\varphi(b+td)=\sqrt{(1-td_{1})^{2}}+td_{3}=|1-td_{1}|+td_{3}=1+t(d_{3}-d_{1}).$

On the other hand, $\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathcal{S}({\rm
D})\\}=1+t(d_{3}-d_{1})$ and

$\displaystyle\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathcal{F}({\rm D})\\}$
$\displaystyle=1+t\sup\\{d_{1}y_{1}+d_{3}\;:\;-1\leq y_{1}\leq 1\\}$
$\displaystyle=1+t(|d_{1}|+d_{3}).$

###### Example 3

Consider the conic problem (P) with $x\in\mathbb{R}$, $K$ is the 3D ice cream
cone in $\mathbb{R}^{3}$, $A=\begin{bmatrix}1\\\ 0\\\ 0\end{bmatrix}$,
$b=(0,0,-1)^{T}$, $c=1$, and $d=(0,1,-1)^{T}$. Clearly, the condition
$Ax\geq_{K}b+td$ is equivalent to $1+t\geq\sqrt{x^{2}+t^{2}}$. For $t>0$ is
small enough, the latter can be rewritten as $x^{2}\leq 2t+1$. It follows that
$\mathcal{F}({\rm P}_{t})=\left[-\sqrt{2t+1};\sqrt{2t+1}\right]$ and
$\varphi(b+td)=-\sqrt{2t+1}$. Meanwhile, $\mathcal{F}({\rm
D})=\left\\{y=(1,y_{2},y_{3})^{T}\in\mathbb{R}^{3}\;:\;y_{3}\geq\sqrt{1+y_{2}^{2}}\right\\}$
and $\mathcal{S}({\rm D})=\left\\{(1,0,1)^{T}\right\\}$. Therefore,
$\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathcal{F}{\rm(D)}\\}=-1-t$ and

$\varphi(b)+t\sup\\{d^{T}y\;:\;y\in\mathcal{S}{\rm(D)}\\}=-1.$

It is clear that $-1-t\leq-\sqrt{2t+1}<-1$ for every $t\in(0,1)$.

##  6 Properties of the Function $\psi(\cdot)$

In this section, differentiability propertiesof the function $\psi(\cdot)$ and
some increment estimates will be obtained.

###### Theorem 6.1

Suppose that both problems (P) and (D) are strictly feasible. Then, one has

$\psi^{\prime}(c;h)=\begin{cases}\inf\limits_{x\in\mathcal{S}({\rm
P})}x^{T}h&\text{ if }\quad h\in A^{T}(\mathbb{R}^{m})\\\ -\infty&\text{ if
}\quad h\notin A^{T}(\mathbb{R}^{m}).\end{cases}$ (21)

Proof By the assumed strict feasibility of (P) and (D) (see Definition 1),
there exist $x^{0}\in\mathbb{R}^{n}$ and $y^{0}\in\mathbb{R}^{m}$ such that
$Ax^{0}>_{K}b$, $y^{0}>_{K^{*}}0$, and $A^{T}y^{0}=c$. Since
$\psi^{\prime}(c;0)=0$, formula (21) is valid for $h=0$. Fix a vector
$h\in\mathbb{R}^{n}\setminus\\{0\\}$ and define the function
$g:\mathbb{R}\to\overline{\mathbb{R}}$ by

$g(t):=-\psi(c+th)=-\inf\\{(c+th)^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b\\}\quad(t\in\mathbb{R}).$

Note that $g(t)\neq-\infty$ for all $t\in\mathbb{R}$ and
$\psi^{\prime}(c;h)=-g^{\prime}(0;1)$. Thanks to the weak duality theorem in
(BN_2001, , Theorem 2.4.1 (assertion 2)), we have

$c^{T}x^{0}\geq v({\rm P})\geq v({\rm D})\geq b^{T}y^{0}.$

It follows that $v({\rm P})>-\infty$ and $v({\rm D})<+\infty$. So, by Lemma 1,
(P) and (D) have solutions, and $v({\rm D})=v({\rm P})$. Hence, the relations
$g(0)=-\psi(c)=-v{\rm(P)}$ imply that the value $g(0)$ is finite. Clearly,
$g(t)\geq-(c+th)^{T}x^{0}$ for any $t\in\mathbb{R}$.

If $h\in A^{T}(\mathbb{R}^{m})$, then $h=A^{T}v$ for some
$v\in\mathbb{R}^{m}$. Note that

$A^{T}(y^{0}+tv)=A^{T}y^{0}+tA^{T}v=c+th.$

Since $y^{0}>_{K^{*}}0$, one can find $\tau>0$ such that $y^{0}+tv>_{K^{*}}0$
for every $t\in]-\tau,\tau[$. For any $t\in]-\tau,\tau[$, applying the weak
duality theorem in (BN_2001, , Theorem 2.4.1 (assertion 2)) for the conic
linear problem

$\min\big{\\{}(c+th)^{T}x\;:\;x\in\mathbb{R}^{n},\ \,Ax\geq_{K}b\big{\\}}$
(22)

and its dual

$\max\big{\\{}b^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c+th,\
\,y\geq_{K^{*}}0\big{\\}},$ (23)

one has $(c+th)^{T}x\geq b^{T}(y^{0}+tv)$ for all $x\in\mathbb{R}^{n}$
satisfying $Ax\geq_{K}b$. Consequently,
$\inf\big{\\{}(c+th)^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b\big{\\}}\geq
b^{T}(y^{0}+tv).$ So, we have $g(t)\leq-b^{T}(y^{0}+tv)$. Since
$g(t)\geq-(c+th)^{T}x^{0}$ for all $t\in\mathbb{R}$, this implies that $g(t)$
is finite for every $t\in]-\tau,\tau[$. Now, fixing a number
$t\in]-\tau,\tau[$ and applying Lemma 1 for the problems (22) and (23), one
has

$\inf\big{\\{}(c+th)^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b\\}\\\
=\sup\\{b^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c+th,\,y\geq_{K^{*}}0\big{\\}}.$

Therefore,

$\displaystyle g(t)$
$\displaystyle=-\sup\big{\\{}b^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c+th,\,y\geq_{K^{*}}0\big{\\}}$
(24)
$\displaystyle=\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c+th,\,y\geq_{K^{*}}0\big{\\}}.$

To apply a result from An_Yen_2015 , we define a function
$f:\mathbb{R}\times\mathbb{R}^{m}\to\mathbb{R}$ by setting

$f(t,y)=(-b)^{T}y\quad\forall(t,y)\in\mathbb{R}\times\mathbb{R}^{m}.$

Clearly, $f$ is convex and continuous on $\mathbb{R}\times\mathbb{R}^{m}$. Let
$G:\mathbb{R}\rightrightarrows\mathbb{R}^{m}$ be the multifunction given by
$G(t):=\big{\\{}y\in\mathbb{R}^{m}\;:\;A^{T}y=c+th,\,y\geq_{K^{*}}0\big{\\}}.$
Note that $G$ is a convex multifunction. Consider the convex optimization
problem

$\min\\{f(t,y)\;:\;y\in G(t)\\},$ (25)

which depends on the parameter $t\in\mathbb{R}$, and observe by (24) that
$g(\cdot)$ is the optimal value function of this problem. According to a
remark given in (An_Yen_2015, , p. 113), $g(\cdot)$ is a convex function. Let
$\bar{y}$ be a solution of $({\rm D})$. Then, it is easy to verify that
$\bar{y}$ is a solution of the parametric problem (25) at $\bar{t}:=0$. Hence,
applying (An_Yen_2015, , Theorem 4.2) for (25) yields

$\partial g(0)=\bigcup\limits_{(t^{*},y^{*})\in\partial
f(0,\bar{y})}\big{\\{}t^{*}+D^{*}G(0,\bar{y})(y^{*})\big{\\}}.$

Since $\partial f(t,y)=\left\\{\begin{bmatrix}0\\\ -b\end{bmatrix}\right\\}$,
this implies that

$\partial g(0)=D^{*}G(0,\bar{y})(-b).$ (26)

By the definition of coderivative for convex multifunctions,

$\displaystyle D^{*}G(0,\bar{y})(-b)$
$\displaystyle=\\{t^{*}\in\mathbb{R}\;:\;(t^{*},b)\in
N((0,\bar{y}),\rm{gph}\,G)\\}$
$\displaystyle=\big{\\{}t^{*}\in\mathbb{R}\;:\;t^{*}t+b^{T}(y-\bar{y})\leq 0\
\,\forall(t,y)\in\rm{gph}\,G\big{\\}}.$

Hence,

$D^{*}G(0,\bar{y})(-b)\\\ =\big{\\{}t^{*}\in\mathbb{R}\;:\;b^{T}y+t^{*}t\leq
b^{T}\bar{y}\ \;\forall(t,y)\textrm{ s.t.
}A^{T}y-th=c,\,y\geq_{K^{*}}0\big{\\}}.$ (27)

Let

$\widetilde{b}:=\begin{bmatrix}b\\\
t^{*}\end{bmatrix},\quad\widetilde{A}:=\begin{bmatrix}A\\\
-h^{T}\end{bmatrix},\quad\widetilde{y}:=\begin{bmatrix}y\\\
t\end{bmatrix},\quad\widetilde{K}:=K\times\\{0\\},\quad\alpha:=b^{T}\bar{y}.$

Since $\widetilde{K}^{*}=K^{*}\times\mathbb{R}$, the system
$\begin{cases}A^{T}y-th=c\\\ y\geq_{K^{*}}0\end{cases}$ is equivalent to
$\begin{cases}\widetilde{A}^{T}\widetilde{y}=c\\\
\widetilde{y}\geq_{\widetilde{K}^{*}}0.\end{cases}$ Hence, from (27) one gets

$\displaystyle
D^{*}G(0,\bar{y})(-b)=\big{\\{}t^{*}\in\mathbb{R}\;:\;\widetilde{b}^{T}\widetilde{y}\leq\alpha\
\forall\widetilde{y}\ \,\textrm{with}\ \,\widetilde{A}^{T}\widetilde{y}=c,\
\widetilde{y}\geq_{\widetilde{K}^{*}}0\big{\\}}.$ (28)

Setting $\widetilde{y}^{0}:=\begin{bmatrix}y^{0}\\\ 0\end{bmatrix}$, we have
$\widetilde{A}^{T}\widetilde{y}^{0}=c$ and
$\widetilde{y}^{0}>_{\widetilde{K}^{*}}0$. Hence, by the Farkas-type result in
Lemma 2(b), we can assert that the inequality
$\widetilde{b}^{T}\widetilde{y}\leq\alpha$ holds for every
$\widetilde{y}\in\mathbb{R}^{m}\times\mathbb{R}$ satisfying
$\widetilde{A}^{T}\widetilde{y}=c,\ \widetilde{y}\geq_{\widetilde{K}^{*}}0$
iff there exists $x\in\mathbb{R}^{n}$ satisfying
$\widetilde{A}x\geq_{\widetilde{K}}\widetilde{b}$ and $c^{T}x\leq\alpha$.
Since $\widetilde{A}x=\begin{bmatrix}Ax\\\ -h^{T}x\end{bmatrix}$, one sees
that the inequality $\widetilde{A}x\geq_{\widetilde{K}}\widetilde{b}$ is
equivalent to the system of conditions $Ax\geq_{K}b$ and $-h^{T}x=t^{*}$.
Therefore, combining (28) with the description of the feasible region of (P),
we have

$\displaystyle D^{*}G(0,\bar{y})(-b)$
$\displaystyle=\\{t^{*}\in\mathbb{R}\;:\;\exists
x\in\mathbb{R}^{n}\;\textrm{s.t.}\;\widetilde{A}x\geq_{\widetilde{K}}\widetilde{b},\;c^{T}x\leq\alpha\\}$
$\displaystyle=\\{t^{*}\in\mathbb{R}\;:\;\exists
x\in\mathbb{R}^{n}\;\textrm{s.t.}\;Ax\geq_{K}b,\;-h^{T}x=t^{*},\;c^{T}x\leq\alpha\\}$
$\displaystyle=\\{-h^{T}x\;:\;x\in\mathbb{R}^{n},\;Ax\geq_{K}b,\;c^{T}x\leq
b^{T}\bar{y}\\}$ $\displaystyle=\\{-x^{T}h\;:\;x\in\mathcal{F}({\rm
P}),\;c^{T}x\leq b^{T}\bar{y}\\}.$

Hence,

$D^{*}G(0,\bar{y})(-b)=\big{\\{}-x^{T}h\;:\;x\in\mathcal{F}({\rm
P}),\;c^{T}x\leq v({\rm D})\big{\\}}.$ (29)

Since $v({\rm D})=v({\rm P})$, by (29) one has

$D^{*}G(0,\bar{y})(-b)=\\{-x^{T}h\;:\;x\in\mathcal{F}({\rm P}),\;c^{T}x\leq
v({\rm P})\\}=\\{-x^{T}h\;:\;x\in\mathcal{S}({\rm P})\\}.$

From this and (26) it follows that $\partial
g(0)=\\{-x^{T}h\;:\;x\in\mathcal{S}({\rm P})\\}.$ Then, since $g(\cdot)$ is a
proper convex function and $0\in{\rm int}({\rm dom}\,g)$, by
(Rockafellar_1970, , Theorem 23.4) we have

$g^{\prime}(0;1)=\sup\limits_{s\in\partial
g(0)}s=\sup\limits_{x\in\mathcal{S}({\rm P})}(-x^{T}h).$ (30)

As $\psi^{\prime}(c;h)=-g^{\prime}(0;1)$, (30) yields

$\psi^{\prime}(c;h)=-\sup\limits_{x\in\mathcal{S}({\rm
P})}(-x^{T}h)=\inf\limits_{x\in\mathcal{S}({\rm P})}x^{T}h.$

We have thus proved the first assertion in (21).

Now, let $h\notin A^{T}(\mathbb{R}^{m})$. In this case, we have $g(t)=+\infty$
for every $t\in\mathbb{R}\setminus\\{0\\}$. Indeed, if $g(t)\in\mathbb{R}$ for
some $t\in\mathbb{R}\setminus\\{0\\}$, then the objective function of the
minimization problem (22) is bounded from below. So, applying Lemma 1 for the
problems (22) and (23), we can assert that (23) has a solution $y^{1}$. Since
$A^{T}y^{1}=c+th$ and $A^{T}y^{0}=c$, one gets
$h=A^{T}\left[t^{-1}(y^{1}-y^{0})\right]$. This is impossible because $h\notin
A^{T}(\mathbb{R}^{m})$. Thus, $g(t)=+\infty$ for every
$t\in\mathbb{R}\setminus\\{0\\}$. It follows that $g^{\prime}(0;1)=+\infty$.
Then we have $\psi^{\prime}(c;h)=-g^{\prime}(0;1)=-\infty$. $\hfill\Box$

###### Proposition 3

For every $h\in\mathbb{R}^{m}$ and $t>0$, one has

$\psi(c+th)\geq\psi(c)+t\inf\limits_{x\in\mathcal{F}{\rm(P)}}h^{T}x,$ (31)

and

$\psi(c+th)\leq\psi(c)+t\inf\limits_{x\in\mathcal{S}{\rm(P)}}h^{T}x.$ (32)

Proof Let $h\in\mathbb{R}^{m}$ and $t>0$ be given arbitrarily. Clearly,

$\displaystyle\psi(c+th)$
$\displaystyle=\inf\big{\\{}(c+th)^{T}x\;:\;x\in\mathcal{F}{\rm(P)}\big{\\}}$
$\displaystyle\geq\inf\big{\\{}c^{T}x\;:\;x\in\mathcal{F}{\rm(P)}\big{\\}}+\inf\big{\\{}th^{T}x\;:\;x\in\mathcal{F}{\rm(P)}\big{\\}}$
$\displaystyle=\psi(c)+t\inf\big{\\{}h^{T}x\;:\;x\in\mathcal{F}{\rm(P)}\big{\\}}.$

So, the inequality in (31) is valid. In addition,

$\displaystyle\psi(c+th)$
$\displaystyle=\inf\big{\\{}(c+th)^{T}x\;:\;x\in\mathcal{F}{\rm(P)}\big{\\}}$
$\displaystyle\leq\inf\big{\\{}(c+th)^{T}x\;:\;x\in\mathcal{S}{\rm(P)}\big{\\}}$
$\displaystyle=\psi(c)+t\inf\limits_{x\in\mathcal{S}{\rm(P)}}h^{T}x.$

This means that the estimate (32) holds. $\hfill\Box$

###### Example 4

Consider problem ${\rm(P)}$ in the setting and notations of Example 2. Choose
$h=(0,-1)^{T}$. For $0<t<1$, using (20) one has

$\displaystyle\psi(c+th)$
$\displaystyle=\inf\Big{\\{}x_{1}-tx_{2}\;:\;x=(x_{1},x_{2})\in\mathbb{R}^{2},\
x_{1}\geq\sqrt{1+x_{2}^{2}}\Big{\\}}$
$\displaystyle=\inf\Big{\\{}\sqrt{1+x_{2}^{2}}-tx_{2}\;:\;x_{2}\in\mathbb{R}\Big{\\}}$
$\displaystyle=\sqrt{1-t^{2}}.$

Note that $\psi(c)=\varphi(b)=1$. Since $\mathcal{F}({\rm
P})=\Big{\\{}x\in\mathbb{R}^{2}\;:\;x_{1}\geq\sqrt{1+x_{2}^{2}}\Big{\\}}$,
(31) gives the trivial lower estimate $\psi(c+th)\geq-\infty$ for every $t>0$.
Meanwhile, as $\mathcal{S}({\rm P})=\big{\\{}(1,0)^{T}\big{\\}}$, (32) gives
the upper estimate $\psi(c+th)\leq 1$ for every $t>0$. Therefore, both
estimates (31) and (32) are strict for all $t\in]0,1[$.

The next increment formula for $\psi$ is a generalization of the corresponding
result stated in (Gauvin_2001, , p. 119), where the case
$K=\mathbb{R}^{m}_{+}$ was considered.

###### Theorem 6.2

Suppose that $K$ is a polyhedral convex cone, (P) is feasible, and (D) is
strictly feasible. Then, for every $h\in A^{T}(\mathbb{R}^{m})$, there exists
$\tau>0$ such that

$\psi(c+th)=\psi(c)+t\inf\limits_{x\in\mathcal{S}{\rm(P)}}h^{T}x.$ (33)

for all $t\in]0,\tau]$.

Proof By our assumptions, there exists $y^{0}\in\mathbb{R}^{m}$ such that
$A^{T}y^{0}=c$ and $y^{0}>_{K^{*}}0$. Since $h\in A^{T}(\mathbb{R}^{m})$,
there is $v\in\mathbb{R}^{m}$ satisfying $h=A^{T}v$. Then, one has
$A^{T}(y^{0}+tv)=A^{T}y^{0}+tA^{T}v=c+th.$ As $y^{0}>_{K^{*}}0$, there exists
a number $\tau^{\prime}>0$ such that $y^{0}+tv>_{K^{*}}0$ for all
$t\in]-\tau^{\prime},\tau^{\prime}[$. For each
$t\in]-\tau^{\prime},\tau^{\prime}[$, the linear optimization problem
$\min\big{\\{}(c+th)^{T}x\;:\;x\in\mathbb{R}^{n},\ \,Ax\geq_{K}b\big{\\}}$ and
its dual $\max\big{\\{}b^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c+th,\
\,y\geq_{K^{*}}0\big{\\}}$ are feasible. Therefore, by the well-known strong
duality theorem in linear programming one has

$\displaystyle\psi(c+th)$
$\displaystyle=\inf\big{\\{}(c+th)^{T}x\;:\;x\in\mathbb{R}^{n},\
\,Ax\geq_{K}b\big{\\}}$
$\displaystyle=\sup\big{\\{}b^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c+th,\
\,y\geq_{K^{*}}0\big{\\}}$

and $\psi(c+th)$ is finite. So,

$\displaystyle\psi(c+th)$
$\displaystyle=-\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y=c+th,\
\,y\geq_{K^{*}}0\big{\\}}$ (34)
$\displaystyle=-\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,A^{T}y\geq
c+th,$ $\displaystyle\hskip
113.81102pt-A^{T}y\geq-(c+th),\,y\geq_{K^{*}}0\big{\\}}$
$\displaystyle=-\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,My\geq_{L}\widetilde{c}+t\widetilde{h}\big{\\}},$

where

$M:=\begin{bmatrix}A^{T}\\\ -A^{T}\\\
E_{m}\end{bmatrix}\in\mathbb{R}^{(2n+m)\times m},\
\,\widetilde{c}:=\begin{bmatrix}c\\\ -c\\\
0\end{bmatrix}\in\mathbb{R}^{2n+m},\ \,\widetilde{h}:=\begin{bmatrix}h\\\
-h\\\ 0\end{bmatrix}\in\mathbb{R}^{2n+m},$

$E_{m}$ denotes the unit matrix in $\mathbb{R}^{m\times m}$, and
$L:=\mathbb{R}^{n}_{+}\times\mathbb{R}^{n}_{+}\times K^{*}$. Clearly, $L$ is a
polyhedral convex cone. So, applying Theorem 5.2 to the problem
$\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,My\geq_{L}\widetilde{c}+t\widetilde{h}\big{\\}},$
one finds a number $\tau\in]0,\tau^{\prime}[$ such that for any $t\in]0,\tau[$
one has

$\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,My\geq_{L}\widetilde{c}+t\widetilde{h}\big{\\}}=\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,My\geq_{L}\widetilde{c}\big{\\}}\\\
\hskip 28.45274pt\ +\
t\sup\big{\\{}\widetilde{h}^{T}z\;:\;z\in\mathbb{R}^{2n+m},\,M^{T}z=-b,\,z\geq_{L^{*}}0,\widetilde{c}^{T}z=\inf\limits_{My\geq_{L}\widetilde{c}}\,(-b)^{T}y\big{\\}}.$

Combining this with (34), we have

$\psi(c+th)=\psi(c)\\\
-t\sup\big{\\{}\widetilde{h}^{T}z\;:\;z\in\mathbb{R}^{2n+m},\,M^{T}z=-b,\,z\geq_{L^{*}}0,\,\widetilde{c}^{T}z=-\psi(c)\big{\\}},$
(35)

where the equality
$\psi(c)=\inf\big{\\{}(-b)^{T}y\;:\;y\in\mathbb{R}^{m},\,My\geq_{L}\widetilde{c}\big{\\}}$
follows from (34) if one takes $t=0$. Substituting $z=\begin{bmatrix}u\\\ v\\\
w\end{bmatrix}$ with $u,v\in\mathbb{R}^{n}$ and $w\in\mathbb{R}^{m}$ into
(35), one gets

$\begin{array}[]{rl}\psi(c+th)=\psi(c)-t\sup\big{\\{}&h^{T}u-h^{T}v\;\;:\;\
u,v\in\mathbb{R}^{n}_{+},\,w\in K,\\\ &Au-
Av+w=-b,\,c^{T}u-c^{T}v=-\psi(c)\big{\\}}.\end{array}$

Setting $x:=v-u$, one has

$\displaystyle\psi(c+th)$ $\displaystyle=\psi(c)$ $\displaystyle\hskip
8.5359pt-t\sup\big{\\{}-h^{T}x\;:\;x\in\mathbb{R}^{n},\,w\in
K,w=Ax-b,\,-c^{T}x=-\psi(c)\big{\\}}$
$\displaystyle=\psi(c)+t\inf\big{\\{}h^{T}x\;:\;x\in\mathbb{R}^{n},\,w\in
K,w=Ax-b,\,c^{T}x=\psi(c)\big{\\}}$
$\displaystyle=\psi(c)+t\inf\big{\\{}h^{T}x\;:\;x\in\mathbb{R}^{n},\,Ax\geq_{K}b,\,c^{T}x=\psi(c)\big{\\}}$
$\displaystyle=\psi(c)+t\inf\limits_{x\in\mathcal{S}{\rm(P)}}h^{T}x.$

This proves that (33) holds. $\hfill\Box$

##  7 Conclusions

Based on strict feasibility conditions and the duality theory in the conic
linear programming, we have shown that two optimal value functions of a conic
linear program, whether either the constraint system is linearly perturbed or
the objective function is linearly perturbed, have some nice continuity and
differentiability properties. It turns out that if the convex cone is non-
polyhedral, then the behaviors of the optimal value functions in question are
more complicated than that of the corresponding optimal value functions of a
linear program.

Properties of the solution maps of parametric conic linear programs and
generalizations of our results for infinite-dimensional conic linear
programming deserve further investigations.

###### Acknowledgements.

This work was supported by National Foundation for Science $\&$ Technology
Development (Vietnam) and Pukyong National University (Busan, Korea). The
first author was partially supported by the Hanoi National University of
Education under grant number SPHN20-07: “Differential Stability in Conic
Linear Programming”. The second author was supported by the National Research
Foundation of Korea Grant funded by the Korean Government
(NRF-2019R1A2C1008672).

## References

  * (1) Bonnans J.F., Shapiro A.: Perturbation Analysis of Optimization Problems. Springer-Verlag, New York (2000)
  * (2) Mordukhovich B.S.: Variational Analysis and Generalized Differentiation, I: Basic Theory. Springer, Berlin (2006)
  * (3) Mordukhovich B.S.: Variational Analysis and Generalized Differentiation, II: Applications. Springer, Berlin (2006)
  * (4) Gauvin J., Tolle J.W.: Differential stability in nonlinear programming. SIAM J. Control Optim. 15, 294–311 (1977)
  * (5) Auslender A.: Differential stability in nonconvex and nondifferentiable programming. Math. Program. Study 10, 29–41 (1979)
  * (6) Gauvin J., Dubeau F.: Differential properties of the marginal function in mathematical programming. Math. Program. Study 19, 101–119 (1982)
  * (7) Rockafellar R.T.: Lagrange multipliers and subderivatives of optimal value functions in nonlinear programming. Math. Program. Study 17, 28–66 (1982)
  * (8) Gauvin J., Dubeau F.: Some examples and counterexamples for the stability analysis of nonlinear programming problems. Math. Program. Study 21, 69–78 (1984)
  * (9) Thibault L.: On subdifferentials of optimal value functions. SIAM J. Control Optim. 29, 1019–1036 (1991)
  * (10) Yen N.D.: Stability of the solution set of perturbed nonsmooth inequality systems and application. J. Optim. Theory Appl. 93, 199–225 (1997)
  * (11) Lee G.M., Tam N.N., Yen N.D.: Stability of a class of quadratic programs with a conic constraint. Taiwanese J. Math. 13, 1823–1836 (2009)
  * (12) Mordukhovich B.S., Nam N.M., Yen N.D.: Subgradients of marginal functions in parametric mathematical programming. Math. Program. Ser. B 116, 369–396 (2009)
  * (13) An D.T.V, Yen N. D.: Differential stability of convex optimization problems under inclusion constraints. Appl. Anal. 94, 108–128 (2015)
  * (14) An D.T.V.: Subdifferentials of Optimal Value Functions in Parametric Convex Optimization Problems. Ph.D. Dissertation, Institute of Mathematics, Vietnam Academy of Science and Technology, Hanoi (2018)
  * (15) Gauvin J.: Formulae for the sensitivity analysis of linear programming problems. In: Approximation, Optimization and Mathematical Economics, 117–120. Physica, Heidelberg (2001).
  * (16) Thieu N.N.: Some differential estimates in linear programming. Acta Math. Vietnam. 41, 243–249 (2016)
  * (17) Ben-Tal A., Nemirovski A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, Philadelphia (2001)
  * (18) Luenberger D.G., Ye Y.: Linear and Nonlinear Programming. Internat. Ser. Oper. Res. Management Sci. 228, 4th ed., Springer, Cham (2016)
  * (19) Chuong T.D., Jeyakumar V.: Convergent conic linear programming relaxations for cone-convex polynomial programs. Oper. Res. Lett. 45, 220–226 (2017)
  * (20) Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton (1970)


# Cognitive Semantic Communication Systems Driven by Knowledge Graph

Fuhui Zhou‡, Yihao Li‡, Xinyuan Zhang†, Qihui Wu‡, Xianfu Lei†, and Rose
Qingyang Hu§
‡Nanjing University of Aeronautics and Astronautics, China,
§Utah State University, Logan, UT 84322 USA
†School of Information Science and Technology, Southwest Jiaotong University,
Chengdu, China
Email: _{<EMAIL_ADDRESS><EMAIL_ADDRESS>zxyleh@gmail.com,_
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>This work was
supported by National Key Research and Development Program of China under
Grant 2020YFB1807602, the National Natural Science Foundation of China under
Grant 62031012, and 62071223 and Grant 61931011, Young Elite Scientist
Sponsorship Program by CAST.

###### Abstract

Semantic communication is envisioned as a promising technique to break through
the Shannon limit. However, the existing semantic communication frameworks do
not involve inference and error correction, which limits the achievable
performance. In this paper, in order to tackle this issue, a cognitive
semantic communication framework is proposed by exploiting knowledge graph.
Moreover, a simple, general and interpretable solution for semantic
information detection is developed by exploiting triples as semantic symbols.
It also allows the receiver to correct errors occurring at the symbolic level.
Furthermore, the pre-trained model is fine-tuned to recover semantic
information, which overcomes the drawback that a fixed bit length coding is
used to encode sentences of different lengths. Simulation results on the
public WebNLG corpus show that our proposed system is superior to other
benchmark systems in terms of the data compression rate and the reliability of
communication.

###### Index Terms:

Cognition semantic communication, knowledge graph, T5 model, inference, error
correction

##  I Introduction

The wireless communication system has been flourishing and evolved from the
first generation (1G) to the latest fifth generation [1]. Those systems has
been developed based on the Shannon information theory. With the development
of the advanced channel coding scheme, such as low-density parity-check (LDPC)
codes and polar codes, the conventional communication system has gradually
approached the Shannon limit [2]. It is imperative to make breakthrough for
this limit to meet the unprecedented proliferation of mobile devices, the
increasing requirements of high data rate and the emerging of diverse ultra-
band wideband services [3].

Semantic communication proposed by Weaver and Shannon is promising to tackle
this issue and has been receiving ever increasing attention from both academic
and industry [4]. Different from the conventional wireless communication
systems that focus on the successful transmission of symbols from the
transmitter to the receiver, the semantic communication system pays more
attention to the semantic information at the transmitter and the meaning
interpreted at the receiver [3]. It can significantly reduce the amount of
data required to be transmitted and also improve the performance robustness.

Up to known, semantic communications can be realized by three paradigms. The
first one is the goal-oriented communication paradigm that only transmits the
important and necessary messages based on the goal-oriented metrics, such as
the control-theoretic accuracy proposed in [5] and the age-of-information-
based metrics proposed in [6], [7]. In this paradigm, semantic compression is
achieved by filtering out redundant messages that are less relevant to the
communication goal. The second paradigm is to embed raw data into a low-
dimensional space by using deep neural networks in order to compress source
information and achieve semantic communication. The authors in [8]-[10]
proposed a joint source channel codec framework based on the natural language
processing (NLP) technology, such as bi-directional long short-term memory
(BiLSTM) and transformer. The last one is to exploit a sharing knowledge base
between the source and destination to achieve semantic compression and
communication [3].

The first paradigm achieves semantic compression explainably and communication
based on the goal-oriented metrics. However, there have been no uniform
metrics for evaluating the achievable performance. Due to this fact, the first
paradigm is restricted to some specific wireless services or communication
environment [11]. The second paradigm relys on the large-scale deep learning
(DL) models to accurately and quickly recognize and extract intended semantic
information, and it does not require semantic metrics. Nevertheless, DL
normally requires a large number of high quality labeled data. Moreover, the
end-to-end operation is identified as a black-box process, which lacks
interpretability. The last one achieves semantic compression and communication
with the help of knowledge base without semantic metrics. Moreover, it has the
interpretability during the compression process due to the reasoning rules in
the knowledge base [3]. The third paradigm is envisioned to be the most
promising one [11]. However, there are few investigations that have focused on
this direction since it requires the interdisciplinary knowledge, such as
wireless communication, computer science, artificial intelligence, etc.

Figure 1: The proposed cognitive semantic communication framework driven by
the knowledge graph.

Motivated by those facts, a cognitive semantic communication system is
proposed by using knowledge graph, which is a sharing knowledge base between
the transmitter and the receiver. In order to develop a simple and general
solution for semantic information detection, the triples are viewed as
semantic symbols. Since the triples are more general form of semantic
organization and are inherently readable, our proposed system is
interpretable. Moreover, the pre-trained model is fine-tuned to recover
semantic information, which overcomes the drawback that a fixed bit length
coding is used to encode sentences of different lengths. Simulation results
demonstrate that our proposed system is superior to other benchmark systems in
terms of the data compression rate and the reliability of communication.

The remainder of this paper is organized as follows. Our proposed cognitive
semantic communication system is presented in Section II. Section III presents
knowledge graph and system implementation. Section IV presents simulation
results. Finally, the paper concludes with Section V.

##  II Cognitive Semantic Communication

In this section, a cognitive semantic communication system is proposed based
on the sharing knowledge graph between the transmitter and the receiver. The
framework for this system is shown in Fig. 1.

###  II-A Cognitive Semantic Communication Framework

In the traditional semantic communication system, the transmitter sends the
abstraction of semantic information and the receiver interprets its meaning
without inference. Our proposed cognitive semantic communication system has
the “cognitive” characteristic, which is enabled by knowledge graph. In the
proposed system, the information is not required to be completely transmitted
and only the important semantic information (such as the triple, namely, the
head entity, relation and tail entity) is transmitted. The receiver interprets
the meaning by inferring from the received information. Due to the inference
characteristic, our proposed cognitive semantic communication system has three
evident advantages. Firstly, a high semantic compression rate can be achieved
since only the important information is transmitted. Secondly, a robust
performance can be obtained due to the reason that the semantic error can be
corrected via inference driven by knowledge graph. Finally, the
interpretability of the communication process can be realized since the
triples of the knowledge graph have the comprehensibility. The details for the
proposed semantic communication system are presented as follows.

The framework of the proposed cognitive semantic communication system is shown
in Fig. 1. A source $S$ generates a message $m\in M$. $M$ is the set of all
the messages. $m$ carries the semantic information that $S$ transmits to $D$.
In this paper, the text transmission is considered as an example. In order to
transmit the semantic of message, semantic requires first to be expressed as a
formal way. According to the work in [2], semantics (meaning) are associated
to a knowledge system. Thus, in our work, the knowledge graph is exploited as
the knowledge system and the triples are exploited to represent semantic. The
semantic symbol is denoted as $s$, and $s$ is included in $S$, where $S$ is a
set of the semantic symbols. In order to improve effectiveness of
communication, the semantic symbol is abstracted from the message $m$. This
process is denoted as $s=f\left(m\right)$. The Text2KG aligner is designed to
implement the abstraction of the semantic symbol $s$ from message $m$.

After the semantic symbol is obtained, the semantic symbol is transmitted by
using the conventional communication modules (CCMs). Specifically, the
semantic symbol $s$ is encoded as $x$ in order to improve the transmission
efficiency. Then, the channel coding is performed and $b$ is obtained. At the
destination, the binary vectors are received and the semantic symbol code is
obtained by channel decoding. Note that the knowledge graph is exploited to
correct error in this process. After that, the semantic symbol is obtained by
using semantic symbol decoding.

Figure 2: An example diagrams the mapping message $m\in M$ to semantic symbol
$s\in S$

Finally, in order to reconstruct message $\hat{m}\in\hat{M}$ from the obtained
semantic symbol, where $\hat{M}$ is the reconstructed message set, the
semantic symbol recognition module is designed based on the NLP technology. In
this paper, different from the work in [9] that the joint source-channel codec
framework is achieved by end-by-end training transformer, a novel framework by
training a NLP technology at the receiver is proposed. Our framework can
overcome the drawback that a fixed bit length coding is used to encode
sentences of different lengths and results in low efficiency.

Note that since the mapping from $m$ to $s$ is many-to-one, the semantic
ambiguity may exist. In order to mitigate semantic ambiguity and implement the
triple-to-text conversion, the pre-training model Text-to-Text Transfer
Transformer model (T5) is fine-tuned on our training corpus [13]. Since the
pre-training model T5 is fed by billions of sentences, it can take context
into account when the reconstructed text is generated. For example, as shown
in Fig. 2, $S$ generates the message ‘Batchoy includes chicken’. However,
‘chicken’ can be translated as animal or meat in different contexts. It
results in the semantic ambiguity. The fine-tuned T5 model is used to
reconstruct the text ‘Chicken is an ingredient of Batchoy.’ at the receiver
side. It is observed that the semantic ambiguity can be removed. In contrast,
the conventional communication system cannot effectively tackle the semantic
redundancy or semantic ambiguity.

###  II-B The Feasibility and Reasonability of Our Proposed Framework.

The semantic information theory is used to verity the feasibility and
reasonability of our proposed cognitive semantic communication system. It is
assumed that the source randomly transmits a message $m$ with the probability
$\Pr(m)$. Thus, a massage entropy $H\left(M\right)$ of the source can be
expressed as

$H\left(M\right)=-\underset{m\epsilon
M}{\mathop{\sum}}\,\Pr(m)\log_{2}\Pr(m).$ $None$

According to the work in [2], the logical probability $\Pr(s)$ of the semantic
symbol $s$ can be expressed as

$\Pr(s)=\underset{s=f\left(m\right),m\in M}{\mathop{\sum}}\,\Pr(m).$ $None$

Thus, based on eq. (2), the semantic entropy $H\left(S\right)$ related to the
semantic symbol set $S$ is

$H\left(S\right)=-\underset{s\epsilon
S}{\mathop{\sum}}\,\Pr(s)\log_{2}\Pr(s).$ $None$

According to the classic information theory, $H\left(S\right)$ can be written
as

$H\left(S\right)=H\left(S/M\right)+I\left(M;S\right),$ $None$

where $H\left(S/M\right)$ represents the uncertainty of the random variable
$S$ under the condition of the known random variable $M$ and
$I\left(M;S\right)$ represents the average mutual information between $S$ and
$M$. Since $I\left(M;S\right)=H\left(M\right)-H\left(M/S\right)$, the semantic
entropy can be rewritten as

$H\left(S\right)=H\left(M\right)+H\left(S/M\right)-H\left(M/S\right).$ $None$

Since the mapping from $m$ to $s$ is often many-to-one by semantic symbol
abstraction, $H\left(S\right)$ is always smaller than $H\left(M\right)$. Thus,
there exists an entropy loss $H\left(M\right)-H\left(S\right)$. The reducing
entropy of the source is a desired compression of the source without a ‘real’
semantic loss, since the messages that contain the same semantics have many
equivalent forms as shown in Fig. 2. For example, ‘Alba Iulia is located in
Romania.’ and ‘Alba Iulia is in Romania.’ are different in the form. However,
they have the same semantic information. Our proposed Text2KG aligner can
align them to the same triple ‘$<$H$>$ Alba Iulia $<$R$>$ country $<$T$>$
Romania ’.

Figure 3: An example for text transmission achieved by using our proposed
cognitive semantic communication system.

##  III Knowledge Graph and System Implementation

In this section, the details for the knowledge graph and the implementation of
our proposed cognitive semantic communication system are presented. An example
for text transmission achieved by using our proposed cognitive semantic
communication system is shown in Fig. 3.

###  III-A Knowledge Graph

Knowledge graph, as the core of cognitive semantic communication, is a
semantic network that reveals the relationship among entities in the form of
graphs. It generally consists of a triple (head, relation, tail) or (entity,
attribute, value) to express facts. Its construction methods are usually
divided into top-down and bottom-up approaches. Large-scale general knowledge
graph used in our cognitive semantic communication is always constructed top-
down including four procedures, namely, information extraction, knowledge
fusion, knowledge processing, and knowledge update [14].

###  III-B Semantic Symbol Abstraction

The semantic symbol abstraction aims to detect and extract the specific
semantic information contained in the message. The implementation of the
semantic symbol abstraction is to align the input text $m$ with the
triplet$(h,r,t)$, where $h$, $r$ and $t$ denote the head entity, the relation
and the tail entity of the knowledge graph, respectively. It is realized by an
Text2KG alignment algorithm, as shown in Table 1 [13]. Note that for each
sentence in the input text, all triples that have $h$ and $t$ are matched.
Moreover, each triple can align to multiple sentences and each sentence can
have multiple triples aligned to it. The relations are not required to be
matched since there are many ways to express them. Similar to the work in
[13], the relation can be expressed as long as the message mentions the head
entity and tail entity.

TABLE I: The alignment algorithm Algorithm 1: The Text2KG alignment algorithm
---
alignment_triples $\leftarrow$ $\left[\ \right]$
for all sentences $s$ $\in$ input text do
for all triples$(h,r,t)$ $\in$ KG do
if s.contains($h$) and s.contains($t$) then
alignment_triples.add($(h,r,t)$)
end if
end for
end for

###  III-C Conventional Communication Modules

After the semantic symbols are obtained, in order to complete semantic
communications, those symbols are transmitted by using the conventional
communication modules, namely, semantic symbol coding, channel coding,
channel, channel decoding and semantic symbols decoding. Specifically,
according to [15], for a propositional logic with finite propositions, the
size of all possible interpretations (worlds) is finite. Thus, the number of
entities and relations in the knowledge graph which describes the world is
finite and it ensures that the semantic symbol code has a limited length.
Firstly, in order to achieve semantic symbol coding, a dictionary
$\left(key,value\right)$ is created. It enables the head entity, tail entity
and relation of the knowledge graph to be uniquely mapped as integers.
Secondly, a binary vector $x$ is obtained by encoding each integer with a
fixed length. This process is denoted as the semantic symbol encoding (SSC).

In order to improve the communication reliability, the channel coding module
is applied and the coded binary vector set $B$ is obtained. Then, the set $B$
is transmitted over the channel. Note that the binary channel is considered in
this paper. Since the channel is noisy, errors can occur during transmission.
In order to improve the robustness of our proposed system, channel decoding is
implemented by exploiting knowledge graph to correct error. The process of the
correction is to traverse the semantic symbols in the knowledge graph to find
the most similar one observed at the receiver. The details for the correction
algorithm denoted as Algorithm 2 can be found in Table II. Semantic symbol
decoding is the reverse process of semantic symbol encoding. After semantic
symbol decoding, the reconstructed semantic symbol $\hat{S}$ is achieved.

TABLE II: The correction algorithm Algorithm 2: The correction algorithm based
on the KG
---
Input: $o$ is the binary vector observed at the receiver,
$KG\\_coding$ is the coding of all triples in the KG
function similar ($a$, $b$)
sim $\leftarrow$ 0
for $i$ $\leftarrow$ 0 to len($b$) by 1 do
if a[$i$] != b[$i$] then
sim++
end for
return sim
end function
tmp $\leftarrow$ $\left[\ \right]$
for each $code$ $\in$ $KG\\_coding$ do
tmp.add(similar ($o$, $code$))
$o$ $\leftarrow$ $KG\\_encode$[tmp.index(max(tmp))]
Output: $o$ is the corrected binary vector

###  III-D Semantic Symbol Recognition

After the semantic symbol is obtained, in order to interpret the meaning of
semantic information, the crucial process of our proposed system is to
transform triples into text. This process needs to exploit the NLP technology.
In this paper, the T5 model [12] is fine-tuned on the local dataset in order
to convert triples in the knowledge graph into natural text. Specifically, the
triples in the dataset need to be concatenated as $head\ relation\\_1\
tail\\_1,....,relation\\_n\ tail\\_n$ for inputing into T5.

##  IV Simulation Results

In this section, simulation results are presented to evaluate the performance
of the proposed cognitive semantic communication system and compare it with
that of the traditional communication system realized by the separate source
and channel coding technologies under the binary symmetric channel (BSC).

###  IV-A Dataset and Finetuning Parameters

The training set of WebNLG English dataset [13] is used to fine-tune the T5
model. It contains knowledge graphs and text from various domains including
Airport, Artist, Astronaut, Athlete, Building, Celestial Body, City, Comics
Character, Food, Mode of Transportation, Monument, Politician, Sports Team,
University and Written Work [13]. The test sets include three additional
domains, namely, Film, Scientist, and Musical Work. The T5 model is fine-tuned
on the training sets for 100 steps with a learning rate of 0.0001. We compare
the performance of the proposed system with the benchmark systems by
transmitting the text in the test set.

Split Number of Samples
---
Train(T-G Pairs) 35426
Test(T-G Pairs) 4464
TABLE III: Number of texts and knowledge graph pairs in the training, test
sets of the WebNLG English dataset.

###  IV-B Performance Comparison

In order to guarantee the fairness of performance comparison, the channel
coding scheme of our proposed system is the same as that of the benchmark
communication systems, namely, the binary convolutional codes under BSC.
Moreover, two source coding schemes are exploited for the benchmark systems,
namely, Huffman and fixed-length coding. In this paper, the fixed-length
coding scheme adopts 7 bits for each char since the corpus is case-sensitive
and contains special characters character. It is well known that the variable-
length coding is more efficient than the fixed-length coding. To demonstrate
the superiority, the fixed-length coding is chosen as the source coding of our
proposed system.

Figure 4: The number of bits required to be transmitted by using different schemes versus the sentence length. Figure 5: The number of bits required to be transmitted by using different schemes versus the number of texts. Figure 6: The semantic similarity score versus the BSC wrong parameter $p$. Figure 7: The BLEU score versus the BSC wrong parameter $p$. Lossless | TX: The leader of Aarhus is Jacob Bundsgaard.
---|---
| RX: The leader of Aarhus is Jacob Bundsgaard.
Rephrasing but lossless semantics | TX: Aarhus Airport’s runway length is 2702.0.
| RX: The runway length of Aarhus Airport is 2702.0.
Align redundant information | TX: Adolfo Suarez Airport is found in San Sebastian de los Reyes.
| RX: Adolfo Suarez Airport is located in San Sebastian de los Reyes, Madrid.
An inexplicable error | TX: Aarhus Airport’s runway length is 2702.0.
| RX: Asam pedas is a dish from Sumatra.
Disambiguation | TX: Batchoy includes chicken.
| RX: Chicken is an ingredient of Batchoy.
TABLE IV: Cases which are transmitted and received using our proposed system
when $p=0.1$.

In traditional communication systems, the symbol error rate (SER) is used to
evaluate the communication performance. However, it is inappropriate for
semantic communication since different sentences at the transmitter and
receiver possibly have the same semantic information [9]. In order to tackle
this issue, the Bilingual evaluation understudy (BLEU) and semantic similarity
score are widely used to evaluate the performance of semantic communication
and that of the traditional communication. BLEU score is usually used to
evaluate the machine translation results. However, the BLEU score can only
compare the difference among words of two sentences rather than their semantic
information. Thus, in this paper, the semantic similarity score is used to
measure performance [9]. According to the cosine similarity, the sentence
similarity between the original sentence $m$ and the recovered sentence
$\hat{m}$ is calculated as

$score\left(\hat{m},m\right)=\frac{{{B}_{\text{ }\\!\\!\Phi\\!\\!\text{
}}}\left(m\right){{B}_{\text{ }\\!\\!\Phi\\!\\!\text{
}}}{{\left({\hat{m}}\right)}^{T}}}{\left|\left|{{B}_{\text{
}\\!\\!\Phi\\!\\!\text{
}}}\left(m\right)\left|\left|~{}\right|\right|{{B}_{\text{
}\\!\\!\Phi\\!\\!\text{ }}}\left({\hat{m}}\right)\right|\right|},$ $None$

where ${{B}_{\text{ }\\!\\!\Phi\\!\\!\text{ }}}$, representing bidirectional
encoder representations from transformers (BERT), is a large pre-trained model
used for extracting the semantic information. It is trained on an ultra large-
scale corpus. Compared with the BLEU score, BERT has been fed by billions of
sentences [9]. Therefore, it can recognize semantic information effectively.

Fig. 4 shows the number of bits required to be transmitted versus the sentence
length. The sentence length depends on the number of characters. It is quite
evident that our proposed cognitive semantic communication system obtains the
highest text compression rate among the benchmark systems, especially for long
sentences. The reason is that the proposed system can capture the semantic
equivalence and realize the semantic compression. Moreover, knowledge graphs
used as the shared knowledge base on both the transmitter and receiver are
benefical for further improving the coding efficiency. Fig. 5 shows the number
of bits required to be transmitted versus the number of texts. The number of
texts depends on the number of sentences. As shown in Fig. 5, the proposed
cognitive semantic communication system transmits the same number of texts
with less data compared with all benchmark systems. It further indicates that
the proposed system has a superior compression rate.

Fig. 6 shows that the semantic similarity score versus the BSC wrong parameter
$p$. The semantic similarity score is used to measure the semantic recovery
performance. Note that $p$ represents the channel wrong parameter and a larger
$p$ represents a worse the channel environment. As shown in Fig. 6, the scores
of the benchmark systems are all close to 1 and higher than our proposed
system when $p<0.05$. Since the channel coding corrects the errors that occur
during transmission, the benchmark systems can recover the text without any
loss at the receiver. However, the semantic information detection in our
system has data loss which is actually the reason that our system can transmit
less data with high semantic fidelity. Meanwhile, the score of our system is
also higher than 0.9, which means that the messages can be well understood.
When $p>0.05$, the channel environment is poor, the channel coding cannot
correct all the error. In this case, the performance of the benchmark systems
degrades rapidly. In contrast, since our proposed cognitive semantic
communication system can more effectively capture and recover semantic
information and confront errors, it can generate easy-to-understand messages.
Fig. 7 shows the same tendency with BLEU score as the criteria for performance
measurement. It is obviously seen that our proposed system is more competitive
and robust in poor channel environments. A few cases between the transmitter
and receiver are shown in Table IV in order to demonstrate the efficiency of
our proposed cognitive semantic communication system.

##  V Conclusion

A cognitive semantic communication system was proposed by using knowledge
graph. Moreover, a simple, general and interpretable solution for semantic
information detection was proposed to improve data compression rate.
Furthermore, the T5 model was adjusted to recover semantic information in
order to overcome the drawback that a fixed bit length coding is used to
encode sentences of different lengths and results in low efficiency. The
proposed cognitive semantic communication system underpins promising
performance. Simulation results demonstrated that the proposed system has a
superior data compression rate and communication reliablity.

## References

  * [1] Q. Wu, T. Ruan, F. Zhou, Y. Huang, F. Xu, S. Zhao, Y. Liu, and X. Huang, “A unified cognitive learning framework for adapting to dynamic environment and tasks,”  _IEEE Wirel. Commun._ , to be published, 2021.
  * [2] E. C. Strinati and S. Barbarossa, “6G networks: Beyond Shannon towards semantic and goal-oriented commeunications,”  _Comput. Netw._ , vol. 190, p.107930, 2021.
  * [3] G. Shi, D. Gao, X. Song, J. Chai, M. Yang, X. Xie, L. Li, and X. Li, “A new communication paradigm: From bit accuracy to semantic fidelity,”  _arXiv preprint arXiv:2101.12649_ , 2021.
  * [4] Y. Xu, J. Wang, Q. Wu, A. Anpalagan, and Y. Yao, “Opportunistic spectrum access in cognitive radio networks: Global optimization using local interaction games,”  _IEEE J Sel Top Signal Process_ , vol. 6, pp. 180-194, 2012.
  * [5] P. Popovski, O. Simeone, F. Boccardi, D. Gunduz, and O. Sahin, “Semantic-effectiveness filtering and control for post-5g wireless connectivity,”  _J Indian Inst Sci_ , vol. 100, pp. 435-443, Dec. 2019.
  * [6] M. Kountouris and N. Pappas, “Semantics-empowered communication for networked intelligent systems,”  _IEEE Commun. Mag._ , vol. 59, no. 6, pp. 96-102, June. 2021.
  * [7] A. Maatouk, M. Assaad, and A. Ephremides, “The age of incorrect information: An enabler of semantics-empowered communication,”  _arXiv preprint arXiv:2012.13214_ , 2020.
  * [8] N. Farsad, M. Rao, and A. Goldsmith, “Deep learning for joint source-channel coding of text,” in _Proc. IEEE Int. Conf. Acoust., Speech Signal Process._ , Calgary, AB, Canada, pp. 2326-2330, Apr. 2018.
  * [9] H. Xie, Z. Qin, G. Y. Li, and B. -H. Juang, “Deep learning enabled semantic communication systems,”  _IEEE Trans. Signal Process._ , vol. 69, pp. 2663-2675, 2021.
  * [10] Z. Weng and Z. Qin, “Semantic communication systems for speech transmission,”  _IEEE J. Sel. Areas Commun._ , vol. 39, no. 8, pp. 2434-2444, Aug. 2021.
  * [11] H. Seo, J. Park, M. Bennis, and M. Debbah, “Semantics-native communication with contextual reasoning,”  _arXiv preprint arXiv:2108.05681_ , 2021.
  * [12] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and J. Liu, “Exploring the limits of transfer learning with a unified text-to-text transformer,”  _arXiv preprint arXiv:1910.10683_ , 2019.
  * [13] O. Agarwal, H. Ge, S. Shaker, and R. Al-Rfou, “Knowledge graph based synthetic corpus generation for knowledge-enhanced language model pre-training,”  _arXiv preprint arXiv:2010.12688_ , 2020.
  * [14] Q. Wu, G. Ding, Y. Xu, S. Feng, Z. Du, J. Wang, and K. Long, “Cognitive internet of things: a new paradigm beyond connection,”  _IEEE Internet Things J._ , vol. 1, pp. 129-143, 2014.
  * [15] F. Zhou, Y. Wu, and Q. Wu, “Resource allocation based on deep reinforcement learning for wideband cognitive radio network,”  _URSI GASS_ , to be published, 2021.