A new analytical envelope
for multivariate global optimizationThanks: ^∗Faculty of Natural and Life Sciences, University of Batna 2, Batna City, Algeria, e-mail: d.aaid@univ-batna2.dz, ORCID: https://orcid.org/0000-0002-2426-2959

Abstract.

We propose a new global optimization method that combines an $\alpha$–dense univariate reduction with explicitly constructed analytical envelopes: a piecewise concave underestimator (PCU) and a piecewise convex overestimator (PCO). By leveraging interval-based curvature bounds, the method provides rigorous global optimality certificates. An adaptive branch-and-bound strategy ensures rapid convergence by refining intervals based on theoretical envelope widths. Numerical experiments on challenging nonconvex and multimodal benchmarks demonstrate strong performance and efficiency.

1. Introduction

Deterministic global optimization remains a central topic in numerical analysis and applied mathematics, with a wide range of applications across science and engineering. Foundational monographs such as Floudas [7] and Locatelli–Schoen [11] provide comprehensive overviews of key approaches, including spatial branch-and-bound, interval methods, Lipschitz-based schemes, and convex or concave relaxations. Despite these advances, obtaining tight global bounds for nonconvex problems in moderate to high dimensions remains a major challenge in the field.

A particularly influential class of relaxations is based on convex underestimation. The $\alpha$BB method developed by Adjiman, Androulakis, and Floudas [4, 5] constructs a convex quadratic lower bound by augmenting the Hessian with diagonal shifts. This paradigm has since been extended through more refined DC relaxations, including recent developments by Strahl, Raghunathan, and Sahinidis [16]. Other underestimation techniques include the DCU method for univariate optimization introduced by Chang, Park, and Lee [6], as well as the convex quadratic relaxations of Le Thi and Ouanes [10]. A broader survey of convex underestimation methods is available in Skjäl [15].

Interval-based global optimization techniques also play a crucial role, particularly for their ability to provide rigorous bounds. Notable examples include the classical one-dimensional algorithm by Sergeyev [13], geometric Lipschitz-based methods by Kvasov and Sergeyev [9], and the homogeneity framework proposed by Sergeyev, Kvasov, and Mukhametzhanov [14]. More recent strategies include the Lipschitz global optimization methods of Malherbe and Vayatis [12] and the constrained Lipschitz-gradient approach of Vinod, Israel, and Topcu [17]. For a comprehensive overview, see the tutorial by Horst [18].

Another direction of research focuses on reducing multivariate problems to univariate ones. Meta-algorithmic frameworks following this idea were recently studied by Gökçesu and Gökçesu [8]. Earlier work by Aaid and collaborators developed constructive transformations for dimensionality reduction, enabling global optimization in the univariate setting [2, 3]. These transformations generate an $\alpha$–dense curve through the domain, aiming to ensure that the global minimizer of the original multivariate function is well approximated by that of the corresponding one-dimensional surrogate.

Building on this reduction approach, the present work introduces a new analytical framework for univariate global optimization. Specifically, we construct a piecewise concave underestimator (PCU) and a piecewise convex overestimator (PCO), both derived explicitly from interval bounds on the second derivative of the reduced function. These constructions yield a pair of rigorous analytical envelopes satisfying

$$\mathrm{PCU}(t)\le F(t)\le \mathrm{PCO}(t),\text{for all }t,$$

with computable curvature parameters. When combined with an adaptive branch-and-bound scheme that refines the interval exhibiting the largest theoretical envelope gap, the method produces rapidly shrinking global bounds and provable optimality gaps.

The main contributions of this article are as follows:

• We derive explicit PCU and PCO envelopes from interval curvature bounds, providing rigorous concave and convex relaxations.

• We integrate these envelopes with the $\alpha$–dense dimension-reduction transformation of Aaid [2, 3], resulting in a fully certified univariate representation of multivariate problems.

• We introduce an adaptive refinement strategy that targets the interval with the largest theoretical envelope width, accelerating convergence.

• Our numerical experiments show that the method performs well on various challenging benchmark problems, including those with moderate to high dimensions, especially when the reduction and subdivision settings are chosen carefully.

It is important to note that the efficiency of the proposed framework depends on how the reduction parameters are chosen especially the density parameter $\alpha$ and the frequency sequence. Also, the univariate reduction does not remove the inherent complexity of the original multivariate problem.

The remainder of the paper is organized as follows. Section 2 presents the dimension reduction framework. Section 3 introduces analytical envelopes. Section 4 describes the adaptive branch-and-bound algorithm. Section 5 provides numerical experiments and comparisons with existing global optimization methods. Section 6 concludes with directions for future research.

2. Preliminaries

We consider the global optimization problem

$$\underset{x\in X}{\min }f(x),X:=\prod _{i=1}^n[a_i,b_i]\subset {ℝ}^n,$$

where the objective function $f:X\to ℝ$ is assumed to be twice continuously differentiable.

2.1. Reductive Transformation via $\alpha$–Dense Curves

Following the framework introduced in [2, 3], we consider a one-dimensional parametric curve $x:[0,{\theta }_{\max }]\to X$ defined by

$$x(\theta )=(x_1(\theta ),\mathrm{\dots },x_n(\theta )),x_i(\theta )=\frac{1}{2}\left[(b_i-a_i)\cos ({\omega }_i\theta +{\phi }_i)+(b_i+a_i)\right],$$

where ${({\omega }_i)}_{i=1}^n$ and ${({\phi }_i)}_{i=1}^n$ are frequency and phase parameters chosen to control the geometry of the curve. Since $\cos ({\omega }_i\theta +{\phi }_i)\in [-1,1]$, it follows that $x(\theta )\in X$ for all $\theta \in [0,{\theta }_{\max }]$.

We denote by

$$\mathrm{\Gamma }:=x([0,{\theta }_{\max }])\subset X$$

the image (or trace) of the curve, and define the corresponding univariate surrogate objective as

(1) $$F(\theta ):=f(x(\theta )),\theta \in [0,{\theta }_{\max }].$$

Clearly, if ${\theta }^{\star }$ is a (global) minimizer of $F$, then $x({\theta }^{\star })$ is a candidate global minimizer of $f$ over $X$.

2.2. $\alpha$–Dense Curves and Reduction Error

Definition .

A set $S\subset X$ is said to be $\alpha$–dense in $X$ if for every $z\in X$, there exists $y\in S$ such that

$$\Vert z-y\Vert \le \alpha .$$

In particular, we say that the curve $\mathrm{\Gamma }$ is $\alpha$-dense in $X$ if it satisfies this property.

The key idea behind this construction is that, for appropriate choices of ${\omega }_i$, ${\phi }_i$, and ${\theta }_{\max }$, the curve $\mathrm{\Gamma }$ can be made $\alpha$-dense in $X$. As a result, minimizing the reduced function $F$ over the interval $[0,{\theta }_{\max }]$ gives a good approximation of the original optimization problem over $X$, with the accuracy directly influenced by the selected density parameter $\alpha$.

Theorem 1 (Reduction Error Bound).

Assume that $\mathrm{\Gamma }$ is $\alpha$-dense in $X$, and that $f$ is Lipschitz continuous on $X$ with Lipschitz constant $L_f>0$. Define

$$m_X:=\underset{x\in X}{\min }f(x),m_{\mathrm{\Gamma }}:=\underset{\theta \in [0,{\theta }_{\max }]}{\min }F(\theta ).$$

Then the reduction error satisfies the bound

(2) $$|m_X-m_{\mathrm{\Gamma }}|\le L_f\alpha .$$

The accuracy of the reduced formulation is directly influenced by the density parameter $\alpha$. Smaller values of $\alpha$ improve the approximation of the original problem but may increase the complexity of the reduced one, due to a larger required range for $\theta$ and increased oscillations of the curve $\mathrm{\Gamma }$. In particular, ensuring $\alpha$-density may demand a large ${\theta }_{\max }$, depending on the dimension and frequency sequence.

