Subgradient bundle and derivative free optimization

Finite sums of vectors in ${\mathbb{R}}^n$ use the additive finite-list sum of Linear combination of a finite list, and the span $\mathrm{span}(S)$ as the smallest linear subspace containing $S$; sums of real coefficients use Finite sums and finite products, by recursion.

Fix $n\ge 1$, an objective oracle $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{\text{nonfinite}\}$, a finite integer call budget $B\ge 0$, positive tolerances ${\epsilon }_x,{\epsilon }_f$, and an ordered initial simplex $(v_0,\dots ,v_n)$. Call the ordered tuple nondegenerate when, for real coefficients ${\lambda }_1,\dots ,{\lambda }_n$, ${\sum }_{i=1}^n{\lambda }_i(v_i-v_0)=0$ implies every ${\lambda }_i=0$. Use reflection $\alpha =1$, expansion $\gamma =2$, contraction $\rho =1\mathrm{/}2$, and shrink $\sigma =1\mathrm{/}2$. Ties in sorting objective values are broken by current vertex slot, lower slot first. When recording the best point seen, replace it only on a strict objective improvement, so ties retain the earliest evaluation; initial vertices are evaluated in slot order.

If the initial simplex is degenerate, return degenerate-simplex. If $B<n+1$, return budget-exhausted with zero calls and no best point. Otherwise evaluate initial vertices in slot order, counting every call. A nonfinite result returns nonfinite-objective and the best finite point seen, if any. For each committed simplex, let $x_b$ be its sorted best vertex, $x_w$ its worst, let $x_2$ denote the second-worst (the best when $n=1$), and set $c:=n^{-1}{\sum }_{i=0}^{n-1}{x}_i$ using the sorted vertices $x_0,\dots ,x_n$. Define the diameter $D={\max }_{0\le i,j\le n}\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2$, and spread $S=f(x_w)-f(x_b)$. Stop with tolerance-met exactly when both $D\le {\epsilon }_x$ and $S\le {\epsilon }_f$.

Otherwise evaluate reflection $x_r=c+(c-x_w)$. If $f(x_r)<f(x_b)$, evaluate expansion $x_e=c+2(x_r-c)$ and replace $x_w$ by $x_e$ iff $f(x_e)<f(x_r)$; a tie keeps reflection. If $f(x_b)\le f(x_r)<f(x_2)$, where $x_2$ is the second-worst vertex, replace $x_w$ by reflection. If $f(x_2)\le f(x_r)<f(x_w)$, evaluate outside contraction $x_{oc}=c+(x_r-c)\mathrm{/}2$ and accept iff $f(x_{oc})\le f(x_r)$; equality accepts. If $f(x_r)\ge f(x_w)$, evaluate inside contraction $x_{ic}=c+(x_w-c)\mathrm{/}2$ and accept iff $f(x_{ic})<f(x_w)$; equality fails. A failed contraction proposes $s_i=x_b+(x_i-x_b)\mathrm{/}2$ for each sorted nonbest vertex $x_i$, $1\le i\le n$, retaining $x_b$. Evaluate $f(s_i)$ in increasing $i$, making a new call even if $s_i$ was evaluated earlier. Apply the budget and nonfinite-result rules below to every such call. Commit the shrunk simplex, in these sorted slots, only after all $n$ values are finite and the complete update passes the nondegeneracy check.

Count every objective call, including rejected trials. Before a needed call, if the budget is exhausted, return budget-exhausted with the last committed simplex and best finite point seen; do not partially commit an update. A nonfinite trial returns nonfinite-objective with the same committed simplex. If a proposed complete update is degenerate, return degenerate-simplex without committing it. After a valid update, recheck both tolerances. No general convergence guarantee is asserted.

Finite sums of vectors in ${\mathbb{R}}^n$ use the additive finite-list sum of Linear combination of a finite list, and the span $\mathrm{span}(S)$ as the smallest linear subspace containing $S$; sums of real coefficients use Finite sums and finite products, by recursion.

Let $n\ge 1$, let $C\subseteq {\mathbb{R}}^n$ be nonempty, closed, and convex, and let $f:C\to \mathbb{R}$ be convex. The finite-budget projected subgradient procedure takes $x_0\in C$, an integer budget $N\ge 1$, and positive stepsizes ${\alpha }_0,\dots ,{\alpha }_{N-1}$. At iteration $k$, an oracle returns either failure or a pair $(f(x_k),g_k)$ with $g_k\in \mathrm{\partial }f(x_k)$, where subgradient has the meaning in Subgradients and the subdifferential of a convex function. On a valid response set $x_{k+1}=P_C(x_k-{\alpha }_k{g}_k),$ where $P_C(u)$ is the unique nearest point in $C$ to $u$. On an oracle failure at iteration $k$, return status oracle-failure, the feasible current iterate, the completed update count, and the least-index best among values observed so far if any (otherwise report none); a full-horizon average is not returned. If all $N$ calls succeed, return status budget-exhausted, the final iterate, the weighted average ${\bar{x}}_N=({\sum }_{k<N}{\alpha }_k{x}_k)\mathrm{/}({\sum }_{k<N}{\alpha }_k)$, and a least-index minimizer of observed values among $x_0,\dots ,x_{N-1}$. Report status and completed update count. This finite procedure makes no convergence claim.

