# Universal Approximation of Parametric Optimization via Neural Networks with
Piecewise Linear Policy Approximation

Hyunglip Bae
Department of Industrial and System Engineering
KAIST
South Korea
<EMAIL_ADDRESS>
&Jang Ho Kim
Depart of Industrial and Management System Engineering
Department of Big Data Analytics
Kyung Hee University
South Korea
<EMAIL_ADDRESS>
&Woo Chang Kim
Department of Industrial and System Engineering
KAIST
South Korea
<EMAIL_ADDRESS>Corresponding Author

###### Abstract

Parametric optimization solves a family of optimization problems as a function
of parameters. It is a critical component in situations where optimal decision
making is repeatedly performed for updated parameter values, but computation
becomes challenging when complex problems need to be solved in real-time.
Therefore, in this study, we present theoretical foundations on approximating
optimal policy of parametric optimization problem through Neural Networks and
derive conditions that allow the Universal Approximation Theorem to be applied
to parametric optimization problems by constructing piecewise linear policy
approximation explicitly. This study fills the gap on formally analyzing the
constructed piecewise linear approximation in terms of feasibility and
optimality and show that Neural Networks (with ReLU activations) can be valid
approximator for this approximation in terms of generalization and
approximation error. Furthermore, based on theoretical results, we propose a
strategy to improve feasibility of approximated solution and discuss training
with suboptimal solutions.

_Keywords_ Neural Networks $\cdot$ Universal Approximation $\cdot$ Parametric
Optimization $\cdot$ The Maximum Theorem

##  1 Introduction

Consider a parametric optimization problem parameterized by $\theta$

$\min_{x}\quad f(x,\theta)\quad\text{subject\;to}\quad x\in C(\theta).$

where $x$ is decision variable, $f$ is objective function and $C(\theta)$ is
feasible region for $x$. Parametric optimization involves a process of solving
a family of optimization problems as a function of parameters. (Nikbakht et
al. (2020); Still (2018)). Therefore, it is commonly applied when decisions
are made repeatedly as the parameters change, while the fundamental problem
structure remains constant over the entire duration. The parameters are often
determined by the environment where decision makers typically can not have
control. Therefore, an optimization problem must be solved after observing the
current state of the environment over and over. As solving an optimization
problem requires certain computational time, it inevitably causes delays
between repetitive decisions, especially for large-scale and complex
optimization problems.

There are many application fields that parametric optimization plays a
significant role, including robotics (Khalaf and Richter (2016)), autonomous
vehicle control (Daryina and Prokopiev (2021)), supply chain optimization (Bai
and Liu (2016)), and energy system management (Wang et al. (2014)). For
example, an autonomous vehicle needs optimal decisions that depend on changes
in speed, road conditions, or amount of traffic. Any delay in decision-making
for autonomous vehicle control could lead to mishandle or even serious traffic
accidents. Similarly, various decisions based on optimization are required for
managing responsive and adaptive manufacturing systems. Sequential and
interconnected systems magnify the importance of computation speed as well as
minimal error. Real-time decision making is also crucial in high frequency
trading of financial assets. Delays in trade execution, even for a fraction of
a second, can lead to significant losses for financial management firms. These
applications clearly highlight the importance of latency issues in parametric
optimization.

In situations where a family of optimization problems needs to be solved
repeatedly, the following two characteristics can be observed. First, the
structure of optimization problems that are solved repeatedly is identical
except for input parameters, which means the dependent variable for the
optimal policy is input parameters. Second, input parameters and their
corresponding optimal policy are accumulated as optimization problems are
solved for new input parameters. This second case gives potential for
supervised learning. Thus, it is intuitive and beneficial to approximate the
mapping from input parameters to the optimal policy via Machine Learning (ML)
techniques in that it is efficient and scalable.

Therefore, in this study, we focus on applying Neural Networks (NN) to
universally approximate parametric optimization problems. We build theoretical
foundations on approximating direct mapping from input parameters to optimal
solution through NN universally and derive conditions that allow the Universal
Approximation Theorem (UAT) to be applied to parametric optimization problems
by constructing piecewise linear policy approximation explicitly. More
specifically, we cast single-valued continuous piecewise linear approximation
for optimal solution of parametric optimization and analyze it in terms of
feasibility and optimality and show that NN with ReLU activations can be valid
approximator in terms of generalization and approximation error. There are
various works on the expressive power of NN for approximating functions,
however, to the best of our knowledge, existing literature lacks theoretical
analysis on the applicability of UAT when the target function of NN is the
result from parametric optimization problem, and our study is the first to
fill this gap.

###  1.1 Related Work.

The power of NN as a universal approximator has been extensively validated
over several decades. Pointedly, initial work on the UAT show that, for any
continuous function on a compact set, there exist a feedforward NN with a
single hidden layer the uniformly approximates the function arbitrarily well
(Hornik et al. (1989); Cybenko (1989); Funahashi (1989); Barron (1993)).
Recently, there has been a growing interest in exploring the capability of NN
for approximating functions stemmed from the works by Liang and Srikant (2016)
and Yarotsky (2017); for more recent developments, see also Yarotsky (2018);
Petersen and Voigtlaender (2018); Shaham et al. (2018); Shen et al. (2019);
Daubechies et al. (2022); Lu et al. (2021). From theoretical view, Telgarsky
(2016) discussed the benefits of depth in NN, which led to various research on
arbitrary depth (Lu et al. (2017); Hanin and Sellke (2017); Kidger and Lyons
(2020); Sun et al. (2016); Daniely (2017)). There are also numerous extensions
of the UAT that is derived from other networks (Baader et al. (2019); Lin and
Jegelka (2018)) or is generalized to unbounded activation functions (Sonoda
and Murata (2017)), discontinuous activation functions (Leshno et al. (1993)),
non-compact domains (Kidger and Lyons (2020)), interval approximation (Wang et
al. (2022)), distribution approximation (Lu and Lu (2020)) and invariant map
(Yarotsky (2022)).

Stability analysis of optimization problems plays an important role in control
theory which has been utilized in many applications such as electronic
engineering (Wang et al. (2019)), biology (Motee et al. (2012)), and computer
science (Bubnicki (2005)). Berge (1963) first proved the Maximum Theorem that
provides conditions for the continuity of optimal value function and upper
hemicontinuity of optimal policy with respect to its parameters. Since the
Maximum Theorem only guarantees upper hemicontinuity of optimal policy, this
led to extensions on studying conditions for lower hemicontinuous of optimal
policy. Approaches in such literature are largely divided into two main types.
Some provide conditions for lower hemicontinuous directly (Robinson and Day
(1974), Zhao (1997), Kien* (2005)). On the other hand, others provide
conditions by limiting structure to be linear (Böhm (1975), Wets (1985), Zhang
and Liu (1990)), quadratic (Lee et al. (2006)), and quasiconvex (Terazono and
A. Matani (2015)). Also, there are generalized versions of Maximum Theorem
(Walker (1979), Leininger (1984), Ausubel and Deneckere (1993)). We handle
these analyses to bridge parametric optimization and NN.

Also, parallel to the development of various optimization methodologies for ML
(Wright and Recht (2022), Boyd and Vandenberghe (2004), Sra et al. (2012)),
there has been increasing interest both from operations research and computer
science communities to solve mathematical optimization problems using ML. The
literature on learning parametric optimization shows two main approaches. The
first approach is to learn the optimal solution directly from the input
parameter by utilizing the existing solution as data (Lillicrap et al. (2015),
Mnih et al. (2015), Vinyals et al. (2015), Dai et al. (2017), Li and Malik
(2016), Donti et al. (2017)). Although this approach is simple and intuitive,
it has the disadvantage of providing solutions that may violate the critical
constraints of optimization problems. This prompted second approach that
applies ML indirectly as intermediate step. Li et al. (2018) used Graphical
Neural Networks to guide a parallelized tree search procedure that rapidly
generate a large number of candidate solutions. Agrawal et al. (2020) applied
ML to approximate gradient of solution of convex optimization. Misra et al.
(2021) and Bertsimas and Stellato (2019) identified optimal active or tight
constraint sets. For more recent works, see Bae et al. (2023); Dai et al.
(2021); Dumouchelle et al. (2022); Kim et al. (2023). In this paper, we
consider the situation where the parametric optimization problems are
approximated by NN directly for utilization of UAT.

###  1.2 Contribution.

In this paper, we derive conditions for UAT to hold for approximating
parametric optimization problems. With our derivations, we can specify how to
formulate the parametric optimization problem rather than naively hoping that
NN will approximate the optimization problem well. The main contribution of
the study can be summarized as below.

  * •

We provide sufficient conditions for UAT to hold for optimal policy for
continuous parametric optimization problems and these conditions are quite
general in that we do not impose convexity or even quasi-convexity of
optimization problems. We only exploit the assumptions and results of the
Maximum Theorem (Berge (1963)).

  * •

We also address situations when these sufficient conditions are not satisfied.
In particular, we define a sampling function and its stability which makes
good approximation possible even without the sufficient conditions in original
problems. Under the stable sampling function, original problems become reduced
problem in which all conditions in main theorem are satisfied.

  * •

We directly link vast amount of literature on NN with approximating
optimization problems. There are many literatures linking the specific
structure of NN to UAT. However, to our best knowledge, the general connection
between the structure of parametric optimization problem and UAT has been
scarcely investigated from the theoretical point of view. Our research
clarifies such a vague connection by constructing piecewise linear policy
approximation for NN.

###  1.3 Outline.

The remainder of the paper is organized as follows. Preliminaries for deriving
our results are included in Section 2, and our main results with piecewise
linear policy approximation are presented in Section 3. Section 4 discuss
suitability of NN as estimator of our policy approximation. Improving
feasibility and training with suboptimal training data are discussed in
Section 5. Finally, Section 6 concludes the paper.

##  2 Preliminaries.

In Section 2, we begin by introducing definitions and notations that are
necessary for deriving our results. We also formally define the problem and
list its assumptions.

###  2.1 Definitions and Notations.

Parametric optimization takes the form,

$\min_{x}\quad f(x,\theta)\quad\text{subject\;to}\quad x\in C(\theta).$

