Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,567 records · Page 87

WRF-simulated low-level jets over Iowa: characterization and sensitivity studies

Abstract. Output from 6 months of high-resolution simulations with the Weather Research and Forecasting (WRF) model are analyzed to characterize local low-level jets (LLJs) over Iowa for winter and spring in the contemporary climate. Low-level jets affect rotor plane aerodynamic loading, turbine structural loading and turbine performance, and thus accurate characterization and identification are pertinent. Analyses using a detection algorithm wherein the wind speed above and below the jet maximum must be below 80 % of the jet wind speed within a vertical window of approximately 20–530 m a.g.l. (above ground level) indicate the presence of an LLJ in at least one of the 14 700 4 km×4 km grid cells over Iowa on 98 % of nights. Nocturnal LLJs are most frequently associated with stable stratification and low turbulent kinetic energy (TKE) and hence are more frequent during the winter months. The spatiotemporal mean LLJ maximum (jet core) wind speed is 9.55 m s−1, and the mean height is 182 m. Locations of high LLJ frequency and duration across the state are seasonally varying, with a mean duration of 3.5 h. The highest frequency occurs in the topographically complex northwest of the state in winter and in the flatter northeast of the state in spring. Sensitivity of LLJ characteristics to the (i) LLJ definition and (ii) vertical resolution at which the WRF output is sampled is examined. LLJ definitions commonly used in the literature are considered in the first sensitivity analysis. These sensitivity analyses indicate that LLJ characteristics are highly variable with definition. Use of different definitions identifies both different frequencies of LLJs and different LLJ events. Further, when the model output is down-sampled to lower vertical resolution, the mean jet core wind speed height decreases, but spatial distributions of regions of high frequency and duration are conserved. Implementation of a polynomial interpolation to extrapolate down-sampled output to full-resolution results in reduced sensitivity of LLJ characteristics to down-sampling.

17 WIND ENERGY↗

Online Energy-optimal Routing for Electric Vehicles with Combinatorial Multi-arm Semi-Bandit

We have seen a rapid growth in the adoption of electric vehicle in today’s commercial mobility service market, from carrying passengers to the delivery of goods. One cardinal issue concerning the operation of EVs is the optimal routing of EV fleets with limited battery capacity. In this study, we investigate the energy-optimal online routing problem for the fleet of EVs, which focuses on identifying real-time minimum electricity consumption paths (MECP) for multiple OD pairs with limited information. We develop a multi-OD combinatorial multi-arm semi-bandit model (MCMAB) that uses the fleet of EVs as sensors in the transportation network and promotes the utilization of common information shared by different OD pairs. We further enrich the model with the path elimination policy to obtain MECP of high confidence while significantly reducing the number of learning iterations and the number of explorations needed. We demonstrate the effectiveness of the MCMAB and the efficiency of the path elimination policy with comprehensive numerical experiments in Manhattan, NYC. The results show that the proposed online routing algorithms can achieve near-optimal MECPs efficiently, and the quality of the solutions is significantly better than using the shortest travel time paths as approximate MECPs.

Chen, Xiaowei↗

Generalized Quantum Signal Processing

Quantum signal processing (QSP) and quantum singular value transformation (QSVT) currently stand as the most efficient techniques for implementing functions of block-encoded matrices, a central task that lies at the heart of most prominent quantum algorithms. However, current QSP approaches face several challenges, such as the restrictions imposed on the family of achievable polynomials and the difficulty of calculating the required phase angles for specific transformations. In this paper, we present a generalized quantum signal processing (GQSP) approach, employing general SU(2) rotations as our signal-processing operators, rather than relying solely on rotations in a single basis. Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that | P | ≤ 1 , a restriction necessary due to the unitary nature of quantum computation. Furthermore, GQSP provides a straightforward recursive formula for determining the rotation angles needed to construct the polynomials in cases where P and Q are known. In cases where only P is known, we provide an efficient optimization algorithm capable of identifying in under a minute of GPU time, a corresponding Q for polynomials of degree on the order of 10 7 . We further illustrate GQSP simplifies QSP-based strategies for Hamiltonian simulation, offer an optimal solution to the ϵ -approximate fractional query problem that requires O ( ( 1 / δ ) + log ( 1 / ϵ ) ) queries to perform where O ( 1 / δ ) is a proved lower bound, and introduces novel approaches for implementing bosonic operators. Moreover, we propose a novel framework for the implementation of normal matrices, demonstrating its applicability through synthesis of diagonal matrices, as well as the development of a new algorithm for convolution through synthesis of circulant matrices using only O ( d log N + log 2 N ) 1 and 2-qubit gates for a filter of lengths d . Published by the American Physical Society 2024

