# Identification and Mitigation of Conducting Package Losses for Quantum
Superconducting Devices

Yizhou Huang  Department of Physics, University of Maryland, College Park, MD
20742, USA  Maryland Quantum Materials Center, University of Maryland, College
Park, MD 20742, USA  Laboratory for Physical Sciences, College Park, MD 20740,
USA  Yi-Hsiang Huang  Laboratory for Physical Sciences, College Park, MD
20740, USA  Department of Electrical and Computer Engineering, University of
Maryland, College Park, MD 20742, USA  Haozhi Wang  Department of Physics,
University of Maryland, College Park, MD 20742, USA  Maryland Quantum
Materials Center, University of Maryland, College Park, MD 20742, USA
Laboratory for Physical Sciences, College Park, MD 20740, USA  Zach Steffen
Department of Physics, University of Maryland, College Park, MD 20742, USA
Maryland Quantum Materials Center, University of Maryland, College Park, MD
20742, USA  Laboratory for Physical Sciences, College Park, MD 20740, USA
Jonathan Cripe  Laboratory for Physical Sciences, College Park, MD 20740, USA
F. C. Wellstood  Department of Physics, University of Maryland, College Park,
MD 20742, USA  Maryland Quantum Materials Center, University of Maryland,
College Park, MD 20742, USA  Joint Quantum Institute, University of Maryland,
College Park, MD 20742, USA  B. S. Palmer<EMAIL_ADDRESS>Department of
Physics, University of Maryland, College Park, MD 20742, USA  Maryland Quantum
Materials Center, University of Maryland, College Park, MD 20742, USA
Laboratory for Physical Sciences, College Park, MD 20740, USA

###### Abstract

Low-loss superconducting microwave devices are required for quantum
computation. Here, we present a series of measurements and simulations showing
that conducting losses in the packaging of our superconducting resonator
devices affect the maximum achievable internal quality factors ($Q_{i}$) for a
series of thin-film Al quarter-wave resonators with fundamental resonant
frequencies varying between 4.9 and 5.8 GHz. By utilizing resonators with
different widths and gaps, we sampled different electromagnetic energy volumes
for the resonators affecting $Q_{i}$. When the backside of the sapphire
substrate of the resonator device is adhered to a Cu package with a conducting
silver glue, a monotonic decrease in the maximum achievable $Q_{i}$ is found
as the electromagnetic sampling volume is increased. This is a result of
induced currents in large surface resistance regions and dissipation
underneath the substrate. By placing a hole underneath the substrate and using
superconducting material for the package, we decrease the ohmic losses and
increase the maximum $Q_{i}$ for the larger size resonators.

††preprint: AIP/123-QED

##  I Introduction

The ability to produce superconducting devices with low microwave loss and
small phase noise is desired for the astronomical detector community and the
quantum information community. Zmuidzinas (2012); de Leon  _et al._ (2021) At
the chip level, this requires the use of low-loss materials, clean fabrication
processes, and good microwave hygiene.Richardson  _et al._ (2016); Chen  _et
al._ (2014); Sheldon  _et al._ (2017) The packaging for the quantum chip
should provide good impedance matching over a large bandwidth, a small amount
of cross-talk between different signal lines, and have good shielding to
reduce radiated losses and prevent stray THz or IR black-body radiation from
leaking into the package.Huang  _et al._ (2021); Córcoles  _et al._ (2011)

In this article, we measure limitations on the maximum achievable internal
quality factors, $Q_{i}$, of a series of superconducting microwave resonators.
The source of this loss is from dissipation in normal metal conductors used in
the package of the resonator chip. The energy stored in the resonator produces
an rf magnetic field $H$ resulting in the production of shielding eddy
currents in nearby conductors when $H$ impinges upon them. A noticeable amount
of dissipation occurs when these shielding currents are produced in conductors
with a finite surface resistance. This loss mechanism was initially identified
when measuring five resonators on a single chip and noticing a systematic
decrease in their quality factors with an increase in the widths and gaps of
the resonators. To model this finding, we performed finite-element simulations
to estimate the magnitude of dissipation in each conductor used in the
package. A conducting adhesive, used to adhere and thermalize the chip to the
package, was identified to be the most significant source of loss. By
implementing a few changes to the packaging, we reduce this loss and
demonstrate over an order of magnitude improvement in the maximum $Q_{i}$ of
the resonators.

##  II Device and Results

The thin film Al chip that we measured consists of five multiplexed quarter-
wave coplanar waveguide (CPW) resonators coupled to a common coplanar
waveguide transmission feedline. Gao  _et al._ (2008) The resonators had
different fundamental resonant frequencies $f_{\circ}$, CPW widths $w$ and
gaps $g$ ranging from $f_{\circ}=$ 4.9 GHz, $w=3\ \mathrm{\mu m}$ and $g=1.5\
\mathrm{\mu m}$ for R1 up to $f_{\circ}=$ 5.8 GHz, $w=22\ \mathrm{\mu m}$ and
$g=11\ \mathrm{\mu m}$ for R5 (see supplemental material for more details).

The same chip was sequentially packaged in four different ways and measured.
To efficiently conduct heat from the chip, a silver impregnated conducting
adhesive,111Loctite Ablestik: 59C diluted with toluene, was used to attach the
chip in each package. For the first measurement, the backside of the chip was
glued to an OFHC Cu package (denoted Cu$\blacksquare$). A two layer Cu printed
circuit board (PCB) was used to interface rf signals from a non-magnetic SMA
connector to the resonator chip (see Fig.1 (a) for a CAD rendering).

(a)

(b)

Figure 1: CAD rendering of resonator chip and surrounding PCB (lid and
sidewall not shown). (a) Plan view of device in Cu$\square$ package, showing
substrate (cyan), resonators (red), center transmission line (white),
surrounding PCB (orange), and glue above (dark purple) and below (light
purple) the substrate. A series of connections were used to represent the
wirebond connections from the chip to the surrounding PCB. The size and
approximate location of the optional hole is denoted with the dashed contour.
(b) Trimetric view of chip and Al$\square$ package.

To measure the low-temperature loss of the resonators, the device was bolted
to the mixing chamber stage of a Leiden cryogen-free dilution refrigerator,
connected to input and output microwave cables, encased in two open ended
Amumetal 4K cylinders, and cooled to a temperature less than 20 mK. (See
Ref.Yeh  _et al._ , 2017 for details of the set-up.) A vector network analyzer
was used to measure the in-phase and out-of-phase ratio of the transmitted
voltage to input voltage at 1601 different discrete frequencies ($S_{21}(f)$)
spanning the resonance and at different input drive voltages. Each $S_{21}(f)$
scan was repeated multiple times, from which the mean $\bar{S}_{21}(f)$ and
the standard deviation $\sigma_{S_{21}}(f)$ at each frequency were calculated
for both quadratures. Both quadratures of the mean $\bar{S}_{21}(f)$ were
simultaneously fitted, weighted by $1/\sigma_{S_{21}}(f)$, using the diameter-
correction methodKhalil  _et al._ (2012) to extract 5 fitting parameters
including $Q_{i}$.

Fig. 2 shows a log-log plot of the fitted $Q_{i}$ versus stored average photon
number from the first measurement of the resonators in Cu$\blacksquare$
package. For R1, a weak increase in $Q_{i}$ with increasing power was observed
with a maximum $Q_{i,m}\simeq 2\times 10^{6}$. As $w$ and $g$ of the
resonators increase, the observed power dependence decreases and $Q_{i,m}$
decreases to $Q_{i,m}=10^{5}$ for resonator R5. The focus of this paper is to
determine the physical mechanism responsible for the limitations on $Q_{i,m}$.
These limitations are not consistent with losses at the interfaces near the
resonator since $Q_{i,m}$ decreases with an increase in $g$ and $w$.Woods  _et
al._ (2019) Instead, loss farther from the resonator was thought to be the
source. Since normal metal conductors were underneath and surrounded the
resonator chip, our conjecture was that Ohmic dissipation from these normal
metal components limited $Q_{i,m}$.

$10^{0}$$10^{2}$$10^{4}$$10^{6}$$10^{8}$$10^{5}$$10^{6}$Photon Number
$n$$Q_{i}$$R_{1}$$R_{2}$$R_{3}$$R_{4}$$R_{5}$ Figure 2: Log-log plot of the
fitted resonator internal quality factors versus stored photon number for
$\text{Cu}\blacksquare$ package. As the width and gap of the resonator
increases from R1 to R5, the measured power dependence is smaller and the
maximum $Q_{i,m}$ decreases. The dashed line on top is a weak $\propto
n^{0.1}$ power law as a guide. The semi-transparent arrows give a bound of the
estimated $Q_{i}$ for the resonators $R_{2}$ to $R_{5}$, assuming the surface
underneath the substrate was filled with Ag impregnated adhesive as the lower
bound and OFHC Cu as the upper bound (see text).

To examine this hypothesis, we modified the package and remeasured the same
resonator chip. First, a 4.2 mm $\times$ 4.2 mm wide hole that was 2.5 mm deep
was milled out of the bottom of the Cu package where the chip resided. To
adhere the device, glue was added to two corners of the chip and along the
sides (see purple regions in Fig. 1(a)). With these modifications (denoted
$\text{Cu}\square$), all of the $Q_{i,m}$’s improved, especially for R5 which
demonstrated over a factor of 20 improvement (see Fig. 3). In addition, there
was no longer a strong correlation between $Q_{i,m}$ to $w$ and $g$ of the
resonators.

$\text{Cu}\blacksquare$ $\text{Cu}\square$ $\text{Al}\blacksquare$
$\text{Al}\square$ $10^{5}$$10^{6}$$10^{7}$Maximum
$Q_{i}$$R_{1}$$R_{2}$$R_{3}$$R_{4}$$R_{5}$ Figure 3: Bar chart of measured
maximum $Q_{i,m}$ on a log scale for each resonator in their corresponding Cu
or Al package, without a hole ($\blacksquare$) and with a 4.2 x 4.2 mm2 hole
($\square$) underneath the 5 x 5 mm2 chip.

To determine whether the $Q_{i,m}$’s could be improved further, two packages
with overall the same geometry were manufactured from aluminum 6063 and used
to measure the same resonator chip. One of them had no hole (Al$\blacksquare$)
and one had a hole (Al$\square$). Similar to the Cu$\square$ case, a smaller
amount of glue was applied underneath or on the perimeter of the chip for both
Al packages. Also, the Cu PCB, which was glued with a silver
epoxy222CircuitWorks: CW2400 to the Al package, was trimmed and cut into two
pieces so that it was only within close proximity to the side of the chip with
the input and output SMA launchers (see Fig.1(b) and supplemental material).
While the $Q_{i,m}$’s for the Al$\blacksquare$ showed an overall increase over
the $Q_{i,m}$’s measured in Cu$\blacksquare$, an increase in the loss with
resonator size from R2 to R5 was still observed. The data in the Al$\square$
package had similar $Q_{i,m}$’s as measured for Cu$\square$. Next, we discuss
a model and the use of microwave finite element simulations to identify the
observed sources of loss in our package.

##  III Model & Simulations

Dissipation from induced eddy currents in the surrounding normal metal
associated with the packaging was hypothesized as the source limiting
$Q_{i,m}$. Neglecting the anomalous skin effect, ac shielding currents in a
normal metal with resistivity $\rho$ decay on a length scale given by the skin
depth $\delta=\sqrt{\frac{2\rho}{2\pi f\mu_{\circ}}}$, this results in an
effective surface resistance $R_{S}=\rho/\delta$.Padamsee, Knobloch, and Tom
(2011); Pozar (2005) The power dissipated in $R_{S}$ also produces a
limitation in the internal quality factor given by Padamsee, Knobloch, and Tom
(2011)

$Q_{i,R_{S}}^{-1}=\frac{R_{S}}{2\pi
f_{\circ}\mu_{\circ}}\gamma=\frac{R_{S}}{2\pi
f_{\circ}\mu_{\circ}}\frac{\int\int_{S}|H|^{2}dS}{\int\int\int_{V}|H|^{2}dV}.$
(1)

Here, the ratio of the two integrals, which we define as $\gamma$, corresponds
to a geometric factor of the ratio of the magnetic field energy at the surface
of $R_{S}$ to the total magnetic field energy. For scaling purposes,
$f_{\circ}=5.6$ GHz for R4 and the ratio $R_{S}/(2\pi
f_{\circ}\mu_{\circ})=(3.4\times 10^{-3}\sqrt{\rho})\
\mathrm{[m/\Omega]}^{1/2}$.

There are three normal conductors of concern present in our packaging. First,
the Ag impregnated glue was measured to have a relatively large dc resistivity
of $\rho_{\text{glue}}=630\ \mu\Omega\cdot$cm at $T=77$ K. For the Ag glue,
the ratio $R_{S,glue}/(\omega_{\circ}\mu_{\circ})=8.5\times 10^{-6}\
\mathrm{m}$ at 5.6 GHz, implying $\gamma_{glue}<(1/8.5)\ \mathrm{m}^{-1}$ to
achieve $Q_{i}>10^{6}$. The other normal conductor of concern was the Cu used
in the two Cu packages. From quality factor measurements of a 3D OFHC Cu
cavity at $T=3$ K, the resistivity of the Cu is estimated to be
$\rho_{\text{Cu}}\simeq 0.6\ \mu\Omega\cdot$cm. The third and final conductor
was the PCB Cu. By manufacturing a bandpass microwave CPW resonator from a
similar PCB and measuring $Q$ at $T=3$ K, a dc resistivity
$\rho_{\text{PCB}}\simeq 2\ \mu\Omega\cdot$cm was estimated.Gupta  _et al._
(1996) These three values of $\rho$ are used to estimate the loss.

