# Efficient numerical algorithm for multi-level ionization of high-atomic-
number gases

Aiqi Cheng  Roman Samulyak  Department of Applied Mathematics and Statistics,
Stony Brook University, Stony Brook, NY 11794, United States  Computational
Science Initiative, Brookhaven National Laboratory, Upton, NY 11973

###### Abstract

An efficient numerical algorithm for the laser driven multi-level ionization
of high-atomic-number gases is proposed and implemented in an electromagnetic
particle-in-cell code SPACE. The algorithm is based on analytical solutions to
the system of differential equations describing ionization evolution. Using
analytical solutions resolves the multiscale issue of ionization due to
different characteristic time scales of ionization processes and the main code
time step. Algorithm efficiency is improved by using a locally-reduced system
of differential equations. The effects of the orbital quantum numbers and
their projections have been examined. The algorithm is applied to the study of
ionization injection of electrons into laser-driven plasma wakefields.

###### keywords:

Laser plasma interaction , ADK model , multi-level tunneling ionization ,
Particle-in-cell , Ionization injection

††journal: Journal of Computational Physics

##  1 Introduction

An accurate numerical model for ionization of gases by high-power lasers is
critical for numerical simulations of laser-plasma interactions and for the
laser-plasma wakefield acceleration (LPWA) of particles in particular[1, 2,
3]. Although modern lasers used for LPWA are capable of completely ionizing
hydrogen gas during several periods of laser filed oscillation and within a
small fraction of the laser pulse duration, the assumption of a pre-ionized
plasma is not accurate for laser intensities close to the tunneling ionization
threshold [4, 5]. Ionization effects such as creation of plasma through
tunneling ionization, frequency up-shifting of the laser, harmonic generation,
and scattering instabilities play a major role in the laser wakefield
acceleration process. An accurate modeling of the laser ionization of gases
significantly improves the resolution of such processes.

The large interest for multi-level ionization of high-atomic-number gases in
the context of LPWA is driven by ideas of the ionization injection of
electrons into plasma wakes [9, 10, 11], a technique that may significantly
reduce the complexity of the LPWA method and improve the quality of resulting
accelerated electron beams. While the ionization of hydrogen, a typical medium
for LPWA experiments, is easy to resolve numerically, multi-level ionization
of high-atomic-number gases presents a set of more complex modeling
challenges. These include the multiscale nature of ionization, complex atomic
states characterized by sets of orbital quantum numbers and their projections,
and various software development issues such as a significant increase of the
memory usage if the evolution of multiple ionization states is tracked at
every computational mesh block in the simulation domain. In this paper, we
propose a numerical alorithm for electromagnatic Particle-in-Cell (PIC) codes
that improves the accuracy and numerical efficiency compared to previously
published models [6]. PIC [7, 8] is a common method for the simulation of
laser-plasma interactions and LPWA which solves the Vlason-Maxwell equations
using a hybrid particle-grid method. In PIC, the electromagnetic Maxwell
equations are discretized and updated on a grid while the distribution
functions of charged particles is sampled by a set of Lagrangian particles,
the motion of which is coupled to the mesh via currents.

The algorithm has been implemented in SPACE, a parallel, relativistic, three-
dimensional particle-in-cell code developed for the simulation of
electromagnetic fields, relativistic particle beams, and plasmas [13]. A
distinct feature of SPACE is a software module for atomic physics
transformations.

This paper is organized as follows. In Section 2, we present the main
equations governing laser tunneling ionization of high-atomic-number gases.
Section 3 describes details of the mathematical model and presents
verification tests. We conclude this paper by Section 4 with a summary of our
results and plans for the future work.

##  2 Laser ionization of high-Z gases

The Ammosov–Delone–Krainov (ADK) model [12, 6] for tunneling ionization in
high-atomic-number gasses derives the following expression for the probability
of ionization

$\displaystyle W_{lm}=$
$\displaystyle\omega_{\alpha}\sqrt{\frac{3{n^{*}}^{3}E_{L}}{\pi
Q^{3}E_{a}}}\frac{Q^{2}}{2{n^{*}}^{2}}\left(\frac{2e}{n^{*}}\right)^{2n^{*}}\exp{\left[-\frac{2E_{a}}{3E_{L}}\left(\frac{Q}{n^{*}}\right)^{3}\right]}\times$
(1) $\displaystyle\frac{(2l+1)(l+|m|)!}{2\pi
n^{*}2^{|m|}(|m|)!(l-|m|)!}\left(2\frac{E_{a}Q^{3}}{E_{L}{n^{*}}^{3}}\right)^{2n^{*}-|m|-1}.$

Here $\omega_{a}=\alpha^{3}c/r_{e}=4.13\times 10^{16}s^{-1}$ is the atomic
unit frequency, $E_{a}=510\ GV/m$ is the atomic unit of Electric field, and
$E_{L}\ (GV/m)$ represents the strength of the local laser electric field. $l$
and $m$ are the electron’s orbital quantum number and projection of the
orbital quantum number respectively, $n^{*}=Q\sqrt{U_{H}/U_{ion}}$ is the
effective principle quantum number, and $U_{H}$ and $U_{ion}$ are the
ionization potential of hydrogen and ion of the material being ionized,
respectively. $Q$ is the charge number after ionization.

Denoting the number density of atoms in the neutral ground state as $n_{0}$
and the number density of ions ionized to the state $j+$ as $n^{j+}$, the
system of equation governing the ionization dynamics is as follows

$\displaystyle\frac{dn_{0}}{dt}$ $\displaystyle=-W_{0}*n_{0}(t),$
$\displaystyle\frac{dn^{+}}{dt}$
$\displaystyle=W_{0}*n_{0}(t)-W_{1}*n^{+}(t),$
$\displaystyle\frac{dn^{(Z-1)+}}{dt}$
$\displaystyle=W_{Z-2}*n^{(Z-2)+}(t)-W_{Z-1}*n^{(Z-1)+}(t),$ (2)
$\displaystyle\frac{dn^{Z+}}{dt}$ $\displaystyle=W_{Z-1}*n^{(Z-1)+},$

where $Z$ denotes the gas atomic number. We would like to note that because
overall time scales of LPWA simulations are short compared to recombination
processes in gases, the recombination terms were not included in the governing
system of equations.

This system of equations must be solved independently at each numerical grid
cell of the computational domain which presents a set of challenging numerical
issues. First, the system includes multiple time scales associated with short
characteristic times for ionization dynamics of each individual level and the
overall characteristic time of the electromagnetic problem being studied.
Second, recording the evolution dynamics of all individual ionization levels
in each computational mesh cell requires a significant increase of the total
memory. In the next Section, we propose an efficient numerical algorithm for
multi-level ionization of high-atomic-number gases that resolves these and
other issues, as well as a set of verification tests for the algorithm.

##  3 Numerical model and its verification

We start with writing equations (2) in the following matrix form:

$\begin{bmatrix}\dot{n_{0}}\\\ \dot{n}^{+}\\\ \dot{n}^{2+}\\\ ...\\\
\dot{n}^{(Z-1)+}\\\
\dot{n}^{Z+}\end{bmatrix}=\begin{bmatrix}-W_{0}&0&0&...&0&0\\\
W_{0}&-W_{1}&0&...&0&0\\\ 0&W_{1}&-W_{2}&...&0&0\\\
\vdots&...&...&\ddots&\vdots&\vdots\\\ \vdots&...&...&W_{Z-2}&-W_{Z-1}&0\\\
0&...&...&0&W_{Z-1}&0\end{bmatrix}\begin{bmatrix}n_{0}\\\ n^{+}\\\ n^{2+}\\\
...\\\ n^{(Z-1)+}\\\ n^{Z+}\end{bmatrix}$ (3)

Since the ionization probabilities contained in the matrix depend on the local
electric field values, our model is based on the natural assumption that
ionization probabilities do not change within each time step of the overall
electromagnetic simulation which updates states of the electromagnetic field.
Assuming that the ionization probabilities are updated at the beginning of
each time step of the overall simulation denoted at $t$, we compute the
analytical solution to (3) at the end of the time step $t+dt$ in terms of the
eigenvalues $\lambda_{i}=-W_{i}(t)$ and eigenvectors $\vec{V}_{j}$ of the
corresponding matrix. The general solution is:

$n^{i+}(t+dt)=\sum\limits_{j=0}^{Z}C_{j}\vec{V}_{j}(i)e^{-W_{j}(t)dt}$ (4)

The initial conditions at each time step $n^{j+}(t)$, $j=0,\ldots,Z$ are used
to compute coefficients $C_{j}$.

$\begin{bmatrix}\vec{V}_{0}&|&\vec{V}_{1}&...&|&\vec{V}_{Z}\end{bmatrix}\begin{bmatrix}C_{0}\\\
C_{1}\\\ \vdots\\\ C_{Z}\end{bmatrix}=\begin{bmatrix}n_{0}(t)\\\ n^{+}(t)\\\
\vdots\\\ n^{Z+}(t)\end{bmatrix}$ (5)

Analytic solutions are computed independently in every computational cell and
the population of ionization levels $n^{i+}$ is updated. Using analytical
solution efficiently resolves the multiscale nature of ionization evolution
and it eliminates the need for fractional time stepping for a numerical solver
for the ODE system (2), as implemented in some electromagnetic codes. Explicit
expressions for the analytical solutions subject to another simplifying
approximations that reduces the total storage will be presented later in this
Section.

The second challenge is associated with strong dependence of ionization
probabilities on the orbital quantum numbers and their projections for
electrons being ionized. A schematic of the electron structure of krypton, the
medium of interest for the two-color injection in laser plasma wakefield
acceleration, is shown in Figure 1.

Figure 1: Schematic the electron structure of krypton

In the present implementation, we assume that electrons are ionized starting
from out-most orbitals and their ionization probabilities are computed
according to the quantum numbers and their projections as indicated in Figure
1. However, we also investigated other scenarios in which after removing the
first two electrons from the $4p$ orbital, the unoccupied p-orbitals coupled
to produce five-fold degenerate singlet-$d$, nondegenerate singlet-$s$, and
triplet-$s$ states, and similar transformations in the lower orbitals. Since
we observed negligibly small changes in the overall ionization dynamics, we
compute probabilities based on quantum numbers presented in Figure 1.

The final challenge is associated with a significant increase of memory
allocation for computing ionization processes. To store all ionization levels
in krypton, 36 floating point numbers must be added to each computational
cell. Of course, the total number of ionization levels could be reduced if
ionization beyond some $N+$, $N<Z$, is unlikely at given laser parameters.
This, however, would require a preliminary study for each new simulation
setting, and fine-tuning of the ionization model for every gaseous material
involved in the laser-matter interaction.