where $x\in X\subset\mathbb{R}^{n}$ is the decision variable,
$\theta\in\Theta\subset\mathbb{R}^{k}$ is the parameter,
$f:\mathbb{R}^{n}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$ is the objective
function and $C:\mathbb{R}^{k}\rightrightarrows 2^{\mathbb{R}^{n}}$ is a
multivalued mapping, or correspondence, representing the feasible region
defined by a set of constraints parameterized by $\theta$. Let the optimal
value function $f^{\ast}:\mathbb{R}^{k}\rightarrow\mathbb{R}$ by
$f^{\ast}(\theta)=\min_{x\in C(\theta)}f(x,\theta)$. We denote the optimal
policy correspondence $C^{\ast}:\mathbb{R}^{k}\rightrightarrows
2^{\mathbb{R}^{n}}$ by $C^{\ast}(\theta)=\arg\min_{x\in
C(\theta)}f(x,\theta)=\\{x\in C(\theta)|f(x,\theta)=f^{\ast}(\theta)\\}$. An
optimal solution $x^{\ast}(\theta)$ is an element of $C^{\ast}(\theta)$.

For any vector $x\in\mathbb{R}^{n}$, its norm $\|x\|$ is defined as the
Euclidean norm, $\|x\|^{2}=\sum_{i=1}^{n}x^{2}_{i}$. For any non-empty set $X$
of vectors in $\mathbb{R}^{n}$, the $\varepsilon$-neighborhood is represented
by $\mathcal{B}_{\varepsilon}(X)=\\{y\in\mathbb{R}^{n}|$ $\exists x\in X$ s.t.
$\|x-y\|<\varepsilon\\}$. We define the stability of correspondence based on
the continuity by Hausdorff (2021). While there are different definitions of
stability (Berge (1963), Hogan (1973)), the Hausdorff’s version is the most
general (Zhao (1997)).

######  Definition 2.1.

Let $C$ be a correspondence from parameter space
$\mathrm{\Theta}\subset\mathbb{R}^{k}$ to $2^{\mathbb{R}^{n}}$. Then,

  1. (a)

$C$ is upper hemicontinuous at $\theta_{0}$ if $\forall\varepsilon>0$,
$\exists\delta>0$ s.t.
$C(\theta)\subset\mathcal{B}_{\varepsilon}(C(\theta_{0})),\forall\theta\in\mathcal{B}_{\delta}(\theta_{0})$

  2. (b)

$C$ is lower hemicontinuous at $\theta_{0}$ if $\forall\varepsilon>0$,
$\exists\delta>0$ s.t.
$C(\theta_{0})\subset\mathcal{B}_{\varepsilon}(C(\theta)),\forall\theta\in\mathcal{B}_{\delta}(\theta_{0})$

  3. (c)

$C$ is continuous at $\theta_{0}$ if $C$ is both upper and lower
hemicontinuous at $\theta_{0}$

UAT describes the capability of NN as an approximator. Although there are many
variations, the key statement is that a function expressed as NN is dense on
the function space of interest. The most classical version of UAT is
independently introduced by Hornik et al. (1989). Since we are utilizing the
key findings of UAT, we summarize and restate this study as presented in
Theorem 2.1, where the term function is written as a single-valued function to
distinguish it from a correspondence.

######  Theorem 2.1 (Universal Approximation Theorem, restated from Hornik et
al. (1989)).

Let $f$ be a continuous single-valued function on a compact set $K$. Then,
there exists a feed forward NN with a single hidden layer that uniformly
approximates $f$ to within an arbitrarily $\varepsilon>0$ on $K$.

###  2.2 The Maximum Theorem.

The Maximum Theorem was presented in Berge (1963), which provides conditions
under which the value function is continuous and the optimal policy
correspondence is upper hemicontinuous for a parametric optimization problem
given by (2.1). This theorem sets the basis for developing a connection
between parametric optimization and UAT. We restate Berge’s Maximum Theorem as
Theorem 2.2.

######  Theorem 2.2 (The Maximum Theorem, restated from Berge (1963)).

Let $f\mathrm{\,:\,}X\times\mathrm{\Theta}\rightarrow\mathbb{R}$ be a
continuous function on the product $X\times\mathrm{\Theta}$, and
$C\mathrm{\,:\,}\Theta\rightrightarrows X$ be a compact-valued correspondence
s.t. $C(\theta)\neq\emptyset,\forall\theta\in\mathrm{\Theta}$. Define the
$f^{\ast}(\theta)$ and $C^{\ast}(\theta)$ as $f^{\ast}(\theta)=\min_{x\in
C(\theta)}f(x,\theta)$ and $C^{\ast}(\theta)=\arg\min_{x\in
C(\theta)}f(x,\theta)=\\{x\in C(\theta)|f(x,\theta)=f^{\ast}(\theta)\\}$. If
$C$ is continuous (i.e. both upper and lower hemicontinuous) at $\theta$, then
$f^{\ast}$ is continuous and $C^{\ast}$ is upper hemicontinuous with non-empty
and compact values.

###  2.3 Problem Description.

Our goal is to find the conditions of $f$ and $C$ that allows UAT to be
applied to approximating the optimal policy correspondence $C^{\ast}$. Suppose
the optimization problem given by (2.1) is formulated so that it changes
stably as $\theta$ varies. The key questions are as follows.

  1. (Q1)

Is $C^{\ast}$ continuous or single-valued function?

  2. (Q2)

Are there bounds on errors from approximation, and do they converge to zero?

  3. (Q3)

Is NN suitable class for learning of $C^{\ast}$?

Questions (Q1) arise as UAT generally requires continuity and a single-valued
function. We analyze (Q1) based on the Maximum Theorem (Berge (1963)), which
is one of the most applied theorems in stability theory. To guarantee an
acceptable approximation, we construct a target function for optimal policy
$C^{\ast}$, which is a piecewise linear continuous function and derive
conditions where the approximation error converges to zero. This will address
question (Q2). Finally, for question (Q3), we represent generalization error
and approximation error of NN on learning constructed piecewise linear
continuous target function.

###  2.4 Assumptions.

For problem (1), we assume that the objective function $f(x,\theta)$ is
continuous on the product $X\times\Theta$, the feasible region $C(\theta)$ is
continuous on $\Theta$ and $C(\theta)$ is a non-empty compact set for each
$\theta\in\Theta$. We make assumptions on the training data for optimal policy
as well. A training example for parametric optimization is a pair of a
parameter and its corresponding optimal solution
$(\theta_{i},x^{\ast}(\theta_{i}))$. Let the training data be the set of
examples, $T=\\{(\theta_{i},x^{\ast}(\theta_{i}))|i=1,\cdots,m\\}$. Notice
that there can be more than one optimal solution $x^{\ast}(\theta_{i})$ for
each $\theta_{i}$. In practice, it is computationally expensive, if not
impossible, to obtain the entire set of optimal solutions. In fact, it is
difficult even to identify whether there are multiple optimal solutions or
not. Therefore, to incorporate such practical aspects, we assume that there
exists a solver that can extract exactly one element $x^{\ast}(\theta_{i})$
from $C^{\ast}(\theta_{i})$ for any given $\theta_{i}$. However, it does not
have control on the choice of $x^{\ast}(\theta_{i})$, so that the optimal
solution is obtained in a random manner from $C^{\ast}(\theta_{i})$. Moreover,
the solver is not able to identify if $C^{\ast}(\theta_{i})$ is a singleton or
not. It is as if the training data is a discrete sample path from the
correspondence $C^{\ast}$ indexed by $\\{\theta_{i}|i=1,\cdots,m\\}$.

##  3 Piecewise Linear Policy Approximation.

In Section 3, we present our main results about piecewise linear policy
approximation. Given the above assumptions on $f$ and $C$, the Theorem 2.2
states that $f^{\ast}$ is a continuous function, and $C^{\ast}$ is a non-empty
and compact-valued upper hemicontinuous correspondence. Thus, unlike the value
function $f^{\ast}$, which guarantees universal approximation, $C^{\ast}$ is
not a single-valued function and is not even continuous, which requires
additional treatments. Before making further steps, we state the following as
a special case.

######  Corollary 3.1.

If $C^{\ast}$ is singleton for each $\theta$, NN universally approximates
$C^{\ast}$.

If the optimal solution for (2.1) is unique for every $\theta$, its optimal
policy is not a correspondence, and reduces to a single-valued function. As
upper hemicontinuity implies the continuity for a function, UAT can readily be
applied for $C^{\ast}$. While this is a special case with a strong assumption,
Corollary 3.1 is the ideal case. In general, there can be multiple optimal
solutions for some $\theta$, and, thus, $C^{\ast}$ is no longer a single-
valued function. But under some conditions on $C^{\ast}$, there is possibility
to find a continuous function called a selection as defined in Definition 3.1.

######  Definition 3.1.

Given two sets $X$ and $Y$, let $F$ be a correspondence from $X$ to $Y$. A
function $f\mathrm{\,:\,}X\rightarrow Y$ is said to be a selection of $F$, if
$\forall x\in X,f(x)\in F(x)$.

######  Proposition 3.1 (Existence of a continuous selection).

$C^{\ast}$ has a continuous selection if it is convex-valued and lower
hemicontinuous.

###### Proof.

This is an immediate result of the selection theorem by Michael Michael
(1956).

∎

There is a potential issue with Proposition 3.1. Some important classes of
optimization, including linear programming problems, do not necessarily have
lower hemicontinuous optimal policy correspondence. To illustrate the issues
on approximating $C^{\ast}$, consider the following linear program with a
parameter $\theta\in[0,2]$,

######  Example 3.1.

$\min_{x_{1},x_{2}}\quad-\theta x_{1}-x_{2}\quad\text{subject\;to}\quad
x_{1}+x_{2}\leq 1,\quad x_{1}\geq 0,\quad x_{2}\geq 0.$

The optimal policy correspondence for the problem given by Example 3.1 becomes

$C^{\ast}(\theta)=\begin{cases}\\{(0,1)\\}&\text{for $\theta\in[0,1)$},\\\
\\{(x_{1},x_{2})|x_{1}+x_{2}=1,\ x_{1}\geq 0,x_{2}\geq 0\\}&\text{for
$\theta=1$},\\\ \\{(1,0)\\}\ &\text{for $\theta\in(1,2]$.}\end{cases}$

As illustrated in Figure 1, $C^{\ast}(\theta)$ contains a jump at $\theta=1$.
Thus, it is evident that there is no continuous selection of
$C^{\ast}(\theta)$. This means that UAT cannot be directly applied, and we
need to find a workaround to make it work.

Figure 1: Optimal policy correspondence of Example 3.1 on $x_{1}+x_{2}=1$

