More Like this

1. An algorithm for stochastic convex-concave fractional programs with applications to production efficiency and equitable resource allocation

   https://doi.org/10.1016/j.ejor.2023.12.020  

   Dey, Shibshankar; Kim, Cheolmin; Mehrotra, Sanjay (December 2023, European Journal of Operational Research)

   We propose an algorithm to solve convex and concave fractional programs and their stochastic counterparts in a common framework. Our approach is based on a novel reformulation that involves differences of square terms in the constraints, and subsequent employment of piecewise-linear approximations of the concave terms. Using the branch-and-bound (B\&B) framework, our algorithm adaptively refines the piecewise-linear approximations and iteratively solves convex approximation problems. The convergence analysis provides a bound on the optimality gap as a function of approximation errors. Based on this bound, we prove that the proposed B\&B algorithm terminates in a finite number of iterations and the worst-case bound to obtain an $$\epsilon$$-optimal solution reciprocally depends on the square root of $$\epsilon$$. Numerical experiments on Cobb-Douglas production efficiency and equitable resource allocation problems support that the algorithm efficiently finds a highly accurate solution while significantly outperforming the benchmark algorithms for all the small size problem instances solved. A modified branching strategy that takes the advantage of non-linearity in convex functions further improves the performance. Results are also discussed when solving a dual reformulation and using a cutting surface algorithm to solve distributionally robust counterpart of the Cobb-Douglas example models. 

   more » « less
2. A Dynamic Discretization Discovery Algorithm for the Minimum Duration Time-Dependent Shortest Path Problem

   https://doi.org/https://doi.org/10.1007/978-3-319-93031-2_21  

   He, E.; Boland, N.; Nemhauser, G.; Savelsbergh, M. (January 2018, Lecture notes in computer science)

   We present an exact algorithm for the Minimum Duration Time-Dependent Shortest Path Problem with piecewise linear arc travel time functions. The algorithm iteratively refines a time-expanded network model, which allows for the computation of a lower and an upper bound, until - in a finite number of iterations - an optimal solution is obtained. 

   more » « less
3. Neural Network Verification with Proof Production

   Isac, Omri; Barrett, Clark; Zhang, Min; Katz, Guy (October 2022, Proceedings of the 22nd International Conference on Formal Methods In Computer-Aided Design (FMCAD))

   Griggio, Alberto; Rungta, Neha (Ed.)

   Deep neural networks (DNNs) are increasingly being employed in safety-critical systems, and there is an urgent need to guarantee their correctness. Consequently, the verification community has devised multiple techniques and tools for verifying DNNs. When DNN verifiers discover an input that triggers an error, that is easy to confirm; but when they report that no error exists, there is no way to ensure that the verification tool itself is not flawed. As multiple errors have already been observed in DNN verification tools, this calls the applicability of DNN verification into question. In this work, we present a novel mechanism for enhancing Simplex-based DNN verifiers with proof production capabilities: the generation of an easy-to-check witness of unsatisfiability, which attests to the absence of errors. Our proof production is based on an efficient adaptation of the well-known Farkas' lemma, combined with mechanisms for handling piecewise-linear functions and numerical precision errors. As a proof of concept, we implemented our technique on top of the Marabou DNN verifier. Our evaluation on a safety-critical system for airborne collision avoidance shows that proof production succeeds in almost all cases and requires only minimal overhead. 

   more » « less
4. A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression

   https://doi.org/10.1145/3744970.3727269  

   Zhang, Yixuan; Huo, Dongyan Lucy; Chen, Yudong; Xie, Qiaomin (June 2025, ACM SIGMETRICS Performance Evaluation Review)

   Motivated by robust and quantile regression problems, we investigate the stochastic gradient descent (SGD) algorithm for minimizing an objective functionfthat is locally strongly convex with a sub--quadratic tail. This setting covers many widely used online statistical methods. We introduce a novel piecewise Lyapunov function that enables us to handle functionsfwith only first-order differentiability, which includes a wide range of popular loss functions such as Huber loss. Leveraging our proposed Lyapunov function, we derive finite-time moment bounds under general diminishing stepsizes, as well as constant stepsizes. We further establish the weak convergence, central limit theorem and bias characterization under constant stepsize, providing the first geometrical convergence result for sub--quadratic SGD. Our results have wide applications, especially in online statistical methods. In particular, we discuss two applications of our results. 1) Online robust regression: We consider a corrupted linear model with sub--exponential covariates and heavy--tailed noise. Our analysis provides convergence rates comparable to those for corrupted models with Gaussian covariates and noise. 2) Online quantile regression: Importantly, our results relax the common assumption in prior work that the conditional density is continuous and provide a more fine-grained analysis for the moment bounds. 

   more » « less
5. Construction of Supplemental Functions for Direct Serendipity and Mixed Finite Elements on Polygons

   https://doi.org/10.3390/math11224663  

   Arbogast, Todd; Wang, Chuning (November 2023, Mathematics)

   New families of direct serendipity and direct mixed finite elements on general planar, strictly convex polygons were recently defined by the authors. The finite elements of index r are H1 and H(div) conforming, respectively, and approximate optimally to order r+1 while using the minimal number of degrees of freedom. The shape function space consists of the full set of polynomials defined directly on the element and augmented with a space of supplemental functions. The supplemental functions were constructed as rational functions, which can be difficult to integrate accurately using numerical quadrature rules when the index is high. This can result in a loss of accuracy in certain cases. In this work, we propose alternative ways to construct the supplemental functions on the element as continuous piecewise polynomials. One approach results in supplemental functions that are in Hp for any p≥1. We prove the optimal approximation property for these new finite elements. We also perform numerical tests on them, comparing results for the original supplemental functions and the various alternatives. The new piecewise polynomial supplements can be integrated accurately, and therefore show better robustness with respect to the underlying meshes used. 

   more » « less