Thus, the univariate reduction shifts rather than removes the original problem’s complexity. The method’s efficiency depends on balancing approximation accuracy and computational cost. We now focus on deriving tight bounds for $F$ on $[0,{\theta }_{\max }]$ and integrating them into a branch-and-bound framework.

Choice of the density parameter $\alpha$.

The parameter $\alpha$ controls the approximation quality of the reduction. By Theorem 1, the error is bounded by $L_f\alpha$. If $L_f$ is unknown, it can be estimated via interval gradients or $\alpha$ can be adjusted empirically.

Smaller $\alpha$ improves accuracy but increases computational cost due to larger ${\theta }_{\max }$ and curvature. A balance must be struck between precision and efficiency.

3. Materials and Methods

3.1. Local Construction of a PCU Bound on an Interval

Let $F:[\alpha ,\beta ]\to ℝ$ be twice continuously differentiable. Consider a partition

and fix an interval

$$I_i:=[t_i,t_{i+1}],h_i:=t_{i+1}-t_i>0.$$

Define the linear shape functions on $I_i$:

$${\mathrm{\ell }}_{i,0}(t):=\frac{t_{i+1}-t}{h_i},{\mathrm{\ell }}_{i,1}(t):=\frac{t-t_i}{h_i},t\in I_i,$$

and the linear interpolant

$$L_{i}F(t):={\mathrm{\ell }}_{i,0}(t)F(t_i)+{\mathrm{\ell }}_{i,1}(t)F(t_{i+1}),t\in I_i.$$

Assume that we know a lower curvature bound on $I_i$, namely

$$F^{\prime \prime }(t)\ge m_i,\forall t\in I_i,$$

for some real constant $m_i\le 0$ (possibly negative). We define the local PCU (Piecewise Concave Underestimator) on $I_i$ by

(3) $${\mathrm{PCU}}_i(t):=L_{i}F(t)+\frac{m_i}{2}(t-t_i)(t_{i+1}-t),t\in I_i.$$

Theorem 2 (Local Concave PCU Bound).

Assume $F\in C^2([\alpha ,\beta ])$ and

$$F^{\prime \prime }(t)\ge m_i,\forall t\in I_i,$$

with $m_i\le 0$. Then, for every $t\in I_i$,

1. ${\mathrm{PCU}}_i(t)\le F(t)$  (valid lower bound),

2. ${\mathrm{PCU}}_i$ is concave on $I_i$, i.e.

   $${\mathrm{PCU}}_i^{\prime \prime }(t)\le 0,\forall t\in I_i.$$

Proof.

1) Valid lower bound. Let

$$E_i(t):=F(t)-L_{i}F(t).$$

By the standard interpolation error formula, for each $t\in I_i$ there exists $\xi (t)\in I_i$ such that

$$E_i(t)=\frac{F^{\prime \prime }(\xi (t))}{2}(t-t_i)(t_{i+1}-t).$$

Since $(t-t_i)(t_{i+1}-t)\ge 0$ on $I_i$ and $F^{\prime \prime }(\xi (t))\ge m_i$, we obtain

$$E_i(t)=\frac{F^{\prime \prime }(\xi (t))}{2}(t-t_i)(t_{i+1}-t)\ge \frac{m_i}{2}(t-t_i)(t_{i+1}-t).$$

Thus

$$F(t)-L_{i}F(t)\ge \frac{m_i}{2}(t-t_i)(t_{i+1}-t),$$

which can be rewritten as

$$L_{i}F(t)+\frac{m_i}{2}(t-t_i)(t_{i+1}-t)\le F(t).$$

By definition from Equation 3, the left-hand side is ${\mathrm{PCU}}_i(t)$, hence

$${\mathrm{PCU}}_i(t)\le F(t),\forall t\in I_i.$$

2) Concavity. Since $L_{i}F$ is affine on $I_i$, ${(L_{i}F)}^{\prime \prime }(t)=0$. We have

$$(t-t_i)(t_{i+1}-t)=-(t^2)+(t_i+t_{i+1})t-t_i{t}_{i+1},$$

so

$$\frac{d^2}{d{t}^2}(t-t_i)(t_{i+1}-t)=-2.$$

Therefore

$$\frac{d^2}{d{t}^2}\left[\frac{m_i}{2}(t-t_i)(t_{i+1}-t)\right]=\frac{m_i}{2}\cdot (-2)=m_i.$$

Hence

$${\mathrm{PCU}}_i^{\prime \prime }(t)={(L_{i}F)}^{\prime \prime }(t)+m_i=0+m_i=m_i\le 0,$$

which proves that ${\mathrm{PCU}}_i$ is concave on $I_i$. ∎

3.2. Global Piecewise Concave Underestimator

Let

be a partition of $[\alpha ,\beta ]$. On each interval $I_i=[t_i,t_{i+1}]$, the local PCU_i is defined as in  Theorem 2:

$${\mathrm{PCU}}_i(t)=L_{i}F(t)+\frac{m_i}{2}(t-t_i)(t_{i+1}-t),t\in I_i,$$

where $m_i\le 0$ satisfies

$$F^{\prime \prime }(t)\ge m_i,\forall t\in I_i.$$

We define the global PCU on $[\alpha ,\beta ]$ by

$$\mathrm{PCU}(t):={\mathrm{PCU}}_i(t),t\in [t_i,t_{i+1}],i=0,\mathrm{\dots },M-1.$$

Theorem 3 (Global PCU Properties).

Under the above assumptions, the global function $\mathrm{PCU}$ satisfies:

1. (Global lower bound)

   $$\mathrm{PCU}(t)\le F(t),\forall t\in [\alpha ,\beta ].$$

2. (Interpolation at the nodes)

   $$\mathrm{PCU}(t_i)=F(t_i),i=0,\mathrm{\dots },M.$$

3. (Continuity and piecewise concavity) $\mathrm{PCU}$ is continuous on $[\alpha ,\beta ]$ and $\mathrm{PCU}{}_{|I{}_i}$ is concave on each interval $I_i=[t_i,t_{i+1}]$.

Proof.

For $t\in I_i$, Theorem 2 yields

$${\mathrm{PCU}}_i(t)\le F(t).$$

By the definition of the global PCU, $\mathrm{PCU}(t)={\mathrm{PCU}}_i(t)$ for $t\in I_i$, hence

$$\mathrm{PCU}(t)\le F(t),\forall t\in [\alpha ,\beta ].$$

At the endpoints of $I_i$ we have

$${\mathrm{PCU}}_i(t_i)=L_{i}F(t_i)+\frac{m_i}{2}(t_i-t_i)(t_{i+1}-t_i)=F(t_i),$$

and

$${\mathrm{PCU}}_i(t_{i+1})=L_{i}F(t_{i+1})+\frac{m_i}{2}(t_{i+1}-t_i)(t_{i+1}-t_{i+1})=F(t_{i+1}),$$

because the quadratic term vanishes at $t=t_i$ and $t=t_{i+1}$ and $L_{i}F$ interpolates $F$ at the nodes. In particular, for $1\le k\le M-1$,

$${\mathrm{PCU}}_{k-1}(t_k)=F(t_k)={\mathrm{PCU}}_k(t_k),$$

so the left and right pieces coincide at every interior node.

From (2), the left and right limits of $\mathrm{PCU}$ at each node $t_i$ coincide and are equal to $F(t_i)$, so $\mathrm{PCU}$ is continuous on $[\alpha ,\beta ]$. On each subinterval $I_i$, we have $\mathrm{PCU}(t)={\mathrm{PCU}}_i(t)$ and  Theorem 2 gives

$${\mathrm{PCU}}_i^{\prime \prime }(t)=m_i\le 0,$$

hence $\mathrm{PCU}$ is concave on each $I_i$. ∎

3.3. Local Construction of a PCO Bound on an Interval

