# Compensating Data Shortages in Manufacturing with Monotonicity Knowledge
## 2 Semi-Infinite Optimization Approach to Monotonic Regression
### Adaptive Solution Strategy  
Since the feasible set of (9) is compact (by the finiteness of the parameter \(r\) in (5)) and non-empty (it contains \(\mathbf{w}:=0\in\mathbb{R}^{N_{m}}\)), the monotonic regression problem (9) has a solution by virtue of the Weierstrass extreme-value theorem. In order to compute such a solution of (9), a variant of the adaptive, iterative discretization algorithm by [39] is used. In a nutshell, the idea is the following: the infinite index set \(X\) of the original regression problem (9) is iteratively replaced by discretizations, that is, finite subsets \(X^{k}\subset X\), and these discretizations are adaptively refined from iteration to iteration. In that manner, in every iteration \(k\) one obtains the ordinary (finite) optimization problem  
\[\min_{\mathbf{w}\in W}f(\mathbf{w})\quad\text{s.t.}\quad g_{j}(\mathbf{w},\mathbf{x})\geq 0 \quad\text{for all $j\in J$ and $\mathbf{x}\in X^{k}$} \tag{11}\]  
featuring only finitely many inequality constraints. As usual, we refer to (11) as the \(k\)th discretized problem. In each iteration \(k\), two steps are performed, namely, an optimization step and an adaptive refinement step. In the optimization step, a solution \(\mathbf{w}^{k}\) of the \(k\)th discretized problem (11) is computed. In the refinement step, for each direction \(j\in J\), a point \(\mathbf{x}^{k,j}\in X\) is computed at which the \(j\)th monotonicity constraint at \(\mathbf{w}=\mathbf{w}^{k}\) is violated most. In more precise terms, for every \(j\in J\), an approximate solution \(\mathbf{x}^{k,j}\) of the global optimization problem  
\[\min_{\mathbf{x}\in X}g_{j}(\mathbf{w}^{k},\mathbf{x}) \tag{12}\]  
is computed. All the points \(\mathbf{x}^{k,j}\) for which a monotonicity violation occurs are then added to the current discretization \(X^{k}\) in order to obtain the new discretization \(X^{k+1}\). If no more monotonicity violations occur, the iteration is stopped. As usual, (12) is referred to as the \((k,j)\)th lower-level problem in the following.  
With regard to the practical implementation of the above solution strategy, it is important to observe that the discretized problems (11) are standard convex quadratic programs [40]. Indeed, by inserting (3) into (8) and using the design matrix \(\Phi\) with entries \(\Phi_{li}:=\phi_{i}(\mathbf{x}_{l})\), one obtains  
\[f(\mathbf{w})=\frac{1}{2}\|\Phi\mathbf{w}-\mathbf{t}\|_{2}^{2}=\frac{1}{2}\mathbf{w}^{\top} \Phi^{\top}\Phi\mathbf{w}-\mathbf{t}^{\top}\Phi\mathbf{w}+\frac{1}{2}\mathbf{t}^{\top}\mathbf{t}.\]  
Consequently, the objective function of (11) is indeed quadratic and convex with respect to \(\mathbf{w}\). It is not strictly convex, though, in the sparse-data case \(N<N_{m}\) considered in this paper. (Indeed, the kernel of the matrix \(\Phi^{\top}\Phi\in\mathbb{R}^{N_{m}\times N_{m}}\) is equal to the kernel of \(\Phi\in\mathbb{R}^{N\times N_{m}}\), and an \(N\times N_{m}\) matrix with \(N<N_{m}\) has a non-trivial kernel, of course.) Also, in view of  
\[g_{j}(\mathbf{w},\mathbf{x})=\sigma_{j}\cdot\partial_{x_{j}}\hat{y}_{\mathbf{w}}(\mathbf{x})= \sigma_{j}\cdot\mathbf{w}^{\top}\big{(}\partial_{x_{j}}\mathbf{\phi}(\mathbf{x})\big{)}, \tag{13}\]  
the constraints of (11) are indeed linear with respect to \(\mathbf{w}\).  
With regard to the practical implementation, it is also important to observe that the objective functions \(\mathbf{x}\mapsto g_{j}(\mathbf{w}^{k},\mathbf{x})\) of the lower-level problems (12) are non-convex polynomials and therefore in general have several local minima. Consequently, (12) needs to be solved numerically with a global optimization solver.