We performed detailed studies of the ionization dynamics of various ionization
levels for different laser settings and concluded that only 2-3 intermediate
levels are populated at any moment of time, with the population of lower and
higher levels effectively approaching zero. Figure 2(a) shows the evolution of
ionization levels in krypton interacting with a $CO_{2}$ laser pulse. A 4J
laser pulse with 2ps duration was used and the laser wavelength was 9.2$\mu
m$. The data was collected from a point on the laser propagation axis. The
highly oscillatory gray line shows, in normalized units, the laser amplitude
evolution at the given point. We observe that the density of neutrals reduces
to zero within 0.35 ps after the laser pulse arrival. Due to a high ionization
probability, this happens at a low laser field amplitude. The density of $Kr+$
rapidly grows and then reduces to zero at about 0.5 ps. Higher ionization
levels undergo a similar dynamics. As the laser amplitude reduces from its
maximum after 2.5 ps, the population of the ionization level $Kr^{10+}$ slowly
reduces and the levels $Kr^{11+}$ and $Kr^{12+}$ slowly grow but their
population remains at the order of magnitude of 1%. Similar dynamics occurs in
other locations of the computational domain, off the laser axis, except that
the maximum ionization level is lower due to lower laser field intensities. We
observe that at any time, the effectively non-zero population is present for
only 2-3 ionization levels.

This observation allowed us to replace the full system of equations for all
ionization levels by a reduced-order system containing only 3 or 4 ionization
levels which is specified independently for each computational cell. The
active ionization levels are shifted to the higher ones independently in each
computational cell when the population of the lowest level drops below a
prescribed threshold. Figure 2 presents a comparison of the evolution of
ionization levels along the laser axis computed by analytic solutions to the
full system of ODE’s (3). The reduced 4-level system of equations describes
this process very accurately. We do not plot the corresponding solution
obtained with the 4-level system since there is no visible difference with the
plot 2(a) obtained with the full system of ODE’s. Instead, we plot the
evolution of solution errors for the reduced 4-level system in Figure 2(b) and
observe that errors are of the order $10^{-4}$ for the intermediate states and
for the final dominant ionization state $Kr^{10+}$. Errors of the partially
ionized states $Kr^{11+}$ and $Kr^{12+}$ are on the order of $10^{-3}$, but
these states contribute very small quantity of electrons to the final
superposition state. Since errors in the final ionization states partially
compensate each other, the relative error of the electron density, depicted in
Figure 2(c), demonstrates high overall accuracy of the method.

(a) Full 36-level system of equations

(b) Errors for 4-level system of equations

(c) Relative error of the electron density

Figure 2: (a) Evolution of the relative population of ionization levels along
the laser axis computed by analytical solutions to the full system of ODE’s
(3) containing 36 ionization levels. (b) Errors of the relative population of
ionization levels for solutions with a reduced 4-level system of equations.
(c) Relative errors of the electron density for solutions with a reduced
4-level system of equations. A 4J, 2 ps $CO_{2}$ laser pulse propagated in
krypton gas with the neutral density of 2.e17 1/cc was used.

The analytical solution for the reduced 4-level system is:

$\displaystyle n_{p}(t+dt)$ $\displaystyle=n_{p}(t)*e^{-W_{p}*dt}$ (6)
$\displaystyle n_{p+1}(t+dt)$
$\displaystyle=n_{p}(t)*\frac{W_{p}}{W_{p}-W_{p+1}}*(e^{-W_{p+1}dt}-e^{-W_{p}dt})+n_{p+1}(t)*e^{W_{p+1}dt}$
(7) $\displaystyle n_{p+2}(t+dt)$
$\displaystyle=n_{p}(t)*\left(\frac{W_{p}W_{p+1}e^{-W_{p+2}dt}}{(W_{p}-W_{p+2})(W_{p+1}-W_{p+2})}-\frac{W_{p}W_{p+1}e^{-W_{p+1}dt}}{(W_{p}-W_{p+1})(W_{p+1}-W_{p+2})}\right.$
$\displaystyle\left.+\frac{W_{p}W_{p+1}e^{-W_{p}dt}}{(W_{p}-W_{p+1})(W_{p}-W_{p+2})}\right)$
$\displaystyle+n_{p+1}(t)*\left(\frac{(W_{p}W_{p+1}-W_{p+1}W_{p+2})e^{-W_{p+2}dt}}{(W_{p}-W_{p+2})(W_{p+1}-W_{p+2})}-\frac{(W_{p}W_{p+1}-W_{p+1}^{2})e^{-W_{p+1}dt}}{(W_{p}-W_{p+1})(W_{p+1}-W_{p+2})}\right)$
$\displaystyle+n_{p+2}(t)*\left(\frac{(W_{p+2}^{2}+W_{p}W_{p+1}-W_{p}W_{p+2}-W_{p+1}W_{p+2})e^{-W_{p+2}dt}}{(W_{p}-W_{p+2})(W_{p+1}-W_{p+2})}\right)$
(8) $\displaystyle n_{p+3}$
$\displaystyle=n_{p}(t)*\left(1+\frac{W_{p}W_{p+1}e^{-W_{p+2}dt}}{(W_{p}-W_{p+2})(W_{p+1}-W_{p+2})}+\frac{W_{p}W_{p+2}e^{-W_{p+1}dt}}{(W_{p}-W_{p+1})(W_{p+1}-W_{p+2})}\right.$
$\displaystyle\left.-\frac{W_{p+1}W_{p+2}e^{-W_{p}dt}}{(W_{p}-W_{p+1})(W_{p}-W_{p+2})}\right)$
$\displaystyle+n_{p+1}(t)*\left(1+\frac{(W_{p}W_{p+1}-W_{p+1}W_{p+2})e^{-W_{p+2}dt}}{(W_{p}-W_{p+2})(W_{p+1}-W_{p+2})}+\frac{(W_{p}W_{p+2}-W_{p+1}W_{p+2})e^{-W_{p+1}dt}}{(W_{p}-W_{p+1})(W_{p+1}-W_{p+2})}\right)$
$\displaystyle+n_{p+2}(t)*\left(1+\frac{(W_{p+2}^{2}+W_{p}W_{p+1}-W_{p}W_{p+2}-W_{p+1}W_{p+2})e^{-W_{p+2}dt}}{(W_{p}-W_{p+2})(W_{p+1}-W_{p+2})}\right)+n_{p+3}(t),$
(9)

where $p$ denoted the lowest ionization level of the system. Initially, $p=0$
uniformly in the computational domain, and the value of $p$ increases non-
uniformly after the cut-off criteria is met in a specific computational cell.

The corresponding reduced 3-level system of ODE’s has also been tested. Since
numerical simulations with the 3-level system showed increased errors in
certain parts of the computational domain, the 4-level system was selected as
the most optimal solution that optimizes the accuracy and numerical cost.

##  4 Implementation in SPACE and numerical examples

The numerical algorithm for multi-level ionization of high-atomic-number gases
was implemented as a module in SPACE [13], a parallel, relativistic, three-
dimensional particle-in-cell code developed for the simulation of
electromagnetic fields, relativistic particle beams, and plasmas. The
algorithm proposed in this paper extends a set of atomic physics algorithms
previously implemented in SPACE that resolve single-electron ionization,
recombination, and electron attachment to dopants in dense neutral gases.
These algorithms were used for longer-time-scale processes compared to LPWA
and can be illustrated by SPACE simulations, performed in support of the
experimental program on the high-pressure hydrogen gas-filled radio frequency
cavity in the Mucool Test Area at Fermilab [14, 15]. The previous SPACE
implementation also employed the ADK ionization model for hydrogen use for the
simulation of LPWA driven by a CO2 laser [17, 18].

The new multi-level ionization model enabled simulation studies of ionization
injection of electrons into wakes created by a $CO_{2}$ laser pulse in high-
atomic-number materials such as krypton. After the plasma wakes are excited by
the $CO_{2}$ laser, a separate high-intensity near-infrared laser with a low
normalized vector potential will inject electrons through ionization inside
the wakes. Detailed simulation study of the interaction of both lasers with
krypton and ionization injection of electrons will be published in a
forthcoming paper. Here we illustrate the use of the multi-level ionization
algorithm by the simulation of a single 4J, 2 ps $CO_{2}$ laser pulse creating
plasma wakes in krypton gas with neutral density of $2\times 10^{17}$1/cc.
Figure 3 shows a distribution of electrons on a 2D plane along the laser
propagation and polarization directions.

Figure 3: 3D SPACE imulation of the 4J, 2 ps $CO_{2}$ laser interacting with
krypton gas with neutral density of $2\times 10^{17}$1/cc. Distribution of
electrons on a 2D plane along the laser propagation and polarization
directions is shown.

##  5 Conclusions and future work

In this paper, we developed an efficient multi-level laser tunneling
ionization algorithm in high-atomic-number gases. The algorithm features
several improvements compared to the previously published methods based on
numerical solutions to the system of ODE’s describing ionization dynamics via
fractional time stepping. By using analytical solutions to the system of
differential equations describing ionization evolution, our method effectively
resolves the multiscale nature of ionization processes which occur at time
scales significantly different compared to the time step of the main code. The
method also eliminates the need to store all ionization states in every cell
of the numerical mesh by using a locally-reduced system of equations, thus
significantly reducing the memory requirement. It also accounts for electron
quantum numbers and their projections while computing ionization
probabilities.

The multi-level ionization algorithm was implemented and verified in the code
SPACE. The algorithm developed in this paper extends a set of atomic physics
algorithms previously implemented in SPACE that resolved single-level
ionization, electron-ion recombination, and electron attachment to dopants in
dense neutral gases. SPACE has been extensively used in a variety of
applications in the area of plasma physics and accelerator design, in
particular for simulations of coherent electron cooling of relativistic ion
beams [16] and the laser-plasma wakefield acceleration [17, 18]. The multi-
level ionization module is currently being applied to numerical studies of the
ionization injection and acceleration of electrons into plasma wakes within
the Brookhaven National Laboratory program on $CO_{2}$ laser driven plasma
wakefield accelerator.

## Acknowledgments

This work was supported by Grant No. DE-SC0014043 funded by the U.S.
Department of Energy, Office of Science, High Energy Physics.