To calculate the geometric factor $\gamma$ at the surface of each conductor of
concern, the $H$ field for each resonator in the different package geometries
was simulated using Ansys’s high frequency simulation software (HFSS). Each
conductor in the simulation was assumed to be a perfect electric conductor to
reduce simulation resources. To simulate the $H$ field associated with the
stored energy of the resonator, and not with the coupling to the CPW
transmission line, we implemented two effects in the simulation. First, the
connections between the signal trace of the resonator chip to the PCB were
removed. This prevented radiation from leaking to the ports where the SMA
connectors were located and also avoiding a standing wave near a resonant
frequency. Second, the open end of the quarter-wave resonator was shunted with
an excitation lumped port with a matched impedance to the resonator waveguide,
which is 50 $\Omega$. The resonator was then excited at $f_{\circ}$, which was
determined by satisfying $\mathrm{Im}\left[(Y_{11}(f_{\circ})\right]=0$ where
$Y_{11}$ is the self-admittance of the lumped port. We simulated each
resonator in the four different packages and calculated $\gamma$ for each
conductor of concern.

Table 1: HFSS simulated magnetic field geometric factors $\gamma$ in units of $\mathrm{m}^{-1}$, for the different size resonators and in the various packages. Three surfaces were considered for the geometric factor calculations: the Cu packaging “Base”, the “PCB” Cu, and regions where “Glue” was used to adhere the device. $\gamma$ factors smaller than $0.005\ \mathrm{m}^{-1}$ are left blank. R# | Cu$\blacksquare$ | Cu$\square$ | Al$\blacksquare$ | Al$\square$
---|---|---|---|---
$\gamma_{\text{Base/Glue}}$ | $\gamma_{\text{PCB}}$ | $\gamma_{\text{Base}}$ | $\gamma_{\text{PCB}}$ | $\gamma_{\text{Glue}}$ | $\gamma_{\text{PCB}}$ | $\gamma_{\text{Glue}}$ | $\gamma_{\text{PCB}}$ | $\gamma_{\text{Glue}}$
R1 | 0.02 | 0.01 | - | - | - | - | - | - | -
R2 | 0.12 | 0.06 | 0.01 | - | - | 0.01 | - | - | -
R3 | 0.35 | 0.16 | 0.02 | 0.02 | - | 0.06 | 0.02 | 0.01 | -
R4 | 0.95 | 0.42 | 0.06 | 0.04 | 0.12 | 0.24 | 0.07 | 0.03 | 0.01
R5 | 1.6 | 0.89 | 0.16 | 0.13 | 0.04 | 0.77 | 0.22 | 0.12 | 0.03

Table 1 presents the calculated geometric factors $\gamma$ associated with the
different normal conducting regions for each resonator in the different
packages. These regions were the OFHC Cu material (“Base”), the Ag impregnated
glue, and the PCB Cu used to feed signals to the resonator device. Since glue
was pervasive underneath the entire substrate of the chip in
$\text{Cu}\blacksquare$ package, we have combined base and glue together for
that measurement. For other packages, pictures of the device were used to
identify the placement of the glue and hence the regions to calculate $\gamma$
(_e.g._ see purple regions in Fig. 1).

Figure 4: Comparison of estimated and measured resonator loss $1/Q_{i,m}$ for
each resonator and in each package. Note the scale of the y-axis changes at
$1\times 10^{-6}$.

Using the corresponding geometric values from Table 1 and the measured
resistivity values, losses due to the glue, Cu package, and PCB were
calculated using Eq. 1 and compared against measured values in the bar chart
of Fig.4. Note that for $\text{Cu}\blacksquare$ package, a 70% fill rate for
the glue was assumed. For R5, as example, in Cu$\blacksquare$,
$0.7\times\gamma_{glue}=1.2\ \mathrm{m}^{-1}$ implying
$Q_{i,R_{S}}\simeq\times 10^{5}$, a value comparable to the observed measured
loss. Loss from the glue explains the $w$ and $g$ trend observed in the
Cu$\blacksquare$ package and the apparent random high loss measured with R4
and R5 in the other three packages. We note that Goetz et al. reached a
similar conclusion for their source of loss being associated with a conducting
adhesive.Goetz  _et al._ (2016) Nonetheless, several benefits of the hole
underneath the chip are noted:

  1. 1.

The induced currents in the PCB are reduced due to the stored $H$ field
residing in vacuum underneath the device (_e.g._ compare $\gamma_{\text{PCB}}$
for Al$\blacksquare$ and Al$\square$).

  2. 2.

The amount of rf current flowing on and off the chip through the wire bonds is
decreased.

  3. 3.

The fundamental resonant frequency of spurious package modes, which can couple
to the quantum device and result in decoherence, increases due to the lower
dielectric constant of the vacuum in the hole. Simulations show the frequency
of the first package mode increases from approximately 11 GHz up to 22 GHz.

Finally, a slight increase in $Q_{i,m}$ with an increase in resonator width
and gap for R1 to R3 in Al$\square$ was observed (see Fig. 4). To account for
this small trend, a 0.35 nm thick surface interface dielectric loss was added
using $\tan\delta\sim 10^{-3}$ and COMSOL was used to simulate this “surface
loss” (see supplementary materials for details).Woods  _et al._ (2019)

##  IV Conclusion

In this work, we found that conducting losses associated with resistant
materials used in the packaging resulted in an increase in the internal losses
of superconducting microwave resonators. To explore the source of these
losses, a resonator chip was measured in four different packages and finite-
element microwave simulations were performed. Our measurements and simulations
show that resonators with wider center line traces and gaps induced a larger
amount of eddy shielding currents in conducting material directly below the
substrate of the chip and that this could limit the resonator’s $Q_{i}$ when
that conductor had a large resistivity. A predominant source of our loss was
associated with the silver impregnated glue that was used as the adhesive
between the substrate and the package base. This loss and loss from a normal
metal conducting PCB surrounding the device can be mitigated by creating a
hole in the package directly below the chip and using material with a smaller
surface resistance.

While the effect of different packages on the quality factors of
superconducting coplaner waveguide resonators was studied in this paper, these
results can be extended to superconducting transmon qubits. In particular, an
x-mon qubit Barends  _et al._ (2013) with $w=g=30\ \mathrm{\mu m}$ and a
fundamental resonance at $f_{\circ}=6\ \text{GHz}$ was simulated. The center
of the x-mon was placed $1.25\ \text{mm}$ away from both edges of the
substrate in $\text{Cu}\blacksquare$, and in the absence of the conducting
glue a $T_{1}\sim 3\ \mathrm{\mu s}$ limited by the surface resistance of the
Cu backing was found. Switching to $\text{Al}\square$ would increase
$T_{1}\sim 80\ \mathrm{\mu s}$ limited by the Cu in the PCB. Furthermore, to
downconvert hot phonons and reduce quasiparticle tunneling charge parity
rates, a few groups have electroplated Cu on the backside of the substrate in
a grid of squaresIaia  _et al._ (2022). For a $0.5\times 0.5$ mm2 Cu grid with
a 50% fill rate, enough induced currents are produced such that $T_{1}\simeq
18\ \mu\text{s}$ for the x-mon considered here.

Based on the results of this paper, a few final recommendations are made:

  1. 1.

The use of normal conducting glues is not recommended; better choices are the
use of dielectric glues or no glue.333Qdevil: Qcage

  2. 2.

Increasing the separation between the resonator or qubit device and normal
conducting material with the use of holes underneath the substrate or the use
of thicker substrates significantly reduces currents underneath as well as on
and off the device through the wirebonds.

  3. 3.

The use of superconductors with a smaller surface resistance in the package
and PCB could be essential to decrease the loss in very low loss future qubits
or resonators.

  4. 4.

Knowledge of the microwave surface resistance of various materials used in the
package is valuable information.

  5. 5.

Simulations similar to the ones performed here to estimate $\gamma$ are a
valuable tool to utilize.

With some of these recommendations, the lifetimes for our planar transmon
qubits have risen from a few microseconds to $T_{1}\sim 100\ \mu$s.

###### Acknowledgements.

The authors acknowledge useful suggestions and conversations with Christopher
Lobb. The authors thank Danielle Braje and MIT Lincoln Laboratory for the
design of the resonator chip and Ashish Alexander and Chris Richardson for the
use of their PCB.

## Data Availability Statement

The data that support the findings of this study are available from the
corresponding author upon reasonable request.

## References

  * Zmuidzinas (2012) J. Zmuidzinas, “Superconducting microresonators: Physics and applications,” Annu. Rev. Condens. Matter Phys. 3, 169–214 (2012).
  * de Leon  _et al._ (2021) N. P. de Leon, K. M. Itoh, D. Kim, K. K. Mehta, T. E. Northup, H. Paik, B. S. Palmer, N. Samarth, S. Sangtawesin, and D. W. Steuerman, “Materials challenges and opportunities for quantum computing hardware,” Science 372, eabb2823 (2021).
  * Richardson  _et al._ (2016) C. J. K. Richardson, N. P. Siwak, J. Hackley, Z. K. Keane, J. E. Robinson, B. Arey, I. Arslan, and B. S. Palmer, “Fabrication artifacts and parallel loss channels in metamorphic epitaxial aluminum superconducting resonators,” Superconductor Science and Technology 29, 064003 (2016).
  * Chen  _et al._ (2014) Z. Chen, A. Megrant, J. Kelly, R. Barends, J. Bochmann, Y. Chen, B. Chiaro, A. Dunsworth, E. Jeffrey, J. Mutus, _et al._ , “Fabrication and characterization of aluminum airbridges for superconducting microwave circuits,” Applied Physics Letters 104, 052602 (2014).
  * Sheldon  _et al._ (2017) S. Sheldon, M. Sandberg, H. Paik, B. Abdo, J. M. Chow, M. Steffen, and J. M. Gambetta, “Characterization of hidden modes in networks of superconducting qubits,” Applied Physics Letters 111, 222601 (2017).
  * Huang  _et al._ (2021) S. Huang, B. Lienhard, G. Calusine, A. Vepsäläinen, J. Braumüller, D. K. Kim, A. J. Melville, B. M. Niedzielski, J. L. Yoder, B. Kannan, _et al._ , “Microwave package design for superconducting quantum processors,” PRX Quantum 2, 020306 (2021).
  * Córcoles  _et al._ (2011) A. D. Córcoles, J. M. Chow, J. M. Gambetta, C. Rigetti, J. R. Rozen, G. A. Keefe, M. Beth Rothwell, M. B. Ketchen, and M. Steffen, “Protecting superconducting qubits from radiation,” Applied Physics Letters 99, 181906 (2011).
  * Gao  _et al._ (2008) J. Gao, M. Daal, A. Vayonakis, S. Kumar, J. Zmuidzinas, B. Sadoulet, B. A. Mazin, P. K. Day, and H. G. Leduc, “Experimental evidence for a surface distribution of two-level systems in superconducting lithographed microwave resonators,” Applied Physics Letters 92, 152505 (2008).
  * Note (1) Loctite Ablestik: 59C.
  * Yeh  _et al._ (2017) J.-H. Yeh, J. LeFebvre, S. Premaratne, F. C. Wellstood, and B. S. Palmer, “Microwave attenuators for use with quantum devices below 100 mK,” Journal of Applied Physics 121, 224501 (2017).
  * Khalil  _et al._ (2012) M. S. Khalil, M. Stoutimore, F. C. Wellstood, and K. D. Osborn, “An analysis method for asymmetric resonator transmission applied to superconducting devices,” Journal of Applied Physics 111, 054510 (2012).
  * Woods  _et al._ (2019) W. Woods, G. Calusine, A. Melville, A. Sevi, E. Golden, D. K. Kim, D. Rosenberg, J. L. Yoder, and W. D. Oliver, “Determining interface dielectric losses in superconducting coplanar-waveguide resonators,” Physical Review Applied 12, 014012 (2019).
  * Note (2) CircuitWorks: CW2400.
  * Padamsee, Knobloch, and Tom (2011) H. Padamsee, J. Knobloch, and H. Tom, “RF Superconductivity for Accelerators,” (Wiley-VCH, Weinheim, 2011) 2nd ed.
  * Pozar (2005) D. M. Pozar, “Microwave Engineering,” (John Wiley & Sons, Hoboken, 2005) 3rd ed.
  * Gupta  _et al._ (1996) K. C. Gupta, R. Garg, I. Bahl, and P. Bhartia, “Microstrip Lines and Slotlines,” (Artech House, Norwood, 1996) 2nd ed.
  * Goetz  _et al._ (2016) J. Goetz, F. Deppe, M. Haeberlein, F. Wulschner, C. W. Zollitsch, S. Meier, M. Fischer, P. Eder, E. Xie, K. G. Fedorov, _et al._ , “Loss mechanisms in superconducting thin film microwave resonators,” Journal of Applied Physics 119, 015304 (2016).
  * Barends  _et al._ (2013) R. Barends, J. Kelly, A. Megrant, D. Sank, E. Jeffrey, Y. Chen, Y. Yin, B. Chiaro, J. Mutus, C. Neill, _et al._ , “Coherent Josephson qubit suitable for scalable quantum integrated circuits,” Physical Review Letters 111, 080502 (2013).
  * Iaia  _et al._ (2022) V. Iaia, J. Ku, A. Ballard, C. Larson, E. Yelton, C. Liu, S. Patel, R. McDermott, and B. Plourde, “Phonon downconversion to suppress correlated errors in superconducting qubits,” Nature Communications 13, 6425 (2022).
  * Note (3) Qdevil: Qcage.


Subgradient evolution of value functions in discrete-time optimal control

Julio Deride |  | Cristopher Hermosilla |  | Mattia Solla |
---|---|---|---|---|---
Department of Mathematics |  | Department of Mathematics |  | Department of Mathematics |
Universidad T.F.Santa María |  | Universidad T.F.Santa María |  | Universidad T.F.Santa María |
<EMAIL_ADDRESS>|  |<EMAIL_ADDRESS>|  |<EMAIL_ADDRESS>|

Abstract. In this paper we investigate how the subgradients of the value
function of a discrete-time convex Bolza problem evolve over time. In
particular, we develop a discrete-time version of the characteristic method
introduced by Rockafellar and Wolenski in the 2000s, by showing that the time-
evolution of the subgradients of the value functions can be associated with
trajectories of a discrete-time Hamiltonian system. To do so, we first prove
that the value function has a dual counterpart, which corresponds to the
conjugate of the value function of a suitable dual problem. We finally make a
discussion about the qualification conditions we require for our results,
showing in particular that classical problems, such as the Liner-Quadratic
regulator, satisfy these hypotheses.
Keywords: Optimal control, Discrete-time systems, Convex Bolza problems,
Linear-Quadratic regulator, Mixed constraints. AMS Classification: 93C55,
46N10, 49N10,49N15. Date:

##  1 Introduction

This paper is concerned with Bolza problems associated with a discrete-time
dynamical system, that is, we aim at studying the optimization problem

$\text{Minimize }\sum_{t=\tau+1}^{T}L_{t}(x_{t-1},\Delta x_{t})+g(x_{T})$

over all $\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ such that
$x_{\tau}=\xi$. Here $\tau$ and $\xi$ are the initial data of the problem,
which for our purposes are considered as inputs of the problem. The value
$T\in\mathbb{N}$ is the final horizon, which is assumed to be fixed all along
this manuscript.

Our goal is to study the value function of the problem, that is the value of
the optimization problem, denoted $V(\tau,\xi)$, seen as a function of the
initial data $(\tau,\xi)$, and in particular to understand the evolution over
time of the subgradients of the function $\xi\mapsto V(\tau,\xi)$.

To undertake this task, we focus on Bolza problems of convex type (see
Assumption (A) below). This fact provides two key points for our analysis. The
first one, being that the value function turns our to be convex with respect
to the state variable, and the second one being that this structural property
of the value function allows to study convex Bolza problems from a duality
viewpoint. Indeed, in the 1970s, in a series of papers [12, 14, 15, 16, 17],
Rockafellar set the foundations of a duality theory for this type of problems
with underlying continuous-time systems. The main advantage when working in
this context is that a convex optimal control problem can be paired with a
dual problem, which turns out also to be a convex Bolza problem. A sample
result that can be obtained from the theory is that coextremals are minimizers
of the dual problem; see for instance [12, Section 10]. This in particular
leads to necessary optimality conditions, which in this case are habitually
sufficient too, to be given in terms of a Hamiltonian system and also in the
form of a Maximum Principle; see for instance [2, 11, 12, 17, 19]. It is worth
mentioning that considerable attention has been put on studying the value
function in the light of this duality theory for problems without pathwise
constraints; see for instance [3, 4, 5, 6, 10, 9, 20, 7, 22, 23]. Some
contributions for the state constrained case have been done by one of the
authors (see [10, 9]), but there are still several questions to be addressed.
In particular, to understand how these results transpose to deterministic
and/or stochastic discrete-time systems.

It is worth mentioning that Bolza problem with possibly non-finite Lagrangians
allow us to recover classical control problems such as the linear quadratic
optimal control problems (see [18, 8, 10]) or Linear-convex problems with
mixed constraints (see [12, Example 2] or [2]). In particular, our approach
provides a framework to investigate linear quadratic optimal control problems
with state constraints and without coercivity assumptions in the control
variable; this was pointed out in [10].

In the context of time-continuous systems, a global _characteristic method_
for Convex Bolza problems was introduced by Rockafellar and Wolenski in [22,
Theorem 2.4]. The characteristic method describes the time-evolution of the
subgradients of the value functions through following trajectories of a
Hamiltonian system. The cited result holds true for Convex Bolza problems
under standard hypotheses where the Lagrangian is coercive and there are no
state constraints implicitly encoded (see [22, Assumption (A) and Section 3]).
This means the minimization in both the primal and dual problems takes places
over the space of absolutely continuous arcs. This results was later extended
in [9] to problem with state constraints and possibly non-coercive Lagrangian,
where the minimization in both the primal and dual problems takes places, in
that case, over the arcs of bounded variation.

The main contributions of this paper are the following. On the one hand, we
transpose the characteristic method to discrete-time systems, by showing that
the time-evolution of the subgradients of the value functions can be
associated with trajectories of a discrete-time Hamiltonian system. To do so,
we first need to prove that the value function turns out to be the conjugate
of the value function of the dual problem. One the other hand, these results
require some qualification condition on the primal as well on the dual
problem. Qualification conditions over the dual problems may be rather
cumbersome to verify, thus we also show that, under appropriate assumptions on
the data of the primal problem, the qualification conditions over the dual
problems are satisfied immediately.

###  1.1 Notation and essentials

Throughout this paper we use the following notation: $|\cdot|$ is the
Euclidean norm and $a\cdot b$ stands for the Euclidean inner product of
$a,b\in\mathbb{R}^{n}$. We set $[\\![p:q]\\!]:=\\{p,p+1,\ldots,q\\}$, that is,
it is the collection of all integers between $p$ and $q$ (inclusive), assuming
always that $p<q$.

Suppose $\varphi:X\to\mathbb{R}\cup\\{\pm\infty\\}$ is a function with $X$
being a topological vector space (t.v.s. for short). The effective domain of
$\varphi$ is the set

$\mathop{\rm dom}(\varphi):=\\{x\in X\mid\ \varphi(x)<+\infty\\}.$

The function $\varphi$ is said to be proper if $\mathop{\rm
dom}(\varphi)\neq\emptyset$ and $\varphi(x)>-\infty$ for all $x\in X$; convex
if $\mathop{\rm epi}(\varphi):=\\{(x,r)\in X\times\mathbb{R}\mid\
\varphi(x)\leq r\\}$ is a convex set, and lower semicontinuous (l.s.c. for
short) if $\mathop{\rm epi}(\varphi)$ is a closed set.

We also use standard nomenclature of Convex Analysis: $\mathop{\rm ri}(S)$
stands for the _relative interior_ of a convex set $S\subset\mathbb{R}^{n}$.
The indicator and support functions of a set $S\subset\mathbb{R}^{n}$ are
denoted by $\delta_{S}$ and $\sigma_{S}$, respectively. The set $S_{\infty}$
stands for the recession cone of a convex set $S\subset\mathbb{R}^{n}$. The
(convex) normal cone to $S$ at $x\in S$ is the set

$\mathcal{N}_{S}(x):=\\{z\in\mathbb{R}^{n}\mid\ z\cdot(s-x)\leq 0,\ \forall
s\in S\\}.$

Suppose $Y$ is another t.v.s. which is in duality with $X$ via a bilinear
mapping $\langle\cdot,\cdot\rangle:X\times Y\to\mathbb{R}$. When
$X=\mathbb{R}^{n}$, we assume it is in duality with itself via the Euclidean
inner product. The conjugate of $\varphi:X\to\mathbb{R}\cup\\{+\infty\\}$ is
the mapping $\varphi^{*}:Y\to\mathbb{R}\cup\\{\pm\infty\\}$ defined via the
formula

$\varphi^{*}(y):=\sup\left\\{\langle x,y\rangle-\varphi(x)\mid\ x\in
X\right\\},\qquad\forall y\in Y,$

and its subdifferential at $x\in\mathop{\rm dom}(\varphi)$ is the set

$\partial\varphi(x):=\\{y\in Y\mid\varphi(x)+\langle
y,z-x\rangle\leq\varphi(z),\ \forall z\in X\\}.$

These mathematical objects are related via the Fenchel-Young equality:

$y\in\partial\varphi(x)\quad\Longleftrightarrow\quad\varphi(x)+\varphi^{*}(y)=\langle
x,y\rangle.$ (1)

A function
$h:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}\cup\\{\pm\infty\\}$ is
called _concave-convex_ if $h_{y}(\cdot)=-h(\cdot,y)$ and
$h_{x}(\cdot)=h(x,\cdot)$ are convex functions. The (concave-convex)
subdifferential of $h$ is the set