We keep the same setting as in the local PCU construction. Let $F:[\alpha ,\beta ]\to ℝ$ be twice continuously differentiable, and consider an interval

$$I_i:=[t_i,t_{i+1}],h_i:=t_{i+1}-t_i>0.$$

The linear interpolant of $F$ on $I_i$ is

$$L_{i}F(t):={\mathrm{\ell }}_{i,0}(t)F(t_i)+{\mathrm{\ell }}_{i,1}(t)F(t_{i+1}),t\in I_i,$$

where

$${\mathrm{\ell }}_{i,0}(t):=\frac{t_{i+1}-t}{h_i},{\mathrm{\ell }}_{i,1}(t):=\frac{t-t_i}{h_i}.$$

Assume that there exists $K_i>0$ such that

$$|F^{\prime \prime }(t)|\le K_i,\forall t\in I_i.$$

We define the local PCO (Piecewise Convex Overestimator) on $I_i$ by

$${\mathrm{PCO}}_i(t):=L_{i}F(t)+{\delta }_i,t\in I_i,$$

where

$${\delta }_i:=\frac{K_i}{8}{h}_i^2.$$

Theorem 4 (Local PCO Bound).

Assume $F\in C^2([\alpha ,\beta ])$ and $|F^{\prime \prime }(t)|\le K_i$ on $I_i$. Then, for every $t\in I_i$,

1. ${\mathrm{PCO}}_i(t)\ge F(t)$  (valid upper bound),

2. ${\mathrm{PCO}}_i$ is convex on $I_i$.

Proof.

Let

$$E_i(t):=F(t)-L_{i}F(t).$$

As in the proof of  Theorem 2, there exists $\xi (t)\in I_i$ such that

$$E_i(t)=\frac{F^{\prime \prime }(\xi (t))}{2}(t-t_i)(t_{i+1}-t).$$

Hence

$$|E_i(t)|\le \frac{|F^{\prime \prime }(\xi (t))|}{2}(t-t_i)(t_{i+1}-t)\le \frac{K_i}{2}(t-t_i)(t_{i+1}-t).$$

The quadratic term $(t-t_i)(t_{i+1}-t)$ attains its maximum at the midpoint $t=(t_i+t_{i+1})/2$, with value

$$\underset{t\in I_i}{\max }(t-t_i)(t_{i+1}-t)=\frac{h_i^2}{4}.$$

Therefore

$$|E_i(t)|\le \frac{K_i}{2}\cdot \frac{h_i^2}{4}=\frac{K_i}{8}{h}_i^2={\delta }_i,\forall t\in I_i.$$

In particular,

$$F(t)\le L_{i}F(t)+{\delta }_i={\mathrm{PCO}}_i(t),\forall t\in I_i,$$

which proves that ${\mathrm{PCO}}_i$ is a valid upper bound on $I_i$.

For convexity, note that $L_{i}F$ is affine on $I_i$ and ${\delta }_i$ is a constant shift. Thus ${\mathrm{PCO}}_i$ is affine on $I_i$, hence convex. ∎

3.4. Global Piecewise Convex Overestimator

Let

be a partition of $[\alpha ,\beta ]$. On each interval $I_i=[t_i,t_{i+1}]$, the local PCO_i is defined as in  Theorem 4:

$${\mathrm{PCO}}_i(t)=L_{i}F(t)+{\delta }_i,{\delta }_i=\frac{K_i}{8}{h}_i^2,h_i=t_{i+1}-t_i.$$

We define the global PCO on $[\alpha ,\beta ]$ by

$$\mathrm{PCO}(t):={\mathrm{PCO}}_i(t),t\in [t_i,t_{i+1}],i=0,\mathrm{\dots },M-1.$$

Theorem 5 (Global PCO Properties).

Assume $F\in C^2([\alpha ,\beta ])$ and, for each $i$, there exists $K_i>0$ such that

$$|F^{\prime \prime }(t)|\le K_i,\forall t\in [t_i,t_{i+1}].$$

Then the global function $\mathrm{PCO}$ satisfies:

1. (Global upper bound)

   $$F(t)\le \mathrm{PCO}(t),\forall t\in [\alpha ,\beta ].$$

2. (Continuity at the nodes) If the constants ${\delta }_i$ are chosen such that

   $${\delta }_0=0,L_{i}F(t_{i+1})+{\delta }_i=L_{i+1}F(t_{i+1})+{\delta }_{i+1}\text{for }i=0,\mathrm{\dots },M-2,$$

   then

   $$\mathrm{PCO}(t_i)=F(t_i)+{\delta }_i,i=0,\mathrm{\dots },M,$$

   and $\mathrm{PCO}$ is continuous on $[\alpha ,\beta ]$.

3. (Piecewise convexity) On each subinterval $I_i$, the restriction $\mathrm{PCO}{}_{|I{}_i}$ is convex.

Proof.

On each $I_i$,  Theorem 4 yields

$$F(t)\le {\mathrm{PCO}}_i(t),\forall t\in I_i.$$

By definition of the global $\mathrm{PCO}$, we have $\mathrm{PCO}(t)={\mathrm{PCO}}_i(t)$ for $t\in I_i$, hence

$$F(t)\le \mathrm{PCO}(t),\forall t\in [\alpha ,\beta ].$$

At each node $t_i$, we have

$${\mathrm{PCO}}_i(t_i)=L_{i}F(t_i)+{\delta }_i=F(t_i)+{\delta }_i,$$

and similarly

$${\mathrm{PCO}}_{i-1}(t_i)=F(t_i)+{\delta }_{i-1},$$

with the convention that $i-1$ is only valid for $i\ge 1$. If the constants ${\delta }_i$ are chosen so that

$$L_{i}F(t_i)+{\delta }_i=L_{i-1}F(t_i)+{\delta }_{i-1},$$

then the left and right limits of $\mathrm{PCO}$ coincide at each node $t_i$, making $\mathrm{PCO}$ continuous on $[\alpha ,\beta ]$. In particular, if we impose ${\delta }_0=0$ and the recursion

$$L_{i}F(t_i)+{\delta }_i=L_{i-1}F(t_i)+{\delta }_{i-1},$$

we obtain $\mathrm{PCO}(t_0)=F(t_0)$ and

$$\mathrm{PCO}(t_i)=F(t_i)+{\delta }_i,i=1,\mathrm{\dots },M.$$

For each $i$, the function ${\mathrm{PCO}}_i$ is affine on $I_i$ (as $L_{i}F$ is affine and ${\delta }_i$ is constant), hence convex. Thus on each $I_i$, the restriction $\mathrm{PCO}{}_{|I{}_i}$ is convex, which proves that $\mathrm{PCO}$ is piecewise convex on $[\alpha ,\beta ]$. ∎

3.5. Bilateral PCU–PCO Envelope and Gap Estimate

Assume $F\in C^2([\alpha ,\beta ])$ and a partition

On each $I_i$, suppose that

$$m_i\le F^{\prime \prime }(t)\le K_i,\forall t\in I_i,$$

with $m_i\le 0$ and $K_i\ge 0$.

The local PCU and PCO are

$${\mathrm{PCU}}_i(t):=L_{i}F(t)+\frac{m_i}{2}(t-t_i)(t_{i+1}-t),t\in I_i,$$

$${\mathrm{PCO}}_i(t):=L_{i}F(t)+{\delta }_i,{\delta }_i:=\frac{K_i}{8}{h}_i^2,t\in I_i,$$

and the global PCU, PCO are defined by

$$\mathrm{PCU}(t):={\mathrm{PCU}}_i(t),\mathrm{PCO}(t):={\mathrm{PCO}}_i(t),t\in I_i,i=0,\mathrm{\dots },M-1.$$

Theorem 6 (Bilateral Envelope and Local Gap).

Under the above assumptions, one has:

1. For all $t\in [\alpha ,\beta ]$,

   $$\mathrm{PCU}(t)\le F(t)\le \mathrm{PCO}(t).$$