Motlagh, Danial↗

PROCESS SIMULATION OF COLD PRESSING OF ARMSTRONG CP-Ti POWDERS

A computational methodology is presented for the process simulation of cold pressing of Armstrong CP-Ti Powders. The computational model was implemented in the commercial finite element program ABAQUSTM. Since the powder deformation and consolidation is governed by specific pressure-dependent constitutive equations, several solution algorithms were developed for the ABAQUS user material subroutine, UMAT. The solution algorithms were developed for computing the plastic strain increments based on an implicit integration of the nonlinear yield function, flow rule, and hardening equations that describe the evolution of the state variables. Since ABAQUS requires the use of a full Newton-Raphson algorithm for the stress-strain equations, an algorithm for obtaining the tangent/linearization moduli, which is consistent with the return-mapping algorithm, also was developed. Numerical simulation results are presented for the cold compaction of the Ti powders. Several simulations were conducted for cylindrical samples with different aspect ratios. The numerical simulation results showed that for the disk samples, the minimum von Mises stress was approximately half than its maximum value. The hydrostatic stress distribution exhibits a variation smaller than that of the von Mises stress. It was found that for the disk and cylinder samples the minimum hydrostatic stresses were approximately 23 and 50% less than its maximum value, respectively. It was also found that the minimum density was noticeably affected by the sample height.

36 MATERIALS SCIENCE↗

molgw 1: Many-body perturbation theory software for atoms, molecules, and clusters

Here, we summarize the MOLGW code that implements density-functional theory and many-body perturbation theory in a Gaussian basis set. The code is dedicated to the calculation of the many-body self-energy within the GW approximation and the solution of the Bethe–Salpeter equation. These two types of calculations allow the user to evaluate physical quantities that can be compared to spectroscopic experiments. Quasiparticle energies, obtained through the calculation of the GW self-energy, can be compared to photoemission or transport experiments, and neutral excitation energies and oscillator strengths, obtained via solution of the Bethe–Salpeter equation, are measurable by optical absorption. The implementation choices outlined here have aimed at the accuracy and robustness of calculated quantities with respect to measurements. Furthermore, the algorithms implemented in MOLGW allow users to consider molecules or clusters containing up to 100 atoms with rather accurate basis sets, and to choose whether or not to apply the resolution-of-the-identity approximation. Finally, we demonstrate the parallelization efficacy of the MOLGW code over several hundreds of processors.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Generalized Quantum Convolution for Multidimensional Data

The convolution operation plays a vital role in a wide range of critical algorithms across various domains, such as digital image processing, convolutional neural networks, and quantum machine learning. In existing implementations, particularly in quantum neural networks, convolution operations are usually approximated by the application of filters with data strides that are equal to the filter window sizes. One challenge with these implementations is preserving the spatial and temporal localities of the input features, specifically for data with higher dimensions. In addition, the deep circuits required to perform quantum convolution with a unity stride, especially for multidimensional data, increase the risk of violating decoherence constraints. In this work, we propose depth-optimized circuits for performing generalized multidimensional quantum convolution operations with unity stride targeting applications that process data with high dimensions, such as hyperspectral imagery and remote sensing. We experimentally evaluate and demonstrate the applicability of the proposed techniques by using real-world, high-resolution, multidimensional image data on a state-of-the-art quantum simulator from IBM Quantum.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Incomplete Sparse Approximate Inverses for Parallel Preconditioning

In this study, we propose a new preconditioning method that can be seen as a generalization of block-Jacobi methods, or as a simplification of the sparse approximate inverse (SAI) preconditioners. The “Incomplete Sparse Approximate Inverses” (ISAI) is in particular efficient in the solution of sparse triangular linear systems of equations. Those arise, for example, in the context of incomplete factorization preconditioning. ISAI preconditioners can be generated via an algorithm providing fine-grained parallelism, which makes them attractive for hardware with a high concurrency level. Finally, in a study covering a large number of matrices, we identify the ISAI preconditioner as an attractive alternative to exact triangular solves in the context of incomplete factorization preconditioning.