$\partial h(x,y):=[-\partial h_{y}(x)]\times\partial
h_{x}(y),\qquad\forall(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{n}.$ (2)

##  2 Fully Convex Bolza problems

The focus of this paper will be on discrete-time dynamical systems that evolve
until a given final time horizon $T>0$, which in our setting is a nonnegative
integer that remains fixed all along the manuscript.

The optimization model we analyze corresponds to a Bolza problem associated
with a running cost
$L:[\\![1:T]\\!]\times\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$
(the Lagrangian of the problem) and a given terminal cost
$g:\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$. In particular, we are
concerned with the value function of this discrete-time Bolza problem, which
is the mapping that to any given initial position
$(\tau,\xi)\in[\\![0:T-1]\times\mathbb{R}^{n}$ assigns the optimal payoff of
the problem

$\vartheta_{\tau}(\xi):=\inf\left\\{\sum_{t=\tau+1}^{T}L_{t}(x_{t-1},\Delta
x_{t})+g(x_{T})\mid\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n},\
x_{\tau}=\xi\right\\},$ (P)

where $\Delta x_{t}=x_{t}-x_{t-1}$ and $L_{t}=L(t,\cdot)$ for any
$t\in[\\![1:T]$. Our task in this paper is to explore duality relations for
this value function, by posing the discussion in a fully convex context. The
latter means that we are mainly concerned with the case when the following
basic assumption holds:

$\displaystyle\begin{cases}L_{t}\text{ is proper, convex and l.s.c. for any
}t\in[\\![1:T];\\\ g\text{ is proper, convex and l.s.c.}\end{cases}$ (A)

Unless otherwise stated, we will always assume that (A) is in force.

###  2.1 Dual Bolza problem and weak duality

The convex setting we are studying in this paper prompts for a duality theory
which can be obtained via the standard approach with perturbation functions
(cf. [21]). Inspired by study done in [22] for time-continuous Bolza problems,
we consider a dual problem to (P), whose value function (the _dual value
function_ in the sequel), is given, for $\tau\in[\\![0:T-1]$ and
$\eta\in\mathbb{R}^{n}$, by the expression

$\omega_{\tau}(\eta):=\inf\left\\{\sum_{t=\tau+1}^{T}K_{t}(p_{t},\Delta
p_{t})+f(p_{T})\mid\\{p_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n},\
p_{\tau}=-\eta\right\\}.$ (D)

Here $\Delta p_{t}=p_{t}-p_{t-1}$,
$f:\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$ is the _dual terminal cost_
given by

$f(b):=g^{*}(-b),\qquad\forall b\in\mathbb{R}^{n},$

and $K_{t}=K(t,\cdot)$, where
$K:[\\![1:T]\\!]\times\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$
is the _dual Lagrangian_ which is given by

$K(t,p,w):=\sup_{x,v\in\mathbb{R}^{n}}\\{x\cdot w+v\cdot
p-L_{t}(x,v)\\},\qquad\forall p,w\in\mathbb{R}^{n}.$

Accordingly, in the sequel, we will refer to the mapping
$(\tau,\xi)\mapsto\vartheta_{\tau}(\xi)$ given by (P) as the _primal value
function_.

######  Remark 2.1.

Although problem (D) has not been written exactly as the primal problem (P),
it is not difficult to see that it can be brought to that form if we consider
the Lagrangian $\tilde{L}_{t}(p,w)=K_{t}(p+w,w)$. In this case, it is also
evident that, since $\tilde{L}_{t}^{*}(v,x)=K_{t}^{*}(v,x-v)=L_{t}(x-v,v)$,
the dual problem to (D) (defined in the way proposed above) is exactly (P).

Notice that, as for the time continuous case, we can extend the definition of
both value functions up to time $\tau=T$ as follows:

$\vartheta_{T}(\xi)=g(\xi)\quad\text{and}\quad\omega_{T}(\eta)=f(-\eta),\qquad\forall\xi,\eta\in\mathbb{R}^{n}.$

From the definition of the conjugate, it follows that

$\vartheta_{T}(\xi)+\omega_{T}(\eta)\geq\xi\cdot\eta,\qquad\forall\xi,\eta\in\mathbb{R}^{n}.$

Notice that in particular, we have that $\omega_{T}\geq\vartheta_{T}^{*}$ and
$\vartheta_{T}\geq\omega_{T}^{*}$. This weak duality relation, becomes strong
(with equality) whenever the transversality condition $-\eta\in\partial
g(\xi)$ holds; this is a straightforward consequence of (1).

The next proposition shows that this weak duality relation propagates backward
in time for any $\tau\in[\\![0:T]\\!]$. Latter on, we will show that the weak
duality stated below becomes strong under certain qualification conditions.

######  Proposition 2.2.

For any $\tau\in[\\![0:T]\\!]$ we have that

$\vartheta_{\tau}(\xi)+\omega_{\tau}(\eta)\geq\xi\cdot\eta,\qquad\forall\xi,\eta\in\mathbb{R}^{n}.$

Moreover, we also have that $\omega_{\tau}\geq\vartheta_{\tau}^{*}$ and
$\vartheta_{\tau}\geq\omega_{\tau}^{*}$.

###### Proof.

We note that it is enough to check the inequality for
$\xi,\eta\in\mathbb{R}^{n}$ such that
$\vartheta_{\tau}(\xi),\omega_{\tau}(\eta)<+\infty$, otherwise the conclusion
is straightforward (considering the convention $+\infty\pm\infty=+\infty$).
Note that we are not assuming a priori that
$\vartheta_{\tau}(\xi),\omega_{\tau}(\eta)>-\infty$.

Let $\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ and
$\\{p_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ be feasible processes for the
optimization problems defined in (P) and (D), respectively. Notice that by the
definition of the conjugate we have

$L_{t}(x_{t-1},\Delta x_{t})+K_{t}(p_{t},\Delta p_{t})\geq x_{t-1}\cdot\Delta
p_{t}+\Delta x_{t}\cdot p_{t}=x_{t}\cdot p_{t}-x_{t-1}\cdot p_{t-1}.$

Thus,

$\sum_{t=\tau+1}^{T}L_{t}(x_{t-1},\Delta
x_{t})+\sum_{t=\tau+1}^{T}K_{t}(p_{t},\Delta p_{t})\geq x_{T}\cdot
p_{T}-x_{\tau}\cdot p_{\tau}=x_{T}\cdot p_{T}+\xi\cdot\eta.$

Since $f(b)=g^{*}(-b)$, the definition of the conjugate of $g$ leads to

$g(x_{T})+f(p_{T})\geq-x_{T}\cdot p_{T}.$

It follows that

$\sum_{t=\tau+1}^{T}L_{t}(x_{t-1},\Delta
x_{t})+g(x_{T})+\sum_{t=\tau+1}^{T}K_{t}(p_{t},\Delta
p_{t})+f(p_{T})\geq\xi\cdot\eta.$

Taking infimum over $\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ and
$\\{p_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ we get the desired inequality.
In particular, we must have that $\vartheta_{\tau}(\xi)>-\infty$ and
$\omega_{\tau}(\eta)>-\infty$, and thus $\eta\in\mathop{\rm
dom}(\omega_{\tau})$ and $\xi\in\mathop{\rm dom}(\vartheta_{\tau})$. ∎

###  2.2 Strong duality

Let us now focus on proving a strong duality result, which in our case means
that the primal and dual value functions are conjugate to each other. For such
purpose we introduce the following qualification condition:

$\displaystyle\begin{cases}\exists\\{\bar{x}_{t}\\}_{t=0}^{T}\subset\mathbb{R}^{n},\quad\text{such
that }\bar{x}_{T}\in\mathop{\rm ri}\left(\mathop{\rm dom}(g)\right),\\\
\bar{x}_{t-1}\in\mathop{\rm
ri}\left({\mathbf{X}}(t)\right)\quad\text{and}\quad\Delta\bar{x}_{t}\in\mathop{\rm
ri}\left(\Gamma_{L}(t,\bar{x}_{t-1})\right),\quad\forall
t\in[\\![1:T]\\!].\end{cases}$ (H)

where

$\Gamma_{L}(t,x):=\\{v\in\mathbb{R}^{n}\mid\
L_{t}(x,v)\in\mathbb{R}\\},\,\quad\text{and}\quad\,{\mathbf{X}}(t):=\\{x\in\mathbb{R}^{n}\mid\
\Gamma_{L}(t,x)\neq\emptyset\\}.$

######  Remark 2.3.

Notice that the minimization process in (P) can be restrained to processes
whose initial position $x_{\tau}=\xi$ is brought to the target $\mathop{\rm
dom}(g)$ at time $t=T$. This means that the set $\mathop{\rm dom}(g)$ can in
this context be understood as a terminal constraint, implicitly encoded in the
formulation of the problem.

Similarly, by allowing each $L_{t}$ to take infinite values, we are handling
implicitly constraints over the state of system $x_{t}$ and the variation
$\Delta x_{t}$. Indeed, any feasible processes of the Bolza problem (P) must
satisfy:

$\displaystyle x_{t-1}\in{\mathbf{X}}(t)\quad\text{and}\quad\Delta
x_{t}\in\Gamma_{L}(t,x_{t-1}),\quad\forall t\in[\\![\tau+1:T]\\!].$

In other words, the set-valued maps $\Gamma_{L}$ and ${\mathbf{X}}$ correspond
respectively to the underlying dynamics of the system and to the (time-
dependent) state-constraint.

Taking this into account, it follows that the qualification condition (H) can
be understood as a _strict feasibility assumption_ over the dynamical system.

We are now in a position to establish a strong duality relation between the
primal and dual value functions.

######  Proposition 2.4.

Under Hypothesis (H), for any $\tau\in[\\![0:T]\\!]$ it follows that
$\vartheta_{\tau}^{*}=\omega_{\tau}$. Moreover, the infimum in the definition
of $\omega_{\tau}(\eta)$ is attained for any $\eta\in\mathop{\rm
dom}(\omega_{\tau})$.

###### Proof.

Let $\tau\in[\\![0:T]\\!]$ be given. Note that from (H), we get
$\vartheta_{\tau}(\bar{x}_{\tau})<+\infty$. In particular, it follows that

$\vartheta_{\tau}^{*}(\eta)\geq\bar{x}_{\tau}\cdot\eta-\vartheta_{\tau}(\bar{x}_{\tau})>-\infty,\qquad\forall\eta\in\mathbb{R}^{n}.$

Let us focus on proving first $\omega_{\tau}=\vartheta_{\tau}^{*}$. Let us
define $\mathbf{E}_{\tau}=\prod_{t=\tau}^{T}\mathbb{R}^{n}$, and observe that
for $\eta\in\mathop{\rm dom}(\vartheta_{\tau}^{*})$ we have

$-\vartheta^{*}_{\tau}(\eta)=\inf_{\xi\in\mathbb{R}^{n}}\left\\{\vartheta_{\tau}(\xi)-\xi\cdot\eta\right\\}=\inf_{\mathbf{x}\in\mathbf{E}_{\tau}}\left\\{\sum_{t=\tau+1}^{T}L_{t}(x_{t-1},\Delta
x_{t})+g(x_{T})-x_{\tau}\cdot\eta\right\\},$

where we have considered $\mathbf{x}=\\{x_{t}\\}_{t=\tau}^{T}$. If we define
$\ell(a,b)=g(b)-a\cdot\eta$, it is not difficult to see that $\mathop{\rm
ri}(\mathop{\rm dom}(\ell))=\mathbb{R}^{n}\times\mathop{\rm ri}(\mathop{\rm
dom}(g))$, and so, from the arguments used to prove [21, Theorem 2], it
follows that (H) implies that $\partial\phi(0)\neq\emptyset$, where for any
$\mathbf{y}=\\{y_{t}\\}_{t=\tau}^{T}\in\mathbf{E}_{\tau}$ the perturbation
function $\phi$ is

$\phi(\mathbf{y})=\inf_{\mathbf{x}\in\mathbf{E}_{\tau}}\left\\{\sum_{t=\tau+1}^{T}L_{t}(x_{t-1},\Delta
x_{t}+y_{t})+\ell(x_{\tau}+y_{\tau},x_{T})\right\\}.$ (3)

From [21, Theorem 3] we get that

$\vartheta^{*}_{\tau}(\eta)=\min_{\mathbf{p}\in\mathbf{E}_{\tau}}\left\\{\sum_{t=\tau+1}^{T}K_{t}(p_{t},\Delta
p_{t})+\ell^{*}(p_{\tau},-p_{T})\mid\mathbf{p}=\\{p_{t}\\}_{t=\tau}^{T}\right\\},$

and the minimum is attained at some
$\\{p^{*}_{t}\\}_{t=\tau}^{T}\in\partial\phi(0)\subset\mathbf{E}_{\tau}$.
Therefore, since $\ell^{*}(a,b)=g^{*}(b)$ if $a=-\eta$ and
$\ell^{*}(a,b)=+\infty$ otherwise, we get that
$\omega_{\tau}=\vartheta_{\tau}^{*}$; for the case
$\vartheta_{\tau}^{*}(\eta)=+\infty$ the equality follows from the weak
duality (Proposition 2.2). ∎

In a symmetric way, if now a qualification condition is imposed over the data
of the dual problem, a similar result can be obtained. To be more precise, let
us consider the following qualification condition

$\displaystyle\begin{cases}\exists\\{\bar{p}_{t}\\}_{t=0}^{T}\subset\mathbb{R}^{n},\quad\text{such
that }\bar{p}_{T}\in\mathop{\rm ri}\left(\mathop{\rm dom}(f)\right),\\\
\bar{p}_{t-1}\in\mathop{\rm
ri}\left({\mathbf{P}}(t)\right)\quad\text{and}\quad\Delta\bar{p}_{t}\in\mathop{\rm
ri}\left(\Gamma_{K}(t,\bar{p}_{t-1})\right),\quad\forall
t\in[\\![1:T]\\!],\end{cases}$ (H’)

where,

$\Gamma_{K}(t,p):=\\{w\in\mathbb{R}^{n}\mid\
K_{t}(p+w,w)\in\mathbb{R}\\},\,\quad\text{and}\quad{\mathbf{P}}(t):=\\{p\in\mathbb{R}^{n}\mid\
\Gamma_{K}(t,p)\neq\emptyset\\}.$

######  Remark 2.5.

Similarly as for the primal problem, the set-valued maps $\Gamma_{K}$ and
${\mathbf{P}}$ can be interpreted respectively as the dynamics and as the
state-constraint of the _dual system_ , which are implicitly encoded in the
formulation of the problem. Also, $\mathop{\rm dom}(f)$ corresponds to the
underlying terminal constraint of the problem. Consequently, any feasible arc
of the dual Bolza problem (D) must satisfy the following constraints:

$\displaystyle p_{t-1}\in{\mathbf{P}}(t)\quad\text{and}\quad\Delta
p_{t}\in\Gamma_{K}(t,p_{t-1}),\quad\forall
t\in[\\![\tau+1:T]\\!]\quad\text{and}\quad p_{T}\in\mathop{\rm dom}(f).$

In this context, the qualification condition (H’) can be understood as a
_strict feasibility assumption_ over the dual dynamical system.

By symmetry, it is not difficult to see (in the light of Remark 2.1), that the
following statement holds true.

######  Proposition 2.6.

Under Hypothesis (H’), for any $\tau\in[\\![0:T]\\!]$ it follows that
$\omega_{\tau}^{*}=\vartheta_{\tau}$. Moreover, the infimum in the definition
of $\vartheta_{\tau}(\xi)$ is attained for any $\xi\in\mathop{\rm
dom}(\vartheta_{\tau})$.

As a consequence, under Hypotheses (H) and (H’), for any
$\tau\in[\\![0:T]\\!]$ we have that $\vartheta_{\tau}$ and $\omega_{\tau}$ are
convex proper and l.s.c. functions on $\mathbb{R}^{n}$. Moreover, they are
conjugate to each other, that is,

$\vartheta_{\tau}^{*}=\omega_{\tau}\quad\text{and}\quad\vartheta_{\tau}=\omega_{\tau}^{*}.$

##  3 Discrete-time Characteristic method

We now present and prove a discrete-time characteristic method, whose main
goal is to provide a description of the evolution of the subgradients of the
primal value function by means of a discrete-time Hamiltonian system.

Let
$H:[\\![0:T]\\!]\times\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}\cup\\{\pm\infty\\}$
be the Hamiltonian associated with the primal problem (P), that is

$H(t,x,p):=\sup_{v\in\mathbb{R}^{n}}\left\\{p\cdot v-L_{t}(x,v)\right\\}.$

For $t\in[\\![1:T]\\!]$ fixed, this function is concave in $x$ and convex in
$p$, thus its subdifferential is given by (2). In particular, setting
$H_{t}=H(t,\cdot)$, we have that $(-w,v)\in\partial H_{t}(\bar{x},\bar{p})$ if
and only if

$H_{t}(x,\bar{p})+w\cdot(x-\bar{x})\leq H_{t}(\bar{x},\bar{p})\leq
H_{t}(\bar{x},p)-v\cdot(p-\bar{p}),\qquad\forall x,p\in\mathbb{R}^{n}.$

######  Definition 3.1.

For any $\tau\in[\\![0:T-1]\\!]$, we say that
$\\{(x_{t},p_{t})\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}\times\mathbb{R}^{n}$ is
a _discrete-time Hamiltonian trajectory_ on $[\\![\tau:T]\\!]$ provided that

$(-\Delta p_{t},\Delta x_{t})\in\partial H_{t}(x_{t-1},p_{t}),\qquad\forall
t\in[\\![\tau+1,T]\\!].$ (4)

The characteristic method and main result of this paper is the following.

######  Theorem 3.2.

Let $\tau\in[\\![0:T-1]\\!]$ and $\xi,\eta\in\mathbb{R}^{n}$ be given. Suppose
that there is a _discrete-time Hamiltonian trajectory_ on $[\\![\tau:T]\\!]$,
say
$\\{(x_{t},p_{t})\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}\times\mathbb{R}^{n}$,
such that $(x_{\tau},p_{\tau})=(\xi,-\eta)$ and that satisfies the
transversality condition

$-p_{T}\in\partial g(x_{T}).$

Then, $\eta\in\partial\vartheta_{\tau}(\xi)$. Moreover, the converse holds
true if the Hypotheses (H) and (H’) are in force.

###### Proof.

Let $l:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}$ be the convex proper
and l.s.c. function given by

$l(a,b)=g(b)-a\cdot\eta$

Let
$\\{(x_{t},p_{t})\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}\times\mathbb{R}^{n}$ be
given. It is not difficult to see that the transversality condition
$-p_{T}\in\partial g(x_{T})$ combined with $p_{\tau}=-\eta$ is equivalent to

$(p_{\tau},-p_{T})\in\partial\ell(x_{\tau},x_{T}).$ (5)

Moreover, since

$H(t,x,p):=\sup_{v\in\mathbb{R}^{n}}\left\\{p\cdot v-L_{t}(x,v)\right\\},$

from [13, Theorem 37.5], we have that the condition of being a _discrete-time
Hamiltonian trajectory_ on $[\\![\tau:T]\\!]$ (see equation (4)) is equivalent
to the _discrete-time Euler-Lagrange relation_

$(\Delta p_{t},p_{t})\in\partial L_{t}(x_{t-1},\Delta x_{t}),\qquad\forall
t\in[\\![\tau+1:T]\\!].$ (6)

Let $\\{(x_{t},p_{t})\\}_{t=\tau}^{T}$ be as on the statement of the theorem.
From [21, Theorem 1], we have that $\\{x_{t}\\}_{t=\tau}^{T}$ is an optimal
trajectory for

$\inf_{\mathbf{y}\in\mathbf{E}_{\tau}}\left\\{\sum_{t=\tau+1}^{T}L_{t}(y_{t-1},\Delta
y_{t})+g(y_{T})-y_{\tau}\cdot\eta\right\\}=\inf_{y_{\tau}\in\mathbb{R}^{n}}\left\\{\vartheta_{\tau}(y_{\tau})-y_{\tau}\cdot\eta\right\\},$
($\mathcal{P}_{0}$)

and that $\\{p_{t}\\}_{t=\tau}^{T}\in\partial\phi(0)$, where we recall that
$\phi$ is the perturbation function given by (3). From [21, Theorem 3], it
follows that $\\{p_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ realizes
$\omega_{\tau}(\eta)$, and moreover, $\mathop{\rm
val}\eqref{eq:auxp}=-\omega_{\tau}(\eta)$. Notice that
$\\{x_{t}\\}_{t=\tau}^{T}$ realizes $\vartheta_{\tau}(\xi)$ as well, and that
$\vartheta_{\tau}(\xi)=\mathop{\rm val}\eqref{eq:auxp}+\xi\cdot\eta$. From
Proposition 2.2, we get that $\vartheta_{\tau}$ and $\omega_{\tau}$ are
conjugate to each other, and that the Fenchel-Young equality holds at
$(\xi,\eta)$, and so $\eta\in\partial\vartheta_{\tau}(\xi)$.

Conversely, let us assume that (H) and (H’) hold and that
$\eta\in\partial\vartheta_{\tau}(\xi)$. In particular $\xi\in\mathop{\rm
dom}(\vartheta_{\tau})$, and so, by Proposition 2.6, there is an optimal
trajectory that realizes $\vartheta_{\tau}(\xi)$, that is, there is
$\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ such that $x_{\tau}=\xi$ and

$\vartheta_{\tau}(\xi)=\sum_{t=\tau+1}^{T}L_{t}(x_{t-1},\Delta
x_{t})+g(x_{T}).$

Notice that the condition $\eta\in\partial\vartheta_{\tau}(\xi)$ is equivalent
to $\xi\in\partial\omega_{\tau}(\eta)$ because $\vartheta_{\tau}$ and
$\omega_{\tau}$ are conjugate to each other. Hence, $\eta\in\mathop{\rm
dom}(\omega_{\tau})$, and thus Proposition 2.4 implies that there is an
optimal trajectory that realizes $\omega_{\tau}(\eta)$, that is,
$\\{p_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ such that $p_{\tau}=-\eta$ and

$\omega_{\tau}(\eta)=\sum_{t=\tau+1}^{T}K_{t}(p_{t},\Delta p_{t})+f(p_{T}).$

From the Fenchel-Young equality we have that
$\vartheta_{\tau}(\xi)+\omega_{\tau}(\eta)=\xi\cdot\eta$. Thus
$\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}$ realizes the infimum in
($\mathcal{P}_{0}$). Moreover, from the proof of Proposition 2.4 we also have
that $\\{p_{t}\\}_{t=\tau}^{T}\in\partial\phi(0)$. It follows from [21,
Theorem 1] that the transversality condition (5) and the discrete-time Euler-
Lagrange relation (6) holds. We have already discussed that these conditions
are equivalent to the transversality condition given on the statement and to
be a discrete-time Hamiltonian trajectory, so the conclusion follows. ∎

##  4 Examples

Let us now provide some explicit formulae for two type of optimal control
problems that fit into the convex setting we have posed for our analysis. The
dynamics that govern both problems are jointly linear in the state and in the
control. In particular, throughout this section, we consider some matrices
$A_{0},\ldots,A_{T-1}$ and $B_{0},\ldots,B_{T-1}$ of dimension ${n\times n}$
and ${n\times m}$, respectively, and some given _drifts_
$\varphi_{0},\ldots,\varphi_{T-1}\in\mathbb{R}^{n}$; these serve as the
building blocks for the linear systems we discuss below.

We also take $\mathcal{X}_{0},\ldots,\mathcal{X}_{T}\subset\mathbb{R}^{n}$ and
$\mathcal{U}_{0}\ldots\mathcal{U}_{T-1}\subset\mathbb{R}^{m}$ to be some given
convex, closed, and nonempty sets; the first ones will play the role of (pure)
state constraints and the second ones of (pure) control constraints.

###  4.1 Linear Quadratic problem with state constraints

The first example we study is the so-called the linear quadratic (LQ) problem.
We show that this model can be studied in the framework of this paper.
Throughout this example, we consider the positive semidefinite matrices
$Q_{1},\ldots,Q_{T}$ and $R_{0},\ldots,R_{T-1}$ of dimension ${n\times n}$ and
${m\times m}$, respectively, associated with the objective cost function of
the problem; we set $Q_{0}$ to be the zero matrix of dimension ${n\times n}$.

Given an initial position $(\tau,\xi)\in[\\![0:T-1]\\!]\times\mathbb{R}^{n}$,
the (LQ) problem we are interested in can be stated as follows:

$\begin{cases}\text{ Minimize
}&\dfrac{1}{2}\left[\displaystyle\sum_{t=\tau}^{T-1}\left(\|x_{t+1}\|^{2}_{Q_{t+1}}+\|u_{t}\|^{2}_{R_{t}}\right)\right]\\\
\text{ over all }&\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}\text{ and
}\\{u_{t}\\}_{t=\tau}^{T-1}\subset\mathbb{R}^{n}\text{ with }x_{\tau}=\xi,\\\
\text{ such that }&\Delta
x_{t+1}=A_{t}x_{t}+B_{t}u_{t}+\varphi_{t},\qquad\forall
t\in[\\![\tau:T-1]\\!],\\\ &u_{t}\in\mathcal{U}_{t},\qquad\forall
t\in[\\![\tau:T-1]\\!],\\\ &x_{t}\in\mathcal{X}_{t},\qquad\forall
t\in[\\![\tau:T]\\!].\end{cases}$ (LQ)

Here we use the notation $\|z\|^{2}_{M}:=z\cdot Mz$ for $z\in\mathbb{R}^{d}$,
and for a $d\times d$ matrix $M$.

To formulate the problem as in (P), we set the endpoint cost
$g:\mathbb{R}^{n}\to\mathbb{R}$ as $g(a):=\frac{1}{2}\|a\|^{2}_{Q_{T}}$, and
the Lagrangian
$L:[\\![1:T]\\!]\times\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$
as

$L(t+1,x,v)=\frac{1}{2}\|x\|^{2}_{Q_{t}}+\delta_{\mathcal{X}_{t}}(x)+\inf_{u\in{\mathcal{U}_{t}}}\left\\{\frac{1}{2}\|u\|^{2}_{R_{t}}\mid
v=A_{t}x+B_{t}u+\varphi_{t}\right\\}.$

In order to ensure the l.s.c of the Lagrangian, we assume the following
qualification condition.

$\displaystyle\ker(B_{t})\cap\ker(R_{t})\cap(\mathcal{U}_{t})_{\infty}=\\{0\\},\qquad\forall
t\in[\\![0:T-1]\\!].$ (CQ)

Given that the recession function of
$u\mapsto\frac{1}{2}\|u\|^{2}_{R_{t}}+\delta_{\mathcal{U}_{t}}(u)$ is the
indicator function of $\ker(R_{t})\cap(\mathcal{U}_{t})_{\infty}$, we can
conclude that (CQ) implies the qualification condition as per [1, Corollary
3.5.7]. Consequently, the infimum in the Lagrangian’s definition is attained,
rendering it an l.s.c. function.

Set

$S_{t}:=\\{(x,u,v)\in\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}^{n}\mid
v=A_{t}x+B_{t}u+\varphi_{t}\\}.$

We can easily see that we have:

$\displaystyle\vartheta(\tau,\xi)=\inf_{\begin{subarray}{c}\\{x_{t}\\}\subset\mathbb{R}^{n}\\\
x_{\tau}=\xi\end{subarray}}\sum_{t=\tau+1}^{T}\left[L_{t}(x_{t-1},\Delta
x_{t})\right]+g(x_{T})$
$\displaystyle=\inf_{\begin{subarray}{c}\\{x_{t}\\}\subset\mathbb{R}^{n}\\\
x_{\tau}=\xi\end{subarray}}\frac{1}{2}\sum_{t=\tau}^{T-1}\left[\|x_{t}\|_{Q_{t}}^{2}+\delta_{\mathcal{X}_{t}}(x_{t})+\inf_{u_{t}\in\mathcal{U}_{t}}\\{\|u_{t}\|_{R_{t}}^{2}+\delta_{S_{t}}(x_{t},u_{t},\Delta
x_{t+1})\\}\right]+\frac{1}{2}\|x_{T}\|_{Q_{T}}^{2}$
$\displaystyle=\inf_{\begin{subarray}{c}\\{x_{t}\\}\subset\mathbb{R}^{n}\\\
\\{u_{t}\\}\subset\mathbb{R}^{m}\\\
x_{\tau}=\xi\end{subarray}}\frac{1}{2}\sum_{t=\tau}^{T-1}\left[\|x_{t+1}\|_{Q_{t+1}}^{2}+\|u_{t}\|_{R_{t}}^{2}+\delta_{\mathcal{X}_{t}}(x_{t})+\delta_{\mathcal{U}_{t}}(u_{t})+\delta_{S_{t}}(x_{t},u_{t},\Delta
x_{t+1})\right].$

Therefore, the Bolza formulation is equivalent to the original problem.
Turning our attention to the dual problem, we proceed to calculate both $f$
and $K_{t}$.

$f(b)=g^{\ast}(-b)=\sup_{x\in\mathbb{R}^{n}}\left\\{-x\cdot
b-\frac{1}{2}\|x\|_{Q_{T}}^{2}\right\\}.$

When $Q_{T}$ is positive definite, the supremum is achieved at
$x=-Q_{T}^{-1}b$, and consequently, $f(b)=\frac{1}{2}\|b\|_{Q_{T}^{-1}}^{2}$.
On the other hand

$\begin{split}&K(t+1,p,w)=\sup_{x,v\in\mathbb{R}^{n}}\left\\{x\cdot w+v\cdot
p-L_{t+1}(x,v)\right\\}\\\ &=\sup_{x,v\in\mathbb{R}^{n}}\left\\{x\cdot
w+v\cdot
p-\frac{1}{2}\left(\|x\|_{Q_{t}}^{2}+\delta_{\mathcal{X}_{t}}(x)+\inf_{u\in\mathcal{U}_{t}}\\{\|u\|_{R_{t}}^{2}+\delta_{S_{t}}(x,u,v)\\}\right)\right\\}\\\
&=\sup_{\begin{subarray}{c}x\in\mathcal{X}_{t}\\\ u\in\mathcal{U}_{t}\\\
v\in\mathbb{R}^{n}\end{subarray}}\left\\{x\cdot w+v\cdot
p-\frac{1}{2}\|x\|_{Q_{t}}^{2}-\frac{1}{2}\|u\|_{R_{t}}^{2}\mid
v=A_{t}x+B_{t}u+\varphi_{t}\right\\}\\\
&=\sup_{\begin{subarray}{c}x\in\mathcal{X}_{t}\\\
u\in\mathcal{U}_{t}\end{subarray}}\left\\{x\cdot(A_{t}^{T}p+w)-\frac{1}{2}\|x\|_{Q_{t}}^{2}+u\cdot
B_{t}^{T}p-\frac{1}{2}\|u\|_{R_{t}}^{2}\right\\}+\varphi_{t}\cdot p,\\\
&=\sup_{x\in\mathcal{X}_{t}}\left\\{x\cdot(A_{t}^{T}p+w)-\frac{1}{2}\|x\|_{Q_{t}}^{2}\right\\}+\sup_{u\in\mathcal{U}_{t}}\left\\{u\cdot
B_{t}^{T}p-\frac{1}{2}\|u\|_{R_{t}}^{2}\right\\}+\varphi_{t}\cdot
p.\end{split}$

We now focus on providing conditions on the primal problem to ensure (H) and
(H’). Recall that
$\Gamma_{L}(t,x)=\\{v\in\mathbb{R}^{n}:L_{t}(x,v)\in\mathbb{R}\\}$, then

$\Gamma_{L}(t,x)\left\\{v\in\mathbb{R}^{n}\mid\|x\|_{Q_{t-1}}^{2}+\delta_{\mathcal{X}_{t-1}}(x)\\\
+\inf_{u\in\mathcal{U}_{t-1}}\left\\{\|u\|_{R_{t-1}}^{2}+\delta_{S_{t-1}}(x,u,v)\right\\}\in\mathbb{R}\right\\}.$

From this, it is staightforward that if $x\notin\mathcal{X}_{t-1}$, then
$\Gamma_{L}(t,x)=\emptyset$. If $x\in\mathcal{X}_{t-1}$, then
$v\in\Gamma_{L}(t,x)$ if and only if
$\inf\left\\{\|u\|_{R_{t-1}}^{2}+\delta_{S_{t-1}}(x,u,v)\mid
u\in\mathcal{U}_{t-1}\right\\}\in\mathbb{R}$. Given that the function
$\|\cdot\|_{R_{t}}^{2}$ is real valued, and bounded from below, it follows
that if $x\in\mathcal{X}_{t-1}$, and

$\begin{split}v\in\Gamma_{L}(t,x)&\Leftrightarrow\exists
u\in\mathcal{U}_{t-1}\ \textrm{s.t.}\ v=A_{t-1}x+B_{t-1}u+\varphi_{t-1},\\\
&\Leftrightarrow v\in
B_{t-1}\mathcal{U}_{t-1}+A_{t-1}x+\varphi_{t-1}.\end{split}$

Therefore, if $x\in\mathcal{X}_{t-1}$,
$\Gamma_{L}(t,x)=B_{t-1}\mathcal{U}_{t-1}+A_{t-1}x+\varphi_{t-1}$. As
$\mathcal{U}_{t-1}$ is nonempty, we have that
${\mathbf{X}}(t)=\mathcal{X}_{t-1}$ for all $t$. Thus, if
$\mathcal{X}_{t}=\mathbb{R}^{n}$ for every $t$, (H) holds true due to the fact
that

$\mathop{\rm ri}(\Gamma_{L}(t,x))=\mathop{\rm
ri}(B_{t-1}(\mathcal{U}_{t-1}))+A_{t-1}x+\varphi_{t-1}=B_{t-1}(\mathop{\rm
ri}(\mathcal{U}_{t-1}))+A_{t-1}x+\varphi_{t-1}$

is always nonempty as $\mathcal{U}_{t-1}$ is convex.

We now study the case where $\mathcal{X}_{1}=\ldots=\mathcal{X}_{T}=X$. We
look for conditions to have an equilibrium point in the system, that is,
$x\in\mathop{\rm ri}(X)$ such that $0\in B_{t}(\mathop{\rm
ri}(\mathcal{U}_{t}))+A_{t}x+\varphi_{t}$. This condition implies (H), as we
can choose $\bar{x}_{1}=\ldots=\bar{x}_{T}=x$. To verify the existence of such
a point, we can solve the following linear system of equations

$\begin{bmatrix}A_{t}&B_{t}\end{bmatrix}\begin{bmatrix}x\\\
u\end{bmatrix}=-\varphi_{t}$

for each $t$, and intersect the solution sets with $\mathop{\rm
ri}(X)\times\mathop{\rm ri}(\mathcal{U}_{t})$. If there is some $\bar{x}$ that
belongs to this intersection for every $t$, then we have (H). In particular,
we can check if $0\in\mathop{\rm ri}(X)$ and $0\in B_{t}(\mathop{\rm
ri}(\mathcal{U}_{t}))+\varphi_{t}$. If $\varphi_{t}=0$, we can replace it with
simply $0\in\mathop{\rm ri}(X)$ and $0\in\mathop{\rm ri}(\mathcal{U}_{t})$.
Moreover, if $X$ has a nonempty interior and $A_{t}$ has rank $n$, then it is
enough to check if $0\in\mathop{\rm int}(X)$ and $0\in\mathcal{U}_{t}$. This
is due to the fact that for $\varepsilon>0$ we can take $\xi\in\mathbb{R}^{m}$
with $|\xi|$ a small enough such that $\xi\in\mathop{\rm
ri}(\mathcal{U}_{t})$, and as $A_{t}$ has rank $n$ there exists
$\tilde{x}\in\mathbb{B}(0,\varepsilon)$ such that
$B_{t}\xi=-A_{t}(\tilde{x})$.

In the general case, by the same argument as before, we have that if the
intersection between the solution set of the following system

$\begin{split}\begin{bmatrix}A_{1}+I_{n}&-I_{n}&B_{1}\end{bmatrix}\begin{bmatrix}x_{1}\\\
x_{2}\\\ u_{1}\end{bmatrix}&=-\varphi_{1},\\\
\begin{bmatrix}A_{2}+I_{n}&-I_{n}&B_{2}\end{bmatrix}\begin{bmatrix}x_{2}\\\
x_{3}\\\ u_{2}\end{bmatrix}&=-\varphi_{2},\\\ &\vdots\\\
\begin{bmatrix}A_{T-1}+I_{n}&-I_{n}&B_{T-1}\end{bmatrix}\begin{bmatrix}x_{T-1}\\\
x_{T}\\\ u_{T-1}\end{bmatrix}&=-\varphi_{T-1},\end{split}$ (7)

and the set $\mathop{\rm ri}(\mathcal{X}_{1})\times\mathop{\rm
ri}(\mathcal{U}_{1})\times...\times\mathop{\rm
ri}(\mathcal{U}_{T-1})\times\mathop{\rm ri}(\mathcal{X}_{T})$ is nonempty,
then condition (H) holds. In particular, if the following conditions are
satisfied: $0\in\mathop{\rm ri}(\mathcal{X}_{t})$, $0\in\mathop{\rm
ri}(\mathcal{U}_{t})$ for every $t$, $0\in{\rm int}(\mathcal{X}_{t})$
,$0\in\mathcal{U}_{t}$, and $A_{t}$ has rank $n$ for every $t$, then condition
(H) remains true.

In terms of the dual problem, to find conditions for (H’), recall that
$\Gamma_{K}(t+1,p)=\\{w\in\mathbb{R}^{n}\mid K_{t}(p+w,w)\in\mathbb{R}\\}$.
Then, $w\in\Gamma_{K}(t+1,p)$ if and only if

$\sup_{x\in\mathcal{X}_{t}}\\{x\cdot(A_{t}^{T}p+A_{t}^{T}w+w)-\frac{1}{2}\|x\|_{Q_{t}}^{2}\\}+\sup_{u\in\mathcal{U}_{t}}\\{u\cdot(B_{t}^{T}p+B_{t}^{T}w)-\frac{1}{2}\|u\|_{R_{t}}^{2}\\}+\varphi_{t}\cdot(p+w)\in\mathbb{R}.$

As the functions $(x,w)\mapsto x\cdot(A_{t}^{T}p+A_{t}^{T}w+w)$ and
$(u,w)\mapsto u\cdot(B_{t}^{T}p+B_{t}^{T}w)$ are linear in $x$ and $u$
respectively, it follows that

$\begin{split}w\in\Gamma_{K}(t+1,p)&\Leftrightarrow\forall
x\in(\mathcal{X}_{t})_{\infty}\cap\ker(Q_{t}),\quad
x\cdot(A_{t}^{T}p+A_{t}^{T}w+w)\leq 0,\\\ &\quad\wedge\forall
u\in(\mathcal{U}_{t})_{\infty}\cap\ker(R_{t}),\quad
u\cdot(B_{t}^{T}p+B_{t}^{T}w)\leq 0.\end{split}$

Note that $\Gamma_{K}(t+1,p)$ is convex, which implies that $\mathop{\rm
ri}(\Gamma_{K}(t+1,p))$ is nonempty. Therefore:

  * •

If $Q_{t}$ is definite positive or $\mathcal{X}_{t}$ is compact for every $t$,
then given $p\in\mathbb{R}^{n}$ the first condition holds true for every
$w\in\mathbb{R}^{n}$. We can choose $w=-p$ to ensure that the second condition
also remains true. Thus, we conclude that in the case
$\mathbf{P}(t)=\mathbb{R}^{n}$ for every $t$, the condition (H’) holds true.

  * •

If $R_{t}$ is definite positive or $\mathcal{U}_{t}$ is compact for every $t$,
then given $p\in\mathbb{R}^{n}$ the second condition is true for every
$w\in\mathbb{R}^{n}$. If we also have that the matrix $A_{t}^{T}+I_{n}$ has
rank $n$, then we can choose $w$ such that $(A_{t}^{T}+I_{n})w=-A_{t}^{T}p$
and so $\mathbf{P}(t)=\mathbb{R}^{n}$ for every $t$, and (H’) holds in this
case.

Furthermore, if $\mathcal{X}_{t}$ and $\mathcal{U}_{t}$ are cones, then
$(\mathcal{X}_{t})_{\infty}=\mathcal{X}_{t}$ and
$(\mathcal{U}_{t})_{\infty}=\mathcal{U}_{t}$, simplifying the conditions for
easier analysis and computations.

Lastly, we focus on the unrestricted case with
$\mathcal{X}_{t}=\mathbb{R}^{n}$ and $\mathcal{U}_{t}=\mathbb{R}^{m}$ for
every $t$. Given $p\in\mathbb{R}^{n}$, we have that $w\in\Gamma_{K}(t+1,p)$ if
and only if for any $x\in\ker(Q_{t})$ and any $u\in\ker(R_{t})$ we have

$x\cdot(A_{t}^{T}p+A_{t}^{T}w+w)\leq 0\quad\text{and}\quad\quad
u\cdot(B_{t}^{T}p+B_{t}^{T}w)\leq 0.$

In this case, $\mathbf{P}(t)$ is a vector space. Indeed, let
$p_{1},p_{2}\in\mathbf{P}(t)$, and $w_{1}\in\Gamma_{K}(t+1,p_{1})$,
$w_{2}\in\Gamma_{K}(t+1,p_{2})$. Taking $w=w_{1}+w_{2}\in\mathbb{R}^{n}$, it
is clear that

$\displaystyle\forall x\in\ker(Q_{t}),\quad
x\cdot(A_{t}^{T}(p_{1}+p_{2})+A_{t}^{T}(w_{1}+w_{2})+w_{1}+w_{2})\leq 0,$
$\displaystyle\forall u\in\ker(R_{t}),\quad
u\cdot(B_{t}^{T}(p_{1}+p_{2})+B_{t}^{T}(w_{1}+w_{2}))\leq 0,$

and thus $p_{1}+p_{2}\in\mathbf{P}(t)$. Let now $p\in\mathbf{P}(t)$,
$w\in\Gamma_{K}(t+1,p)$ and $\lambda\in\mathbb{R}$. If $\lambda\geq 0$, it is
evident that $\lambda p\in\mathbf{P}(t)$ as $\lambda
w\in\Gamma_{K}(t+1,\lambda p)$. If $\lambda<0$, we can take $\lambda w$ and
obtain

$\displaystyle\forall x\in\ker(Q_{t}),\quad-x\cdot(A_{t}^{T}(\lambda
p)+A_{t}^{T}(\lambda w)+\lambda w)\leq 0,$ $\displaystyle\forall
u\in\ker(R_{t}),\quad-u\cdot(B_{t}^{T}(\lambda p)+B_{t}^{T}(\lambda w))\leq
0.$

As $\ker(Q_{t})$ and $\ker(R_{t})$ are vector spaces, $\lambda
w\in\Gamma_{K}(t+1,\lambda p)$ and therefore $\lambda p\in\mathbf{P}(t)$.
Consequently, $\mathbf{P}(t)$ is a vector space. This implies, in particular,
that $0\in\mathop{\rm ri}(\mathbf{P}(t))$ for every $t$. We take
$\bar{p}_{1}=\ldots=\bar{p}_{T}=0$ in (H’), as it’s easy to see that the set
$\Gamma_{K}(t+1,0)$ is a vector space too, and therefore $0\in\mathop{\rm
ri}(\Gamma_{K}(t+1,0))$. In fact, let $w_{1},w_{2}\in\Gamma_{K}(t+1,0)$ and
$\lambda\in\mathbb{R}$. Then

$\displaystyle\forall x\in\ker(Q_{t}),\quad
x\cdot(A_{t}^{T}(w_{1}+w_{2})+w_{1}+w_{2})\leq 0,$ $\displaystyle\forall
u\in\ker(R_{t}),\quad u\cdot(B_{t}^{T}(w_{1}+w_{2}))\leq 0,$

and

$\displaystyle\forall x\in\ker(Q_{t}),\quad\langle x,A_{t}^{T}(\lambda
w)+\lambda w\rangle\leq 0,$ $\displaystyle\forall u\in\ker(R_{t}),\quad\langle
u,B_{t}^{T}(\lambda w)\rangle\leq 0,$

if $\lambda\geq 0$, and we can use the same argument as before for
$\lambda<0$. Therefore, in the unrestricted case (H’) holds.

We summarize the main results of this subsection in the following proposition:

######  Proposition 4.1.

The problem (LQ) admits a Bolza formulation under (CQ) and therefore Theorem
3.2 holds true. Moreover, the converse also holds true if one of the following
conditions holds

  1. 1.

$\mathcal{X}_{t}=\mathbb{R}^{n}$, for every $t\in[\\![1:T]\\!]$ and either

    1. (a)

$\mathcal{U}_{t}=\mathbb{R}^{m}$ for all $t\in[\\![1:T]\\!]$,

    2. (b)

$Q_{t}$ is positive definite for all $t\in[\\![1:T]\\!]$,

    3. (c)

$\mathcal{U}_{t}$ is compact and $A_{t}^{T}+I_{n}$ has rank $n$ for all
$t\in[\\![1:T]\\!]$, or

    4. (d)

$R_{t}$ is positive definite and $A_{t}^{T}+I_{n}$ has rank $n$ for all
$t\in[\\![1:T]\\!]$.

  2. 2.

$\mathcal{X}_{t}$ is compact or $Q_{t}$ is positive definite for every
$t\in[\\![1:T]\\!]$ and either

    1. (a)

The intersection between the solution set of (7) and the set $\mathop{\rm
ri}(\mathcal{X}_{1})\times\mathop{\rm
ri}(\mathcal{U}_{1})\times\ldots\times\mathop{\rm
ri}(\mathcal{U}_{T-1})\times\mathop{\rm ri}(\mathcal{X}_{T})$ is nonempty. In
particular, $0\in\mathop{\rm ri}(\mathcal{X}_{t}),0\in\mathop{\rm
ri}(\mathcal{U}_{t})$ for all $t\in[\\![1:T]\\!]$, or

    2. (b)

$0\in\mathop{\rm int}(\mathcal{X}_{t}),0\in\mathcal{U}_{t}$ and $A_{t}$ has
rank $n$ for every $t\in[\\![1:T]\\!]$.

  3. 3.

$\mathcal{U}_{t}$ is compact or $R_{t}$ is positive definite and
$A_{t}^{T}+I_{n}$ has rank $n$ for all $t\in[\\![1:T]\\!]$, and either

    1. (a)

The intersection between the solution set of (7) and the set $\mathop{\rm
ri}(\mathcal{X}_{1})\times\mathop{\rm
ri}(\mathcal{U}_{1})\times\ldots\times\mathop{\rm
ri}(\mathcal{U}_{T-1})\times\mathop{\rm ri}(\mathcal{X}_{T})$ is nonempty. In
particular, $0\in\mathop{\rm ri}(\mathcal{X}_{t}),0\in\mathop{\rm
ri}(\mathcal{U}_{t})$ for all $t\in[\\![1:T]\\!]$, or

    2. (b)

$0\in\mathop{\rm int}(\mathcal{X}_{t}),0\in\mathcal{U}_{t}$ and $A_{t}$ has
rank $n$ for all $t\in[\\![1:T]\\!]$.

Note that there are many possible combinations of the given conditions over
time that also allow the converse to be true, but we omit the details.

###  4.2 Linear-convex problem with mixed constraints

The second model we study is a linear-convex problem with mixed constraints,
that is, constraints that affect jointly the state and control of the system
(at the same time). Following an analogous procedure, we first show that this
model can be stated as in our framework. Throughout this part,
$\ell_{0},\ldots,\ell_{T-1}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$
and $f_{0},\ldots,f_{T-1}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$ are
given real-valued convex functions,

The optimal control problem we deal with now is the following:

$\left\\{\begin{array}[]{lll}\text{ Minimize
}&\displaystyle\sum_{t=\tau}^{T-1}\ell_{t}(x_{t},u_{t})+g(x_{T}),\\\ \text{
over all }&\\{x_{t}\\}_{t=\tau}^{T}\subset\mathbb{R}^{n}\text{ and
}\\{u_{t}\\}_{t=\tau}^{T-1}\subset\mathbb{R}^{n}\text{ with }x_{\tau}=\xi,\\\
\text{ such that }&\Delta
x_{t+1}=A_{t}x_{t}+B_{t}u_{t}+\varphi_{t},\quad\forall
t\in[\\![\tau:T-1]\\!],\\\ &f_{t}(x_{t},u_{t})\leq 0,\qquad\forall
t\in[\\![\tau:T-1]\\!],\\\ &u_{t}\in\mathcal{U}_{t},\qquad\forall
t\in[\\![\tau:T-1]\\!],\\\ &x_{t}\in\mathcal{X}_{t},\qquad\forall
t\in[\\![\tau:T]\\!].\\\ \end{array}\right.$ (P${}_{\text{mix}}$)

We define the Lagrangian associated to (P${}_{\text{mix}}$) as

$L_{t+1}(x,v)=\inf_{u\in\mathbb{R}^{m}}\left\\{\ell_{t}(x,u)+\delta_{\mathcal{U}_{t}}(u)+\delta_{D_{t}}(x,u)+\delta_{S_{t}}(x,u,v)\right\\}+\delta_{\mathcal{X}_{t}}(x),$

where $D_{t}=\\{(x,u):f_{t}(x,u)\leq 0\\}$. It is not difficult to see that
$\mathop{\rm val}(\rm{P_{mix}})=\vartheta_{\tau}(\xi)$.

However, we still need $L_{t}$ to satisfy the conditions of a convex Bolza
formulation.

  1. a)

Convexity. Write $L_{t+1}$ as $G_{t}(x,v)+\delta_{\mathcal{X}_{t}}(x)$, where
$G_{t}(x,v)=\inf_{u\in\mathbb{R}^{m}}g_{t}(x,v,u)$ and
$g_{t}(x,v,u)=\ell_{t}(x,u)+\delta_{\mathcal{U}_{t}}(u)+\delta_{D_{t}}(x,u)+\delta_{S_{t}}(x,u,v)$.
Then, as $g_{t}$ is clearly convex, $G_{t}$ is convex too, and so $L_{t+1}$ is
convex.

From now on, we make the following assumption

$\forall t,\,\exists\psi_{t}:\mathbb{R}^{n}\to\mathbb{R}\
\textrm{u.s.c.}\quad\textrm{s.t.}\quad\sup_{u\in\mathcal{U}_{t}}\\{|u|\mid
f_{t}(x,u)\leq 0\\}\leq\psi_{t}(x)\quad\forall x\in\mathcal{X}_{t},$ (A)

where u.s.c. stands for upper semicontinuous functions. This is the discrete
version of [2, Assumption (A5)]. Define
$\Omega_{t}=\\{(x,u):x\in\mathcal{X}_{t},u\in\mathcal{U}_{t},\ f_{t}(x,u)\leq
0\\}$.

  1. b)

Properness. It is clear that $L_{t+1}\not\equiv+\infty$ as long as there is a
feasible solution to the problem. We show that we also have that there is no
$(x,v)$ such that $L_{t+1}(x,v)=-\infty$. For the sake of contradiction,
suppose that there is one. Then there is a sequence $\\{u_{k}\\}$ such that
$(x,u_{k})\in\Omega_{t}$ for every $k\in\mathbb{N}$ and
$\ell_{t}(x,u_{k})\to-\infty$. By (A), $\\{u_{k}\\}$ is bounded by
$\psi_{t}(x)$, which contradicts the continuity of $\ell_{t}$ ($\ell_{t}$ is a
real valued convex function). Therefore, $L_{t+1}$ is proper.

  2. c)

Lower semi-continuity. To prove that $L_{t+1}$ is l.s.c., we rely on [24,
Chapter 5]. We first show that $g_{t}$ is level-bounded in $u$ locally
uniformly in $(x,v)$, as defined in [24]. Let
$(\bar{x},\bar{v})\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ and
$\alpha\in\mathbb{R}$. Fix $\varepsilon>0$ and let $M>0$ such that
$\sup_{x\in\mathbb{B}(\bar{x},\varepsilon)}\psi_{t}(x)\leq M$ (its existence
is guaranteed by the upper semi-continuity of $\psi_{t}$). We define
$B=\mathbb{B}_{\mathbb{R}^{m}}(0;M)$, the ball in $\mathbb{R}^{m}$, centered
at 0 with radius $M$.

If $u\in\\{u\mid g(x,v,u)\leq\alpha\\}$, with
$x\in\mathbb{B}(\bar{x},\varepsilon)$ and $v\in\mathbb{R}^{n}$, then
$u\in\mathcal{U}_{t}$ and $f_{t}(x,u)\leq 0$. By (A),

$|u|\leq\psi_{t}(x)\leq M,$

and we have that $u\in B$. Therefore, $\\{u\mid g(x,v,u)\leq\alpha\\}\subset
B$ for every $(x,v)\in\mathbb{B}((\bar{x},\bar{v}),\varepsilon)$ and then
$g_{t}$ is level-bounded in $u$ locally uniformly in $(x,v)$.

We prove now that $G_{t}$ is l.s.c. Let $(\bar{x},\bar{v})\in\mathop{\rm
dom}(G_{t})$ and $(x_{k},v_{k})\to(x,v)$. We consider two cases. First,
suppose that there is a subsequence such that
$G_{t}(x_{k_{j}},v_{k_{j}})<+\infty$ for every $j\in\mathbb{N}$. By continuity
of $\ell_{t}$, we can choose $\\{(x_{k_{j}},v_{k_{j}})\\}$ so that
$G_{t}(x_{k_{j}},v_{k_{j}})<M$ for some $M>0$ large enough. Then,
$\\{G_{t}(x_{k_{j}},v_{k_{j}})\\}$ is bounded from above. As we have already
proved that $g_{t}$ is level-bounded in $u$ locally uniformly in $(x,v)$, by
[24, Proposition 5.4] we obtain that the sequence
$g_{t}(x_{k_{j}},v_{k_{j}},\cdot)$ is tight in the sense of [24, Definition
5.3]. With this, we can follow the steps on [24, Theorem 5.6(a)] to prove that

$\liminf_{k\to\infty}(G_{t}(x_{k},v_{k}))=\liminf_{j\to\infty}(G_{t}(x_{k_{j}},v_{k_{j}})\geq
G_{t}(\bar{x},\bar{v}).$

In the second case, there exists a natural number $n$ from which every element
of the sequence is $+\infty$. It follows that

$\liminf_{k\to\infty}(G_{t}(x_{k},v_{k}))=+\infty\geq G_{t}(\bar{x},\bar{v})$

Therefore, $G_{t}$ is l.s.c. in $(\bar{x},\bar{v})$. To conclude, we show that
$\mathop{\rm dom}G_{t}$ is closed.

Let $\\{(x_{k},v_{k})\\}\subset\mathop{\rm dom}G_{t}$ such that
$(x_{k},v_{k})\to(x,v)$. This implies that for every $k\in\mathbb{N}$ there is
$u_{k}\in\mathcal{U}_{t}$ such that $f_{t}(x_{k},u_{k})\leq 0$ and
$v_{k}=A_{t}x_{k}+B_{t}u_{k}+\varphi_{t}$. The sequence $\\{x_{k}\\}$ is
bounded because it is convergent. Thus, by (A) $\\{u_{k}\\}$ is bounded too.
Then, there is a convergent subsequence of $\\{u_{k}\\}$. Let $u$ be the limit
of this subsequence. By continuity of $f_{t}$, we obtain that $f_{t}(x,u)\leq
0$ and $v=A_{t}x+B_{t}u+\varphi_{t}$, concluding that $(x,v)\in\mathop{\rm
dom}G_{t}$. This implies that $G_{t}$ is lsc and so is $L_{t+1}$.

With the above arguments, $L_{t+1}$ satisfies all of the conditions for a
Bolza type formulation. Let us now focus on studying the dual problem. In
particular we are interesting in computing $K_{t}$

$\begin{split}K(t,p,w)&=\sup_{x,v\in\mathbb{R}^{n}}\\{x\cdot w+v\cdot
p-L_{t}(x,v)\\},\\\ &=\sup_{\begin{subarray}{c}(x,u)\in\Omega_{t}\\\
v=A_{t}x+B_{t}u+\varphi_{t}\end{subarray}}\\{x\cdot w+v\cdot
p-\ell_{t}(x,u)\\},\\\
&=\sup_{(x,u)\in\Omega_{t}}\\{x\cdot(w+A_{t}^{T}p)+u\cdot
B_{t}^{T}p-\ell_{t}(x,u)\\}+\varphi_{t}\cdot p.\end{split}$

Our focus now is on establishing conditions on the primal problem to satisfy
(H) and (H’). Firstly, we proceed to calculate $\Gamma_{L}(t+1,x)$:

$\begin{split}\Gamma_{L}(t+1,x)&=\\{v\in\mathbb{R}^{n}\mid
L_{t+1}(x,v)\in\mathbb{R}\\},\\\
&=\left\\{v\in\mathbb{R}^{n}\mid\inf_{u\in\mathcal{U}_{t}}\\{\ell_{t}(x,u):f_{t}(x,u)\leq
0\,\wedge\,v=A_{t}x+B_{t}u+\varphi_{t}\\}\in\mathbb{R}\right\\},\end{split}$

for $x\in\mathcal{X}_{t}$. If $x\notin\mathcal{X}_{t}$, then
$\Gamma_{L}(t+1,x)=\emptyset$ trivially. By (A), we have that $\forall
x\in\mathcal{X}_{t}$:

$\inf_{u\in\mathcal{U}_{t}}\\{\ell_{t}(x,u):f_{t}(x,u)\leq
0\\}\geq\inf_{|u|\leq\psi_{t}(x)}\\{\ell_{t}(x,u)\\}>-\infty.$

Therefore, if $x\in\mathcal{X}_{t}$:

$\begin{split}v\in\Gamma_{L}(t+1,x)&\Leftrightarrow\exists
u\in\mathcal{U}_{t}\ \textrm{s.t.}\
v=A_{t}x+B_{t}u+\varphi_{t}\,\wedge\,f_{t}(x,u)\leq 0,\\\ &\Leftrightarrow
v\in B_{t}(\mathcal{U}_{t}\cap\\{u:f_{t}(x,u)\leq
0\\})+A_{t}x+\varphi_{t}.\end{split}$

As the set $\\{u:f_{t}(x,u)\leq 0\\}$ is clearly convex, we note that
$\mathop{\rm ri}(\Gamma_{L}(t+1,x))=B_{t}(\mathop{\rm
ri}(\mathcal{U}_{t})\cap\mathop{\rm ri}(\\{u:f_{t}(x,u)\leq
0\\}))+A_{t}x+\varphi_{t}$ and thus it is always nonempty. With this,

${\mathbf{X}}(t)=\mathcal{X}_{t}\cap\\{x\mid\exists
u\in\mathcal{U}_{t}\,\textrm{s.t.}\ f_{t}(x,u)\leq 0\\}.$

By convexity of $\mathcal{U}_{t}$ and $f_{t}$, the set $\\{x\mid\exists
u\in\mathcal{U}_{t}\,\textrm{s.t.}\ f_{t}(x,u)\leq 0\\}$ is convex. It follows
that $\mathop{\rm ri}({\mathbf{X}}(t))=\mathop{\rm
ri}(\mathcal{X}_{t})\cap\mathop{\rm ri}(\\{x\mid\exists
u\in\mathcal{U}_{t}\,\textrm{s.t.}\ f_{t}(x,u)\leq 0\\})$.

Considering this, we can address the system (7) explored in the problem (LQ)
to seek a sequence that meets (H), provided there exists at least one solution
satisfying a Slater condition $f_{t}(x_{t},u_{t})<0$ for all $t$. The
arguments for the equilibrium point and the specific cases examined in the
previous section are applicable to this problem as well.

Next, our attention shifts to establishing conditions for (H’). Note that:

$\Gamma_{K}(t+1,p)=\bigg{\\{}w\in\mathbb{R}^{n}\mid\sup_{(x,u)\in\Omega_{t}}\\{x\cdot(w+A_{t}^{T}w+A_{t}^{T}p)\\\
+u\cdot(B_{t}^{T}p+B_{t}^{T}w)-\ell_{t}(x,u)\\}\in\mathbb{R}\bigg{\\}},$

is convex. In fact, let $w_{1},w_{2}\in\Gamma_{K}(t+1,p)$ and
$\lambda\in[0,1]$. We have that

$\begin{split}&\sup_{(x,u)\in\Omega_{t}}\\{x\cdot\left(\lambda
w_{1}+(1-\lambda)w_{2}+A_{t}^{T}(\lambda
w_{1}+(1-\lambda)w_{2})+A_{t}^{T}p\right)\\\
&\qquad+u\cdot\left(B_{t}^{T}p+B_{t}^{T}(\lambda
w_{1}+(1-\lambda)w_{2})\right)-\ell_{t}(x,u)\\}\\\
&=\lambda\sup_{(x,u)\in\Omega_{t}}\\{x\cdot(w_{1}+A_{t}^{T}w_{1}+A_{t}^{T}p)+u\cdot(B_{t}^{T}p+B_{t}^{T}w_{1})-\ell_{t}(x,u)\\}\\\
&\qquad+(1-\lambda)\sup_{(x,u)\in\Omega_{t}}\\{x\cdot(w_{2}+A_{t}^{T}w_{2}+A_{t}^{T}p)+u\cdot(B_{t}^{T}p+B_{t}^{T}w_{2})-\ell_{t}(x,u)\\}\in\mathbb{R},\end{split}$

and so $\lambda w_{1}+(1-\lambda)w_{2}\in\Gamma_{K}(t+1,p)$. Hence, as done
before, we seek conditions that ensure $\mathbf{P}(t)=\mathbb{R}^{n}$ for any
$t$, because these conditions will imply (H’).

Firstly, it’s worth noting that if $\mathcal{X}_{t}$ is compact, we can select
$w=-p$ for every $p\in\mathbb{R}^{n}$, resulting in

$\begin{split}\sup_{(x,u)\in\Omega_{t}}&\\{x\cdot(w+A_{t}^{T}w+A_{t}^{T}p)+u\cdot(B_{t}^{T}p+B_{t}^{T}w)-\ell_{t}(x,u)\\}=\\\
&\sup_{(x,u)\in\Omega_{t}}\\{\langle
x,p+2A_{t}^{T}p\rangle-\ell_{t}(x,u)\\}\in\mathbb{R},\end{split}$

by continuity of $\ell_{t}$. Therefore, (H’) holds true in this case.
Similarly, (H’) also holds if $\mathcal{U}_{t}$ is compact and
$A_{t}^{T}+I_{n}$ has rank $n$ for every $t$.

By continuity of $\ell_{t}$, we also have that (H’) holds if $\Omega_{t}$ is
compact. This is true if, for example, $f_{t}$ is coercive in $x$. To prove
this, for the sake of contradiction let $\\{(x_{k},u_{k})\\}\subset\Omega_{t}$
such that $|(x_{k},u_{k})|\to\infty$. We have two cases. Either
$|x_{k}|\to\infty$, which contradicts the coercivity of $f_{t}$ in $x$, or
$|u_{k}|\to\infty$ and $\\{x_{k}\\}$ is bounded, which contradicts (A).

On the other hand, it is easy to see that if $\ell_{t}$ is coercive for any
$t$, then (H’) holds. If the matrix $A_{t}^{T}+I_{n}$ has rank $n$ for all
$t$, we can refine this argument by asking

$\displaystyle\exists\kappa_{0}\in\mathbb{R},h_{t}:\mathbb{R}^{m}\to\mathbb{R}\
\textrm{such that}$ (B)
$\displaystyle\quad\sup_{(x,u)\in\Omega_{t}}\\{|x|:\ell_{t}(x,u)-\langle
z,u\rangle\leq\kappa_{0}\\}\leq h_{t}(z),\quad\forall z\in\mathbb{R}^{m}.$

In this case, $\mathbf{P}(t)=\mathbb{R}^{n}$ for every $t$ as well. To prove
this, let $p\in\mathbb{R}^{n}$ and $w\in\mathbb{R}^{n}$ such that
$w+A_{t}^{T}w=-A_{t}^{T}p$. For the sake of contradiction, suppose that
$\exists\\{(x_{k},u_{k})\\}\subset\Omega_{t}$ such that

$x_{k}\cdot(w+A_{t}^{T}w+A_{t}^{T}p)+u_{k}\cdot(B_{t}^{T}p+B_{t}^{T}w)-\ell_{t}(x_{k},u_{k})=u_{k}\cdot(B_{t}^{T}p+B_{t}^{T}w)-\ell_{t}(x_{k},u_{k})\to\infty.$

This implies that there exists some natural $N_{0}$ such that

$u_{k}\cdot(B_{t}^{T}p+B_{t}^{T}w)-\ell_{t}(x_{k},u_{k})\geq-\kappa_{0},\qquad\forall
k\geq N_{0}.$

By taking $z=B_{t}^{T}p+B_{t}^{T}w$ in (B), then $\sup_{k\geq
N_{0}}|x_{k}|\leq h_{t}(z)$. Then, by (A), there exists some $M\in\mathbb{R}$
such that $\sup_{k\geq N_{0}}|u_{k}|\leq M$, which is a contradiction with
$u_{k}\cdot(B_{t}^{T}p+B_{t}^{T}w)-\ell_{t}(x_{k},u_{k})\to\infty$ as
$\ell_{t}$ is continuous.

The condition (B) corresponds to the discrete version of [2, Assumption (A6)],
and it is satisfied, for example, if $\ell_{t}$ is coercive in $u$ and has at
least linear growth in $x$.

The main results of this subsection are summarized in the following
proposition:

######  Proposition 4.2.

Under condition (A), the problem (P${}_{\text{mix}}$) admits a Bolza problem
formulation and, therefore, Theorem 3.2 holds true. Moreover, the converse
remains true if the intersection between the solution set of (7) and the set
$\mathop{\rm ri}(\mathcal{X}_{1})\times\mathop{\rm
ri}(\mathcal{U}_{1})\times\ldots\times\mathop{\rm
ri}(\mathcal{U}_{T-1})\times\mathop{\rm ri}(\mathcal{X}_{T})$ is nonempty, and
at least one of its elements satisfies the condition $f_{t}(x_{t},u_{t})<0$
for every $t\in[\\![1:T]\\!]$ and either of the following holds:

  1. a)

$\mathcal{U}_{t}$ is compact and the matrix $A_{t}^{T}+I_{n}$ has rank $n$,
$\mathcal{X}_{t}$ is compact or $f_{t}$ is coercive in $x$ for all
$t\in[\\![1:T]\\!]$.

  2. b)