2. For every $i=0,\mathrm{\dots },M-1$ and all $t\in I_i$,

   $$0\le \mathrm{PCO}(t)-\mathrm{PCU}(t)\le \frac{K_i-m_i}{8}{h}_i^2.$$

Proof.

Fix $i$ and $t\in I_i$.

1) Bilateral bounds.

Define the interpolation error

$$E_i(t):=F(t)-L_{i}F(t).$$

There exists $\xi (t)\in I_i$ such that

$$E_i(t)=\frac{F^{\prime \prime }(\xi (t))}{2}(t-t_i)(t_{i+1}-t).$$

Since $t\in I_i$,

$$(t-t_i)(t_{i+1}-t)\ge 0.$$

From $F^{\prime \prime }(\xi (t))\ge m_i$,

$$E_i(t)=\frac{F^{\prime \prime }(\xi (t))}{2}(t-t_i)(t_{i+1}-t)\ge \frac{m_i}{2}(t-t_i)(t_{i+1}-t),$$

so

$$F(t)-L_{i}F(t)\ge \frac{m_i}{2}(t-t_i)(t_{i+1}-t),$$

i.e.

$$L_{i}F(t)+\frac{m_i}{2}(t-t_i)(t_{i+1}-t)\le F(t).$$

By definition of ${\mathrm{PCU}}_i$,

$${\mathrm{PCU}}_i(t)\le F(t).$$

From $F^{\prime \prime }(\xi (t))\le K_i$,

$$E_i(t)=\frac{F^{\prime \prime }(\xi (t))}{2}(t-t_i)(t_{i+1}-t)\le \frac{K_i}{2}(t-t_i)(t_{i+1}-t).$$

Moreover,

$$0\le (t-t_i)(t_{i+1}-t)\le \frac{h_i^2}{4},$$

so

$$E_i(t)\le \frac{K_i}{2}\cdot \frac{h_i^2}{4}=\frac{K_i}{8}{h}_i^2={\delta }_i.$$

Thus

$$F(t)-L_{i}F(t)\le {\delta }_i,$$

i.e.

$$F(t)\le L_{i}F(t)+{\delta }_i={\mathrm{PCO}}_i(t).$$

Therefore, on $I_i$,

$${\mathrm{PCU}}_i(t)\le F(t)\le {\mathrm{PCO}}_i(t).$$

By the global definition of PCU and PCO on $[\alpha ,\beta ]$, this yields

$$\mathrm{PCU}(t)\le F(t)\le \mathrm{PCO}(t),\forall t\in [\alpha ,\beta ].$$

2) Local gap estimate.

For $t\in I_i$, we have

$${\mathrm{PCO}}_i(t)-{\mathrm{PCU}}_i(t)=\left(L_{i}F(t)+{\delta }_i\right)-\left(L_{i}F(t)+\frac{m_i}{2}(t-t_i)(t_{i+1}-t)\right)={\delta }_i-\frac{m_i}{2}(t-t_i)(t_{i+1}-t).$$

Since $(t-t_i)(t_{i+1}-t)\ge 0$ and $m_i\le 0$, it follows that

$$-\frac{m_i}{2}(t-t_i)(t_{i+1}-t)\ge 0,$$

and therefore

$${\mathrm{PCO}}_i(t)-{\mathrm{PCU}}_i(t)\ge {\delta }_i\ge 0.$$

Moreover,

$$(t-t_i)(t_{i+1}-t)\le \frac{h_i^2}{4},$$

which implies that

$${\mathrm{PCO}}_i(t)-{\mathrm{PCU}}_i(t)\le {\delta }_i-\frac{m_i}{2}\cdot 0\text{or, more precisely,}{\mathrm{PCO}}_i(t)-{\mathrm{PCU}}_i(t)\le {\delta }_i-\frac{m_i}{2}\cdot \frac{h_i^2}{4}.$$

Using ${\delta }_i=\frac{K_i}{8}{h}_i^2$ and the identity $-m_i=|m_i|$, we obtain

$${\mathrm{PCO}}_i(t)-{\mathrm{PCU}}_i(t)\le \frac{K_i}{8}{h}_i^2-\frac{m_i}{8}{h}_i^2=\frac{K_i-m_i}{8}{h}_i^2.$$

Thus, for every $t\in I_i$,

$$0\le {\mathrm{PCO}}_i(t)-{\mathrm{PCU}}_i(t)\le \frac{K_i-m_i}{8}{h}_i^2.$$

By the global definition,

$$0\le \mathrm{PCO}(t)-\mathrm{PCU}(t)\le \frac{K_i-m_i}{8}{h}_i^2,t\in I_i.$$

∎

4. Global Branch-and-Bound Scheme in the Reduced Space

In this section, we present a deterministic branch-and-bound scheme tailored to the reduced one-dimensional optimization problem.

$$\underset{\theta \in [0,{\theta }_{\max }]}{\min }F(\theta ),$$

where $F(\theta )=f(x(\theta ))$ and $x(\theta )$ is the $\alpha$–dense parametric transformation introduced in the previous section. The bounds used in the algorithm are given by the piecewise concave underestimator (PCU) and the piecewise convex overestimator (PCO), both analytically constructed based on interval curvature bounds.

4.1. Interval Partition and Bounds

Let ${ℒ}_k$ be the list of active intervals at iteration $k$. Each element $I\in {ℒ}_k$ is a closed interval

$$I=[a,b]\subset [0,{\theta }_{\max }].$$

On each $I$, we define:

$$\underset{¯}{F}(I):=\underset{t\in I}{\min }\mathrm{PCU}(t),\overline{F}(I):=\underset{t\in I}{\min }\mathrm{PCO}(t).$$

Since $\mathrm{PCU}$ is concave on each base subinterval and $\mathrm{PCO}$ is convex (piecewise affine), these local problems reduce to endpoint evaluations on each primitive subinterval. More precisely, if $I$ is contained in a single mesh interval $[t_i,t_{i+1}]$ used in the construction of PCU and PCO, then:

$$\underset{¯}{F}(I)=\min \{\mathrm{PCU}(a),\mathrm{PCU}(b)\},\overline{F}(I)=\underset{t\in I}{\min }\mathrm{PCO}(t)=\min \{\mathrm{PCO}(a),\mathrm{PCO}(b)\},$$

since a concave (resp. convex) function attains its minimum (resp. maximum) on an interval at one of the endpoints.

In practice, when $I$ overlaps several mesh intervals $[t_i,t_{i+1}]$, we refine $I$ along the mesh nodes so that each branch-and-bound subinterval is a union of such primitive pieces; the above formulas then apply on each piece.

We maintain the global lower and upper bounds at iteration $k$:

$${\underset{¯}{F}}_k:=\underset{I\in {ℒ}_k}{\min }\underset{¯}{F}(I),{\overline{F}}_k:=\underset{I\in {ℒ}_k}{\min }\overline{F}(I).$$

4.2. Branch-and-Bound Algorithm in the $\theta$–Space

Let $\epsilon >0$ be a prescribed tolerance. The algorithm starts from the initial interval

$$I^{(0)}:=[0,{\theta }_{\max }],{ℒ}_0:=\{I^{(0)}\}.$$

4.3. Adaptive Gap-Based Branch-and-Bound in the Reduced Space

We use the same curvature bounds $m_i,K_i$ and the maximal theoretical gap

$${\mathrm{\Delta }}^{\max }(I):=\frac{K_i-m_i}{8}h{(I)}^2,I\subset [t_i,t_{i+1}],$$

where $h(I)$ is the length of $I$ and $I$ is always contained in a single base mesh interval $[t_i,t_{i+1}]$.

The initial interval $[0,{\theta }_{\max }]$ is uniformly subdivided into $N$ subintervals

$$I_j^{(0)}:=[\frac{j}{N}{\theta }_{\max },\frac{j+1}{N}{\theta }_{\max }],j=0,\mathrm{\dots },N-1,$$