97 MATHEMATICS AND COMPUTING↗

Monte Carlo chord length sampling for d-dimensional Markov binary mixtures

The Chord Length Sampling (CLS) algorithm is a powerful Monte Carlo method that models the effects of stochastic media on particle transport by generating on-the-fly the material interfaces seen by the random walkers during their trajectories. This annealed disorder approach, which formally consists of solving the approximate Levermore–Pomraning equations for linear particle transport, enables a considerable speed-up with respect to transport in quenched disorder, where ensemble-averaging of the Boltzmann equation with respect to all possible realizations is needed. However, CLS intrinsically neglects the correlations induced by the spatial disorder, so that the accuracy of the solutions obtained by using this algorithm must be carefully verified with respect to reference solutions based on quenched disorder realizations. When the disorder is described by Markov mixing statistics, such comparisons have been attempted so far only for one-dimensional geometries, of the rod or slab type. In this work we extend these results to Markov media in two-dimensional (extruded) and three-dimensional geometries, by revisiting the classical set of benchmark configurations originally proposed by Adams, Larsen and Pomraning and extended by Brantley. In particular, we examine the discrepancies between CLS and reference solutions for scalar particle flux and transmission/reflection coefficients as a function of the material properties of the benchmark specifications and of the system dimensionality.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Parallel fast gauss transform

We present fast adaptive parallel algorithms to compute the sum of N Gaussians at N points. Direct sequential computation of this sum would take O(N{sup 2}) time. The parallel time complexity estimates for our algorithms are O(N/n{sub p}) for uniform point distributions and O( (N/n{sub p}) log (N/n{sub p}) + n{sub p}log n{sub p}) for non-uniform distributions using n{sub p} CPUs. We incorporate a plane-wave representation of the Gaussian kernel which permits 'diagonal translation'. We use parallel octrees and a new scheme for translating the plane-waves to efficiently handle non-uniform distributions. Computing the transform to six-digit accuracy at 120 billion points took approximately 140 seconds using 4096 cores on the Jaguar supercomputer. Our implementation is 'kernel-independent' and can handle other 'Gaussian-type' kernels even when explicit analytic expression for the kernel is not known. These algorithms form a new class of core computational machinery for solving parabolic PDEs on massively parallel architectures.

99 GENERAL AND MISCELLANEOUS↗

Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decomposition

This report demonstrates satisfactory data compression of SOLPS-ITER simulation output ranging from 2D fields, 1D profiles, and 0D scalar variables with a novel matrix decomposition approach. The singular value decomposition (SVD) scales poorly for large matrix sizes and is unsuited to the application on high dimensional data common to fusion plasma physics simulation. In this work, we employ the columns-submatrix-rows (CUR) matrix factorization technique in order to compute a low-rank approximation up to two orders of magnitude faster than the SVD, but within a nominal L2-norm relative error of ε = 10 –2 . In addition, the CUR approach maintains the original format of the data, in its extracted columns and rows, allowing for interpretable data storage at the original resolution of the simulation. We utilize an iterative algorithm to compute the CUR decomposition of simulation output by maximizing the volume, or linearly independent information content, of a low-rank submatrix contained within the data. Experiments over $\textit{n} × \textit{n}$ randomized test matrices with embedded rank-deficient features show that this maximum volume implementation of CUR matrix approximation has reduced asymptotic computational complexity on the order of n compared to the SVD, which scales approximately as $n^3$. These results show that the CUR technique can be used to effectively select time step snapshots (columns) of over 140 SOLPS-ITER output variables and the associated discretized coordinate timeseries (rows) allowing for reconstruction of the complete simulation dynamics.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Exactly unitary discrete representations of the metaplectic transform for linear-time algorithms

The metaplectic transform (MT), a generalization of the Fourier transform sometimes called the linear canonical transform, is a tool used ubiquitously in modern optics, for example, when calculating the transformations of light beams in paraxial optical systems. The MT is also an essential ingredient of the geometrical-optics modeling of caustics that we recently proposed. In particular, this application relies on the near-identity MT (NIMT); however, the NIMT approximation used so far is not exactly unitary and leads to numerical instability. Here, we develop a discrete MT that is exactly unitary, and approximate it to obtain a discrete NIMT that is also unitary and can be computed in linear time. We prove that the discrete NIMT converges to the discrete MT when iterated, thereby allowing the NIMT to compute MTs that are not necessarily near-identity. Finally, we then demonstrate the new algorithms with a series of examples.