## References

  * [1] Tajima, T. and Dawson, J. M., Laser electron accelerator, Phys. Rev. Lett. 43, 267 (1979).
  * [2] E. Esarey, C.B. Schroeder, W.P. Leemans, Physics of laser-driven plasma-based electron accelerators. Rev. Mod. Phys. 81, 1229 (2009).
  * [3] A.J. Gonsalves et al., Petawatt laser guiding and electron beam acceleration to 8 GeV in a laser-heated capillary discharge waveguide, Phys. Rev. Lett. 122 (2019) 084801.
  * [4] D. L. Bruhwiler, D. A. Dimitrov, J. R. Gary, E. Esarey, W. Leemans, and R. E. Giacone, Particle-in-cell simulations of tunneling ionization effects in plasmabased accelerators, Phys. Plasmas 10 (2003) 2022–2030.
  * [5] Kumar, P., Yu, K., Zgadzaj, R., Amorim, L., Downer, M. C., Welch, J., Litvinenko, V. N., Vafaei-Najafabadi, N. and Samulyak R. Simulation study of co2 laser-plasma interactions and self-modulated wakefield acceleration. Phys. Plasmas 26, 083106 (2019).
  * [6] M. Chen, E. Cormier-Michel, C.G.R. Geddes, D.L. Bruhwiler, L.L. Yu, E. Esarey, C.B. Schroeder, W.P. Leemans, Numerical modeling of laser tunneling ionization in explicit particle-in-cell codes, Journal of Computational Physics, 236 (2013), 220–228.
  * [7] C.K. Birdsall, A.B. Langdon, V. Vehedi, J.P. Verboncoeur, Plasma Physics via Computer Simulations, Adam Hilger, Bristol, 1991.
  * [8] R. Hockney, J. Eastwood, Computer Simulation using Particles, Taylor & Francis Group, New York, 1988.
  * [9] L.-L. Yu, E. Esarey, C.B. Schroeder, J.-L. Vay, C. Benedetti, C.G.R. Geddes, M. Chen, W.P. Leemans, Two-color laser-ionization injection, Phys. Rev. Lett., 112 (2014) 125001.
  * [10] C.B. Schroeder, J.-L. Vay, E. Esarey, S.S. Bulanov, C. Benedetti, L.-L. Yu, M. Chen, C.G¿ Geddes, W. Leemans, Thermal emittance from ionization-induced trapping in plasma accelerators, PRAB, 17 (2014) 101301.
  * [11] M. Chen, Z.-M. Sheng, Y.-Y. Ma, J. Zhang, Electron injection and trapping in a laser wakefield by field ionization to high-charge states of gases, Journal of Applied Physics, 99 (2006) 056109.
  * [12] M. V. Ammosov, P. A. Golovinsky, I. Yu. Kiyan, V. P. Krainov, Tunneling ionization of atoms and atomic ions in an intense laser field with a nonhomogeneous space–time distribution Sov. Phys. JETP 64 (1986) 1191
  * [13] K. Yu, P. Kumar, S. Yuang, A. Cheng, R. Samuyak, SPACE: 3D Parallel Solvers for Vlasov-Maxwell and Vlasov-Poisson Equations for Relativistic Plasmas with Atomic Transformations, submitted to Comp. Phys. Comm., 2022, arXiv:2111.04139.
  * [14] K. Yu, R. Samulyak, K. Yonehara, B. Freemire, Simulation of beam-induced plasma in gas-filled rf cavities, Physical Review Accelerators and Beams 20 (3) (2017) 032002.
  * [15] K. Yu, R. Samulyak, K. Yonehara, B. Freemire, Simulation of plasma loading of high-pressure RF cavities, JINST 13 (2018) P01008.
  * [16] G. W. J. Ma, R. Samulyak, V. Litvinenko, X. Wang, K. Yu, Simulation studies of modulator for coherent electron cooling, Physical Review Accelerators and Beams 21 (2018) 111001.
  * [17] P. Kumar, K. Yu, R. Zgadzaj, L. Amorim, M. C. Downer, J. Welch, V. N. Litvinenko, N. Vafaei-Najafabadi, R. Samulyak, Simulation study of co2 laser-plasma interactions and self-modulated wakefield acceleration, Physics of Plasmas 26 (8) (2019) 083106.
  * [18] P. Kumar, K. Yu, R. Zgadzaj, M. C. Downer, I. Petrushina, R. Samulyak, V. N. Litvinenko, N. Vafaei-Najafabadi, Evolution of the self-injection process in long wavelength infrared laser driven lwfa, Physics of Plasmas 28 (1) (2021) 013102\.


000∗Prospective student; recently completed undergraduate studies at the
National and Kapodistrian University of Athens, Department of Mathematics,
Athens, Greece.Work was completed at the Game Theory Lab, School of
Mathematical Sciences in Tel Aviv University, while a visiting student.
Invitation was given by professor Eilon Solan of Tel Aviv University while
still being an undergraduate student. All research facilities were provided by
the same department. Besides professor Eilon Solan, for this enlightening
academic opportunity that he offered and his extremely significant help and
guidance, the author would also like to thank Panayotis Mertikopoulos,
Alexander Shapiro and Rakesh Vohra for their comments and
recommendations.000email address<EMAIL_ADDRESS>
# Duality theory and characterizations of optimal solutions for a class of
conic linear problems

Nick Dimou∗

###### Abstract.

For a primal-dual pair of conic linear problems that are described by convex
cones $S\subset X$, $T\subset Y$, bilinear symmetric objective functions
$\langle\cdot,\cdot\rangle_{X}$, $\langle\cdot,\cdot\rangle_{Y}$ and a linear
operator $A:X\rightarrow Y$, we show that the existence of optimal solutions
$x^{*}\in S$, $y^{*}\in T$ that satisfy $Ax^{*}=b$ and $A^{T}y^{*}=c$
eventually comes down to the consistency and solvability of the problems
$min\langle z,z\rangle_{Y},\;z\in\\{Ax-b:x\in S\\}$ and $min\langle
w,w\rangle_{X},\;w\in\\{A^{T}y-c:y\in T\\}$. Assuming that these two problems
are consistent and solvable, strong duality theorems as well as geometric and
algebraic characterizations of optimal solutions are obtained via natural
generalizations of the Farkas’ Lemma without a closure condition. Some
applications of the main theory are discussed in the cases of continuous
linear programming and linear programming in complex space.

###### Key words and phrases:

Duality theory, conic linear programming, optimal solutions, complementarity
conditions, Farkas Lemma, strict feasibility

###### 2020 Mathematics Subject Classification:

90C05, 90C46, 49N15

##  1\. Introduction

Optimization problems of the subsequent form have been profoundly studied and
strong duality theorems under different frameworks have been acquired:

${(P^{\prime})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\langle
c,x\rangle_{X}\\\ s.t.\;\;Ax-b\in T\\\ \;\;\;\;\;\;\;\;x\in S\end{array}$
${(D^{\prime})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\langle
y,b\rangle_{Y}\\\ s.t.\;\;-A^{T}y+c\in S^{*}\\\ \;\;\;\;\;\;\;\;\;\;\;y\in
T^{*}\end{array}$

where the objective functions are usually defined over pairings
$(X,X^{\prime})$ and $(Y,Y^{\prime})$. Such primal-dual pairs of problems are
called conic linear problems when the objective functions are bilinear,
$A:X\rightarrow Y$ is a linear map and $S,T$ are convex cones [3]. The above
pair of problems is often characterized by many authors as a generalized form
of the following primal-dual pair of conic optimization problems to the
infinite-dimensional case:

${(P^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\langle c,x\rangle_{X}\\\
s.t.\;\;Ax=b\\\ \;\;\;\;\;\;\;\;x\in S\end{array}$
${(D^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\langle y,b\rangle_{Y}\\\
s.t.\;\;-A^{T}y+c\in S^{*}\\\ \;\;\;\;\;\;\;\;\;\;\;y\in T\end{array}$

Here the objecive functions usually represent inner products defined over a
product of finite Euclidean spaces and the sets $S,$ $T$ are (polyhedral)
convex cones.

For problems of both forms that are defined over finite-dimensional vector
spaces, a rather complete theory of duality has been developed (see e.g. [5,
12]). The infinite-dimensional case is not yet considered complete, however
numerous results regarding strong duality have been obtained under general
frameworks and assumptions. These assumptions over the feasible sets are known
as constraint qualifications (CQs) in the relevant literature, and in
comparison to the standard linear programming (LP) case, they are more than
often necessary for a zero duality gap to exist. The most well-known,
sufficient of these constraint qualifications turns out to be that of strict
feasibility, or else known as Slater CQ (or Slater’s CQ), which assumes that a
feasible solution on the (relative) interior of the corresponding cone exists.
In particular the following known result for the pair of problems
$\\{(P^{*}),(D^{*})\\}$ in the finite-dimensional case can be readily found in
any textbook of semidefinite programming (for example [5, 16]):

Theorem. Suppose that there exists $y^{*}\in T^{*}$ such that
$-A^{T}y^{*}+c\in int(S^{*})$. Then $val(P^{*})=val(D^{*})$ and there exists
optimal feasible $x^{*}\in S$ such that $Ax^{*}=b$.

Various CQs have been proved to guarantee a zero duality gap between the
primal and dual conic linear problems in the infinite dimensional case; Some
early results are given by Kretschmer [8] in 1961, where he treated problems
of the form $\\{(P^{\prime}),(D^{\prime})\\}$ defined over paired vector
spaces and closed convex cones with respect to the weak topologies through
subconsistency and subvalues. A wide review of duality theory in infinite-
dimensional linear programming was later given by Anderson [1] and Nash and
Anderson [2]. A very interesting connection between conic linear problems and
sensitivity analysis was also made by Shapiro [15]. In his work strong duality
results were obtained under the subdifferentiality of the optimal value
function $v(y):=inf\\{\langle c,x\rangle:x\in S,$ $Ax-y\in T\\}$ in $b$.
Results in a framework and problem setup similar to [8] were recently given by
Khanh et al. [7].

However, in all the above, strong duality results for the pair of conic linear
problems $\\{(P^{\prime}),(D^{\prime})\\}$ are obtained in topological
frameworks where a Slater CQ, when it does guarantee strong duality, does not
necessarily guarantee the existence of optimal solutions $x^{*}\in S$,
$y^{*}\in T$ that satisfy $Ax^{*}=b$ and $A^{T}y^{*}=c$ respectively. In other
words, while the complementarity conditions (slackness)

(1.1) $\langle y^{*},Ax^{*}-b\rangle_{Y}=0\;\;\mbox{and\;\;}\langle
c-A^{T}y^{*},x^{*}\rangle_{X}=0$

strongly hold (that is there exist $x^{*}\in S$ such that $Ax^{*}=b$) for the
pair $\\{(P^{*}),(D^{*})\\}$, they do not necessarily strongly hold for the
primal-dual pair of conic linear problems $\\{(P^{\prime}),(D^{\prime})\\}$.

In this paper we show that in a certain class of conic linear problems, under
strict feasibility the complementarity conditions (slackness) (1.1) hold, and
therefore strong duality between $(P^{\prime})$ and $(D^{\prime})$ also holds.
In fact we show something stronger; if there exists an optimal solution
$x^{*}$ such that it belongs to int$S$, then whether $Ax^{*}-b$ belongs to the
interior of $T$ or not, there always exists feasible $y^{*}$ such that
$A^{T}y^{*}=c$; and the same goes for a feasible solution of $(D^{\prime})$ in
int$T^{*}$. That is we show that (1.1) strongly holds for both the primal and
the dual under some specific conditions.

This particular class of conic linear problems is defined over a more general
topological framework than that of conic convex programming problems of the
form $(P^{*}),$ $(D^{*})$, since the objective functions are not necessarily
inner products (nor continuous), the vector spaces $X$, $Y$ are not
necessarily Euclidean spaces (or subsets) and the convex cones $S,$ $T$ are
not necessarily closed nor polyhedral. It should be mentioned that conic
linear problems treated here belong to the wider class of problems that appear
in previous work ([7, 8, 15]) and therefore similar duality results are
already known.

The key to our approach resides on the fact that the basic properties that
constitute this class of conic linear problems are such that the proof of zero
duality gap eventually comes down to the requirement that the two subsequent
problems are consistent and solvable (that is that they have optimal feasible
solutions):

(1.2) $min\langle z,z\rangle_{Y},\;z\in\\{Ax-b:x\in
S\\}\;\;\;\mbox{and\;\;\;}min\langle w,w\rangle_{X},\;w\in\\{A^{T}y-c:y\in
T\\}$

In fact, it can be easily shown that (1.2) can be replaced be three other
conditions, the alternations that involve the max$\langle z,z\rangle_{Y}$ and
min$\langle w,w\rangle_{X}$ (that we shall call condition (1.2)a), min$\langle
z,z\rangle_{Y}$ and max$\langle w,w\rangle_{X}$ (condition (1.2)b), and
max$\langle z,z\rangle_{Y}$ and max$\langle w,w\rangle_{X}$ (condition
(1.2)c), of the objective functions of these two convex sets respectively.

Since our aim is to prove the existence of points $x^{*}$ and $y^{*}$ such
that $Ax^{*}=b$ and $A^{T}y^{*}=c$ it is only logical that our approach should
involve some kind of theorems similar to the Farkas alternative in real space.
Indeed, for the proof of the two main results we use simple generalized
versions of the Farkas’ Lemma which hold without a closure assumption, in
comparison to the trivial case of (LP) and other similar linear problems that
require a closeness property for strong duality to hold. Instead, these
generalized forms of the Farkas’ Lemma derive from properties that constitute
the class of conic linear problems treated, and from simple extended
hyperplane theorems.

The rest of the paper is organized as follows: in Section 2 the framework and
class of conic linear problems are defined, the main results are formulated
and some basic notations are given. The main section of this paper, Section 3,
includes the proofs of the two key theorems as well as some other useful
results regarding solutions that satisfy (1.1) and the consistency of some
subsets of the feasible sets. In Section 4 some applications of the main
theory are discussed in the case of linear programming in complex space.
Lastly, in Section 5 we obtain a simple result regarding continuous linear
programming problems which can be characterized as complementary to the strong
duality results given by Grinold [6] and Levinson [9].

##  2\. A class of conic linear problems

In this paper we deal with conic linear problems of the following form:

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\langle c,x\rangle_{X}\\\
s.t.\;\;Ax-b\in T^{*}\\\ \;\;\;\;\;\;\;\;x\in S\end{array}$
${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\langle y,b\rangle_{Y}\\\
s.t.\;\;-A^{T}y+c\in S^{*}\\\ \;\;\;\;\;\;\;\;\;\;\;y\in T\end{array}$

Similarly to the linear restrictions that appear in conic programming theory
$S,T$ are convex cones10001 A set $S\subset X$ is a convex cone iff
$\forall\lambda\in[0,1]:$ $\lambda S+(1-\lambda)S\subset S$ and
$\forall\mu\in[0,\infty):$ $\mu S\subset S$., subsets of vector spaces $X$ and
$Y$ respectively and $S^{*},T^{*}$ are their respective positive dual
cones20002 The positive dual cone of $S$ is the convex set $S^{*}:=\\{x^{*}\in
X:\langle x^{*},x\rangle_{X}\geq 0\;\forall x\in S\\}$.. The objective
functions $\langle\cdot,\cdot\rangle_{X}$, $\langle\cdot,\cdot\rangle_{Y}$
defined over $X\times X$ and $Y\times Y$ respectively, are bilinear and
symmetric (although symmetry is not always necessary in the following). Here
$A:X\rightarrow Y$ is a linear operator and $A^{T}:Y\rightarrow X$ is its
adjoint30003 Some authors also denote the adjoint by $A^{*}$., $b\in Y$ and
$c\in X$. In addition, the spaces $X,Y$ are not necessarily assumed to be
Euclidean or Hilbert spaces, nor do the objective functions represent
specifically defined inner products. Alike [15], the topologies corresponding
to the vector spaces (if $X,\;Y$ are equipped with any) are abstract and the
space $X$ is “large” enough, such that the adjoint of the linear operator
exists. That is, either the linear mapping $A$ is assumed continuous (usually
represented by a matrix function), or space $X$ is “large” enough such that
“for every $y\in Y$ there exists a unique $x^{*}\in X$ such that $\langle
y,Ax\rangle=\langle x^{*},x\rangle$ for every $x\in X$”, so that the adjoint
can be accordingly defined and $\langle y,Ax\rangle=\langle A^{T}y,x\rangle$
for every $x\in S$ and every $y\in T$.

A noticable difference between the two structures of the restrictions of dual
problems $(P^{\prime}),(D^{\prime})$ and $(P),(D)$ lies on the switching of
the cones $T$ and $T^{*}$. Although this alternation might seem confusing to
the reader that is familiar with the known work on duality theory of conic
programming, it does not affect the gist of the following analysis nor the
main purposes of the paper.

The class of conic linear problems that is treated in the above form is
characterized by the following three assumptions:

(F1) Convex cones $S,\;T$ are solid, that is int$S\neq\O$, int$T\neq\O$.
(F2) The positive-definiteness condition is met for the objective functions in
the sets $(C_{A}-b)\times(C_{A}-b)$, $(D_{A}-c)\times(D_{A}-c)$, where
$C_{A}:=\\{Ax:x\in X\\}\subset Y$ and $D_{A}:=\\{A^{T}y:y\in Y\\}\subset X$,
that is $\langle z,z\rangle_{Y}>0$ for every $0\neq z\in C_{A}-b$, $\langle
w,w\rangle_{X}>0$ for every $0\neq w\in D_{A}-c$.
(F3) The objective functions $\langle\cdot,\cdot\rangle_{Y}$,
$\langle\cdot,\cdot\rangle_{X}$ acquire a minimum value in the sets
$(C_{A}-b)\times(C_{A}-b)$, $(D_{A}-c)\times(D_{A}-c)$ respectively.

Assumption (F1) means that we only deal with essential non-trivial conic
linear problems. It is also essential for strictly feasible solutions to
exist. Assumption (F2) generalizes the case of the objective functions being
inner products, and (F3) implies that the closure of the convex cones $S$, $T$
and the continuity of the objective functions are not required.

Hypothesis (F3) essentially translates into the significant remark we made on
the previous senction, that is that the existence of optimal solutions
$x^{*}\in S$, $y^{*}\in T$ such that $Ax^{*}=b$ and $A^{T}y^{*}=c$ eventually
comes down to the consistency and solvability of the problems $min\langle
z,z\rangle_{Y},\;z\in\\{Ax-b:x\in S\\}$ and $min\langle
w,w\rangle_{X},\;w\in\\{A^{T}y-c:y\in T\\}$. In addition, it seems to be the
most obscure of the three judging by the fact that the first two are met more
than often, compared to (F3), in the relevant literature. However, the latter
is also met under some generic hypotheses and known results in variational
analysis (e.g. see [14] Theorem 1.9). Moreover, in the framework of [5] (F2)
and (F3) are also true for the closure of the sets $C_{A}$, $D_{A}$, therefore
it is seen that the case of $S,T$ being closed overlaps already known results
in finite (real) Euclidean spaces.

It must be pointed out that, due to the symmetric form of the primal-dual pair
and the linear symmetry that appears in the proofs of the generalized forms of
the Farkas’ Lemma, this last assumption may be replaced by the acquirement of
the maximum instead of the minimum, respectively. What this essentially means
is that if assumptions (F1), (F2) hold as well as just one of the four
different variations of assumption (F3) (conditions (1.2), (1.2)a, (1.2)b,
(1.2)c), then the same main results presented here hold. In what follows we
only treat with the case where the minimization of the two problems is
assumed, in order to avoid repeating results.

Before we state the two main results of this paper, we give some basic
notations that are used throughout the next sections:

We denote by $\mathcal{S}(P):=\\{x\in S:Ax-b\in T^{*}\\}$ the set of all
feasible solutions of the primal problem $(P)$. Respectively, we denote by
$\mathcal{S}(D):=\\{y\in T:-A^{T}y+c\in S^{*}\\}$ the set of all feasible
solutions of the dual problem $(D)$. The optimal value of the primal problem
$(P)$ is defined by $v(P):=inf\\{\langle c,x\rangle_{X}:Ax-b\in T^{*}$, $x\in
S\\}$ and the optimal value of the dual problem $(D)$ is defined by
$v(D):=sup\\{\langle y,b\rangle_{Y}:-A^{T}y+c\in S^{*}$, $y\in T\\}$, when of
course the respective feasibility sets are non-empty (we define
$v(P):=\infty$, $v(D):=-\infty$ if the problems have no feasible solutions).
The following weak duality relation holds by the standard minimax duality:

(2.1) $v(P)\geq v(D)$

In addition we define the sets
$\tilde{\mathcal{S}}(P):=\\{x\in\mathcal{S}(P):\langle
c,x\rangle_{X}<\infty\\}$ and
$\tilde{\mathcal{S}}(D):=\\{y\in\mathcal{S}(D):\langle
y,b\rangle_{Y}>-\infty\\}$ (we tend to use these sets of feasible solutions in
order to avoid “unsavory” optimization cases). We lastly denote by
$\mathcal{S}^{*}(P)$ and $\mathcal{S}^{*}(D)$ the sets of all optimal feasible
solutions of problems $(P)$ and $(D)$ respectively, that is the sets of all
feasible solutions for which the minimum and maximum value is attained
respectively.

Note that a problem might have an optimal value while not having an optimal
solution (the interested reader may look at problem (4.10) in [5]).

We shall also from now on skip the indicators $``X",\;``Y"$ of the objective
functions, and we will write $\langle\cdot,\cdot\rangle$ without provoking any
confusion regarding the space that this is defined over.

We now state the two main results that are to be obtained in the next section.
Under assumptions (F1)-(F3) the following is true:

######  Theorem 2.1.

If the problems $(P)$, $(D)$ have optimal solutions $x^{*}$, $y^{*}$
respectively such that $x^{*}\in$ int$S$, $y^{*}\in$ int$T$ and the optimal
values are finite, then $v(P)=v(D)$. In fact, there exist optimal solutions
$\hat{x}\in S$, $\hat{y}\in T$ of $(P)$, $(D)$ respectively such that
$A\hat{x}=b$ and $A^{T}\hat{y}=c$.

Now assume the following: (F4) The sets $X\smallsetminus$int$S$ and
$Y\smallsetminus$int$T$ are cones (not necessarily convex).

Let the sets $\hat{\mathcal{S}}(D):=\\{y\in$ int$T:-A^{T}y+c\in
S^{*},-A^{T}y\in S^{*},\langle y,b\rangle>-\infty\\}$,
$\hat{\mathcal{S}}(P):=\\{x\in$ int$S:Ax-b\in T^{*},Ax\in T^{*},\langle
x,c\rangle<\infty\\}$. If (F4) also holds for the above class of conic linear
problems, then the following is true:

######  Theorem 2.2.

If $\hat{\mathcal{S}}(D)\neq\O$, $\hat{\mathcal{S}}(P)\neq\O$,
$\tilde{\mathcal{S}}(P)\smallsetminus\hat{\mathcal{S}}(P)\neq\O$,
$\tilde{\mathcal{S}}(D)\smallsetminus\hat{\mathcal{S}}(D)\neq\O$ and if
$v(P),\;v(D)$ are finite, then $v(P)=v(D)$. In fact, there exist optimal
solutions $\hat{x}\in S$, $\hat{y}\in T$ of $(P)$, $(D)$ respectively such
that $A\hat{x}=b$ and $A^{T}\hat{y}=c$.

Even though assumption (F4) “shortens” the main class that is treated in this
paper, it essentially releases us from the necessity of the existence of
optimal solutions for both dual problems when specific feasible solutions can
be found. The boundeness conditions for the optimal values and the upper and
lower boundeness for the values of certain feasible solutions in the
formulations of the two results could as well be omitted when their existence
is known, while their presence insinuates that a class of functions that take
infinite values over the cones $S,T$ is not excluded from this particular
framework.

Now, one can straight away identify the geometric and algebraic
characterizations that occur from the above results regarding the existence of
optimal solutions:

The algebraic characterization has a clear explanation as it directly occurs
from both Theorems that there exist points $x^{*}\in S$, $y^{*}\in T$ that are
solutions to the linear “systems” $Ax=b$, $A^{T}y=c$. The geometric
characterizations is justified by the converse direction. To be more specific,
if there exist optimal solutions of the dual problems with finite optimal
values, but the two systems $Ax=b$, $x\in S$ and $A^{T}y=c$, $y\in T$ do not
have a solution, then every optimal solution of the two problems belongs to
the boundary of the corresponding convex cone (when of course such set is non-
empty). Same goes with Theorem 2.2., for in the case where the two systems
have no feasible solutions, but the optimal values exist and are finite, then
the subsets $\hat{\mathcal{S}}(P):=\\{x\in$ int$S:Ax-b\in T^{*}$, $Ax\in
T^{*},\langle x,c\rangle<\infty\\}$, $\hat{\mathcal{S}}(D):=\\{y\in$
int$T:-A^{T}y+c\in S^{*}$, $-A^{T}y\in S^{*},\langle y,b\rangle>-\infty\\}$ of
feasible solutions are empty. In other words, by knowing that the linear
“systems” $Ax=b$, $A^{T}y=c$ have no solutions in $S$ and $T$ respectively,
then we instantly know in which “geometric” place to “look for” the optimal
solutions.

##  3\. Duality theory and characterization of optimal solutions

In this section the main results of the paper are proved. Theorem 2.1 derives
from the following two key theorems, which can be characterized as dual due to
their formulation and initial hypothesis.

######  Theorem 3.1.

If $\mathcal{S}^{*}(D)\;\cap$ int$T\neq\O$ and $v(D)<+\infty$ then there
exists $\hat{x}\in\mathcal{S}(P)$ such that $A\hat{x}=b$.

######  Theorem 3.2.

If $\mathcal{S}^{*}(P)\;\cap$ int$S\neq\O$ and $v(P)>-\infty$ then there
exists $\hat{y}\in\mathcal{S}(D)$ such that $A^{T}\hat{y}=c$.

Here we only prove Theorem 3.1; the proof of Theorem 3.2 is completely
analogous, as are the proofs of the lemmas that are used in the following
analysis.

In what follows we only deal with the class of conic linear problems of
Section 2, that is the convex cones $S$, $T$ and the objective functions
satisfy assumptions (F1)-(F3).

######  Lemma 3.3.

Let $C$ be a convex subset of $X$ such that the positive-definiteness
condition is met for the objective function over $C-b$ for some $b\in
X\smallsetminus C$ and let $c\in C$. Then the following are equivalent:

  * (i)

$\langle c-b,c-b\rangle\leq\langle x,x\rangle$ $\forall x\in C-b$

  * (ii)

$\langle c-b,x-c\rangle\geq 0$ $\forall x\in C$

###### Proof.

(i)$\Rightarrow$(ii): Let $x\in C$ and $\lambda\in(0,1)$, then
$c+\lambda(x-c)\in C$. We now have:

$\langle c-b+\lambda(x-c),c-b+\lambda(x-c)\rangle-\langle
c-b,c-b\rangle=2\lambda\langle c-b,x-c\rangle+\lambda^{2}\langle
x-c,x-c\rangle$

due to the linearity and symmetry of $\langle\cdot,\cdot\rangle$. By (i)
$2\langle c-b,x-c\rangle+\lambda\langle x-c,x-c\rangle\geq 0$, hence for
$\lambda=1/n$, $n\in\mathbb{N}$ we obtain (ii) as $\lambda\rightarrow 0$.

(ii)$\Rightarrow$(i): Let $x\in C$. Then

$\langle x-b,x-b\rangle-\langle c-b,c-b\rangle=\langle x-c,x-c\rangle+2\langle
c-b,x-c\rangle\Rightarrow\langle x-b,x-b\rangle-\langle c-b,c-b\rangle\geq 0$

by (ii) and the positive-definiteness condition.
∎

######  Proposition 3.4.

Let $C$ be a convex subset of $X$ and let $b\in X\smallsetminus C$ such that
the positive-definiteness condition is met for the objective function over
$C-b$. If $\langle\cdot,\cdot\rangle$ acquires a minimum value on $C-b$ then
there exists $\alpha\in X$ such that
$\langle\alpha,b\rangle<\langle\alpha,x\rangle$ $\forall x\in C$. In fact
$\alpha\in C-b$.

###### Proof.

Let $\gamma\in C$ such that $\langle\gamma-b,\gamma-b\rangle\leq\langle
x-b,x-b\rangle$ $\forall x\in C$. Then by Lemma 3.3 and the positive-
definiteness condition:

$\langle\gamma-b,x\rangle\geq\langle\gamma-b,\gamma\rangle>\langle\gamma-b,b\rangle$

since $\gamma\neq b$. The inequality
$\langle\alpha,b\rangle<\langle\alpha,x\rangle$ holds for $\alpha:=\gamma-b\in
C-b$.
∎

We now obtain the following generalized form of Farkas’ Lemma:

######  Theorem 3.5.

(1st generalized form of Farkas’ Lemma) Let $S\subset X$ be a convex cone,
$S^{*}$ its positive dual and $b\in Y$. Then exactly one of the following
problems has at least one solution:

$(I)\left.\begin{array}[]{ll}Ax=b\\\ x\in
S\end{array}\right.,\;\;\;(II)\left.\begin{array}[]{ll}(-A)^{T}y\in S^{*}\\\
\langle y,-b\rangle<0\\\ y\in Y\end{array}\right.$

###### Proof.

Suppose that both $(I)$ and $(II)$ have solutions. Let $\hat{x}\in S$ be a
solution of $(I)$ and $\hat{y}\in Y$ be a solution of $(II)$. Then:

$(-A)^{T}\hat{y}\in S^{*}\Rightarrow\langle(-A)^{T}\hat{y},x\rangle\geq
0\;\;\;\forall x\in S\Rightarrow\langle(-A)^{T}\hat{y},\hat{x}\rangle\geq
0\Rightarrow\langle\hat{y},-A\hat{x}\rangle\geq
0\Rightarrow\langle\hat{y},-b\rangle\geq 0$

which is a contradiction.

Now assume that $(I)$ does not have a solution. Then $b\not\in
C_{A}=\\{Ax:x\in S\\}\subset Y$. Since $S$ is a convex cone and $A$ is linear,
the set $C_{A}$ is also a convex cone. Therefore Proposition 3.4 can be
applied for $C_{A}$ in space $Y$ as (F2) and (F3) hold; there exists
$\alpha\in-C_{A}+b$ such that
$\langle\alpha,-b\rangle<\langle\alpha,-Ax\rangle$ $\forall x\in S$. Let $x\in
S$, then $\lambda x\in S$ $\;\forall\lambda\in(0,\infty)$ hence
$\langle\alpha,-b\rangle/\lambda<\langle\alpha,-Ax\rangle$. Since $x\in S$ is
arbitrary, for $\lambda=n\in\mathbb{N}$ we obtain

$\langle\alpha,-Ax\rangle\geq 0\;\;\forall x\in
S\Rightarrow\langle-A^{T}\alpha,x\rangle\geq 0\;\;\forall x\in
S\Rightarrow-A^{T}\alpha\in S^{*}$

The inequality $\langle\alpha,-b\rangle<0$ holds by definition ($0\in S$),
therefore $\alpha\in-C_{A}+b\subset Y$ is a solution of $(II)$.
∎

The proof of Theorem 3.1 now follows:

###### Proof.

(Theorem 3.1) Suppose by contradiction that a feasible solution $x\in S$ of
$(P)$ such that $Ax=b$ does not exist. By Theorem 3.5 the following problem
has a solution:

$(II^{*})\left.\begin{array}[]{ll}(-A)^{T}y\in S^{*}\\\ \langle
y,-b\rangle<0\\\ y\in Y\end{array}\right.$

Suppose that for every solution $\hat{y}$ of $(II^{*})$ there exists
$(y^{*},\lambda)\in(\mathcal{S}^{*}(D)\;\cap$ int$T)\times(0,\infty)$ such
that $y^{*}+\lambda\hat{y}\in$ int$T$. Then
$y^{*}+\lambda\hat{y}\in\mathcal{S}(D)$. Indeed:

$\langle-A^{T}y^{*}+c,x\rangle\geq 0\mbox{
and}\;\langle-A^{T}\hat{y},x\rangle\geq 0\;\;\forall x\in
S\Rightarrow\langle-A^{T}(y^{*}+\lambda\hat{y})+c,x\rangle\geq 0\;\;\forall
x\in S$

Then $\langle y^{*}+\lambda\hat{y},b\rangle=\langle
y^{*},b\rangle+\lambda\langle\hat{y},b\rangle>\langle y^{*},b\rangle$, which
is a contradiction since $y^{*}$ is optimal and $v(D)<\infty$.

Therefore there exists a solution $\hat{y}$ of $(II^{*})$ such that
$\forall(y^{*},\lambda)\in(\mathcal{S}^{*}(D)\;\cap$ int$T)\times(0,\infty)$
$y^{*}+\lambda\hat{y}\in Y\smallsetminus$int$T$. For $\lambda=1/n$,
$n\in\mathbb{N}$ we obtain $y^{*}\in Y\smallsetminus$int$T$ for every
$y^{*}\in\mathcal{S}^{*}(D)\;\cap$ int$T$ as $\lambda\rightarrow 0$ since
$Y\smallsetminus$int$T$ is closed (with respect to the corresponding topology
of $Y$).
∎

The proof of Theorem 3.2 is completely analogous to the above, and derives
from the generalized form of the Farkas’ Lemma, which is similarly formulated
and proved in the topological vector space $Y$ as follows:

######  Theorem 3.6.

(2nd generalized form of Farkas’ Lemma) Let $T\subset Y$ be a convex cone,
$T^{*}$ its positive dual and $c\in X$. Then exactly one of the following
problems has at least one solution:

$(I^{\prime})\left.\begin{array}[]{ll}A^{T}y=c\\\ y\in
T\end{array}\right.,\;\;\;(II^{\prime})\left.\begin{array}[]{ll}Ax\in T^{*}\\\
\langle x,c\rangle<0\\\ x\in X\end{array}\right.$

For the purposes of this paper, the proof is omitted (we leave the
formulations and proofs of the corresponding Lemma 3.3 and Proposition 3.4 to
the reader).

By Theorems 3.1 and 3.2 we obtain the following corollary which is the first
of the two main results of this paper:

######  Corollary 3.7.

(Theorem 2.1) If both $(P)$ and $(D)$ have optimal solutions $x^{*}$, $y^{*}$
such that $x^{*}\in$ int$S$, $y^{*}\in$ int$T$, and $v(P),\;v(D)$ are finite
then there exist feasible solutions $\hat{x}\in S$, $\hat{y}\in T$ that
satisfy $A\hat{x}=b$, $A^{T}\hat{y}=c$ and therefore $v(P)=v(D)$ and
$\hat{x},$ $\hat{y}$ are optimal.

Similarly to Theorem 2.1, the second main result of this paper, Theorem 2.2,
results from two key theorems when (F4) holds:

######  Theorem 3.8.

If $\hat{\mathcal{S}}(D)=\\{y\in$ int$T:-A^{T}y+c\in S^{*},-A^{T}y\in
S^{*},\langle y,b\rangle>-\infty\\}\neq\O$,
$\tilde{\mathcal{S}}(D)\smallsetminus\hat{\mathcal{S}}(D)\neq\O$ and
$v(D)<\infty$ then there exists $\hat{x}\in\mathcal{S}(P)$ such that
$A\hat{x}=b$.

######  Theorem 3.9.

If $\hat{\mathcal{S}}(P)=\\{x\in$ int$S:Ax-b\in T^{*},Ax\in T^{*},\langle
x,c\rangle<\infty\\}\neq\O$,
$\tilde{\mathcal{S}}(P)\smallsetminus\hat{\mathcal{S}}(P)\neq\O$ and
$v(P)>-\infty$ then there exists $\hat{y}\in\mathcal{S}(D)$ such that
$A^{T}\hat{y}=c$.

Again, the proof of Theorem 3.9 is omitted and only that of Theorem 3.8 is
given in order to avoid superfluous repeated methods and contiguous results.
We will need the following Lemma:

######  Lemma 3.10.

Let $S\subset X$, $T\subset Y$. Then at most one of the following two problems
has a solution:

$(I)\left.\begin{array}[]{ll}\langle Ax-b,y\rangle\leq 0\;\;\forall y\in T\\\
x\in S\end{array}\right.,\;\;\;(II)\left.\begin{array}[]{ll}A^{T}y\in S^{*}\\\
\langle y,b\rangle<0\\\ y\in T\end{array}\right.$

###### Proof.

Suppose that both $(I)$ and $(II)$ have a solution. Let $\hat{x}\in S$ be a
solution of $(I)$ and $\hat{y}\in T$ be a solution of $(II)$. Then

$\langle A\hat{x}-b,y\rangle\leq 0\;\;\forall y\in T\Rightarrow\langle
A\hat{x},\hat{y}\rangle\leq\langle b,\hat{y}\rangle<0$

while $\langle A\hat{x},\hat{y}\rangle=\langle\hat{x},A^{T}\hat{y}\rangle\geq
0$, which is a contradiction.
∎

We can now prove Theorem 3.8:

###### Proof.

(Theorem 3.8) Suppose by contradiction that a feasible solution $x\in S$ of
$(P)$ such that $Ax=b$ does not exist. By Theorem 3.5 the following problem
has a solution:

$(II^{*})\left.\begin{array}[]{ll}(-A)^{T}y\in S^{*}\\\ \langle
y,-b\rangle<0\\\ y\in Y\end{array}\right.$

The set $\hat{\mathcal{S}}(D)$ is non-empty, therefore the feasible set
$Ax-b\in T^{*}$, $x\in S$ is non-empty. Due to the relation
$T^{*}\subset($int$T)^{*}$, $Ax-b\in($int$T)^{*}$, $x\in S$ has a solution.
Hence there exists $x\in S$ such that $\langle(-A)x-(-b),y\rangle\leq 0$
$\forall y\in$ int$T$. By Lemma 3.10 for the sets $S,$ int$T$ the following
does not have a solution:

$(II)\left.\begin{array}[]{ll}(-A)^{T}y\in S^{*}\\\ \langle y,-b\rangle<0\\\
y\in\mbox{int}T\end{array}\right.$

Therefore problem $(III)$ has a solution, where problem $(III)$ is defined by:

$(III)\left.\begin{array}[]{ll}(-A)^{T}y\in S^{*}\\\ \langle y,-b\rangle<0\\\
y\in Y\smallsetminus\mbox{int}T\end{array}\right.$

Note that if $\hat{y}\in Y\smallsetminus$int$T$ is a solution of $(III)$ then
$\lambda\hat{y}$ is also a solution of the problem
$\forall\lambda\in(0,\infty)$ due to (F4).

Now suppose that for every solution $\hat{y}$ of $(III)$ there exists a
feasible solution $y^{*}\in T$ such that $\hat{y}+y^{*}\in$ int$T$ and
$\langle y^{*},b\rangle>-\infty$. Then $\hat{y}+y^{*}$ is also a feasible
solution. Indeed, we have

$\langle-A^{T}y^{*}+c,x\rangle\geq 0\mbox{
and}\;\langle-A^{T}\hat{y},x\rangle\geq 0\;\;\forall x\in
S\Rightarrow\langle-A^{T}(y^{*}+\hat{y})+c,x\rangle\geq 0\;\;\forall x\in S$

For solutions $\\{n\hat{y}\in Y\smallsetminus$int$T:n\in\mathbb{N}\\}$, where
$\hat{y}$ is a solution of $(III)$, we obtain $v(D)\rightarrow\infty$ as
$n\rightarrow\infty$, which is a contradiction.

Therefore there exists a solution $\hat{y}\in Y\smallsetminus$int$T$ of
$(III)$ such that $\forall y\in\tilde{\mathcal{S}}(D)$: $\hat{y}+y\in
Y\smallsetminus$int$T$. Let
$y^{*}\in\hat{\mathcal{S}}(D)\subset\tilde{\mathcal{S}}(D)$. Then
$-A^{T}y^{*}\in S^{*}$, hence $\langle-A^{T}ny^{*}+c,x\rangle\geq 0$ $\forall
x\in S$ and $\forall n\in\mathbb{N}$. Alike the above we obtain that
$ny^{*}\in\tilde{\mathcal{S}}(D)$, $\forall y^{*}\in\hat{\mathcal{S}}(D)$ and
$\forall n\in\mathbb{N}$.

Since $Y\smallsetminus$int$T$ is a cone and $\hat{y}+ny^{*}\in
Y\smallsetminus$int$T$ $\forall y^{*}\in\hat{\mathcal{S}}(D)$, $\forall
n\in\mathbb{N}$ we obtain that $\hat{y}/n+y^{*}\in Y\smallsetminus$int$T$
$\forall y^{*}\in\hat{\mathcal{S}}(D)$, $\forall n\in\mathbb{N}$. As
$n\rightarrow\infty$ we get $y^{*}\in Y\smallsetminus$int$T$ $\forall
y^{*}\in\hat{\mathcal{S}}(D)$, which is a contradiction. ∎

Again, the proof of Theorem 3.9 is similar to the above, and the dual
formulation of Lemma 3.10 is used (the reader may complement the unnecessary
details). Theorem 2.2 is obtained as a corollary of the two results:

######  Corollary 3.11.

(Theorem 2.2) If $\hat{\mathcal{S}}(P)\neq\O$, $\hat{\mathcal{S}}(D)\neq\O$,
$\tilde{\mathcal{S}}(P)\smallsetminus\hat{\mathcal{S}}(P)\neq\O$,
$\tilde{\mathcal{S}}(D)\smallsetminus\hat{\mathcal{S}}(D)\neq\O$ and the
optimal values $v(P),v(D)$ are finite, then there exist feasible solutions
$\hat{x}\in S$, $\hat{y}\in T$ such that $A\hat{x}=b$, $A^{T}\hat{y}=c$
respectively and therefore $v(P)=v(D)$ and $\hat{x}$, $\hat{y}$ are optimal.

##  4\. Linear programming in Complex space

The application of the main results in the trivial case of linear programming
in real space is obvious and equivalent results are already known; it suffices
to look at any textbook on linear programming and duality theory.

We will particularly work with conic linear problems that are formulated in
complex space and discuss some cases where the main results can be put in an
application. Firstly, let the following primal-dual pair of problems:

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;Re(c,z)\\\ s.t.\;\;Az-b\in
T^{*}\\\ \;\;\;\;\;\;\;\;z\in S\end{array}$
${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;Re(w,b)\\\
s.t.\;\;-A^{*}w+c\in S^{*}\\\ \;\;\;\;\;\;\;\;w\in T\end{array}$

Here the objective function is bilinear, symmetrical and continuous, and is
defined by $Re(z,c)=Re(z\cdot
c)=Re(z^{*}c)=Re(\displaystyle\sum_{i=1}^{m}\bar{z_{i}}c_{i})$. The sets $S,T$
are defined by

$S:=\\{z\in\mathbb{C}^{m}:|argz|\leqq\alpha\\},\;\;\;T:=\\{w\in\mathbb{C}^{n}:|argw|\leqq\beta\\}$

where $\alpha$, $\beta$ are real m and n-vectors in $(0,\frac{\pi}{2})e$
respectively, where $e$ are the m and n-vectors with all coordinates equal to
$1$. Note that the sets $S,T$ are closed convex cones and that their positive
duals are defined by

$S^{*}=\\{z\in\mathbb{C}^{m}:|argz|\leqq\
\frac{\pi}{2}e-\alpha\\},\;\;\;T^{*}=\\{w\in\mathbb{C}^{n}:|argw|\leqq\frac{\pi}{2}e-\beta\\}$

Therefore the dual problems can also be writen as

${(P)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;Re(z,c)\\\ s.t.\;\;\lvert
argz\rvert\leqq\alpha\\\ \lvert
arg(Az-b)\rvert\leqq\frac{\pi}{2}e-\beta\end{array}$
${(D)\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;Re(w,b)\\\ s.t.\;\;\lvert
argw\rvert\leqq\beta\\\ \lvert
arg(-A^{*}w+c)\rvert\leqq\frac{\pi}{2}e-\alpha\end{array}$

In addition, the linear operator $A$ is a $n\times m$ complex matrix and
$A^{*}$ is its conjugate transpose.

Strong duality for the above pair of problems was first proved by Levinson
[10].:

######  Theorem 4.1.

If $(P),(D)$ have feasible solutions, then they have optimal solutions
$\hat{z}\in S$, $\hat{w}\in T$ respectively and $v(P)=v(D)$.

Conditions (F1), (F2) hold by definition, while the case of assumption (F3) is
slightly more complicated and, in agreement to the previous discussion in
Sections 1 and 2, is the one that essentially needs to hold in order for the
main theorems to be applied. Let us see the following example:

Let $\alpha\in(0,\frac{\pi}{2})e$, $\beta\in(0,\frac{\pi}{2})e$,
$S=\\{z\in\mathbb{C}^{m}:0\leqq
argz\leqq\alpha\\},\;T=\\{w\in\mathbb{C}^{n}:0\geqq argw\geqq-\beta\\}$ and
all elements $a_{ij}$ of the matrix $A$ satisfy:

$-\frac{\pi}{2}\leq arg(a_{ij})\leq 0$

Then, the objective function $Re(\cdot,\cdot)$ is lower level-bounded over the
sets $C_{A}-b$, $D_{A}-c$ and as a result (F3) is true ([14] Theorem 1.9) and
Theorems $2.1$, $2.2$ can be applied. In particular, we can easily identify
the geometric properties of the optimal solutions and get the longed for
characterizations analyzed in the previous section:

By Theorem $2.1$ if $0<argz<\alpha$ and $0>argw>-\beta$ (for a least one
coordinate) then there exist solutions $z^{*}\in S$, $w^{*}\in T$ such that
$Az=b$ and $A^{*}w=c$.

Now assume that the linear problems $\\{Az=b$, $0\leqq argz\leqq\alpha\\}$ and
$\\{A^{*}w=c$, $0\geqq argw\geqq-\beta\\}$ have no solutions. Then, again by
Theorem 2.1 we instantly obtain that the optimal solutions $\hat{z},\hat{w}$
belong to the boundary of their corresponfing cones, that is
$arg\hat{z}\equiv\alpha$ and $arg\hat{w}\equiv-\beta$ (when the optimal
solutions are not real numbers). Therefore, since we already know that the
optimal solutions exist when both problems are feasible (Theorem 4.1) and that
the two linear systems have no solutions in $S,T$, significant information
regarding the geometrical location of these optimal solutions is immediately
acquired; when they are not real numbers, they lie on the boundary of the
argument cones in their corresponding finite-dimensional complex planes. Note
that since (F1)-(F3) hold for cones that are not necessarily closed, this
example also holds for cones $S$ and $T$ in which their elements might have
coordinates whose argument strictly belongs to $(0,\alpha_{j})$ (to
$(-\beta_{i},0)$ respectively).

The latter analysis for this case of complex linear problems however does not
work if our goal is to apply the second main result. Obviously, this is due to
the fact that all elements of $A$ have a positive real part. One should
therefore work in a different setup. For instance, one could work with matrix
$A$ such that $|arg(a_{ij})|\leqq\frac{\pi}{2}+min\\{\alpha,\beta\\}_{k^{*}}$,
$\forall i,j$, with $b>0$ and $c\in S^{*}$ (why?).

The geometric characterization of the optimal solutions of dual problems
$(P),(D)$ obtained can have further appliances, such as in game theory. For
example, if one works with complex matrix games, as they are defined and
analyzed in [4], Theorem 2.1 implies whether or not the players $I$ and $II$
choose optimal strategies that lie on the boundary of their respective compact
strategy sets. Of course, as seen from the proof of the minimax theorem in
[4], the closed cones $S,T$ have a stricter geometrical structure, as they are
defined by

$S=\\{z\in\mathbb{C}^{m}:|argz|\leqq\alpha,\;\displaystyle\sum_{i=1}^{m}Im(z_{i})=0\\},\;\;T=\\{w\in\mathbb{C}^{n}:|argw|\leqq\beta,\;\displaystyle\sum_{j=1}^{n}Im(w_{j})=0\\}$

Therefore the main results can readily be applied in the case of finite-
dimensional linear programs under the three original assumptions, where
duality theory already exists and combutational methods for the solution of
the complex linear systems $Az=b$, $A^{*}w=c$ are known. These results however
may be applied in the case of infinite linear programming problems in complex
space as well, where the above linear systems turn out to be harder to solve.

For instance, consider the space of all square-summable complex sequences
$\ell^{2}(\mathbb{C})$ with objective function
$Re(z,w)=Re(\displaystyle\sum_{i=1}^{\infty}z_{i}\bar{w_{i}})$. Let
$b,c\in\ell^{2}(\mathbb{C})$, $A\in\mathcal{M}(\ell^{2}(\mathbb{C}))$ and the
convex cones:

$S:=\\{z\in\ell^{2}(\mathbb{C}):|argz|\leqq\alpha\\},\;T:=\\{w\in\ell^{2}(\mathbb{C}):|argw|\leqq\beta\\}$

where $\alpha\in(0,\frac{\pi}{w})e$, $\beta\in(0,\frac{\pi}{2})e$. We assume
that the linear operator $A$ and its adjoint $A^{*}$ are well defined, that
is:

$\displaystyle\sum_{i=1}^{\infty}\displaystyle\sum_{j=1}^{\infty}{z_{i}}\bar{a_{ij}}\bar{w_{j}}=\displaystyle\sum_{i=1}^{\infty}\displaystyle\sum_{j=1}^{\infty}\bar{z_{i}}a_{ij}w_{j}<\infty\;\;\forall
z\in S,\;\;\forall w\in T$

Conditions (F1), (F2) and (F4) hold be definition, while the case of (F3) is
again more sensitive. However, when working with specific subsets of the
feasible cones and certain cases of the linear operators $A,A^{*}$, such as in
the previous example, the third assumption holds by the known theory of
minimum attainment (see [9]). Therefore Theorem 2.1 can be applied. Note that
solutions of the problems $\\{Az=b$, $z\in S\\}$ and $\\{A^{*}w=c$, $w\in
T\\}$ are not so easily found by similar combutational methods as in the
finite case (e.g. with Gauss elimination). Hence the results obtained in
Section 3 are instantly more significant and useful for the infinite case.

Since some regular and strong duality theorems for conic linear problems in
infinite-dimensional Hilbert spaces have already been obtained (see for
instance [1, 2]), the existence of optimal solutions can result in valuable
mathematical details regarding both the geometric properties of such
solutions, that is whether or not they lie on the boundary of the cones $S,T$,
as well as the existence and form of solutions of the systems $\\{Az=b$, $z\in
S\\}$ and $\\{A^{*}w=c$, $w\in T\\}$.

##  5\. Continuous linear programming

Another interesting application takes place in continuous linear programming.
Here problems of the subsequent forms are discussed:

${(P^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}min\;\;\mathop{{\int_{0}^{T}}}x(t)c(t)dt\\\
s.t.\;\;x(t)B(t)\geqq
b(t)+\mathop{{\int_{t}^{T}}}x(s)K(s,t)ds\;\;\;\;\;\;f.a.e.\;\;t\in[0,T]\\\
x(t)\geqq 0\;\;f.a.e.\;\;t\in[0,T]\\\ \\\ \end{array}$

${(D^{*})\;\;\;\;\;\;\;\;}\begin{array}[]{ll}max\;\;\mathop{{\int_{0}^{T}}}y(t)b(t)dt\\\
s.t.\;\;B(t)y(t)\leqq
c(t)+\mathop{{\int_{0}^{t}}}K(s,t)y(s)ds\;\;\;\;\;\;f.a.e.\;\;t\in[0,T]\\\
y(t)\geqq 0\;\;f.a.e.\;\;t\in[0,T]\\\ \\\ \end{array}$

where $c(t),b(t)$ are bounded and Lebesgue measurable m and n-vectors
(functions) respectively, $B(t)$ is an $m\times n$ bounded and Lebesgue
measurable matrix, $K(s,t)$ is an $m\times n$ bounded and Lebesgue measurable
matrix which is equal to 0 for $s>t$, the functions $x(t),y(t)$ are bounded
and Lebesgue measurable, $T$ is finite and $f.a.e.$ $t\in[0,T]$ stands for
“for almost every” $t\in[0,T]$, that is the inequalities that apart the
feasible regions hold for every $t\in[0,T]\smallsetminus U$, where
$U\subset[0,T]$ has a Lebesgue measure of zero.

Problems of the above form have been discussed in [6, 9] and strong duality
theorems have been acquired under specific hypotheses. The following algebraic
assumptions are always made:

(5.1) $\\{z:B(t)z\leqq 0,z\geqq 0\\}=\\{0\\}\;\;\forall t\in[0,T]$ (5.2)
$B(t)\geqq 0,\;K(s,t)\geqq 0,\;c(t)\geqq 0\;\;\forall s,t\in[0,T]$

while the continuity of these functions (almost everywhere in $[0,T]$) is also
required for no duality gap between $(P^{*})$ and $(D^{*})$. In particular,
the following strong duality theorem is known:

######  Theorem 5.1 ([6] Theorem 3.4, [9] Theorem 3).

If (5.1) and (5.2) hold and if $B(t),\;b(t),\;c(t),\;K(s,t),\;$ are continuous
at almost all $t$ in $[0,T]$ and almost all $s,\;t$ in $[0,T]\times[0,T]$
respectively, then $v(P^{*})=v(D^{*})$.

Here we work with the conves cones:

$S:=(L_{\infty}^{+}[0,T])^{m},\;\;\;T:=(L_{\infty}^{+}[0,T])^{n}$

where $L_{\infty}^{+}[0,T]$ is the space of all almost everywhere positively
valued on $[0,T]$ bounded Lebesgue measurable functions. Strong duality
results regarding continuous linear problems of similar form with these exact
feasible convex cones are given in [15].

The linear operators $A:X\rightarrow Y$, $A^{T}:Y\rightarrow X$ are defined
by:

$(Ax)(t):=x(t)B(t)-\mathop{{\int_{t}^{T}}}x(s)K(s,t)ds,\;\;t\in[0,T]$
$(A^{T}y)(t):=B(t)y(t)-\mathop{{\int_{0}^{t}}}K(s,t)y(s)ds,\;\;t\in[0,T]$

We can see that these are well defined under our initial hypothesis. Also for
the bilinear and symmetric objective function $\langle
z(t),w(t)\rangle=\mathop{{\int_{0}^{T}}}z(t)w(t)dt$ the following is true:
$\langle(Az)(t),w(t)\rangle=\langle z(t),(A^{T}w)(t)\rangle$. Indeed, it
suffices to show that:

$\mathop{{\int_{0}^{T}}}\left(\mathop{{\int_{t}^{T}}}z(s)K(s,t)ds\right)w(t)dt=\mathop{{\int_{0}^{T}}}z(t)\left(\mathop{{\int_{0}^{t}}}K(s,t)w(s)ds\right)dt$

This is true by the Fubini Theorem (see [6], Proposition 1.3).

Now (F1),(F2),(F4) hold by definition for almost every $t\in[0,T]$ (it is easy
to notice that the “for almost every” does not affect the gist of the main
results - the reader may fill in the appropriate details). Condition (F3) is
the one that discommodes us once again. In contrast to the previous example,
it is not wise to work with $L_{\infty}^{+}[0,T]$ (or a subspace
$L_{k}^{+}[0,T]$ for some $k\in\mathbb{N}$) in order to prove level-boundness
and/or apply Theorems of the attainment of minimum, as it was done previously.
This is mainly because the set
$\\{f(t)\in(L_{\infty}^{+}[0,T])^{m}:|f(t)|\leqq N,t\in[0,T]\\}$ for some
$N\in\mathbb{R}$ is not bounded. Therefore we would either have to work in
specific subspaces of $L_{\infty}^{+}[0,T]$, that is with specific spaces -
types - of bounded Lebesgue measurable functions, or with suitable matrices
$K(s,t)$, $B(t)$ and vectors $b(t)$, $c(t)$, as it was effectively done in the
previous section.

For the main purposes of this section we shall not deal with the analysis of
cases under which this condition is met; for the result that follows we will
assume that (F3) is true.

The next Theorem can be characterized as partially complementary to Theorem
5.1:

######  Theorem 5.2.

Let $\hat{x}(t)$ be a feasible solution of $(P^{*})$ and $\hat{y}(t)$ be a
feasible solution of $(D^{*})$ such that $\hat{x}(t)>0$ and $\hat{y}(t)>0$
f.a.e. $t\in[0,T]$. Assume that the optimal values $v(P^{*})$, $v(D^{*})$
exist and are bounded, assumption (F3) holds and that either $(i)$ or $(ii)$
of the following is satisfied:

(i) $B(t)\leqq 0$, $K(s,t)\geqq 0$ $\forall s,t\in[0,T]$ and $b\in T^{*}$
(ii) $B(t)\geqq 0$, $K(s,t)\leqq 0$ $\forall s,t\in[0,T]$ and $-c\in S^{*}$

Then there exist optimal solutions $x^{*}(t)$ of $(P^{*})$ and $y^{*}(t)$ of
$(D^{*})$ such that $x^{*}(t)B(t)=b(t)+\int_{t}^{T}x^{*}(s)K(s,t)ds$ and
$B(t)y^{*}(t)=c(t)+\int_{0}^{t}K(s,t)y^{*}(s)ds$, f.a.e. $t\in[0,T]$, and
$v(P^{*})=v(D^{*})$.

###### Proof.

Assume that the first condition $(i)$ is met (the proof for condition $(ii)$
is completely analogous). Then, since $B(t)\leqq 0$ and $K(s,t)\geqq 0$ for
$s,t\in[0,T]$, the set $\hat{\mathcal{S}}(D^{*})=\\{y\in$ int$T:-A^{T}y+c\in
S^{*},-A^{T}y\in S^{*},\langle y,b\rangle>-\infty\\}$, where the linear
operator $A^{T}$ is defined as above, is nonempty for almost every
$t\in[0,T]$. Therefore, by Theorem 3.8 there exists
$x^{*}(t)\in\mathcal{S}(P^{*})$ such that $Ax^{*}=b$, that is
$x^{*}(t)B(t)=b(t)+\int_{t}^{T}x^{*}(s)K(s,t)ds$ for almost every $t\in[0,T]$.
Now, since $b\in T^{*}$, Theorem 3.9 may also be applied, hence there also
exists $y^{*}(t)\in\mathcal{S}(D^{*})$ such that $A^{T}y^{*}=c$, that is
$B(t)y^{*}(t)=c(t)+\int_{0}^{t}K(s,t)y^{*}(s)ds$, f.a.e. $t\in[0,T]$. The
strong duality relation $v(P^{*})=v(D^{*})$ follows. ∎

Note that for the proof the continuity of $B(t),\;b(t),\;c(t),\;K(s,t)$ is not
assumed in comparison to Theorem 5.1, although it may be (partially) needed in
order for (F3) to hold.

## References

  * [1] E.J. Anderson, A review of duality theory for linear programming over topological vector spaces, J. Math. Anal. Appl., 97, 380–392, 1983.
  * [2] E.J. Anderson and P. Nash, Linear Programming in Infinite–Dimensional Spaces, New York, NY: Wiley, 1987.
  * [3] J.F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000.
  * [4] N. Dimou, An Introduction to Complex Game Theory, Undergraduate Paper, ArXiv: 2204.02277, 2022.
  * [5] B. Gränder and J. Matou$\check{s}$ek, Approximation Algorithms and Semidefinite Programming, Berlin, Germany, Springer-Verlag, 2012.
  * [6] R.C. Grinold, Symmetric duality for continuous linear programs, SIAM Journal of Appl. Math., 18, 84–96, 1970.
  * [7] P.D. Khanh, T. Hong Mo and Thrinh T.T. Tran, Necessary and Sufficient Conditions for Qualitative Properties of Infinite Dimensional Linear Programming Problems, Numerical Functional Analysis and Optimization, 40, no. 8, 924–943, 2019.
  * [8] K.S. Kretschmer, Programmes in Paired Spaces, Canadian Journal of Mathematics, 13, 221–238, 1961.
  * [9] N. Levinson, A class of continuous linear programming problems, J. Math. Anal. Appl., 16, 78–83, 1966.
  * [10] N. Levinson, Linear programming in complex space, J. Math. Anal. Appl., 14, 44–62, 1966.
  * [11] C. Melolidakis, Basic Optimization Theory (in Greek), Lecture Notes, Dept. of Mathematics, National and Kapodistrian Univ. of Athens, 2003.
  * [12] Yu. Nesterov and A. Nemirovsky, Conic formulation of a convex programming problem and duality, Optimization Methods and Software, 1, no. 2, 95–115, 1992.
  * [13] G. Pataki, Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals, in: Comp. and Anal. Math., Springer Proceedings in Mathematics & Statistics, 50, Springer, New York, NY, 2013.
  * [14] R.T. Rockafellar, and R.J. Wets, Max and Min, in Grundlehren der Mathematischen Wissenschaften, Variational Analysis, 317, 1–37, Berlin Heidelberg: Springer, 2009.
  * [15] A. Shapiro, On duality theory of conic linear problems, in Semi-infinite programming (Alicate, 1999), Nonconvex Opt. Appl., 57, 135–165, Klumer Acad. Publ., Dordrecht, 2001.
  * [16] A. Shapiro and K. Scheinberg, Duality and Optimality Conditions. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds) Handbook of Semidefinite Programming, International Series in Operations Research & Management Science, 27, Springer, Boston, MA, 2000.
  * [17] L. Tunçel and H. Wolkowicz, Strong duality and minimal representations for optimization, Comput. Optim. Appl., 53, 619–648, 2013.
  * [18] Y. Ye, Conic Linear Programming, Lecture Notes, Standford University (2004), revised version 2017.