Thus, we drop the assumption that $C^{\ast}$ is lower hemicontinuous and only
take upper hemicontinuity of $C^{\ast}$, which is guaranteed by Theorem 2.2.
Since a continuous selection generally does not exist, we construct a new
target function. For given training data
$T=\\{(\theta_{i},x^{\ast}(\theta_{i}))|i=1,\cdots,m\\}$, we attempt to
estimate the optimal solution on the convex hull of
$\theta_{1},\theta_{2},\ldots,\theta_{m}$ denoted as
$Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})$. Furthermore, we
consider a finite collection $\mathcal{S}=\\{S_{1},\ldots,S_{d}\\}$ of subset
of $\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\}\subset\mathbb{R}^{k}$ such
that

  1. (a)

For each $j\in\\{1,\ldots,d\\}$, $|S_{j}|=k+1$ i.e. $Conv(S_{j})$ is
$k$-dimensional simplex.

  2. (b)

$Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})=\bigcup_{j=1}^{d}Conv(S_{j})$.

  3. (c)

For any non-empty subset $J\subseteq\\{1,2,\ldots,d\\}$, $\bigcap_{j\in
J}Conv(S_{j})=Conv(\bigcap_{j\in J}S_{j})$.

This collection is called triangulations (Lee and Santos (2017)). One way of
constructing this is lexicographic triangulations introduced by Sturmfels
(1991). Given such collection $\mathcal{S}$, for any $\theta\in
Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})$, there exists index
$j_{\theta}\in\\{1,\ldots,d\\}$ such that
$\theta=\lambda^{j_{\theta}}_{1}\theta^{j_{\theta}}_{1}+\ldots+\lambda^{j_{\theta}}_{k+1}\theta^{j_{\theta}}_{k+1}$
where
$\\{\theta^{j_{\theta}}_{1},\ldots,\theta^{j_{\theta}}_{k+1}\\}=S_{j_{\theta}}\in\mathcal{S}$
and $\lambda^{j_{\theta}}_{1},\ldots,\lambda^{j_{\theta}}_{k+1}\geq
0,\lambda^{j_{\theta}}_{1}+\ldots+\lambda^{j_{\theta}}_{k+1}=1$. Our key
approach is to approximate $x^{\ast}(\theta)$ as
$\lambda^{j_{\theta}}_{1}{x^{\ast}(\theta}_{1}^{j_{\theta}})+\ldots+\lambda^{j_{\theta}}_{k+1}{x^{\ast}(\theta}_{k+1}^{j_{\theta}})$.
This approximation is a single-valued by construction, and continuous function
by following theorem, so that UAT can be applied.

######  Theorem 3.1 (Continuity of Policy Approximation).

Consider a finite collection $\mathcal{S}=\\{S_{1},\ldots,S_{d}\\}$ of subset
of $\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\}\subset\mathbb{R}^{k}$ such
that

  1. (a)

For each $j\in\\{1,\ldots,d\\}$, $|S_{j}|=k+1$ i.e. $Conv(S_{j})$ is
$k$-dimensional simplex.

  2. (b)

$Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})=\bigcup_{j=1}^{d}Conv(S_{j})$.

  3. (c)

For any non-empty subset $J\subseteq\\{1,2,\ldots,d\\}$, $\bigcap_{j\in
J}Conv(S_{j})=Conv(\bigcap_{j\in J}S_{j})$.

Denote $S_{j}=\\{\theta^{j}_{1},\ldots,\theta^{j}_{k+1}\\}$. For any
$\theta\in Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})$, let
$j_{\theta}$ be index of $\mathcal{S}$ such that $\theta\in
Conv(S_{j_{\theta}})$. Then, the function
$\hat{x}:Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})\rightarrow\mathbb{R}^{n}$

$\hat{x}(\theta)=\lambda^{j_{\theta}}_{1}{x^{\ast}(\theta}_{1}^{j_{\theta}})+\ldots+\lambda^{j_{\theta}}_{k+1}{x^{\ast}(\theta}_{k+1}^{j_{\theta}}).$

is continuous where
$\lambda^{j_{\theta}}_{1},\ldots,\lambda^{j_{\theta}}_{k+1}$ are weights of
convex combination for $\theta$ i.e.
$\theta=\lambda^{j_{\theta}}_{1}\theta^{j_{\theta}}_{1}+\ldots+\lambda^{j_{\theta}}_{k+1}\theta^{j_{\theta}}_{k+1}$

###### Proof.

We first prove Lemma 3.1.

######  Lemma 3.1.

Let $X_{1},X_{2},\ldots,X_{d}$ be closed subsets of $\mathbb{R}^{k}$. Suppose
that $f_{j}:X_{j}\rightarrow\mathbb{R}^{n},j=1,\ldots,d$ are continuous
functions such that for any nonempty subset $J\subseteq\\{1,2,\ldots,d\\}$ and
for any $j_{1},j_{2}\in J$

$f_{j_{1}}|\bigcap_{j\in J}X_{j}=f_{j_{2}}|\bigcap_{j\in J}X_{j}$

Then, the function

$f:\bigcup_{j=1}^{d}X_{j}\rightarrow\mathbb{R}^{n},\quad
x\rightarrow\begin{cases}f_{1}(x),\quad x\in X_{1}\\\ f_{2}(x),\quad x\in
X_{2}\\\ \vdots\\\ f_{d}(x),\quad x\in X_{d}\\\ \end{cases}$

is also continuous.

###### Proof of Lemma 3.1.

Let $A\subseteq\mathbb{R}^{n}$ be closed in $\mathbb{R}^{n}$. Because $f_{j}$
is continuous, $f_{j}^{-1}(A)$ is closed in $X_{j}$. More formally, there is
$Y_{j}\subseteq\mathbb{R}^{k}$ such that $Y_{j}$ is closed in $\mathbb{R}^{k}$
and $f^{-1}(A)=Y_{j}\cap X_{j}$. Then, we have

$f^{-1}(A)=\bigcup_{j=1}^{d}f_{j}^{-1}(A)=\bigcup_{j=1}^{d}(Y_{j}\cap
X_{j})=(X_{1}\cup\ldots\cup
X_{d})\cap(\bigcap_{Z_{j}\in\\{X_{j},Y_{j}\\},j=2,\ldots,d}(Y_{1}\cup
Z_{2}\cup\ldots\cup Z_{d})).$

If follows from $Y_{j},X_{j}$ are closed in $\mathbb{R}^{k}$ that
$B:=\bigcap_{Z_{j}\in\\{X_{j},Y_{j}\\},j=2,\ldots,d}(Y_{1}\cup
Z_{2}\cup\ldots\cup Z_{d})$ are closed in $\mathbb{R}^{k}$. Hence,
$f^{-1}(A)=(X_{1}\cup\ldots\cup X_{d})\cap B$ is closed in
$(X_{1}\cup\ldots\cup X_{d})$. Thus, $f$ is continuous. ∎

Now we prove Theorem 3.1. Define function
$\hat{x}_{j}:Conv(S_{j})\rightarrow\mathbb{R}^{n}$ as
$\hat{x}_{j}(\theta)=\lambda^{j}_{1}{x^{\ast}(\theta}_{1}^{j})+\ldots+\lambda^{j}_{k+1}{x^{\ast}(\theta}_{k+1}^{j})$
for
$\theta=\lambda_{1}^{j}\theta_{1}^{j}+\ldots+\lambda_{k+1}^{j}\theta_{k+1}^{j}$.
Next, we prove the function $\hat{x}_{j}$ is continuous. For
$\theta=\lambda_{1}^{j}\theta_{1}^{j}+\ldots+\lambda_{k+1}^{j}\theta_{k+1}^{j}\in
Conv(S_{j})$, let $y_{j}(\theta)=(\lambda^{j}_{1},\ldots,\lambda^{j}_{k+1})$.
Then, $y_{j}(\theta)$ is inverse of linear function (which is linear) and
$\hat{x}_{j}(\theta)=y_{j}(\theta)^{T}(x^{\ast}(\theta^{j}_{1}),\ldots,x^{\ast}(\theta^{j}_{k+1}))$
is linear function of $y_{j}(\theta)$. Thus, $\hat{x}_{j}(\theta)$ is
composite function of two linear functions which is continuous. Also, for any
nonempty subset $J\subseteq\\{1,2,\ldots,d\\}$ and for any $j_{1},j_{2}\in J$,

$\hat{x}_{j_{1}}|\bigcap_{j\in J}Conv(S_{j})=\hat{x}_{j_{2}}|\bigcap_{j\in
J}Conv(S_{j}).$

since $\bigcap_{j\in J}Conv(S_{j})=Conv(\bigcap_{j\in J}S_{j})$. Thus, by the
Lemma 3.1, the function $\hat{x}$

$\hat{x}:Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})\rightarrow\mathbb{R}^{n},\quad\theta\rightarrow\begin{cases}\hat{x}_{1}(\theta),\quad\theta\in
Conv(S_{1})\\\ \hat{x}_{2}(\theta),\quad\theta\in Conv(S_{2})\\\ \vdots\\\
\hat{x}_{d}(\theta),\quad\theta\in Conv(S_{d}).\end{cases}$

is continuous function. ∎

An inherent question regarding the function $\hat{x}$ pertains to the degree
of approximation accuracy. We first remark that there exists parametric
optimization problem where convergence of errors of $\hat{x}$ is not
guaranteed since $x^{\ast}(\theta)$ is arbitrarily chosen from
$C^{\ast}(\theta)$.

######  Example 3.2.

$\min_{x}\quad f(x,\theta)=(x-1)^{2}(x-3)^{2}\quad\text{subject\;to}\quad x\in
C(\theta)=\\{1,3\\}.$

For the trivial parametric optimization problem given by Example 3.2, the
optimal policy correspondence is

$C^{\ast}(\theta)=\\{1,3\\},\forall\theta$

In this case, our construction always has suboptimality of 1 for some $\theta$
because $|f^{\ast}({(\theta}_{1}+\theta_{2})/2)-f(2,\
{(\theta}_{1}+\theta_{2})/2)|=1$ if $(\theta_{1},1)$ and $(\theta_{2},3)$ are
sampled with $\theta_{1}<\theta_{2}$.

In order to determine the suitability of using $\hat{x}$ for approximating
specific parametric optimization problems, we establish metrics to assess the
performance of the target function $\hat{x}$. These metrics are referred to as
$\varepsilon$-suboptimality and $\varepsilon$-infeasibility. We present our
main development in Theorem 3.2, which states that a constructed function is
$\varepsilon$-infeasible and $\varepsilon$-suboptimal solution for
sufficiently dense training data under certain conditions. While this adds
some restrictions, it allows applying UAT to parametric optimization and these
two conditions can be lifted with a stable sampler, which we further discuss
in the subsequent sections.