and the local PCU/PCO bounds and gaps are computed on each $I_j^{(0)}$.

Moreover, at each branching step, the selected interval is subdivided into $N_{\text{sub}}\ge 2$ equal subintervals.

Input: $N$ initial subdivisions, $N_{\text{sub}}\ge 2$ children per branch, tolerance $\epsilon >0$.

Result: Global minimum approximation

1

Initialization: 2

Construct $I_j^{(0)}$, $j=0,\mathrm{\dots },N-1$. 3

For each $I_j^{(0)}$, compute $\underset{¯}{F}(I_j^{(0)})$, $\overline{F}(I_j^{(0)})$ via PCU/PCO, and ${\mathrm{\Delta }}^{\max }(I_j^{(0)})$. 4

Set

$${\underset{¯}{F}}_0:=\underset{j}{\min }\underset{¯}{F}(I_j^{(0)}),{\overline{F}}_0:=\underset{j}{\min }\overline{F}(I_j^{(0)}),{\mathrm{\Delta }}_0:={\overline{F}}_0-{\underset{¯}{F}}_0$$

Set ${ℒ}_0:=\{I_j^{(0)}:j=0,\mathrm{\dots },N-1\}$ and $k\leftarrow 0$. 5

6

while ${\mathrm{\Delta }}_k>\epsilon$ do 7

// Selection: interval with largest theoretical gap

    Select

$$I_k:=\arg \underset{I\in {ℒ}_k}{\max }{\mathrm{\Delta }}^{\max }(I).$$

Let $I_k=[a_k,b_k]$. Remove $I_k$ from ${ℒ}_k$. 8

    9

   // Branch: subdivision of $I_k$ into $N_{\text{sub}}$ subintervals

    Set $h_k:=b_k-a_k$ and define the subdivision points

$$s{}_{k,\mathrm{\ell }}:=a{}_k+\mathrm{\ell }\frac{h_k}{N_{\text{sub}}},\mathrm{\ell }=0,1,\mathrm{\dots },N{}_{\text{sub}}.$$

For each $\mathrm{\ell }=0,\mathrm{\dots },N_{\text{sub}}-1$, define the child interval

$$I_k^{(\mathrm{\ell })}:=[s_{k,\mathrm{\ell }},s_{k,\mathrm{\ell }+1}].$$

10

   // Local PCU/PCO bounds and local gaps on children

    for $\mathrm{\ell }=0,\mathrm{\dots },N_{\text{sub}}-1$ do 11

    Compute $\underset{¯}{F}(I_k^{(\mathrm{\ell })})$ and $\overline{F}(I_k^{(\mathrm{\ell })})$ using PCU/PCO restricted to $I_k^{(\mathrm{\ell })}$. 12

       Identify the base mesh index $i$ such that $I_k^{(\mathrm{\ell })}\subset [t_i,t_{i+1}]$ and set

$${\mathrm{\Delta }}^{\max }(I_k^{(\mathrm{\ell })}):=\frac{K_i-m_i}{8}{\left(h(I_k^{(\mathrm{\ell })})\right)}^2.$$

13

   // Bounding and pruning

    Initialize ${ℒ}_{k+1}:={ℒ}_k$. 14

    for $\mathrm{\ell }=0,\mathrm{\dots },N_{\text{sub}}-1$ do 15

    if $\underset{¯}{F}(I_k^{(\mathrm{\ell })})\le {\overline{F}}_k$ then 16

       insert $I_k^{(\mathrm{\ell })}$ into ${ℒ}_{k+1}$ 17

          18

   // Update global bounds and global gap

    Set

$${\underset{¯}{F}}_{k+1}:=\underset{I\in {ℒ}_{k+1}}{\min }\underset{¯}{F}(I),{\overline{F}}_{k+1}:=\underset{I\in {ℒ}_{k+1}}{\min }\overline{F}(I),{\mathrm{\Delta }}_{k+1}:={\overline{F}}_{k+1}-{\underset{¯}{F}}_{k+1}.$$

Increment $k\leftarrow k+1$. 19

    return any ${\theta }^{\epsilon }$ such that $\overline{F}({\theta }^{\epsilon })={\overline{F}}_k$ as an $\epsilon$–optimal reduced solution.

Algorithm 1 Adaptive Gap-Based Branch-and-Bound with $N_{\text{sub}}$-Subdivision

4.4. Convergence of the Branch-and-Bound Scheme

We show that the above algorithm converges to the global minimum of $F$ on $[0,{\theta }_{\max }]$.

Let

$$F^{\star }:=\underset{\theta \in [0,{\theta }_{\max }]}{\min }F(\theta ).$$

Theorem 7 (Global Convergence in the Reduced Space).

Assume $F\in C^2([0,{\theta }_{\max }])$ and that, for each mesh interval $[t_i,t_{i+1}]$, there exist $m_i\le 0\le K_i$ with

$$m_i\le F^{\prime \prime }(t)\le K_i,\forall t\in [t_i,t_{i+1}].$$

Then the branch-and-bound Algorithm 1 generates sequences $({\underset{¯}{F}}_k)$ and $({\overline{F}}_k)$ such that

$${\underset{¯}{F}}_k\le F^{\star }\le {\overline{F}}_k,\forall k,$$

and

$$\underset{k\to \mathrm{\infty }}{lim}{\underset{¯}{F}}_k=F^{\star }=\underset{k\to \mathrm{\infty }}{lim}{\overline{F}}_k.$$

In particular, for any $\epsilon >0$, the algorithm terminates in a finite number of iterations with an $\epsilon$–optimal solution.

Proof.

Step 1. Lower and upper bounds. For any interval $I\subset [0,{\theta }_{\max }]$,  Theorem 6 yields

$$\mathrm{PCU}(t)\le F(t)\le \mathrm{PCO}(t),\forall t\in I.$$

Taking minimum over $t\in I$,

$$\underset{t\in I}{\min }\mathrm{PCU}(t)\le \underset{t\in I}{\min }F(t)\le \underset{t\in I}{\min }\mathrm{PCO}(t),$$

i.e.

$$\underset{¯}{F}(I)\le \underset{t\in I}{inf}F(t)\le \overline{F}(I).$$

(continued on p. 18)

Thus, for every iteration $k$,

$${\underset{¯}{F}}_k=\underset{I\in {ℒ}_k}{\min }\underset{¯}{F}(I)\le \min {}_{I\in {ℒ}_k}{}^{}\underset{t\in I}{inf}F(t)\le \underset{t\in [0,{\theta }_{\max }]}{inf}F(t)=F^{\star },$$

and

$$F^{\star }\le \underset{I\in {ℒ}_k}{\min }\overline{F}(I)={\overline{F}}_k.$$

Hence

$${\underset{¯}{F}}_k\le F^{\star }\le {\overline{F}}_k,\forall k.$$

Step 2. Refinement and vanishing gap. At each branching step, an interval $I_k=[a_k,b_k]$ is split into two subintervals of length $h_k/2$, where $h_k:=b_k-a_k$. Thus the maximal length of intervals in ${ℒ}_k$,

$$H_k:=\underset{I\in {ℒ}_k}{\max }\mathrm{length}(I),$$

satisfies

$$H_{k+1}\le \frac{1}{2}{H}_k,$$

so that

$$\underset{k\to \mathrm{\infty }}{lim}{H}_k=0.$$

On any interval $I\subset [t_i,t_{i+1}]$ with length $|I|\le h_i$,  Theorem 6 yields

$$0\le \overline{F}(I)-\underset{¯}{F}(I)\le \frac{K_i-m_i}{8}{|I|}^2.$$

Hence, for each fixed $i$,

$$\underset{|I|\to 0}{lim}\left[\overline{F}(I)-\underset{¯}{F}(I)\right]=0.$$

Step 3. Limit of the global gap. At iteration $k$, the global gap satisfies