47 OTHER INSTRUMENTATION↗

Stochastic Optimization for Grid Resilience. FY18 Final Technical Report

The optimal restoration problem lies at the foundation of the evaluation and improvement of resilience in power systems. In this report we present a scalable decomposition algorithm for solving this problem for realistic power systems. The algorithm has been developed in three major research threads, corresponding to the chapters in the present report. Chapter 1 studies mixed-integer programming (MIP) formulations for the requirement that each electrical island that appears after a recon guration must have at least one energized generator. We provide three alternative MIP formulations for this restriction, show their equivalence, and prove that two of them are stronger in terms of their linear programming relaxation than the formulation most commonly used in the power systems literature. Since the time to solve MIPs can vary signi cantly between equivalent formulations, we also present computational experiments on IEEE test systems for the Intentional Controlled Islanding (ICI) and the Black Start Allocation (BSA) problems. We observe that a polynomially separable, exponential in size, strong formulation yields the best performance for the BSA problem and exhibits a comparable performance to a linear in size, weak formulation for the ICI problem. Chapter 2 presents a methodology to generate mixed-integer linear approximations of the AC power ow equations governing lines, transformers (including tap regulators and phase shifters), shunt and series compensators, and consumption responsive to voltage. Our approximations are capable of capturing limitations for power grids under abnormal or uncommon operating conditions where common assumptions used in power ow relaxations may not hold. Particularly, the approximation captures overvoltages under almost no load, which is a major concern when energizing lines after a blackout. The method constructs piecewise linear approximations of the non-linear power ow equations by minimizing the squared approximation error over a subset of the feasible domain. We test the method using a realistic database for the Chilean system (1548 buses, 1114 lines, 564 transformers). The resulting approximations yield root mean square errors in the order of 0.05pu and are successfully applied to solve a transmission switching instance for the Chilean system. Chapter 3 presents our algorithm for optimal restoration. The algorithm works by partitioning the problem into a master problem and a slave problem. The master problem optimizes over energization sequences of generators, buses and branches, for the entire restoration horizon, while respecting the energization requiments studied in Chapter 1. The slave problem veri es that there exist power ow solutions supporting the energization sequences proposed by the master problem, adding cuts to the master if an infeasible sequence is detected.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Applications of the worldline Monte Carlo formalism in quantum mechanics

Highlights: Universal approach to the numerical computation of the Euclidean path integral. Inspired by recent work in relativistic quantum field theory. Here adapted to non-relativistic quantum mechanics. Worked out for the computation of propagators and ground-state energies. Special smoothing procedure for singular potentials. -- Abstract: In recent years efficient algorithms have been developed for the numerical computation of relativistic single-particle path integrals in quantum field theory. Here, we adapt this “worldline Monte Carlo” approach to the standard problem of the numerical approximation of the non-relativistic path integral, resulting in a formalism whose characteristic feature is the fast, non-recursive generation of an ensemble of trajectories that is independent of the potential, and is thus universally applicable. The numerical implementation discretises the trajectories with respect to their time parametrisation but maintains a continuous spatial domain. In the case of singular potentials, the discretised action gets adapted to the singularity through a “smoothing” procedure. We show for a variety of examples (the harmonic oscillator in various dimensions, the modified Pöschl–Teller potential, delta-function potentials, the Coulomb and Yukawa potentials) that the method allows one to obtain fast and reliable estimates for the Euclidean propagator and use them in a certain time window suitable for extracting the ground state energy. Usually Monte Carlo calculations in quantum mechanics are performed using algorithms that involve a more specific adaptation to the potential, and we briefly compare our method with the most widely used such algorithms, which are of Metropolis type. As an aside, we apply it for studying the classical limit where nearly classical trajectories are expected to dominate in the path integral. We expect the advances made here to be useful also in the relativistic case.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

SU-E-T-458: Determining Threshold-Of-Failure for Dead Pixel Rows in EPID-Based Dosimetry