######  Definition 3.2.

Let $f$ be the objective function and $C$ be the correspondence in the
formulation given by (2.1). Then, for $\varepsilon>0$,

  1. (a)

$\hat{x}(\theta)$ is $\varepsilon$-infeasible solution if
$\hat{x}(\theta)\in\mathcal{B}_{\varepsilon}(C(\theta)).$

  2. (b)

$\hat{x}(\theta)$ is $\varepsilon$-suboptimal solution if
$|f(\hat{x}(\theta),\theta)-f(x^{\ast}(\theta),\theta)|<\varepsilon.$

######  Theorem 3.2 (Convergence Property of Piecewise Linear Policy
Approximation).

Suppose that $f$, $C$ satisfy all conditions for Theorem 2.2. Define a
training data set
$T=\\{(\theta_{i},x^{\ast}(\theta_{i}))|\theta_{i}\in\mathrm{\Theta},i=1,\cdots,m\\}$
where $x^{\ast}(\theta_{i})$ is an arbitrarily chosen point from
$C^{\ast}(\theta_{i})$. For $\theta\in
Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})$, define
$d(S_{j_{\theta}})=\max\\{\|p-q\|:p,q\in Conv(S_{j_{\theta}})\\}$ where
$S_{j_{\theta}}$ is element of finite collection $\mathcal{S}$ in Theorem 3.1.
Then, the function $\hat{x}(\theta)$ in Theorem 3.1 satisfies the followings.

  1. (a)

If $Conv(C^{\ast}(\theta))\subseteq C(\theta)$, for given $\varepsilon>0$,
$\exists\delta>0$ s.t. if $d(S_{j})<\delta$, $\hat{x}(\theta)$ is
$\varepsilon$-infeasible solution.

  2. (b)

If $f(x,\theta)=f^{\ast}(\theta),\forall x\in Conv(C^{\ast}(\theta))$, for
given $\varepsilon>0$, $\exists\delta>0$ s.t. if $d(S_{j})<\delta$,
$\hat{x}(\theta)$ is $\varepsilon$-suboptimal solution.

###### Proof.

(a) Assume $Conv(C^{\ast}(\theta))\subseteq C(\theta)$ and let
$\varepsilon>0$. Since $f$, $C$ satisfy all conditions for Theorem 2.2,
$C^{\ast}$ is upper hemicontinuous. Thus, a set

$\mathrm{\Delta}_{\theta}=\\{\delta>0:\|\theta-\theta^{\prime}\|<\delta\Longrightarrow
C^{\ast}(\theta^{\prime})\subseteq\mathcal{B}_{\varepsilon}(C^{\ast}(\theta))\\}.$

is not empty.

Define $\delta_{\theta}=\sup{\mathrm{\Delta}_{\theta}}$. Choose
$\delta=\delta_{\theta}$. If $d(S_{j_{\theta}})<\delta$,
$\|\theta-\theta^{j_{\theta}}_{l}\|<\delta$ i.e.
$C^{\ast}(\theta_{l}^{j_{\theta}})\subseteq\mathcal{B}_{\varepsilon}(C^{\ast}(\theta)),\forall
l=1,\ldots,k+1$. Then, with the assumption and $C^{\ast}(\theta)\subseteq
Conv(C^{\ast}(\theta))$,

$x^{\ast}(\theta_{l}^{j_{\theta}})\in
C^{\ast}(\theta_{l}^{j_{\theta}})\subseteq\mathcal{B}_{\varepsilon}(C^{\ast}(\theta))\subseteq\mathcal{B}_{\varepsilon}(Conv(C^{\ast}(\theta)))\subseteq\mathcal{B}_{\varepsilon}(C(\theta)),\forall
l=1,2,\ldots,k+1.$

Thus,
$x^{\ast}(\theta_{l}^{j_{\theta}})\in\mathcal{B}_{\varepsilon}(Conv(C^{\ast}(\theta)))\subseteq\mathcal{B}_{\varepsilon}(C(\theta))$.
Note that, since $Conv(C^{\ast}(\theta))$ is convex set,
$\mathcal{B}_{\varepsilon}(Conv(C^{\ast}(\theta)))$ is also convex set. This
means the convex combination

$\lambda^{j_{\theta}}_{1}{x^{\ast}(\theta}_{1}^{j_{\theta}})+\ldots+\lambda^{j_{\theta}}_{k+1}{x^{\ast}(\theta}_{k+1}^{j_{\theta}}).$

is in $\mathcal{B}_{\varepsilon}(Conv(C^{\ast}(\theta)))$. Thus,
$\hat{x}(\theta)\in B_{\varepsilon}(C(\theta))$.

(b) We first prove Lemma 3.2.

######  Lemma 3.2.

If $A\subseteq\mathbb{R}^{n}$ is a compact set, $Conv(A)$ is also a compact
set.

###### Proof of Lemma 3.2.

Carathéodory Theorem (Danninger-Uchida Danninger-Uchida (2009)) states that
each element of the convex hull of $A$ is a convex combination of $n+1$
elements of $A$. By defining $Simp(n)=\\{(w_{0},\ldots,w_{n}):w_{j}\geq
0,w_{0}+\ldots+w_{n}=1\\}$ and $F(a_{0},\ldots,a_{n};\
w_{0},\ldots,w_{n})=\sum_{i}w_{i}a_{i}$, $Conv(A)$ can be expressed as the
image of the compact set $A^{n+1}\times Simp(n)$ under a continuous map $F$,
and so it is compact. ∎

Now assume $f(x,\theta)=f^{\ast}(\theta),\forall x\in Conv(C^{\ast}(\theta))$
and let $\varepsilon>0$. We first show there exists $\delta^{\prime}>0$ such
that,

$\inf_{x^{\ast}\in
Conv(C^{\ast}(\theta))}\|x^{\prime}-x^{\ast}\|<\delta^{\prime}\Longrightarrow|f(x^{\prime},\theta)-f^{\ast}(\theta)|<\varepsilon,\forall
x^{\prime}\in\mathcal{B}_{\varepsilon}(C(\theta)).$

Since $C$ is compact-valued correspondence,
$\mathcal{B}_{\varepsilon}(C(\theta))\times{\theta}$ is compact set. Thus, $f$
is uniformly continuous on
$\mathcal{B}_{\varepsilon}(C(\theta))\times{\theta}$. Thus, there exist
$\delta^{\prime\prime}>0$ such that,

$\|y-z\|<\delta^{\prime\prime}\Longrightarrow|f(y,\theta)-f(z,\theta)|<\varepsilon,\forall
y,z\in\mathcal{B}_{\varepsilon}(C(\theta)).$

Choose $\delta^{\prime}=\delta^{\prime\prime}$. Note that $C^{\ast}$ is
compact-valued correspondence from Theorem 2.2. Thus, $Conv(C^{\ast}(\theta))$
is also compact set from Lemma 3.2. Hence,

$x_{min}^{\ast}={\arg\min}_{x^{\ast}\in
Conv(C^{\ast}(\theta))}\|x^{\prime}-x^{\ast}\|={\arg\min}_{x^{\ast}\in
Conv(C^{\ast}(\theta))}\|x^{\prime}-x^{\ast}\|.$

is in $Conv(C^{\ast}(\theta))$. Now we have

$\inf_{x^{\ast}\in
Conv(C^{\ast}(\theta))}\|x^{\prime}-x^{\ast}\|<\delta^{\prime}\Longrightarrow\|x^{\prime}-x_{min}^{\ast}\|<\delta^{\prime}=\delta^{\prime\prime}\Longrightarrow|f(x^{\prime},\theta)-f(x_{min}^{\ast},\theta)|<\varepsilon.$

Since $x_{min}^{\ast}\in Conv(C^{\ast}(\theta))$,
$f(x_{min}^{\ast},\theta)=f^{\ast}(\theta)$. Thus,
$|f(x^{\prime},\theta)-f^{\ast}(\theta)|<\varepsilon$

Now, we prove part (b) of the theorem. From the above statement, there exists
$\delta^{\prime}>0$ such that,

$\inf_{x^{\ast}\in
Conv(C^{\ast}(\theta))}\|x^{\prime}-x^{\ast}\|<\delta^{\prime}\Longrightarrow|f(x^{\prime},\theta)-f^{\ast}(\theta)|<\varepsilon,\forall
x^{\prime}\in\mathcal{B}_{\varepsilon}(C(\theta)).$

Also, since $f$, $C$ satisfy all conditions for Theorem 2.2, $C^{\ast}$ is
upper hemicontinuous. Thus, a set

$\mathrm{\Delta}_{\theta}=\\{\delta>0|\;if\;\|\theta-\theta^{\prime}\|<\delta,C^{\ast}(\theta^{\prime})\subseteq\mathcal{B}_{\delta}^{\prime}(C^{\ast}(\theta))\\}.$

is not empty.

Define $\delta_{\theta}=\sup{\mathrm{\Delta}}_{\theta}$. Choose
$\delta=\delta_{\theta}$. If $d(S_{j})<\delta$,
$\|\theta-\theta^{j_{\theta}}_{l}\|<\delta$ i.e.
$C^{\ast}(\theta_{l}^{j_{\theta}})\subseteq\mathcal{B}_{\delta^{\prime}}(C^{\ast}(\theta)),\forall
l=1,\ldots,k+1$. Then with $C^{\ast}(\theta)\subseteq Conv(C^{\ast}(\theta))$,

$x^{\ast}(\theta_{l}^{j_{\theta}})\in
C^{\ast}(\theta_{l}^{j_{\theta}})\subseteq\mathcal{B}_{\delta^{\prime}}(C^{\ast}(\theta))\subseteq\mathcal{B}_{\delta^{\prime}}(Conv(C^{\ast}(\theta))),\forall
l=1,\ldots,k+1.$

Since $Conv(C^{\ast}(\theta))$ is convex set,
$\mathcal{B}_{\delta^{\prime}}(Conv(C^{\ast}(\theta)))$ is also convex set.
This means the convex combination

$\hat{x}(\theta)=\lambda^{j_{\theta}}_{1}{x^{\ast}(\theta}_{1}^{j_{\theta}})+\ldots+\lambda^{j_{\theta}}_{k+1}{x^{\ast}(\theta}_{k+1}^{j_{\theta}}).$

