We study attainment boundaries for linear optimization over unbounded convex sets. For epigraphs of finite convex functions, convex conjugacy separates recession-cone copositivity, boundedness below, and attainment through three nested subsets of conjugate space. At a finite but unattained boundary value, we establish a facewise asymptotic selection theorem for inward perturbations of the objective. The theorem identifies the escaping directions of the perturbed minimizers, their precise blow-up scale, and the leading asymptotics of the optimal value; the critical set may be multidimensional, and no radial symmetry is assumed. For radial asymptotically conic epigraphs, we obtain a complete boundary trichotomy and universal scaling laws for objective tilting, hard truncation, and power regularization. For shifted ellipsoidal second-order cone programs, we derive explicit primal--dual formulas together with sharp escape, conditioning, and regularization rates. These models also admit an exact robust-optimization representation. At the attainment boundary, strict primal feasibility, zero duality gap, and dual attainment can coexist with failure of primal attainment.
We study convex optimization over a compact convex set when the objective is smooth and convex only on an open domain. Under a boundary-blow-up condition, every feasible initialization yields a compact invariant sublevel set separated from the complement of the objective domain, and an optimal solution exists. For a domain-aware Armijo projected-gradient method, a safe-neighborhood analysis establishes well-defined objective evaluations, finite backtracking, sufficient decrease, and a run-specific but iteration-independent positive lower bound on the accepted step sizes. These properties yield explicit sublinear objective and stationarity guarantees, together with convergence of the full iterate sequence. Positive curvature restricted to feasible displacement directions further guarantees uniqueness and linear convergence. We apply the framework to controllability scoring with prescribed input directions and compact convex allocation constraints. Feasibility is characterized exactly by controllability of the input directions eligible for positive allocation, while restricted injectivity of the Gramian map guarantees uniqueness of the optimal allocation and provides explicit strong-convexity bounds. A directed-network example illustrates how candidate exclusion can preserve or destroy feasibility and alter the optimal allocation in a criterion- and horizon-dependent manner.
The conditional gradient method is attractive when linear minimization over the feasible region is substantially cheaper than projection. Its classical convergence theory, however, is formulated for compact feasible sets, whereas many natural convex feasible regions are closed and unbounded. This paper studies a simple compact-restriction principle for applying conditional gradient steps to unbounded feasible regions. The first scheme uses one compact convex set containing the initial objective sublevel set. The second scheme updates the restriction by intersecting compact convex sets generated along the iterations. In both cases the linear minimization oracle is solved only over compact subsets, but the resulting objective values converge to the global optimum of the original problem, provided the compact restrictions contain the corresponding objective sublevel sets. For smooth convex objectives we obtain the standard superlinear convergence rate of the objective. We also record constructive restrictions based on strong convexity, exact sublevel sets, and epigraph caps, and include a nonsmooth conditional subgradient extension with a sublinear convergence rate under a curvature assumption. Numerical experiments illustrate the behaviour of the fixed and dynamic restrictions on unbounded feasible regions.
We develop new characterizations of both global and local error bounds for general functions, using directional derivatives and tangent cones without imposing convexity or linear structure. We first establish several equivalent conditions for the global error bound of a nonnegative lower semicontinuous function. These equivalences hold for general, possibly nonconvex and nonsmooth functions. We further link the error bound with perturbation stability, Hausdorff stability of sublevel sets, and an inverse-sublevel-set estimate. Turning to directional derivatives, we introduce the minimal unit-sphere directional derivative \(\varphi(x)\) on the tangent cone and clarify its exact relation with the global slope. For Lipschitz continuous functions we prove that \(\sup_{x\notin S_0} \varphi(x)<0\) is sufficient for an error bound, and for convex functions on convex sets this condition is also necessary, In finite dimensions we obtain sharp local results: if \(\varphi(\bar{x})>0\) at a solution \(\bar{x}\), then a local error bound holds and the optimal constant is exactly \(1/\varphi(\bar{x})\); if \(\varphi(\bar{x}) = 0\) and a suitable direction exists outside the tangent cone of the solution set, the local error bound fails. A general estimate relating the directional derivative to the distance from the tangent cone of the solution set is also derived.
Motivated by sampling and approximation schemes arising in nonsmooth optimization, we study the stability of parameterized set-valued integrals under weak perturbations of the underlying probability distribution. For a compact parameter set, we show that compact convex-valued and jointly outer semicontinuous integrands induce set-valued integral maps that converge graphically in excess distance along any weakly convergent sequence of probability measures. The result holds under a superlinear integrability condition and provides a unified stability principle for measure approximations of set-valued expectations. We discuss the sharpness of the assumptions through examples. In particular, we emphasize that joint outer semicontinuity is required in general and that the superlinear envelope condition is tight relative to the classical i.i.d. empirical setting. As a consequence, we obtain outer stability of solution sets for stochastic generalized equations. We illustrate the stability result in several settings, including stochastic nonsmooth optimization with Markovian sampling, smoothing by mollifiers, and parameter-dependent distributional dynamics.
We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions. Our focus is on obtaining non-asymptotic bounds for the expected excess risk rather than sampling guarantees for the full target distribution. The key ingredient of our analysis is a direct passage from relative entropy to objective-value error, based on a weighted Csisz\'ar--Kullback--Pinsker inequality and exponential-moment estimates. This avoids intermediate Wasserstein bounds and yields sharper dependence on the Log-Sobolev constant, a quantity that may scale exponentially with the inverse temperature and the dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds on $\mathbb{E}[F(x_k)]-\min F$ in terms of the inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to an inexact-gradient version of ULA, allowing for biased and stochastic gradient surrogates whose mean-square error grows at most quadratically in the state. This framework covers stochastic gradients and zeroth-order estimators based only on function evaluations. In particular, we show that both Gaussian and spherical finite-difference estimators fit into the inexact-ULA theory and obtain explicit function-evaluation complexity bounds for zeroth-order Langevin optimization. To the best of our knowledge, these are the first non-asymptotic global non-convex optimization complexity bounds for zeroth-order ULA. We also provide numerical experiments illustrating the behavior of the proposed zeroth-order Langevin schemes.
E. Naldi, Marco Rando, Lorenzo Rosasco et al.· 0 citations
We study convex approximations of mixed-integer recourse functions in two-stage stochastic programming. For first-stage decisions, the relevant approximation error is the signed expected residual between the convex approximation and the integer-recourse value function. On bounded uncertainty boxes, we identify residual conditions that yield deterministic bounds for this expectation error. The central condition is coordinate slice-centering, under which integration by parts gives an anisotropic total-variation bound and a mixed-derivative bound whose all-coordinate case is expressed through Vitali variation of the density. Exact centering, however, may be incompatible with convexity, even for totally unimodular ceiling recourse. We therefore use commuting coordinate projectors to decompose an arbitrary residual into a centered component and an explicit slice-mean defect. The resulting defect-adjusted bounds provide selectable error certificates and uniform first-stage decision-quality guarantees. We further establish sharp constants, extend the mixed-derivative estimate to nonsmooth densities, and develop tensor-product and geometric extensions of the framework, alongside a max-affine convex fitting and audit methodology.