Alternatively, $\ell_{t}$ is coercive or the matrix $A_{t}^{T}+I_{n}$ has rank
$n$ and $\ell_{t}$ satisfies (B) for all $t\in[\\![1:T]\\!]$.

##  5 Conclusion

In this paper we have shown that the evolution over time of the subgradients
of the value function of a (deterministic) discrete-time convex Bolza problem
can be associated with trajectories of a discrete-time Hamiltonian system.
This is the so-called _discrete-time characteristic method_. We have also
demonstrated that the qualificiation conditions required for our results to
hold are satisfied in several cases of interest; e.g. the Linear-Quadratic
problem and the Linear-Convex problem with mixed constraints.

This paper paves the way for future extension to stochastic convex Bolza
problems. Indeed, our main result (Theorem 3.2) as well as our intermedediate
results (Proposition 2.4 and 2.6) are consequences of the research reported by
Rockafellar and Wets in [21]. For our paper, we have only used the
deterministic part, but we plan to use the stochastic part in a forthcoming
paper.

## References

  * [1] A. Auslender and M. Teboulle.  Asymptotic Cones and Functions in Optimization and Variational Inequalities.  Springer-Verlag, 2003.
  * [2] J. Becerril and C. Hermosilla.  Optimality conditions for linear-convex optimal control problems with mixed constraints.  Journal of Optimization Theory and Applications, 194(3):795–820, 2022.
  * [3] R. Goebel.  Regularity of the optimal feedback and the value function in convex problems of optimal control.  Set-Valued Analysis, 12(1-2):127–145, 2004.
  * [4] R. Goebel.  Stationary Hamilton–Jacobi equations for convex control problems: uniqueness and duality of solutions.  In Optimal control, stabilization and nonsmooth analysis, pages 313–322. Springer, 2004.
  * [5] R. Goebel.  Convex optimal control problems with smooth Hamiltonians.  SIAM Journal on Control and Optimization, 43(5):1787–1811, 2005\.
  * [6] R. Goebel.  Duality and uniqueness of convex solutions to stationary Hamilton–Jacobi equations.  Transactions of the American Mathematical Society, 357(6):2187–2203, 2005.
  * [7] R. Goebel and R. T. Rockafellar.  Linear-convex control and duality.  In Geometric Control And Nonsmooth Analysis: In Honor of the 73rd Birthday of H Hermes and of the 71st Birthday of RT Rockafellar, pages 280–299. World Scientific, 2008.
  * [8] R. Goebel and M. Subbotin.  Continuous time linear quadratic regulator with control constraints via convex duality.  IEEE Transactions on Automatic Control, 52(5):886–892, 2007.
  * [9] C. Hermosilla and P. Wolenski.  A characteristic method for fully convex bolza problems over arcs of bounded variation.  SIAM Journal on Control and Optimization, 57(4):2873–2901, 2019\.
  * [10] C. Hermosilla and P. R. Wolenski.  Constrained and impulsive linear quadratic control problems.  In Proceeding of thye 20th World Congress of the IFAC, volume 50, pages 1637–1642, 2017.
  * [11] T. Pennanen and A.-P. Perkkiö.  Duality in convex problems of Bolza over functions of bounded variation.  SIAM Journal on Control and Optimization, 52(3):1481–1498, 2014\.
  * [12] R. T. Rockafellar.  Conjugate convex functions in optimal control and the calculus of variations.  Journal of Mathematical Analysis and Applications, 32(1):174–222, 1970.
  * [13] R. T. Rockafellar.  Convex Analysis, volume 28.  Princeton University Press, 1970.
  * [14] R. T. Rockafellar.  Existence and duality theorems for convex problems of Bolza.  Transactions of the American Mathematical Society, 159(1–40), 1971\.
  * [15] R. T. Rockafellar.  State constraints in convex control problems of Bolza.  SIAM Journal on Control and Optimization, 10(4):691–715, 1972.
  * [16] R. T. Rockafellar.  Saddle points of Hamiltonian systems in convex problems of Lagrange.  Journal of Optimization Theory and Applications, 12:367–390, 1973\.
  * [17] R. T. Rockafellar.  Dual problems of Lagrange for arcs of bounded variation.  In Calculus of variations and control theory (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1975; dedicated to Laurence Chisholm Young on the occasion of his 70th birthday), pages 155–192. Academic Press, New York, 1976.
  * [18] R. T. Rockafellar.  Linear-quadratic programming and optimal control.  SIAM Journal on Control and Optimization, 25(3):781–814, 1987.
  * [19] R. T. Rockafellar.  Hamiltonian trajectories and duality in the optimal control of linear systems with convex costs.  SIAM Journal on Control and Optimization, 27(5):1007–1025, 1989\.
  * [20] R. T. Rockafellar.  Hamilton-Jacobi theory and parametric analysis in fully convex problems of optimal control.  Journal of Global Optimization, 28(3-4):419–431, 2004.
  * [21] R. T. Rockafellar and R. Wets.  Deterministic and stochastic optimization problems of Bolza type in discrete time.  Stochastics: An International Journal of Probability and Stochastic Processes, 10(3-4):273–312, 1983.
  * [22] R. T. Rockafellar and P. R. Wolenski.  Convexity in Hamilton-Jacobi theory I: Dynamics and duality.  SIAM Journal on Control and Optimization, 32(2):442–470, 2000.
  * [23] R. T. Rockafellar and P. R. Wolenski.  Convexity in Hamilton-Jacobi theory II: Envelope representations.  SIAM Journal on Control and Optimization, 39(5):1351–1372, 2000\.
  * [24] J. O. Royset and R. J.-B. Wets.  An optimization primer.  Springer, 2022.