$$0\le {\overline{F}}_k-{\underset{¯}{F}}_k=\underset{I\in {ℒ}_k}{\min }\overline{F}(I)-\underset{I\in {ℒ}_k}{\min }\underset{¯}{F}(I)\le \underset{I\in {ℒ}_k}{\max }\left[\overline{F}(I)-\underset{¯}{F}(I)\right].$$

Since every interval length in ${ℒ}_k$ is bounded by $H_k$ and $H_k\to 0$, it follows that

$$\underset{k\to \mathrm{\infty }}{lim}\left({\overline{F}}_k-{\underset{¯}{F}}_k\right)=0.$$

Combined with ${\underset{¯}{F}}_k\le F^{\star }\le {\overline{F}}_k$, this implies

$$\underset{k\to \mathrm{\infty }}{lim}{\underset{¯}{F}}_k=F^{\star }=\underset{k\to \mathrm{\infty }}{lim}{\overline{F}}_k.$$

Step 4. Finite termination for a given $\epsilon >0$. Since the global gap converges to $0$, there exists $k_{\epsilon }$ such that

$${\overline{F}}_{k_{\epsilon }}-{\underset{¯}{F}}_{k_{\epsilon }}\le \epsilon .$$

At that iteration, the algorithm stops by the termination condition in Algorithm 1, and any ${\theta }^{\epsilon }$ selected from the interval attaining ${\overline{F}}_{k_{\epsilon }}$ is $\epsilon$–optimal. ∎

4.5. Interval-Based Computation of Curvature Bounds

In practice, the local curvature bounds $m_i$ and $K_i$ on each interval $I_i=[t_i,t_{i+1}]$ are obtained by interval analysis applied to the second derivative of the reduced function $F(\theta )=f(x(\theta ))$.

Recall that

$$F^{\prime \prime }(\theta )=x^{\prime }{(\theta )}^T{H}_f(x(\theta ))x^{\prime }(\theta )+⟨\nabla f(x(\theta )),x^{\prime \prime }(\theta )⟩,$$

where $\nabla f$ and $H_f$ denote the gradient and the Hessian of $f$, respectively.

4.5.1. Interval Enclosures for $x(\theta )$, $x^{\prime }(\theta )$, $x^{\prime \prime }(\theta )$

On each $I_i=[t_i,t_{i+1}]$, using standard interval arithmetic for the trigonometric functions we compute interval vectors

$${[X]}_i,{[X^{\prime }]}_i,{[X^{\prime \prime }]}_i\subset {ℝ}^n$$

such that

$$x(\theta )\in {[X]}_i,x^{\prime }(\theta )\in {[X^{\prime }]}_i,x^{\prime \prime }(\theta )\in {[X^{\prime \prime }]}_i,\forall \theta \in I_i.$$

More precisely, for each coordinate

$$x_j(\theta )=\frac{1}{2}\left[(b_j-a_j)\cos ({\omega }_j\theta +{\phi }_j)+(b_j+a_j)\right],$$

we compute interval bounds

$${[\cos ({\omega }_j\theta +{\phi }_j)]}_i$$

for $\theta \in I_i$, then propagate these bounds to obtain ${[x_j]}_i$. Differentiating,

$$x_j^{\prime }(\theta )=-\frac{1}{2}(b_j-a_j){\omega }_j\sin ({\omega }_j\theta +{\phi }_j),$$

$$x_j^{\prime \prime }(\theta )=-\frac{1}{2}(b_j-a_j){\omega }_j^2\cos ({\omega }_j\theta +{\phi }_j),$$

and, again by interval evaluation of $\sin$ and $\cos$ on $I_i$, we obtain intervals ${[x_j^{\prime }]}_i$ and ${[x_j^{\prime \prime }]}_i$, which yield ${[X^{\prime }]}_i$ and ${[X^{\prime \prime }]}_i$.

4.5.2. Interval Enclosures for $\nabla f$ and $H_f$

Let

$$X_i:={[X]}_i\subset X$$

be the interval box containing all points $x(\theta )$ with $\theta \in I_i$. Using interval arithmetic (or any sound automatic differentiation / interval Hessian procedure), we compute an interval vector and an interval matrix

$${[\nabla f]}_i\subset {ℝ}^n,{[H_f]}_i\subset {ℝ}^{n\times n},$$

such that

$$\nabla f(z)\in {[\nabla f]}_i,H_f(z)\in {[H_f]}_i,\forall z\in X_i.$$

4.5.3. Interval Enclosure for $F^{\prime \prime }$

For $\theta \in I_i$, one has

$$F^{\prime \prime }(\theta )=x^{\prime }{(\theta )}^T{H}_f(x(\theta ))x^{\prime }(\theta )+⟨\nabla f(x(\theta )),x^{\prime \prime }(\theta )⟩.$$

Let $v\in {[X^{\prime }]}_i$, $w\in {[X^{\prime \prime }]}_i$, $g\in {[\nabla f]}_i$ and $H\in {[H_f]}_i$ be arbitrary. We define the interval

$$[{\mathrm{\Phi }}_i]:=\{v^{T}Hv+⟨g,w⟩:v\in {[X^{\prime }]}_i,H\in {[H_f]}_i,g\in {[\nabla f]}_i,w\in {[X^{\prime \prime }]}_i\}.$$

By interval arithmetic, we can compute an enclosing interval

$$[{\mathrm{\Phi }}_i]\subset ℝ$$

such that

$$F^{\prime \prime }(\theta )\in [{\mathrm{\Phi }}_i],\forall \theta \in I_i.$$

We then set

$$m_i:=inf[{\mathrm{\Phi }}_i],K_i:=sup[{\mathrm{\Phi }}_i].$$

Theorem 8 (Soundness of Interval Curvature Bounds).

For each $i$, the interval $[{\mathrm{\Phi }}_i]$ computed by interval arithmetic satisfies

$$m_i\le F^{\prime \prime }(\theta )\le K_i,\forall \theta \in I_i,$$

so that

$$m_i\le F^{\prime \prime }(t)\le K_i,\forall t\in I_i.$$

In particular, the assumptions of  Theorem 6 hold with these values of $m_i$ and $K_i$.

Proof.

By construction of ${[X]}_i$, ${[X^{\prime }]}_i$, ${[X^{\prime \prime }]}_i$, ${[\nabla f]}_i$, ${[H_f]}_i$, we have, for every $\theta \in I_i$,

$$x(\theta )\in {[X]}_i,x^{\prime }(\theta )\in {[X^{\prime }]}_i,x^{\prime \prime }(\theta )\in {[X^{\prime \prime }]}_i,\nabla f(x(\theta ))\in {[\nabla f]}_i,H_f(x(\theta ))\in {[H_f]}_i.$$

Hence

$$F^{\prime \prime }(\theta )=x^{\prime }{(\theta )}^T{H}_f(x(\theta ))x^{\prime }(\theta )+⟨\nabla f(x(\theta )),x^{\prime \prime }(\theta )⟩\in [{\mathrm{\Phi }}_i],$$

by the soundness of interval arithmetic. By definition of $m_i$ and $K_i$,

$$m_i\le F^{\prime \prime }(\theta )\le K_i,\forall \theta \in I_i.$$

∎

Remark on curvature growth and subdivision complexity.

From the expression

$$F^{\prime \prime }(\theta )=x^{\prime }{(\theta )}^{\top }{H}_f(x(\theta ))x^{\prime }(\theta )+⟨\nabla f(x(\theta )),x^{\prime \prime }(\theta )⟩,$$

we see that the curvature of $F$ can grow with the frequency parameters ${\omega }_i$, since $\Vert x^{\prime }(\theta )\Vert =𝒪({\omega }_i)$ and $\Vert x^{\prime \prime }(\theta )\Vert =𝒪({\omega }_i^2)$. Higher frequencies may thus lead to larger interval curvature bounds $K_i$, looser PCU–PCO envelopes, and finer subdivisions to maintain accuracy.