Purpose: A pixel correction map is applied to all EPID-based applications on the TrueBeam (Varian Medical Systems, Palo Alto, CA). When dead pixels are detected, an interpolative smoothing algorithm is applied using neighboring-pixel information to supplement missing-pixel information. The vendor suggests that when the number of dead pixels exceeds 70,000, the panel should be replaced. It is common for entire detector rows to be dead, as well as their neighboring rows. Approximately 70 rows can be dead before the panel reaches this threshold. This study determines the number of neighboring dead-pixel rows that would create a large enough deviation in measured fluence to cause failures in portal dosimetry (PD). Methods: Four clinical two-arc VMAT plans were generated using Eclipse's AXB algorithm and PD plans were created using the PDIP algorithm. These plans were chosen to represent those commonly encountered in the clinic: prostate, lung, abdomen, and neck treatments. During each iteration of this study, an increasing number of dead-pixel rows are artificially applied to the correction map and a fluence QA is performed using the EPID (corrected with this map). To provide a worst-case-scenario, the dead-pixel rows are chosen so that they present artifacts in the highfluence region of the field. Results: For all eight arc-fields deemed acceptable via a 3%/3mm gamma analysis (pass rate greater than 99%), VMAT QA yielded identical results with a 5 pixel-width dead zone. When 10 dead lines were present, half of the fields had pass rates below the 99% pass rate. With increasing dead rows, the pass rates were reduced substantially. Conclusion: While the vendor still suggests to request service at the point where 70,000 dead rows are measured (as recommended by the vendor), the authors suggest that service should be requested when there are greater than 5 consecutive dead rows.

60 APPLIED LIFE SCIENCES↗

Physics based model for online fault detection in autonomous cryogenic loading system

We report the progress in the development of the chilldown model for a rapid cryogenic loading system developed at NASA-Kennedy Space Center. The nontrivial characteristic feature of the analyzed chilldown regime is its active control by dump valves. The two-phase flow model of the chilldown is approximated as one-dimensional homogeneous fluid flow with no slip condition for the interphase velocity. The model is built using commercial SINDA/FLUINT software. The results of numerical predictions are in good agreement with the experimental time traces. The obtained results pave the way to the application of the SINDA/FLUINT model as a verification tool for the design and algorithm development required for autonomous loading operation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Evaluation of the spline reconstruction technique for PET

Purpose: The spline reconstruction technique (SRT), based on the analytic formula for the inverse Radon transform, has been presented earlier in the literature. In this study, the authors present an improved formulation and numerical implementation of this algorithm and evaluate it in comparison to filtered backprojection (FBP). Methods: The SRT is based on the numerical evaluation of the Hilbert transform of the sinogram via an approximation in terms of “custom made” cubic splines. By restricting reconstruction only within object pixels and by utilizing certain mathematical symmetries, the authors achieve a reconstruction time comparable to that of FBP. The authors have implemented SRT in STIR and have evaluated this technique using simulated data from a clinical positron emission tomography (PET) system, as well as real data obtained from clinical and preclinical PET scanners. For the simulation studies, the authors have simulated sinograms of a point-source and three digital phantoms. Using these sinograms, the authors have created realizations of Poisson noise at five noise levels. In addition to visual comparisons of the reconstructed images, the authors have determined contrast and bias for different regions of the phantoms as a function of noise level. For the real-data studies, sinograms of an{sup 18}F-FDG injected mouse, a NEMA NU 4-2008 image quality phantom, and a Derenzo phantom have been acquired from a commercial PET system. The authors have determined: (a) coefficient of variations (COV) and contrast from the NEMA phantom, (b) contrast for the various sections of the Derenzo phantom, and (c) line profiles for the Derenzo phantom. Furthermore, the authors have acquired sinograms from a whole-body PET scan of an {sup 18}F-FDG injected cancer patient, using the GE Discovery ST PET/CT system. SRT and FBP reconstructions of the thorax have been visually evaluated. Results: The results indicate an improvement in FWHM and FWTM in both simulated and real point-source studies. In all simulated phantoms, the SRT exhibits higher contrast and lower bias than FBP at all noise levels, by increasing the COV in the reconstructed images. Finally, in real studies, whereas the contrast of the cold chambers are similar for both algorithms, the SRT reconstructed images of the NEMA phantom exhibit slightly higher COV values than those of FBP. In the Derenzo phantom, SRT resolves the 2-mm separated holes slightly better than FBP. The small-animal and human reconstructions via SRT exhibit slightly higher resolution and contrast than the FBP reconstructions. Conclusions: The SRT provides images of higher resolution, higher contrast, and lower bias than FBP, by increasing slightly the noise in the reconstructed images. Furthermore, it eliminates streak artifacts outside the object boundary. Unlike other analytic algorithms, the reconstruction time of SRT is comparable with that of FBP. The source code for SRT will become available in a future release of STIR.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Rays for Roots - Integrating Backscatter X-Ray Phenotyping, Modeling and Genetics to Increase Carbon Sequestration and Switchgrass Resource Use (Final Report)