is in $\mathcal{B}_{\delta^{\prime}}(Conv(C^{\ast}(\theta)))$. Also, note that
$\hat{x}(\theta)\in\mathcal{B}_{\varepsilon}(C(\theta))$ from part (a) since
assumption in (b) indicates $Conv(C^{\ast}(\theta))\subseteq
C^{\ast}(\theta)\subseteq C(\theta)$. Accordingly,
$|f(\hat{x}(\theta),\theta)-f^{\ast}(\theta)|<\varepsilon$.

∎

Theorem 3.2 shows that if the problem (2.1) satisfies the sufficient
conditions, the errors on feasibility and optimality of our piecewise linear
policy approximation $\hat{x}(\theta)$ converges to zero. For example, suppose
that training data
$T=\\{(\theta_{i},x^{\ast}(\theta_{i}))|\theta_{i}\in\mathrm{\Theta},\
i=1,\cdots,m\\}$ is sampled from Example 3.1. With out loss of generality,
suppose that $\theta_{1}\leq\theta_{2}\leq\ldots\leq\theta_{m}$. Then, the
finite collection $\mathcal{S}$ in Theorem 3.1 can be constructed as
$\mathcal{S}=\\{S_{j},j=1,\ldots,m-1\\}$ where
$S_{j}=\\{\theta_{j},\theta_{j+1}\\}$. Let $l$ be an index such that
$\theta_{l}\leq\ 1\leq\theta_{l+1}$. Then $\hat{x}(\theta)$ is

$\hat{x}(\theta)=\begin{cases}(0,\ 1)&\text{$\theta\leq\theta_{l}$},\\\
(\frac{\theta-\theta_{l}}{\theta_{l+1}-\theta_{l}},\frac{\theta_{l+1}-\theta}{\theta_{l+1}-\theta_{l}})&\text{$\theta_{l}<\theta<\theta_{l+1}$},\\\
(1,\ 0)&\text{$\theta_{l+1}\leq\theta$}.\end{cases}$

Note that $\hat{x}(\theta)$ is a feasible solution, and, thus, an
$\varepsilon$-infeasible solution. We want to further show that
$\hat{x}(\theta)$ is an $\varepsilon$-suboptimal solution. It holds that
$f^{\ast}(\theta)=f(\hat{x}(\theta),\theta)$ for the three cases:
$\theta\leq\theta_{l},\theta\geq\theta_{l+1}$, or $\theta=1$. For
$\theta_{l}<\theta<1$, $\varepsilon$-suboptimality can be shown as below if we
choose $\delta<4\varepsilon$,

$f^{\ast}(\theta)-f(\hat{x}(\theta),\theta)=1-\frac{\theta(\theta-\theta_{l})}{\theta_{l+1}-\theta_{l}}-\frac{\theta_{l+1}-\theta}{\theta_{l+1}-\theta_{l}}$
$=\frac{(\theta-\theta_{l})(1-\theta)}{\theta_{l+1}-\theta_{l}}<\frac{(\theta-\theta_{l})(1-\theta)}{1-\theta_{l}}\leq\frac{1-\theta_{l}}{4}<\frac{\delta}{4}<\varepsilon.$

Similarly, the same results can be derived for $1<\theta<\theta_{l+1}$. Thus,
$\hat{x}(\theta)$ is an $\varepsilon$-suboptimal solution.

###  3.1 General Case with a Stable Sampling Function.

We have shown that the proposed piecewise linear policy approximation can be a
reasonable solution under some assumptions on $f$ and $C$ for dense enough
training data. In this subsection, a stable sampling function designed to
tackle a broader range of parametric optimization problem. Note that Example
3.2 does not satisfy the conditions for Theorem 3.2 since
$Conv(C^{\ast}(\theta))\nsubseteq C^{\ast}(\theta)$ and
$Conv(C^{\ast}(\theta))\nsubseteq C(\theta)$. But even in this case, it may be
possible to apply the Theorem 3.2 by sampling data from certain parts of
$C^{\ast}(\theta)$, which has practical implications since decision makers
often understand the nature of parametric optimization problems. Based on this
idea, we define notion and stability of a sampling function.

######  Definition 3.3.

Define a sampling function
$s\mathrm{\,:\,}\mathrm{\Theta}\rightarrow\bigcup_{\theta}{C^{\ast}(\theta)}$
as $s(\theta)=x^{\ast}(\theta)$. Sampling function $s$ is stable with respect
to $C^{\ast}$ if there exists a non-empty, compact, and convex-valued upper
hemicontinuous correspondence $\overline{C^{\ast}}$ such that
$s(\theta)\in\overline{C^{\ast}}(\theta)\subseteq
C^{\ast}(\theta)\;\forall\theta.$

Note that the stable sampling function does not always exist. It depends on
formulation of parametric optimization problem. For example, any sampling
function in Example 3.1 is stable since $C^{\ast}(\theta)$ is convex-valued.
In Example 3.2, a sampling function that samples only 1 or 3 is stable, choose
$\overline{C^{\ast}}$ as $\\{1\\}$ or $\\{3\\}$. Consider the following
modified version of Example 3.2.

######  Example 3.3.

$\min_{x}\quad
f(x,\theta)=(x-1)^{2}(x-3)^{2}-\theta(x-3)\quad\text{subject\;to}\quad
C(\theta)=\\{1,3\\}.$

The optimal policy correspondence for the problem given by Example 3.3 is

$C^{\ast}(\theta)=\begin{cases}\\{1\\}&\text{$\theta<0$},\\\ \\{1,\
3\\}&\text{$\theta=0$},\\\ \\{3\\}\ &\text{$\theta>0$}\end{cases}$

Note that there are two convex-valued sub correspondences of
$C^{\ast}(\theta)$, $C^{1}(\theta)$ and $C^{2}(\theta)$, which neither is
upper hemicontinuous.

$C^{1}(\theta)=\begin{cases}\\{1\\}&\text{$\theta<0$},\\\
\\{1\\}&\text{$\theta=0$},\\\ \\{3\\}\ &\text{$\theta>0$}\end{cases}\quad
C^{2}(\theta)=\begin{cases}\\{1\\}&\text{$\theta<0$},\\\
\\{3\\}&\text{$\theta=0$},\\\ \\{3\\}\ &\text{$\theta>0$}\end{cases}$

The advantage of a stable sampling function is that it makes Theorem 3.2
applicable even to parametric optimization problems that do not satisfy
conditions $Conv(C^{\ast}(\theta))\subseteq C(\theta)$ and
$f(x,\theta)=f^{\ast}(\theta),\forall x\in Conv(C^{\ast}(\theta))$. The
following theorem shows that these two conditions become trivial if $C^{\ast}$
is convex-valued correspondence.

######  Theorem 3.3.

If $C^{\ast}$ is convex-valued correspondence, the followings are hold.

  1. (a)

$Conv(C^{\ast}(\theta))\subseteq C(\theta)$

  2. (b)

$f(x,\theta)=f^{\ast}(\theta),\forall x\in Conv(C^{\ast}(\theta))$

###### Proof.

Since $C^{\ast}(\theta)$ is convex set,
$Conv(C^{\ast}(\theta))=C^{\ast}(\theta)$. With this fact, we have

(a) $Conv(C^{\ast}(\theta))=C^{\ast}(\theta)\subseteq
C^{\ast}(\theta)\subseteq C(\theta)$.

(b) $C^{\ast}(\theta)\subseteq C^{\ast}(\theta)$ implies
$f(x,\theta)=f^{\ast}(\theta),\forall x\in Conv(C^{\ast}(\theta))$.

∎

If we have a stable sampling function $s$, $\overline{C^{\ast}}(\theta)$ can
be considered as a substitute for $C^{\ast}(\theta)$. Since
$\overline{C^{\ast}}(\theta)$ is convex-valued, the sufficient conditions
$Conv(\overline{C^{\ast}}(\theta))\subseteq C(\theta)$ and
$f(x,\theta)=f^{\ast}(\theta),\forall x\in Conv(\overline{C^{\ast}}(\theta))$
become redundant from Theorem 3.3. Furthermore, since
$\overline{C^{\ast}}(\theta)$ is compact-valued and upper hemicontinuous, the
same arguments in proof of Theorem 3.2 are applicable to
$\overline{C^{\ast}}(\theta)$, so that we can apply Theorem 3.2 to more
general parametric optimization.

##  4 Suitability of Neural Networks.

In previous section, we focused on constructing and evaluating the target
function. We build up our target function as continuous piecewise linear
single-valued function and state its goodness in terms of
$\varepsilon$-infeasibility and $\varepsilon$-suboptimality. In this section,
we discuss capability of NN in approximating the target function. It is also
possible to obtain a target function directly from training data. However, for
a new parameter, this require to find $k+1$ points and its corresponding
weights of the convex combination. This process requires considerable
computation cost as the dimension of the parameter space increases, so it is
not suitable for real-time decision making. On the other hand, the forward
process of passing data to NN requires no additional processing time for
finding the $k+1$ points once it is trained in advance. Then, is NN a really
good estimator for our piecewise linear policy approximation? We answer this
question by two aspect, generalization error (GE) and approximation error
(AE).

In order to define and examine the GE and AE of NN, it is necessary to make
choices regarding the architecture and loss function. This paper focuses on a
specific type of neural network architecture, namely a feed forward network
with rectified linear unit (ReLU) activations. The ReLU activation function is
defined as $ReLU(h)=\max(h,0)$. The layers of a ReLU network, denoted as
$h^{l},\forall l=1,\ldots,L$, are defined recursively using the following
relation: $h^{l}=ReLU(W^{l}h^{l-1}+b)$, where $h^{0}=ReLU(b)$. Here, $W^{l}$
represents the weight matrices associated with each layer, and they satisfy
the constraint that their infinity norms, denoted as $\|W^{l}\|_{\infty}$, are
bounded by $B_{l}$. Additionally, we assume that $\|W^{1}\|$ is bounded by
$B_{1}$. To sum up, the set of functions that can be represented by the output
at depth $L$ in a ReLU network is denoted as
$\mathcal{H}^{L}=\\{h^{L}(\\{W^{l}\\}_{l=1}^{L}):\|W^{l}\|_{\infty}\leq
B_{l},l\in[1,L],\|W^{1}\|\leq B_{1}\\}$. For a loss function of NN, we prove
following theorem

######  Theorem 4.1.

Let $h(\theta)$ be ReLU NN and let $\hat{x}(\theta)$ be a constructed
piecewise linear approximation.

  1. (a)