This highlights a trade-off: higher frequency improves domain coverage but increases curvature. Our framework addresses this using slowly growing frequency sequences and an adaptive gap-based subdivision strategy, focusing refinement where the envelope gap is significant. As shown in the experiments, this balance maintains practical efficiency while ensuring global optimality.

4.6. Back-Projection to the Original Multivariate Problem

Let

$$f^{\star }:=\underset{x\in X}{\min }f(x),F^{\star }:=\underset{\theta \in [0,{\theta }_{\max }]}{\min }F(\theta )=\underset{\theta \in [0,{\theta }_{\max }]}{\min }f(x(\theta )).$$

Assume:

• The curve $\mathrm{\Gamma }=x([0,{\theta }_{\max }])$ is $\alpha$–dense in $X$.

• $f$ is Lipschitz continuous on $X$ with constant $L_f>0$.

• The interval-based curvature bounds $m_i,K_i$ satisfy  Theorem 8.

From  Theorem 1, we have

(4) $$|f^{\star }-F^{\star }|\le L_f\alpha .$$

Let $({\underset{¯}{F}}_k,{\overline{F}}_k)$ be the lower and upper bounds generated by the branch-and-bound algorithm in the reduced space, and let ${\theta }^k\in [0,{\theta }_{\max }]$ be any point associated with the interval attaining ${\overline{F}}_k$, i.e.

$${\overline{F}}_k=\overline{F}(I_k),{\theta }^k\in I_k.$$

By  Theorem 7,

$${\underset{¯}{F}}_k\le F^{\star }\le {\overline{F}}_k,\underset{k\to \mathrm{\infty }}{lim}({\overline{F}}_k-{\underset{¯}{F}}_k)=0.$$

For a given tolerance $\epsilon >0$, the algorithm stops at some $k_{\epsilon }$ with

$${\overline{F}}_{k_{\epsilon }}-{\underset{¯}{F}}_{k_{\epsilon }}\le \epsilon .$$

Theorem 9 (Approximate Multivariate Global Solution).

Let $\epsilon >0$ and let ${\theta }^{\epsilon }:={\theta }^{k_{\epsilon }}$ be the reduced-space solution returned by the branch-and-bound algorithm. Define

$$x^{\epsilon }:=x({\theta }^{\epsilon })\in X.$$

Then

(5) $$f(x^{\epsilon })-f^{\star }\le \epsilon +L_f\alpha .$$

In particular, $x^{\epsilon }$ is a $(\epsilon +L_f\alpha )$–global approximate minimizer of $f$ over $X$.

Proof.

From the branch-and-bound algorithm and the definition of ${\theta }^{\epsilon }$,

$$F({\theta }^{\epsilon })\le {\overline{F}}_{k_{\epsilon }}\le F^{\star }+\epsilon .$$

Thus

$$F({\theta }^{\epsilon })-F^{\star }\le \epsilon .$$

By definition, $F({\theta }^{\epsilon })=f(x^{\epsilon })$ and

$$F^{\star }=\underset{\theta }{\min }F(\theta ).$$

Using the triangle inequality and (4), we write

$$f(x^{\epsilon })-f^{\star }=f(x^{\epsilon })-F^{\star }+F^{\star }-f^{\star }\le \left(F({\theta }^{\epsilon })-F^{\star }\right)+|F^{\star }-f^{\star }|.$$

Hence

$$f(x^{\epsilon })-f^{\star }\le \epsilon +L_f\alpha .$$

∎

Remark. For fixed $\alpha$, the algorithm converges on $\mathrm{\Gamma }$ as $\epsilon \to 0$, with error bounded by $L_f\alpha$.

5. Numerical Experiments

This section presents a numerical evaluation of the proposed Alienor–PCU–PCO global optimization framework. All experiments were performed on a standard workstation (3.0 GHz CPU, 16 GB RAM) using a MATLAB/Julia prototype implementation. Interval arithmetic computations were handled via the INTLAB package.

The goals of the study are threefold:

1. to assess the tightness of the PCU–PCO envelope bounds;

2. to evaluate the efficiency of the univariate branch-and-bound scheme in the reduced $\theta$–space;

3. to compare the proposed method against state-of-the-art solvers on challenging multivariate benchmark problems.

5.1. Benchmark Problems

A suite of standard nonconvex test functions

$$f:\mathrm{\Omega }=\prod _{i=1}^n[a_i,b_i]\to ℝ$$

was selected, covering dimensions from $n=5$ to $n=40$. The benchmarks include classical smooth and multimodal landscapes such as the Rosenbrock, Powell, Wood, Ackley, Griewank, Rastrigin, Shekel, Hartmann 6, Shubert, Lévy, and Styblinski–Tang functions, along with randomly generated quartic–quadratic composites.

Each multivariate function is transformed into a reduced univariate form via the $\alpha$–dense mapping

$$x(\theta )=\frac{1}{2}\left[(b_i-a_i)\cos ({\omega }_i\theta +{\phi }_i)+(b_i+a_i)\right],\theta \in [0,{\theta }_{\max }],$$

resulting in the reduced objective $F(\theta )=f(x(\theta ))$. The frequencies ${\omega }_i$ follow a slow, deterministic growth:

$${\omega }_i={\omega }_0+(i-1)\mathrm{\Delta }\omega ,i=1,\mathrm{\dots },n,$$

with ${\omega }_0=1$ and $\mathrm{\Delta }\omega =1$, ensuring domain coverage without excessive oscillations.

To guarantee that $x(\theta )$ is $\alpha$–dense in $\mathrm{\Omega }$, the following density condition is enforced:

$${\theta }_{\max }\ge \underset{1\le i\le n}{\max }\frac{\pi (b_i-a_i)}{\alpha {\omega }_i},\alpha ={10}^{-3},$$

yielding a reduction error of order $𝒪(L_f\alpha )$.

Default numerical parameters.

Unless stated otherwise, experiments use: $\alpha ={10}^{-3}$, $N=50$, $N_{\mathrm{sub}}\in \{3,4,5\}$, and tolerance $\epsilon ={10}^{-6}$. The range ${\theta }_{\max }$ satisfies

$${\theta }_{\max }\ge \underset{1\le i\le n}{\max }\frac{\pi (b_i-a_i)}{\alpha {\omega }_i}.$$

All computations use interval arithmetic to certify curvature bounds and global optimality.

5.2. Branch-and-Bound Framework

The interval $[0,{\theta }_{\max }]$ is initially partitioned into $M$ uniform subintervals. For each subinterval $[t_i,t_{i+1}]$, interval arithmetic is used to compute second-derivative bounds $m_i\le F^{\prime \prime }(\theta )\le K_i$. These bounds are then used to construct the corresponding local piecewise concave underestimator (PCU) and convex overestimator (PCO).

At each iteration, the subinterval with the largest theoretical PCU–PCO gap

$${\mathrm{\Delta }}^{\max }(I)=\frac{K_i-m_i}{8}h{(I)}^2$$

is selected and subdivided adaptively into $N_{\text{sub}}\in \{3,4,5\}$ subintervals. The procedure repeats until the global duality gap

$${\mathrm{\Delta }}_k={\overline{F}}_k-{\underset{¯}{F}}_k$$

falls below the target tolerance $\epsilon ={10}^{-6}$.

5.3. Performance Metrics

For each benchmark problem, the following metrics are recorded:

• final lower and upper bounds $({\underset{¯}{F}}_k,{\overline{F}}_k)$;

• final duality gap ${\overline{F}}_k-{\underset{¯}{F}}_k$;

• total number of interval subdivisions;

• total CPU time (in seconds);

• reconstructed multivariate solution $x^{\epsilon }=x({\theta }^{\epsilon })$ and its associated global error $f(x^{\epsilon })-f^{\star }$.