To increase carbon (C) deposition in the soil and enhance crop resource use efficiency, characterizing root form and function is essential. Several root and soil traits have been linked to increased root-to-soil C transfer. Technology that could provide high-resolution characterization of many of these traits in field conditions would revolutionize our ability to study and understand how to increase C sequestration. In this effort, we developed an initial early prototype backscatter X-ray system for non-destructive imaging of root traits. We collected initial backscatter X-ray data in field and lab settings and carried out early analysis of these data. Along with this prototype, we also developed a suite of root phenotyping approaches including advanced minirhizotron image analysis, soil core imaging, and mesocosm imaging. Minirhizotron (MR) tubes are clear tubes inserted into the soil in the field and used to image roots and the surrounding soil. Our team has developed deep learning-based methods that can segment roots from soil that can learn from imprecise image-level labels. The ability to learn or fine-tune our deep learning algorithms from image-level labels allows easier and faster application of these approaches to new locations and new plant species. We have successfully implemented and applied our MR analysis approaches to thousands of switchgrass MR images collected across geographical regions. An advantage of MR imaging is the ability to collect root and soil images over time. Our soil core analysis included collecting hundreds of soil core samples from harvested switchgrass fields and imaging these cores with both X-ray CT and backscatter X-ray imaging. Initial segmentation approaches for the X-ray CT images of these cores have been developed and applied. An advantage of soil core analysis is that it preserves the three-dimensional structures of the roots and soil in the core collected. Our group also developed photogrammetry-based mesocosm root imaging and phenotyping approaches. In this approach, a plant was grown in a large mesocosm with a three-dimensional grid of thin supporting lines inserted throughout the mesocosm. After the plant (and, correspondingly, the root architecture is grown and established) the soil media was removed and the supporting lines approximately preserved the three-dimensional root architecture. Then, we applied photogrammetry techniques to create a three-dimensional digital representation of the root architecture for which we developed analysis algorithms including skeletonization. We carried out our phenotyping development with powerful switchgrass resources and physiological and agroecosystem modeling to deliver novel technology. This project contributes to multiple ARPA-E missions including reduction of foreign imports of energy, reduction of energy-related emissions including greenhouse gases, and ensuring that the United States maintains a technological lead in developing and deploying advanced energy technology. Furthermore, the developed tools could transform public and private plant breeding and could be broadly applicable to other crops and, potentially, other application areas. Our team of engineers, plant and soil scientists, and modelers i) developed an early prototype backscatter X-ray platform that can operate in field conditions; ii) developed a suite of root phenotyping and characterization approaches as described above; iii) developed and carried out plant biology and physiology roots studies and; iv) developed and implemented mechanistic physiological modeling.

42 ENGINEERING↗

Inexact Newton-CG algorithms with complexity guarantees

Abstract We consider variants of a recently developed Newton-CG algorithm for nonconvex problems (Royer, C. W. & Wright, S. J. (2018) Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477) in which inexact estimates of the gradient and the Hessian information are used for various steps. Under certain conditions on the inexactness measures, we derive iteration complexity bounds for achieving $\epsilon $-approximate second-order optimality that match best-known lower bounds. Our inexactness condition on the gradient is adaptive, allowing for crude accuracy in regions with large gradients. We describe two variants of our approach, one in which the step size along the computed search direction is chosen adaptively, and another in which the step size is pre-defined. To obtain second-order optimality, our algorithms will make use of a negative curvature direction on some steps. These directions can be obtained, with high probability, using the randomized Lanczos algorithm. In this sense, all of our results hold with high probability over the run of the algorithm. We evaluate the performance of our proposed algorithms empirically on several machine learning models. Our approach is a first attempt to introduce inexact Hessian and/or gradient information into the Newton-CG algorithm of Royer & Wright (2018, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477).

Mathematics↗