$\forall\varepsilon>0,\exists\delta>0$ such that If
$\|\hat{x}(\theta)-h(\theta)\|<\delta$ and $\hat{x}(\theta)$ is
$\varepsilon/2$-infeasible solution, $h(\theta)$ is $\varepsilon$-infeasible
solution.

  2. (b)

$\forall\varepsilon>0,\exists\delta>0$ such that If
$\|\hat{x}(\theta)-h(\theta)\|<\delta$ and $\hat{x}(\theta)$ is
$\varepsilon/2$-suboptimal solution, $h(\theta)$ is $\varepsilon$-suboptimal
solution.

###### Proof.

(a) Since $\hat{x}(\theta)$ is $\varepsilon/2$-infeasible solution,
$\hat{x}(\theta)\in\mathcal{B}_{\varepsilon/2}(C(\theta))$. Choose
$\delta=\varepsilon/2$. Then, since $\|\hat{x}(\theta)-h(\theta)\|<\delta$,

$h(\theta)\in\mathcal{B}_{\varepsilon/2}(\hat{x}(\theta))\subseteq\mathcal{B}_{\varepsilon}(C(\theta)).$

Thus, $h(\theta)$ is $\varepsilon$-infeasible solution
(b) Since $\hat{x}(\theta)$ is $\varepsilon/2$-suboptimal solution,
$|f(\hat{x}(\theta),\theta)-f(x^{\ast}(\theta),\theta)|<\varepsilon/2$ Also,
since $f$ is continuous, there exists $\delta^{\prime}>0$ such that,

$\|\hat{x}(\theta)-h(\theta)\|<\delta^{\prime}\Longrightarrow|f(\hat{x}(\theta),\theta)-f(h(\theta),\theta)|<\varepsilon/2$

Choose $\delta=\delta^{\prime}$. Then,

$|f(x^{\ast}(\theta),\theta)-f(h(\theta),\theta)|$
$=|f(x^{\ast}(\theta),\theta)-f(\hat{x}(\theta),\theta)+f(\hat{x}(\theta),\theta)-f(h(\theta),\theta)|$
$\leq|f(x^{\ast}(\theta),\theta)-f(\hat{x}(\theta),\theta)|+|f(\hat{x}(\theta),\theta)-f(h(\theta),\theta)|$
$<\varepsilon/2+\varepsilon/2=\varepsilon$

Thus, $h(\theta)$ is $\varepsilon$-suboptimal solution.

∎

Theorem 4.1 says that if the NN is sufficiently close to our target function
$\hat{x}(\theta)$, NN also gives $\varepsilon$-infeasible and
$\varepsilon$-suboptimal solution. Thus, for a set of $m$ training examples
$T=\\{(\theta_{i},x^{\ast}(\theta_{i}))\\}_{i=1}^{m}$ and ReLU NN $h$, we
suppose that the weights are learned by minimizing a loss function $\ell$
which is defined as

$\ell(h(\theta),x^{\ast}(\theta))=\|h(\theta)-x^{\ast}(\theta)\|^{2}$

###  4.1 Generalization error.

For a hypothesis class $\mathcal{H}$, the GE is defined as

$\mathcal{G}(\mathcal{H})=\mathbb{E}_{T}\sup_{h\in\mathcal{H}}(L_{D}(h)-L_{T}(h)).$

where $L_{D}(h)=\mathbb{E}_{\theta\sim D}\ell(h(\theta),x^{\ast}(\theta))$
represents the expected loss when evaluating estimator $h$ with respect to the
underlying parameter distribution $D$, and
$L_{T}(h)=\frac{1}{m}\sum_{i=1}^{m}\ell(h(\theta_{i}),x^{\ast}(\theta_{i}))$
denotes the average empirical loss computed over the training set $T$,
consisting of $m$ data samples. The GE is a global characteristic that
pertains to the class of estimators, which evaluates their suitability for
given learning problem. A large generalization error indicates that within
this class of estimators, there exist estimators that significantly deviate in
performance on average between the true loss $L_{D}$, and the empirical loss
$L_{T}$. Given the loss function $\ell$, Shultzman et al. (2023) proved the
following theorem which gives bound for generalization error of the class of
ReLU networks $\mathcal{H}^{L}$.

######  Theorem 4.2 (Bound for GE, restated from Shultzman et al. (2023)).

Consider the class of feed forward networks of depth-$L$ with ReLU activations
$\mathcal{H}^{L}=\\{h^{L}(\\{W^{l}\\}_{l=1}^{L}):\|W^{l}\|_{\infty}\leq
B_{l},l\in[1,L],\|W^{1}\|\leq B_{1}\\}$ and $m$ training samples. For a loss
function
$\ell(h(\theta),x^{\ast}(\theta))=\|h(\theta)-x^{\ast}(\theta)\|^{2}$, its
generalization error satisfies

$\mathcal{G}(\mathcal{H}^{L})\leq 2\frac{\prod_{l=0}^{L}B_{l}}{\sqrt{m}}.$

Thus, for $m$ training samples, it can be seen that the GE of
$\mathcal{H}^{L}$ is bounded as $O(\frac{1}{\sqrt{m}})$ in learning our
piecewise linear policy approximation.

###  4.2 Approximation error.

The AE represents the lowest possible error that an estimator can achieve
within a given hypothesis class. It quantifies the amount of error incurred
due to the limitation of selecting from a specific class. Unlike
generalization error, the approximation error is independent of the size of
the sample. For the hypothesis class $\mathcal{H}$, the AE is defined as

$\mathcal{A}(\mathcal{H})=\min_{h\in\mathcal{H}}L_{D}(h).$

Note that our target function $\hat{x}(\theta)$ is continuous piecewise linear
function. It has been shown that any continuous piecewise linear function can
be represented by a deep ReLU implementation (Wang and Sun (2005), Arora et
al. (2016)), which means that the AE of NN with ReLU activations for our
piecewise linear policy approximation is zero. In other words, if
$h^{\ast}=\arg\min_{h\in\mathcal{H}^{L}}L_{D}(h)$, $h^{\ast}(\theta)$ is
$\varepsilon$-infeasible and $\varepsilon$-suboptimal solution.

##  5 Improving Feasibility.

In this section, we address issue that NN may give infeasible solutions for
the original problem. This occurs due to the inability of NN to discern the
underlying structure of an optimization problem solely through the provided
training data. This is a critical issue because NN has been mainly used in
high-assurance systems such as autonomous vehicles (Kahn et al. (2017)),
aircraft collision avoidance (Julian and Kochenderfer (2017)) and high-
frequency trading (Arévalo et al. (2016)).

Therefore, we propose a strategy to improve feasibility and discuss training
with suboptimal solutions. In general, it is not easy to get an accurate
optimal solution. Most algorithms that solve optimization problems set a
certain level of threshold and stop once the threshold is achieved. We
demonstrate that it is possible to preserve $\varepsilon$-infeasibility even
when employing suboptimal solutions for approximating parametric optimization
problems, but the optimality of the approximation is inevitably reduced by the
suboptimality of the suboptimal solutions.

###  5.1 Infeasibility and Suboptimality.

Representative approaches to improve feasibility include specifying the
structure of NN, such as analyzing the output range of each layer (Dutta et
al. (2018)), or obtaining a feasible solution from predictions of NN, such as
greedy selection algorithm (Dai et al. (2017)). In our case, we already know
that an $\varepsilon$-infeasible solution can be obtained from suitable
optimization problems. Thus, if more strict feasible solutions than
$\varepsilon$ are used, feasible solutions to the original problems can be
obtained. Note that improving feasibility infers suboptimality. Therefore,
before demonstrating this strategy, we discuss about feasibility and
optimality of our piecewise linear policy approximation with suboptimal
solutions. Suboptimal solution sets can be seen as a general case of optimal
solution sets. If a suboptimal policy correspondence is also compact valued
and upper hemicontinuous, similar arguments can be applied as in Theorem 3.2.
Thus, we first show this fact by starting with the following proposition.

######  Proposition 5.1.

Define $C^{\gamma}(\theta)$ as $C^{\gamma}(\theta)=\\{x\in
C(\theta):|f(x,\theta)-f^{\ast}(\theta)|\leq\gamma\\}$. Then,
$C^{\gamma}(\theta)$ is compact valued upper hemicontinuous correspondence.

###### Proof.

We first prove Lemma 5.1

######  Lemma 5.1.

If $C_{1},C_{2}\mathrm{\,:\,}\mathrm{\Theta}\rightrightarrows X$ are
correspondences, $C_{1}$ is upper hemicontinuous and compact valued, and
$C_{2}$ is closed, then $C_{1}\cap
C_{2}\mathrm{\,:\,}\mathrm{\Theta}\rightrightarrows X$ defined by $\
(C_{1}\cap C_{2})(\theta)=C_{1}(\theta)\cap C_{2}(\theta)$ is upper
hemicontinuous.

###### Proof of Lemma 5.1.

See Papageorgiou (1997) ∎

To see that $C^{\gamma}(\theta)$ is compact valued, note that
$f_{\theta}:C(\theta)\rightarrow\mathbb{R}$ is continuous since $f(x,\theta)$
is continuous. Since $C^{\gamma}(\theta)$ is closed subset of the compact set
$C(\theta)$, $C^{\gamma}(\theta)$ is also compact. Finally, since $C(\theta)$
is compact valued continuous correspondence, it is upper hemicontinuous and
compact valued. Thus, by Lemma 5.1, $C^{\gamma}(\theta)=C(\theta)\cap
C^{\gamma}(\theta)$ is upper hemicontinuous. ∎

With Proposition 5.1, the following theorem can be proved similarly as Theorem
3.2, which state our piecewise linear policy approximation become
$\varepsilon$-infeasible and $(\varepsilon+\gamma)$-optimality solution under
same conditions in Theorem 3.2.

######  Theorem 5.1.

Suppose that $f$, $C$ satisfy all conditions for Theorem 2.2. Define a
training data set
$T=\\{(\theta_{i},x^{\gamma}(\theta_{i}))|\theta_{i}\in\mathrm{\Theta},i=1,\cdots,m\\}$
where $x^{\gamma}(\theta_{i})$ is an arbitrarily chosen point from
$C^{\gamma}(\theta_{i})$. For $\theta\in
Conv(\\{\theta_{1},\theta_{2},\ldots,\theta_{m}\\})$, define
$d(S_{j_{\theta}})=\max\\{\|p-q\|:p,q\in Conv(S_{j_{\theta}})\\}$ where
$S_{j_{\theta}}$ is element of finite collection $\mathcal{S}$ in Theorem 3.1.
Then, the function
$\hat{x}(\theta)=\lambda^{j_{\theta}}_{1}{x^{\gamma}(\theta}_{1}^{j_{\theta}})+\ldots+\lambda^{j_{\theta}}_{k+1}{x^{\gamma}(\theta}_{k+1}^{j_{\theta}})$
satisfies the followings.

  1. (a)