Across all benchmarks, the Alienor–PCU–PCO approach consistently yields tight bounds and reliable convergence. It outperforms classical interval and Lipschitz-based solvers in both solution accuracy and computational efficiency.

5.4. Comparison with State-of-the-Art Global Optimization Methods

The performance of the proposed Alienor–PCU–PCO framework was compared with several representative global optimization solvers covering distinct algorithmic paradigms, including DIRECT, $\alpha$BB, classical interval Branch-and-Bound (B&B), COUENNE, GloptiPoly 3, and stochastic MultiStart L-BFGS/IPOPT. All solvers were executed under identical experimental conditions, with a uniform evaluation budget of $N_{\max }=5\times {10}^5$, identical test functions and gradients, and a common hardware environment. Each test was repeated ten times for reproducibility. Performance was evaluated using the relative objective error $\mathrm{err}(x)=|f(x)-f^{\star }|/(1+|f^{\star }|)$, the achieved optimality gap, CPU time, number of subdivisions or nodes, and success rate within the prescribed tolerance ${\epsilon }_{\mathrm{glob}}={10}^{-6}$. The comparative analysis shows that DIRECT often suffers from domain explosion in high dimensions and $\alpha$BB produces conservative relaxations for non-separable functions, while COUENNE and GloptiPoly offer strong guarantees but scale poorly. In contrast, the proposed Alienor–PCU–PCO scheme achieves competitive or superior results across all benchmarks, maintaining certified bounds with significantly fewer subdivisions. Its reduced 1D formulation and adaptive subdivision yield favorable scaling with dimension on benchmarks, while ensuring certified global optimality.

5.5. Performance Comparison Tables

Table 1 and Table 2 summarize the numerical performance of the proposed Alienor–PCU–PCO method against several state-of-the-art global solvers on a representative set of ten benchmark problems.

Function	$n$	Method	Nodes	CPU (s)	Final Gap / Error	Success
Rosenbrock	10	Alienor–PCU–PCO	1 240	0.42	$7.9\times {10}^{-7}$	Yes
		DIRECT	58 400	2.95	$1.2\times {10}^{-4}$	No
		$\alpha$BB	3 210	1.74	$4.7\times {10}^{-5}$	Partial
		Couenne	4 820	3.81	$1.0\times {10}^{-6}$	Yes
		Interval B&B	152 900	5.40	${10}^{-3}$	No
Powell	12	Alienor–PCU–PCO	1 520	0.38	$9.1\times {10}^{-7}$	Yes
		DIRECT	65 900	3.12	$2.3\times {10}^{-4}$	No
		$\alpha$BB	4 180	2.45	$7.5\times {10}^{-5}$	Partial
		Couenne	6 230	4.21	${10}^{-6}$	Yes
		Interval B&B	190 300	6.85	${10}^{-3}$	No
Wood	5	Alienor–PCU–PCO	410	0.10	$5.2\times {10}^{-7}$	Yes
		DIRECT	12 500	0.50	$1.0\times {10}^{-3}$	No
		$\alpha$BB	910	0.42	$2.9\times {10}^{-5}$	Partial
		Couenne	1 620	0.92	${10}^{-6}$	Yes
		Interval B&B	33 100	1.60	${10}^{-2}$	No

Table 1. Comparison on classical smooth benchmarks

Function	$n$	Method	Nodes	CPU (s)	Final Gap / Error	Success
Rastrigin	20	Alienor–PCU–PCO	2 480	0.75	$8.6\times {10}^{-7}$	Yes
		DIRECT	120 000	7.40	$3.1\times {10}^{-2}$	No
		$\alpha$BB	11 800	5.92	$1.5\times {10}^{-3}$	Partial
		Couenne	19 300	12.4	$2.2\times {10}^{-5}$	Yes
		Interval B&B	450 000	18.9	${10}^{-1}$	No
Ackley	30	Alienor–PCU–PCO	3 200	1.05	$9.1\times {10}^{-7}$	Yes
		DIRECT	180 000	11.0	$8.8\times {10}^{-2}$	No
		$\alpha$BB	14 900	7.40	$6.2\times {10}^{-3}$	Partial
		Couenne	25 800	18.7	$9.5\times {10}^{-6}$	Yes
		Interval B&B	680 000	29.5	$0.2$	No
Griewank	40	Alienor–PCU–PCO	3 950	1.40	$6.4\times {10}^{-7}$	Yes
		DIRECT	300 000	16.2	$1.9\times {10}^{-1}$	No
		$\alpha$BB	25 100	10.3	$2.1\times {10}^{-2}$	Partial
		Couenne	33 700	24.1	$3.0\times {10}^{-5}$	Yes
		Interval B&B	1 100 000	54.0	$0.5$	No

Table 2. Comparison on multimodal and non-separable benchmarks

Figure 1. Comparative CPU time of the proposed Alienor–PCU–PCO method and several global solvers on selected benchmarks.

5.6. Discussion of Numerical Results and Conclusion

The numerical experiments confirm the effectiveness and robustness of the proposed Alienor–PCU–PCO framework across a broad suite of classical and multimodal benchmark problems. The method consistently achieves the target global tolerance ($\text{gap}\le {10}^{-6}$) while requiring substantially fewer nodes than existing solvers—often by nearly two orders of magnitude compared to DIRECT and classical interval branch-and-bound methods.

This efficiency is primarily due to three key components: the one-dimensional reduction in $\theta$-space via the $\alpha$-dense transformation; the analytically tight PCU–PCO envelopes constructed from interval curvature bounds; and the adaptive subdivision strategy that targets intervals with the largest theoretical gaps. The approach reliably delivers certified optimality gaps on the order of ${10}^{-7}$, while solvers such as DIRECT and $\alpha$BB typically stagnate at much larger tolerances.

On challenging high-dimensional and highly multimodal landscapes—such as the Rastrigin and Ackley functions The method demonstrates robust performance on problems of dimension up to $n=40$ within the considered benchmark set. Outperforming deterministic and convex-relaxation-based solvers such as COUENNE and $\alpha$BB, which suffer from rapidly increasing computational costs and node counts with dimension. In contrast, our framework consistently achieves tighter bounds, typically requires fewer subdivisions and converges faster on the tested problems, and converges faster, benefiting from the reduced one-dimensional structure and analytical envelopes that avoid overestimation due to multivariate dependency effects.

The algorithm also exhibits notable robustness with respect to variations in key parameters, including the frequency profile $({\omega }_i)$, the initial partition size $N$, and the subdivision factor $N_{\text{sub}}$. Furthermore, the use of interval arithmetic contributes to its numerical stability throughout the computations.

The primary limitations of the approach are associated with the computational cost of evaluating interval Hessians in very large-scale settings and the conservatism of curvature bounds in ill-scaled or near-singular regions. Nonetheless, within the tested range ($5\le n\le 40$), the Alienor-PCU-PCO scheme delivers certified global solutions with competitive or superior performance relative to state-of-the-art methods, combining theoretical rigor with practical efficiency.

Overall, the proposed framework—grounded in the $\alpha$-dense reduction and the construction of analytical piecewise concave and convex envelopes—opens promising avenues for future work. These include extensions to constrained global optimization, applications in optimal control, and further refinement of curvature-based bounding techniques.

6. Conclusion

We have introduced a new global optimization framework that combines an $\alpha$–dense dimensionality reduction with analytical one-dimensional PCU–PCO envelopes derived from interval curvature bounds. The resulting branch-and-bound algorithm operates entirely in the reduced univariate space and provides rigorous global optimality certificates. Numerical experiments demonstrate that the proposed method is both efficient and competitive with state-of-the-art solvers, particularly in nonconvex and moderately high-dimensional settings under carefully selected reduction and subdivision parameters.

Acknowledgements.

The author would like to thank the editor in charge and the anonymous reviewers for their careful reading of the manuscript and for their constructive comments and suggestions, which helped to improve the quality and clarity of this paper.