Let $C\subseteq {\mathbb{R}}^n$ be nonempty, closed, and convex; let $f:C\to \mathbb{R}$ be convex; fix $t>0$, a serious-step fraction $m_s\in (0,1)$, a center $x_0\in C$, and an integer outer budget $N\ge 1$. A valid oracle call at $y\in C$ returns $(f(y),g_y)$ with $g_y\in \mathrm{\partial }f(y)$; otherwise it fails. Store every cut $m_y(z)=f(y)+⟨g_y,z-y⟩$ from every successful call, with no memory cap, and set $M_k$ to the maximum of the stored cuts. If no cut exists, call the oracle at the current center. If this initialization call fails, return status oracle-failure with the current center, zero completed trials, and no candidate or model residual; otherwise store its cut. Find the unique minimizer $z_k=\arg {\min }_{z\in C}(M_k(z)+\frac{\mathrm{\parallel }z-x_k{\mathrm{\parallel }}_2^2}{2t}),P_k=f(x_k)-M_k(z_k)\mathrm{.}$ If $P_k\le 0$, return status stationary-or-model-failure with $x_k,z_k,P_k$. Otherwise evaluate at $z_k$. An oracle failure returns oracle-failure. Declare a serious step exactly when $f(x_k)-f(z_k)\ge m_s{P}_k$, set $x_{k+1}=z_k$ then, and otherwise take a null step and set $x_{k+1}=x_k$. Append the valid trial cut after either step. Return budget-exhausted after $N$ trials. This finite algorithm makes no generic convergence claim.

Let $n\ge 1$ and let $D=(d_1,\dots ,d_m)$ be a nonempty finite ordered list in ${\mathbb{R}}^n$. For coefficients ${\lambda }_1,\dots ,{\lambda }_m$, the finite vector sum ${\sum }_{i=1}^m{\lambda }_i{d}_i$ means the vector whose $k$th coordinate is ${\sum }_{j<m}{\lambda }_{j+1}(d_{j+1}{)}_k$ for each $k<n$; this is the finite real sum of Finite sums and finite products, by recursion. The list is positive spanning if every $w\in {\mathbb{R}}^n$ has such a representation with ${\lambda }_i\ge 0$. Keep the order to make a deterministic poll. Define the directional score ${\psi }_D(v)={\max }_{1\le i\le m}(-⟨v,d_i⟩)$ for unit $v$, and the largest poll norm $D_{\max }={\max }_{1\le i\le m}\mathrm{\parallel }{d}_i{\mathrm{\parallel }}_2$. These maxima exist because their indexing sets are nonempty and finite (Every nonempty finite set of reals has a maximum and a minimum, Maximum and minimum of a set). A positive uniform lower bound for ${\psi }_D$ is a separate theorem, not part of this definition.

Let $K$ be compact in Euclidean ${\mathbb{R}}^n$ and let $V\subseteq {\mathbb{R}}^n$ be open with $K\subseteq V$. There is $\delta >0$ such that for every $x\in K$, if $\mathrm{\parallel }y-x{\mathrm{\parallel }}_2<\delta$, then $y\in V$. If $K=\mathrm{\varnothing }$, any positive $\delta$ works.

Let $U\subseteq {\mathbb{R}}^n$ be open, let $f:U\to \mathbb{R}$ be totally differentiable at every point, and suppose its gradient is $L$-Lipschitz on $U$ for some $L\ge 0$. If $x,y\in U$ and the whole segment $[x,y]$ lies in $U$, then $f(y)\le f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{L}{2}\mathrm{\parallel }y-x{\mathrm{\parallel }}_2^2\mathrm{.}$

Let $U\subseteq {\mathbb{R}}^n$ be open, $f:U\to \mathbb{R}$ be an objective accessible only by function evaluations, and let $x_0\in U$. Fix an ordered finite positive-spanning poll list $D=(d_1,\dots ,d_m)$, initial mesh ${\mathrm{\Delta }}_0>0$, cap ${\mathrm{\Delta }}_{\max }\ge {\mathrm{\Delta }}_0$, forcing function $\rho :(0,{\mathrm{\Delta }}_{\max }]\to (0,\mathrm{\infty })$ with $\rho (\mathrm{\Delta })\mathrm{/}\mathrm{\Delta }\to 0$ as $\mathrm{\Delta }\downarrow 0$, factors $0<{\gamma }_{dec}<1<{\gamma }_{inc}$, and integer poll budget $N\ge 0$. Evaluate $f(x_0)$ first and include it in the best-point record. At poll $k$, inspect $x_k+{\mathrm{\Delta }}_k{d}_i$ in list order, ignoring points outside $U$ without an objective call. Accept the first in-domain point $y$ satisfying $f(y)<f(x_k)-\rho ({\mathrm{\Delta }}_k)$; then set $x_{k+1}=y$ and ${\mathrm{\Delta }}_{k+1}=\min ({\mathrm{\Delta }}_{max},{\gamma }_{inc}{\mathrm{\Delta }}_k)$. If none succeeds, declare an unsuccessful poll, set $x_{k+1}=x_k$, and ${\mathrm{\Delta }}_{k+1}={\gamma }_{dec}{\mathrm{\Delta }}_k$. Return the least-index best point among all evaluated points, current center, mesh, evaluation count, and status budget-exhausted after at most $N$ polls. A finite budget is not a stationarity certificate.