If $Conv(C^{\gamma}(\theta))\subseteq C(\theta)$, for given $\varepsilon>0$,
there exists $\delta>0$ s.t. if $d(S_{j})<\delta$, $\hat{x}(\theta)$ is
$\varepsilon$-infeasible solution.

  2. (b)

If $|f(x,\theta)-f^{\ast}(\theta)|\leq\gamma,\forall x\in
Conv(C^{\gamma}(\theta))$, for given $\varepsilon>0$, there exists $\delta>0$
s.t. if $d(S_{j})<\delta$, $\hat{x}(\theta)$ is
$(\varepsilon+\gamma)$-suboptimal solution

###### Proof.

(a) Since $C^{\gamma}$ is upper hemicontinuous, similar to statement for (a)
in Theorem 3.2, we get

$\lambda^{j\theta}_{1}{x^{\gamma}(\theta}_{1}^{j\theta})+\ldots+\lambda^{j\theta}_{k+1}{x^{\gamma}(\theta}_{k+1}^{j\theta})\in\mathcal{B}_{\varepsilon}(Conv(C^{\gamma}(\theta))).$

With the assumption,
$\hat{x}(\theta)\in\mathcal{B}_{\varepsilon}(Conv(C^{\gamma}(\theta)))\subseteq\mathcal{B}_{\varepsilon}(C(\theta))$.

(b) Assume $|f(x,\theta)-f^{\ast}(\theta)|\leq\gamma,\forall x\in
Conv(C^{\gamma}(\theta))$ and let $\varepsilon>0$. Since $C^{\gamma}$ is upper
hemicontinuous and compact valued, similar to statement for (b) in Theorem
3.2, there exists $\delta^{\prime}>0$ such that,

$\inf_{x^{\gamma}\in
Conv(C^{\gamma}(\theta))}\|x^{\prime}-x^{\gamma}\|<\delta^{\prime}\Longrightarrow|f(x^{\prime},\theta)-f_{min}^{\gamma}(\theta)|<\varepsilon,\forall
x^{\prime}\in\mathcal{B}_{\varepsilon}(C(\theta)).$

where $x_{min}^{\gamma}={\arg\min}_{x^{\gamma}\in
Conv(C^{\gamma}(\theta))}\|x^{\prime}-x^{\gamma}\|$. Since
$x_{min}^{\gamma}\in Conv(C^{\gamma}(\theta))$, we have

$|f(x^{\prime},\theta)-f^{\ast}(\theta)|\leq|f(x^{\prime},\theta)-f(x^{\gamma}_{min},\theta)|+|f(x^{\gamma}_{min},\theta)-f^{\ast}(\theta)|<\varepsilon+\gamma.$

Then, similar to (b) of Theorem 3.2, we have

$\hat{x}(\theta)=\lambda^{j\theta}_{1}{x^{\gamma}(\theta}_{1}^{j\theta})+\ldots+\lambda^{j\theta}_{k+1}{x^{\gamma}(\theta}_{k+1}^{j\theta})\in\mathcal{B}_{\delta^{\prime}}(Conv(C^{\gamma}(\theta))).$

Also, note that condition in (b) implies $Conv(C^{\gamma}(\theta))\subseteq
C^{\gamma}(\theta)\subseteq C(\theta)$ which indicates
$\hat{x}(\theta)\in\mathcal{B}_{\varepsilon}(C(\theta))$. Accordingly,
$|f(\hat{x}(\theta),\theta)-f^{\ast}(\theta)|<\varepsilon+\gamma$.

∎

Now we demonstrate the proposed strategy with linear programming (LP) and
quadratic programming (QP). Note that, since the optimal solution set of every
convex optimization is convex, convex optimization satisfies the condition for
part (a) in Theorem 3.2. Thus, our strategy for improving feasibility can be
applied. The formulations of LP and QP are as follows which are modified
version with with slightly perturbed right hand side in standard formulation.
For each problem, parameters except $\theta$ and $t$ were randomly generated
and fixed.

For LP,

$\min_{x}\quad c^{T}x\quad\text{subject\;to}\quad
Ax\leq\theta-t\mathbf{1},\quad c,x,\theta\in\mathbb{R}^{n},\quad
A\in\mathbb{R}^{nxn}$

For QP,

$\min_{x}\quad(1/2)x^{T}Px+q^{T}x\quad\text{subject\;to}\quad
Gx\leq\theta-t\mathbf{1},\quad q,x,\theta\in\mathbb{R}^{n},\quad
P,G\in\mathbb{R}^{nxn}$

where $\mathbf{1}=\begin{bmatrix}1\\\ 1\\\ \vdots\\\ 1\end{bmatrix}$

Here, $t$ serves to obtain a solution further inside than the feasible region
of the original problem. Problems (5.1) and (5.1) are solved for a total of
10,000 times each while slightly increasing the value of $t$ for each
iteration. At this time, 10,000 samples for $\theta$ are generated from
standard normal distribution for each problem. For each $t$, we trained NN
with training pair $\\{\theta,x(\theta)\\}$ and calculated the ratio of the
feasible approximation of NN to the problem when $t=0$. As shown in Figure 2,
the ratio converges to 100% in every problem, which indicates our strategy
guarantees feasibility.

Figure 2: Ratio(%) of feasible solutions to original problem ($t=0$)

##  6 Conclusion.

In this paper, we build theoretical foundations on approximating direct
mapping from input parameters to optimal solution through NN universally and
derive conditions that allow the Universal Approximation Theorem to be applied
to parametric optimization problems by constructing piecewise linear policy
approximation explicitly. More specifically, we cast single-valued continuous
piecewise linear approximation for optimal solution of parametric optimization
and analyze it in terms of feasibility and optimality and show that NN with
ReLU activations can be valid approximator in terms of generalization and
approximation error. Moreover, we propose strategy to improve feasibility and
discuss on the suboptimal training data, findings from this study can directly
benefit solving parametric optimization problems in real-time control systems
or high-assurance systems. In future research, we plan to extend our theory to
more general parametric optimization problems such as integer programming, and
study more approaches for addressing infeasibility of approximated solutions.