Every invocation of Finite-budget Nelder–Mead simplex procedure with finite call budget $B$ returns a status after at most $B$ objective calls. If it returns tolerance-met, both the simplex diameter and objective spread satisfy their stated tolerances. The status is a finite-budget result only and does not certify global or local optimality.

For every finite positive-spanning list $D=(d_1,\dots ,d_m)$ in ${\mathbb{R}}^n$, $n\ge 1$, the score ${\psi }_D(v)={\max }_i(-⟨v,d_i⟩)$ on the unit sphere attains a strictly positive minimum. Write this minimum as ${\kappa }_D>0$. Thus for every $v\in {\mathbb{R}}^n$ there is $d_i\in D$ with $-⟨v,d_i⟩\ge {\kappa }_D\mathrm{\parallel }v{\mathrm{\parallel }}_2$.

Let $N\ge 1$ be an integer and run Projected subgradient method with finite budget with all stated inputs. Every execution returns after at most $N$ oracle calls. On failure it returns the feasible current iterate and a best observed point if one has been observed, or none otherwise; it does not return a full-horizon average. If all calls succeed, the weighted average is defined and feasible, a best observed iterate exists, and the status is budget-exhausted after exactly $N$ updates.

Under the projected-subgradient update of Projected subgradient method with finite budget, let $x^{\ast }\in C$ and suppose the $k$th oracle call returns $g_k\in \mathrm{\partial }f(x_k)$. Then $\mathrm{\parallel }{x}_{k+1}-x^{\ast }{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }{x}_k-x^{\ast }{\mathrm{\parallel }}_2^2-2{\alpha }_k(f(x_k)-f(x^{\ast }))+{\alpha }_k^2\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2\mathrm{.}$

Let $C\subseteq {\mathbb{R}}^n$ be nonempty, closed, and convex; let $t>0$, $v\in {\mathbb{R}}^n$, and let $m_i(y)=b_i+⟨a_i,y⟩$ be a nonempty finite list of affine functions. Then $\mathrm{\Phi }(y)={\max }_i{m}_i(y)+\frac{\mathrm{\parallel }y-v{\mathrm{\parallel }}_2^2}{2t},y\in C,$ has a unique global minimizer on $C$.

Let $F:{\mathbb{R}}^n\to (-\mathrm{\infty },+\mathrm{\infty }]$ be convex, let $t>0$, $v\in {\mathbb{R}}^n$, and suppose $p$ minimizes $Q(y)=F(y)+\mathrm{\parallel }y-v{\mathrm{\parallel }}_2^2\mathrm{/}(2t)$ with $Q(p)<+\mathrm{\infty }$. Then for every $z$ with $F(z)<+\mathrm{\infty }$, $Q(z)\ge Q(p)+\frac{\mathrm{\parallel }z-p{\mathrm{\parallel }}_2^2}{4t}\mathrm{.}$

For every integer poll budget $N\ge 0$, each invocation of Finite-budget deterministic direct search with positive-spanning polling returns after at most $N$ polls with a feasible current center and a best evaluated point.

For a finite integer budget $N\ge 1$, every invocation of Finite-memory-free proximal bundle method with serious and null steps returns one of its specified statuses after at most $N$ trials. Every trial point used by the procedure is uniquely defined unless an earlier oracle-failure or stationary-or-model-failure status has already returned.

Consider an infinite continuation of the polling and mesh-update rules of Finite-budget deterministic direct search with positive-spanning polling, using its admissible inputs and exact branch rules but with no finite poll-budget cap. Write its fixed finite positive-spanning poll list as $D$ and its forcing function as $\rho$. Suppose a subsequence of unsuccessful polls indexed by $k_j$ has ${\mathrm{\Delta }}_{k_j}\to 0$ and centers $x_{k_j}$ in a compact set $K\subseteq V$, where $V\subseteq U$ is open. Assume $f:U\to \mathbb{R}$ is totally differentiable at every point of $V$ and $\mathrm{\nabla }f$ is $L$-Lipschitz there. Here an accumulation point means a limit of a subsequence in the Euclidean metric. Then every such point is stationary, meaning $\mathrm{\nabla }f(\bar{x})=0$. Compactness ensures at least one such accumulation point. This asymptotic claim concerns the untruncated continuation; a finite-budget return is not a stationarity certificate.