## References

  * Nikbakht et al. [2020] Rasoul Nikbakht, Anders Jonsson, and Angel Lozano.  Unsupervised learning for parametric optimization.  _IEEE Communications Letters_ , 25(3):678–681, 2020.
  * Still [2018] Georg Still.  Lectures on parametric optimization: An introduction.  _Optimization Online_ , 2018.
  * Khalaf and Richter [2016] Poya Khalaf and Hanz Richter.  Parametric optimization of stored energy in robots with regenerative drive systems.  In _2016 IEEE International Conference on Advanced Intelligent Mechatronics (AIM)_ , pages 1424–1429. IEEE, 2016.
  * Daryina and Prokopiev [2021] Anna N Daryina and Igor V Prokopiev.  Parametric optimization of unmanned vehicle controller by pso algorithm.  _Procedia Computer Science_ , 186:787–792, 2021.
  * Bai and Liu [2016] Xuejie Bai and Yankui Liu.  Robust optimization of supply chain network design in fuzzy decision system.  _Journal of intelligent manufacturing_ , 27:1131–1149, 2016\.
  * Wang et al. [2014] Ligang Wang, Yongping Yang, Changqing Dong, Tatiana Morosuk, and George Tsatsaronis.  Parametric optimization of supercritical coal-fired power plants by minlp and differential evolution.  _Energy Conversion and Management_ , 85:828–838, 2014.
  * Hornik et al. [1989] K. Hornik, M. Stinchcombe, and H. White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Cybenko [1989] G. Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * Funahashi [1989] K. I. Funahashi.  On the approximate realization of continuous mappings by neural networks.  _Neural networks_ , 2(3):183–192, 1989.
  * Barron [1993] Andrew R Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  _IEEE Transactions on Information theory_ , 39(3):930–945, 1993.
  * Liang and Srikant [2016] Shiyu Liang and Rayadurgam Srikant.  Why deep neural networks for function approximation?  _arXiv preprint arXiv:1610.04161_ , 2016.
  * Yarotsky [2017] Dmitry Yarotsky.  Error bounds for approximations with deep relu networks.  _Neural Networks_ , 94:103–114, 2017.
  * Yarotsky [2018] Dmitry Yarotsky.  Optimal approximation of continuous functions by very deep relu networks.  In _Conference on learning theory_ , pages 639–649. PMLR, 2018.
  * Petersen and Voigtlaender [2018] Philipp Petersen and Felix Voigtlaender.  Optimal approximation of piecewise smooth functions using deep relu neural networks.  _Neural Networks_ , 108:296–330, 2018.
  * Shaham et al. [2018] Uri Shaham, Alexander Cloninger, and Ronald R Coifman.  Provable approximation properties for deep neural networks.  _Applied and Computational Harmonic Analysis_ , 44(3):537–557, 2018.
  * Shen et al. [2019] Zuowei Shen, Haizhao Yang, and Shijun Zhang.  Deep network approximation characterized by number of neurons.  _arXiv preprint arXiv:1906.05497_ , 2019.
  * Daubechies et al. [2022] Ingrid Daubechies, Ronald DeVore, Simon Foucart, Boris Hanin, and Guergana Petrova.  Nonlinear approximation and (deep) relu networks.  _Constructive Approximation_ , 55(1):127–172, 2022.
  * Lu et al. [2021] Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang.  Deep network approximation for smooth functions.  _SIAM Journal on Mathematical Analysis_ , 53(5):5465–5506, 2021.
  * Telgarsky [2016] M. Telgarsky.  Benefits of depth in neural networks.  In _Conference on learning theory_ , pages 1517–1539. PMLR, 2016\.
  * Lu et al. [2017] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang.  The expressive power of neural networks: A view from the width.  _Advances in neural information processing systems_ , 30, 2017.
  * Hanin and Sellke [2017] B. Hanin and M. Sellke.  Approximating continuous functions by relu nets of minimal width.  _arXiv preprint arXiv:1710.11278_ , 2017.
  * Kidger and Lyons [2020] P. Kidger and T. Lyons.  Universal approximation with deep narrow networks.  In _Conference on learning theory_ , pages 2306–2327. PMLR, 2020\.
  * Sun et al. [2016] Shizhao Sun, Wei Chen, Liwei Wang, Xiaoguang Liu, and Tie-Yan Liu.  On the depth of deep neural networks: A theoretical view.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 30(1), Mar. 2016.  doi:10.1609/aaai.v30i1.10243.  URL https://ojs.aaai.org/index.php/AAAI/article/view/10243.
  * Daniely [2017] Amit Daniely.  Depth separation for neural networks.  In _Conference on Learning Theory_ , pages 690–696. PMLR, 2017.
  * Baader et al. [2019] M. Baader, M. Mirman, and M. Vechev.  Universal approximation with certified networks.  _arXiv preprint arXiv:1909.13846_ , 2019.
  * Lin and Jegelka [2018] H. Lin and S. Jegelka.  Resnet with one-neuron hidden layers is a universal approximator.  _arXiv preprint arXiv:1806.10909_ , 2018.
  * Sonoda and Murata [2017] S. Sonoda and N. Murata.  Neural network with unbounded activation functions is universal approximator.  _Applied and Computational Harmonic Analysis_ , 43(2):233–268, 2017.
  * Leshno et al. [1993] M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken.  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  _Neural networks_ , 6(6):861–867, 1993.
  * Wang et al. [2022] Zi Wang, Aws Albarghouthi, Gautam Prakriya, and Somesh Jha.  Interval universal approximation for neural networks.  _Proceedings of the ACM on Programming Languages_ , 6(POPL):1–29, 2022.
  * Lu and Lu [2020] Yulong Lu and Jianfeng Lu.  A universal approximation theorem of deep neural networks for expressing probability distributions.  _Advances in neural information processing systems_ , 33:3094–3105, 2020.
  * Yarotsky [2022] Dmitry Yarotsky.  Universal approximations of invariant maps by neural networks.  _Constructive Approximation_ , 55(1):407–474, 2022.
  * Wang et al. [2019] Puyu Wang, Na Deng, Xiao-Ping Zhang, and Ningqiang Jiang.  Parametric analysis and optimization of a dc current flow controller in meshed mtdc grids.  _IEEE Access_ , 7:87960–87976, 2019.
  * Motee et al. [2012] Nader Motee, Bassam Bamieh, and Mustafa Khammash.  Stability analysis of quasi-polynomial dynamical systems with applications to biological network models.  _Automatica_ , 48(11):2945–2950, 2012.
  * Bubnicki [2005] Zdzislaw Bubnicki.  _Modern control theory_ , volume 2005925392.  Springer, 2005.
  * Berge [1963] C. Berge.  Espaces topologiques (translated by patterson, em): Topological spaces.  _Oliver and Boyd_ , 1963.
  * Robinson and Day [1974] S. M. Robinson and R. H. Day.  A sufficient condition for continuity of optimal sets in mathematical programming.  _Journal of Mathematical Analysis and Applications_ , 45(2):506–511, 1974.
  * Zhao [1997] J. Zhao.  The lower semicontinuity of optimal solution sets.  _Journal of Mathematical Analysis and Applications_ , 207(1):240–254, 1997.
  * Kien* [2005] B. T. Kien*.  On the lower semicontinuity of optimal solution sets.  _Optimization_ , 54(2):123–130, 2005.
  * Böhm [1975] V. Böhm.  On the continuity of the optimal policy set for linear programs.  _SIAM Journal on Applied Mathematics_ , 28(2):303–306, 1975.
  * Wets [1985] R. J. B. Wets.  On the continuity of the value of a linear program and of related polyhedral-valued multifunctions.  In _Mathematical Programming Essays in Honor of George B. Dantzig Part I_ , pages 14–29. Springer, 1985.
  * Zhang and Liu [1990] X. S. Zhang and D. G. Liu.  A note on the continuity of solutions of parametric linear programs.  _Mathematical Programming_ , 47(1):143–153, 1990\.
  * Lee et al. [2006] G. M. Lee, N. N. Tam, and N. D. Yen.  Continuity of the solution map in quadratic programs under linear perturbations.  _Journal of optimization theory and applications_ , 129(3):415–423, 2006.
  * Terazono and A. Matani [2015] Y. Terazono and Ayumu A. Matani.  Continuity of optimal solution functions and their conditions on objective functions.  _SIAM Journal on Optimization_ , 25(4):2050–2060, 2015.
  * Walker [1979] M. Walker.  A generalization of the maximum theorem.  _International Economic Review_ , pages 267–272, 1979.
  * Leininger [1984] W. Leininger.  A generalization of the ‘maximum theorem’.  _Economics Letters_ , 15(3-4):309–313, 1984.
  * Ausubel and Deneckere [1993] L. M. Ausubel and R. J. Deneckere.  A generalized theorem of the maximum.  _Economic Theory_ , 3(1):99–107, 1993.
  * Wright and Recht [2022] Stephen J Wright and Benjamin Recht.  _Optimization for data analysis_.  Cambridge University Press, 2022.
  * Boyd and Vandenberghe [2004] Stephen P Boyd and Lieven Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Sra et al. [2012] Suvrit Sra, Sebastian Nowozin, and Stephen J Wright.  _Optimization for machine learning_.  Mit Press, 2012.
  * Lillicrap et al. [2015] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Mnih et al. [2015] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Vinyals et al. [2015] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Dai et al. [2017] H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song.  Learning combinatorial optimization algorithms over graphs.  _arXiv preprint arXiv:1704.01665_ , 2017.
  * Li and Malik [2016] Ke Li and Jitendra Malik.  Learning to optimize.  _arXiv preprint arXiv:1606.01885_ , 2016.
  * Donti et al. [2017] Priya Donti, Brandon Amos, and J Zico Kolter.  Task-based end-to-end model learning in stochastic optimization.  _Advances in neural information processing systems_ , 30, 2017.
  * Li et al. [2018] Z. Li, Q. Chen, and V. Koltun.  Combinatorial optimization with graph convolutional networks and guided tree search.  _arXiv preprint arXiv:1810.10659_ , 2018.
  * Agrawal et al. [2020] A. Agrawal, S. Barratt, S. Boyd, and B. Stellato.  Learning convex optimization control policies.  In _Learning for Dynamics and Control_ , pages 361–373. PMLR, 2020\.
  * Misra et al. [2021] S. Misra, L. Roald, and Y. Ng.  Learning for constrained optimization: Identifying optimal active constraint sets.  _INFORMS Journal on Computing_ , 2021.
  * Bertsimas and Stellato [2019] D. Bertsimas and B. Stellato.  Online mixed-integer optimization in milliseconds.  _arXiv preprint arXiv:1907.02206_ , 2019.
  * Bae et al. [2023] Hyunglip Bae, Jinkyu Lee, Woo Chang Kim, and Yongjae Lee.  Deep value function networks for large-scale multistage stochastic programs.  In _International Conference on Artificial Intelligence and Statistics_ , pages 11267–11287. PMLR, 2023.
  * Dai et al. [2021] Hanjun Dai, Yuan Xue, Zia Syed, Dale Schuurmans, and Bo Dai.  Neural stochastic dual dynamic programming.  _arXiv preprint arXiv:2112.00874_ , 2021.
  * Dumouchelle et al. [2022] Justin Dumouchelle, Rahul Patel, Elias B Khalil, and Merve Bodur.  Neur2sp: Neural two-stage stochastic programming.  _arXiv preprint arXiv:2205.12006_ , 2022.
  * Kim et al. [2023] Chanyeong Kim, Jongwoong Park, Hyunglip Bae, and Woo Chang Kim.  Transformer-based stagewise decomposition for large-scale multistage stochastic optimization.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 16747–16770. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/kim23r.html.
  * Hausdorff [2021] F. Hausdorff.  _Set theory_ , volume 119.  American Mathematical Soc., 2021.
  * Hogan [1973] W. W. Hogan.  Point-to-set maps in mathematical programming.  _SIAM review_ , 15(3):591–603, 1973.
  * Michael [1956] E. Michael.  Continuous selections. i.  _Annals of mathematics_ , pages 361–382, 1956.
  * Lee and Santos [2017] C. W. Lee and F. Santos.  Subdivisions and triangulations of polytopes.  In _Handbook of discrete and computational geometry_ , pages 415–447. Chapman and Hall/CRC, 2017.
  * Sturmfels [1991] B. Sturmfels.  Grobner bases of toric varieties.  _Tohoku Mathematical Journal, Second Series_ , 43(2):249–261, 1991.
  * Danninger-Uchida [2009] G. E. Danninger-Uchida.  _Carathéodory theorem_ , pages 358–359.  Springer US, Boston, MA, 2009.  ISBN 978-0-387-74759-0.  URL https://doi.org/10.1007/978-0-387-74759-0_64.
  * Shultzman et al. [2023] Avner Shultzman, Eyar Azar, Miguel RD Rodrigues, and Yonina C Eldar.  Generalization and estimation error bounds for model-based neural networks.  _arXiv preprint arXiv:2304.09802_ , 2023.
  * Wang and Sun [2005] S. Wang and X. Sun.  Generalization of hinging hyperplanes.  _IEEE Transactions on Information Theory_ , 51(12):4425–4431, 2005.
  * Arora et al. [2016] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee.  Understanding deep neural networks with rectified linear units.  _arXiv preprint arXiv:1611.01491_ , 2016.
  * Kahn et al. [2017] G. Kahn, T. Zhang, S. Levine, and P. Abbeel.  Plato: Policy learning using adaptive trajectory optimization.  In _2017 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 3342–3349. IEEE, 2017.
  * Julian and Kochenderfer [2017] K. D. Julian and M. J. Kochenderfer.  Neural network guidance for uavs.  In _AIAA Guidance, Navigation, and Control Conference_ , page 1743, 2017.
  * Arévalo et al. [2016] A. Arévalo, J. Niño, G. Hernández, and J. Sandoval.  High-frequency trading strategy based on deep neural networks.  In _International conference on intelligent computing_ , pages 424–436. Springer, 2016.
  * Dutta et al. [2018] S. Dutta, S. Jha, Sriram Sankaranarayanan, and Ashish Tiwari.  Output range analysis for deep feedforward neural networks.  In _NASA Formal Methods Symposium_ , pages 121–138. Springer, 2018\.
  * Papageorgiou [1997] S. H. N. Papageorgiou.  Handbook of multivalued analysis. volume i: Theory.  _Mathematics and Its Applications_ , 419, 1997.