Search NASA⌕ Search

SEARCH · Search NASA

Results for “Optimization 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 181 records · Page 10
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Variational design principles for nonequilibrium colloidal assembly

Using large deviation theory and principles of stochastic optimal control, we show that rare molecular dynamics trajectories conditioned on assembling a specific target structure encode a set of interactions and external forces that lead to enhanced stability of that structure. Such a relationship can be formulated into a variational principle, for which we have developed an associated optimization algorithm and have used it to determine optimal forces for targeted self-assembly within nonequilibrium steady-states. We illustrate this perspective on inverse design in a model of colloidal cluster assembly within linear shear flow. We find that colloidal clusters can be assembled with high yield using specific short-range interactions of tunable complexity. Shear decreases the yields of rigid clusters, while small values of shear increase the yields of nonrigid clusters. The enhancement or suppression of the yield due to shear is rationalized with a generalized linear response theory. Furthermore, by studying 21 unique clusters made of six, seven, or eight particles, we uncover basic design principles for targeted assembly out of equilibrium.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2020

Reducing Communication in Graph Neural Network Training

Graph Neural Networks (GNNs) are powerful and flexible neural networks that use the naturally sparse connectivity information of the data. GNNs represent this connectivity as sparse matrices, which have lower arithmetic intensity and thus higher communication costs compared to dense matrices, making GNNs harder to scale to high concurrencies than convolutional or fully-connected neural networks. Here, we introduce a family of parallel algorithms for training GNNs and show that they can asymptotically reduce communication compared to previous parallel GNN training methods. We implement these algorithms, which are based on 1D, 1. 5D, 2D, and 3D sparse-dense matrix multiplication, using torch.distributed on GPU-equipped clusters. Our algorithms optimize communication across the full GNN training pipeline. We train GNNs on over a hundred GPUs on multiple datasets, including a protein network with over a billion edges.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

A non-intrusive parallel-in-time approach for simultaneous optimization with unsteady PDEs

This paper presents a non-intrusive framework for integrating existing unsteady partial differential equation (PDE) solvers into a parallel-in-time simultaneous optimization algorithm. The time-parallelization is provided by the non-intrusive software library XBraid [Parallel multigrid in time, software available at http://llnl.gov/casc/xbraid], which applies an iterative multigrid reduction technique to the time domain of existing time-marching schemes for solving unsteady PDEs. Its general user-interface has been extended in [S. Günther, N.R. Gauger, and J.B. Schroder, A non-intrusive parallel-in-time adjoint solver with the XBraid library, Comput. Vis. Sci. 19 (2018), pp. 85–95. Available at arXiv, math.OC/1705.00663] for computing adjoint sensitivities such that gradients of output quantities with respect to design changes can be computed parallel-in-time alongside with the primal PDE solution. In this paper, the primal and adjoint XBraid iterations are embedded into a simultaneous optimization framework, namely the One-shot method. In this method, design updates towards optimality are employed after each state and adjoint update such that optimality and feasibility of the design and the PDE solution are reached simultaneously. Finally, the time-parallel optimization method is validated on an advection-dominated flow control problem which shows significant speedup over a classical time-serial optimization algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Analog Systems for Edge Optimization

Over the past decade, analog computing has the subject of substantial research interest providing a path toward improved computational efficiency in the post-Dennard era. Analog matrix vector multiplication (MVM) accelerators provide a popular approach given the ubiquity of MVM operations in numerous applications. However, historically analog computing systems can struggle with applications requiring high precision due to the inherent susceptibility of these systems to analog non-idealities. Therefore, prior work on analog systems has focused either on applications known to be tolerant of limited precision (e.g., neural network inference), or using expensive techniques to emulate high-precision using many analog MVM operations. In this work, we propose an alternative approach. Motivated by recent advances in inexact nonlinear solvers and optimizers, we explore the potential of co-designing optimization algorithms which can take full advantage of the fundamentally inexact analog MVM operations. To enable these co-designed algorithms we also develop a general mathematical theory of the precision and energy efficiency of analog operations, and a new system architecture for tightly-coupled analog and digital computation. Finally, we examine the applicability of analog computing to a wider class of symmetric positive definite systems and find potential in using analog operations as a sparse approximate inverse preconditioner. With these core innovations, this project provides a path toward effectively implementing optimization algorithms on power-constrained autonomous and semi-autonomous systems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Automated and highly parallelized Bayesian optimization scheme for direct drive fusion experiments on OMEGA

Finding the optimal implosion design on existing experimental facilities for inertial confinement fusion requires an exhaustive search of the vast design parameter space. This is infeasible both with experiments and with simulations. Consequently, a large fraction of the experimentally realizable design space remains unexplored, and new design schemes are challenging to optimize in a reasonable time frame. On the OMEGA laser facility, predictive machine learning models have been developed to accurately forecast the result of an experiment using only inexpensive simulations and the large dataset of prior experimental data. However, the full design space remains vast enough to be unassailable with simple optimization techniques. Here we develop an automated and optimally parallel Bayesian optimization algorithm that can entirely optimize the target and pulse shape of a direct-drive ICF implosion under a given design paradigm. We use this algorithm to find a markedly improved design for the performance implosions on OMEGA that is predicted to hydroequivalently scale to ignition at 2.15 MJ.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2020

Coupling High-Throughput Experiments and Regression Algorithms to Optimize PGM-Free ORR Electrocatalyst Synthesis

Over the past decades, significant improvement has been achieved in the performance of platinum group metal-free (PGM-free) materials as an alternative to Pt-based electrocatalysts for oxygen reduction reaction (ORR). However, further progress in ORR activity requires evaluation of precursors and synthesis approaches. In response to this challenge, we generated a first of its kind experimental data set of 36 samples using high-throughput synthesis and activity measurements. Several control parameters (e.g., Fe precursor identity, the precursor content, and pyrolysis temperature) were varied. We then developed several state-of-the-art machine learning (ML) based regression models to predict ORR activity, dependent on selected synthesis variables. Through an iterative algorithm, higher prediction accuracy (smaller root-mean-square error) was achieved. We identified that gradient boosting regression (GBR) and support vector regression (SVR), among several methods, work best for this data set. Aided by our ML-based surrogate models, we decided to alter catalyst synthesis conditions, which resulted in a 36% increase in measured ORR activity in comparison to the maximum ORR mass activity value of 21.9 A/g catalyst in the original data set. Overall, this combined experiment and machine learning approach represents a promising path forward toward developing highly efficient next-generation ORR electrocatalysts and, more generally, functional materials.

25 ENERGY STORAGE↗
DOE OSTI2020

Autonomous Intelligent Charging/Discharging of Electric Vehicles using Distributed Multi-Agent ADMM Framework for Grid Ancillary Services

The increasing popularity of Electric Vehicles (EVs) in the distribution grid along with technological advancement in EV electronics such as vehicle to grid (V2G) technique has enabled them to participate in grid ancillary services. To achieve this, the EVs need to establish a contract with third-party aggregators and connect to a charging unit, either residential or commercial. At any time they are connected, the EVs can decide to take part in the ancillary services program offered to them by the aggregators. If agreed, the aggregators will use the EVs as a power source capable of charging/discharging power according to the input signal, and in return, they will be compensated. This inter-temporal nature of charging/discharging is also transforming the traditional optimal power flow (OPF) problem into a dynamic OPF problem. This chapter aims at developing a multi-layer time-dependent optimization algorithm to utilize EV potential and provide ancillary services while maximizing its utilization function. Specifically, in the upper layer, an autonomous distributed ADMM algorithm is developed to optimize the cost for charging/discharging EVs while using them to regulate the voltage at each bus in the distribution grid. The distributed ADMM algorithm is also expanded to the lower layer where the individual EVs active and reactive power is controlled for voltage regulation while maintaining the desired state of the charge of the vehicle at the end of the charging period. Here, the effectiveness and performance improvement of the proposed multi-layer algorithm is illustrated through analytical analysis and simulation results.

Rahman, Towfiq↗
DOE OSTI2020

Autonomous Intelligent Charging/Discharging of Electric Vehicles using Distributed Multi-Agent ADMM Framework for Grid Ancillary Services

The increasing popularity of Electric Vehicles (EVs) in the distribution grid along with technological advancement in EV electronics such as vehicle to grid (V2G) technique has enabled them to participate in grid ancillary services. To achieve this, the EVs need to establish a contract with third-party aggregators and connect to a charging unit, either residential or commercial. At any time they are connected, the EVs can decide to take part in the ancillary services program offered to them by the aggregators. If agreed, the aggregators will use the EVs as a power source capable of charging/discharging power according to the input signal, and in return, they will be compensated. This inter-temporal nature of charging/discharging is also transforming the traditional optimal power flow (OPF) problem into a dynamic OPF problem. This chapter aims at developing a multi-layer time-dependent optimization algorithm to utilize EV potential and provide ancillary services while maximizing its utilization function. Specifically, in the upper layer, an autonomous distributed ADMM algorithm is developed to optimize the cost for charging/discharging EVs while using them to regulate the voltage at each bus in the distribution grid. The distributed ADMM algorithm is also expanded to the lower layer where the individual EVs active and reactive power is controlled for voltage regulation while maintaining the desired state of the charge of the vehicle at the end of the charging period. The effectiveness and performance improvement of the proposed multi-layer algorithm is illustrated through analytical analysis and simulation results.

Rahman, Towfiq↗
DOE OSTI2020

The potential of quantum annealing for rapid solution structure identification

Abstract The recent emergence of novel computational devices, such as quantum computers, coherent Ising machines, and digital annealers presents new opportunities for hardware-accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has the potential to quickly identify the structure of high-quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggests that quantum annealing’s performance on the proposed optimization tasks is distinct. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and suggests the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

DECA: scalable XHMM exome copy-number variant calling with ADAM and Apache Spark

Abstract Background XHMM is a widely used tool for copy-number variant (CNV) discovery from whole exome sequencing data but can require hours to days to run for large cohorts. A more scalable implementation would reduce the need for specialized computational resources and enable increased exploration of the configuration parameter space to obtain the best possible results. Results DECA is a horizontally scalable implementation of the XHMM algorithm using the ADAM framework and Apache Spark that incorporates novel algorithmic optimizations to eliminate unneeded computation. DECA parallelizes XHMM on both multi-core shared memory computers and large shared-nothing Spark clusters. We performed CNV discovery from the read-depth matrix in 2535 exomes in 9.3 min on a 16-core workstation (35.3× speedup vs. XHMM), 12.7 min using 10 executor cores on a Spark cluster (18.8× speedup vs. XHMM), and 9.8 min using 32 executor cores on Amazon AWS’ Elastic MapReduce. We performed CNV discovery from the original BAM files in 292 min using 640 executor cores on a Spark cluster. Conclusions We describe DECA’s performance, our algorithmic and implementation enhancements to XHMM to obtain that performance, and our lessons learned porting a complex genome analysis application to ADAM and Spark. ADAM and Apache Spark are a performant and productive platform for implementing large-scale genome analyses, but efficiently utilizing large clusters can require algorithmic optimizations and careful attention to Spark’s configuration parameters.

Linderman, Michael D. (ORCID:0000000296437148)↗
DOE OSTI2020

Finite-Temperature Structures of Supported Subnanometer Catalysts Inferred via Statistical Learning and Genetic Algorithm-Based Optimization

Single-atom catalysts (SACs) minimize noble metal utilization and can alter the activity and selectivity of supported metal nanoparticles. However, the morphology of active centers, including single atoms and subnanometer clusters of a few atoms, remains elusive due to experimental challenges. The computational cost to describe numerous cluster shapes and sizes makes direct first-principles calculations impractical. We present a computational framework to enable structure determination for single-atom and subnanometer cluster catalysts. As a case study, we obtained the low energy structures of Pd n (n = 1-21) clusters supported on CeO 2 (111), which are critical components of automobile three-way catalysts. Trained on density functional theory data, a three-dimensional cluster expansion is established using statistical learning to describe the Hamiltonian and predict energies of supported Pdn clusters of any structure. Low energy stable and metastable structures are identified using a Metropolis Monte Carlo-based genetic algorithm in the canonical ensemble at 300 K. We observe that supported single atoms sinter to form bilayer clusters and large cluster isomers share similarities in both shape and energy, and elucidate the significance of the support and microstructure on cluster stability. We discovered a simple surrogate structure-energy model, where the energy per atom scales with the square root of the average first coordination number, which can be used to estimate energies and compare the stability of clusters. Our framework, applicable to any metal/support system, fills an important methodological gap to predict the stability of supported metal catalysts in the subnanometer regime.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2023

Optimizing cloud motion estimation on the edge with phase correlation and optical flow

Abstract. Phase correlation (PC) is a well-known method for estimating cloud motion vectors (CMVs) from infrared and visible spectrum images. Commonly, phase shift is computed in the small blocks of the images using the fast Fourier transform. In this study, we investigate the performance and the stability of the blockwise PC method by changing the block size, the frame interval, and combinations of red, green, and blue (RGB) channels from the total sky imager (TSI) at the United States Atmospheric Radiation Measurement user facility's Southern Great Plains site. We find that shorter frame intervals, followed by larger block sizes, are responsible for stable estimates of the CMV, as suggested by the higher autocorrelations. The choice of RGB channels has a limited effect on the quality of CMVs, and the red and the grayscale images are marginally more reliable than the other combinations during rapidly evolving low-level clouds. The stability of CMVs was tested at different image resolutions with an implementation of the optimized algorithm on the Sage cyberinfrastructure test bed. We find that doubling the frame rate outperforms quadrupling the image resolution in achieving CMV stability. The correlations of CMVs with the wind data are significant in the range of 0.38–0.59 with a 95 % confidence interval, despite the uncertainties and limitations of both datasets. A comparison of the PC method with constructed data and the optical flow method suggests that the post-processing of the vector field has a significant effect on the quality of the CMV. The raindrop-contaminated images can be identified by the rotation of the TSI mirror in the motion field. The results of this study are critical to optimizing algorithms for edge-computing sensor systems.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2018

Highway Eco-Driving of an Electric Vehicle Based on Minimum Principle

The digital map in the on-board navigation system on passenger vehicles nowadays gives controllers access to detailed information of a planned route. Connected automated vehicles equipped with high computing power, are able to process data and leverage high control freedom available through automation. This paper proposes a fast optimization algorithm for eco-driving of electric vehicles in highway cruising scenarios. The algorithm is based on optimal control theory and takes into account road grades as well as state constraints imposed by speed limits and safe headway to the preceding car. Using Autonomie, the proposed algorithm is evaluated by simulating two example scenarios. The first result demonstrates an energy saving potential of 4.4%.

connected automated vehicle↗
DOE OSTI2018

Quantum Optimization and Approximation Algorithms

Shor's groundbreaking quantum algorithm for integer factoring provides an exponential speedup over the best-known classical algorithms. In the 20 years since Shor's algorithm was conceived, only a handful of fundamental quantum algorithmic kernels, generally providing modest polynomial speedups over classical algorithms, have been invented. To better understand the potential advantage quantum resources provide over their classical counterparts, one may consider other resources than execution time of algorithms. Quantum Approximation Algorithms direct the power of quantum computing towards optimization problems where quantum resources provide higher-quality solutions instead of faster execution times. We provide a new rigorous analysis of the recent Quantum Approximate Optimization Algorithm, demonstrating that it provably outperforms the best known classical approximation algorithm for special hard cases of the fundamental Maximum Cut graph-partitioning problem. We also develop new types of classical approximation algorithms for finding near-optimal low-energy states of physical systems arising in condensed matter by extending seminal discrete optimization techniques. Our interdisciplinary work seeks to unearth new connections between discrete optimization and quantum information science.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Dual-map framework for noise characterization of quantum computers

In order to understand the capabilities and limitations of quantum computers, it is necessary to develop methods that efficiently characterize and benchmark error channels present on these devices. In this paper, we present a method that faithfully reconstructs a marginal (local) approximation of the effective noise (MATEN) channel, that acts as a single layer at the end of the circuit. We first introduce a dual-map framework that allows us to analytically derive expectation values of observables with respect to noisy circuits. These findings are supported by numerical simulations of the quantum approximate optimization algorithm (QAOA) that also justify the MATEN, even in the presence of nonlocal errors that occur during a circuit. Finally, we demonstrate the performance of the method on Rigetti's Aspen-11 quantum computer for QAOA circuits up to six qubits, successfully predicting the observed measurements on a majority of the qubits.

Sud, James↗
DOE OSTI2023

Communication-Constrained Robust Control and Learning of Grid-Connected

The electric grid of things (EGoT) promises great potential for innovative grid services by tapping into vast load flexibility. However, the unique characteristics of EGoT, being a part of the cyber-physical electric power system, present both opportunities and challenges, especially concerning supply-demand balancing, stability, and communication constraints. Traditionally, centralized control was employed to ensure balance and stability in power systems. However, with the massive influx of EGoT devices, new strategies are needed to efficiently coordinate and control these distributed devices for optimal grid operations. While some studies have explored efficiency and economic models, there remains a gap in ensuring reliability under everyday operations and resilience during extreme conditions. Addressing this gap, this project develops the technology for an Energy Service Interface (ESI) that includes novel pricing, control, learning, and distributed optimization algorithms, which will enable utilities to recruit EGoT assets for crucial grid services such as load flexibility, voltage regulation, and situation-awareness. The key novelty of the proposed technology is the careful distribution of learning and control functions across utility and EGoT asset owners such that provably efficient and resilient grid operations are attained while respecting communication and information-exchange constraints. Specifically, the project team develops machine-learning enhanced load modeling methods to allow EGoT asset owners to learn their load capability and flexibility, and develops pricing-based and decentralized learning-based control so that asset owners can coordinate to meet system-wide demand-supply balance and reliability goals. For extreme situations involving high-impact, low-probability catastrophic events (termed the “black-sky” events), the team also develops (1) a “Feeder-Operating Center-on-a-Laptop” (FOCAL) software that can assist utility personnel in leveraging EGoT assets to accelerate the service recovery of damaged feeders, and (2) distributed optimization algorithms that can coordinate the operation points of EGoT devices under severe communication constraints. The proposed technology has been extensively tested and evaluated through simulations and on a testbed. In summary, as we transition into a more interconnected and digital power grid era, our project’s findings and developments offer a pivotal step toward guaranteeing both efficiency and resilience in the face of both everyday operations and rare “black-sky” events.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2026

Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms

The emergent practical applicability of the Quantum Approximate Optimization Algorithm (QAOA) for approximate combinatorial optimization is a subject of considerable interest. One of the primary limitations of QAOA is the task of finding a set of good parameters, which is usually done using a variational optimization loop. Parameter transfer, or parameter concentration, is a phenomenon where QAOA angles trained on problem instances that are self-similar tend to perform well for other problem instances from that similar class. This suggests a potentially highly efficient and scalable non-variational learning method for QAOA angle finding. In this work, we systematically study QAOA parameter transferability from small problem sizes (16 and 27 decision variables) onto large problem instances (up to 156 qubits) for heavy-hex graph Ising models with geometrically local higher order terms using the Julia based QAOA simulation tool \texttt{JuliQAOA} to perform classical angle finding for up to $49$ QAOA layers ($p$). Parameter transfer of the fixed angles is validated using a combination of full statevector, Projected Entangled Pair States (PEPS), Matrix Product State (MPS), and LOWESA numerical simulations. We find that the QAOA parameter transfer from single instances applied to other (unseen) problem instances does not in general provide monotonically improving performance as a function of $p$ - there are many cases where the performance temporarily decreases as a function of $p$ - but despite this the transferred angles have a general trend of improved expectation value as the QAOA depth increases, in many cases converging close to the true ground-state energy of the $100+$ qubit instances. We also sample the hardware-compatible Ising models using the ensemble of transfer-learned QAOA parameters on several superconducting qubit IBM Quantum processors with 127, 133, and 156 qubits. We find continuous solution quality improvement of the hardware-compatible QAOA circuits run on the IBM NISQ processors up to $p=5$ on \texttt{ibm\_fez}, up to $p=9$ on \texttt{ibm\_torino}, and up to $p=10$ on \texttt{ibm\_pittsburgh}.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2020

LCOE Design Optimization Using Genetic Algorithm with Improved Component Models for Medium-Voltage Transformerless PV Inverters

For real-world installations of photovoltaic and other renewable energy resources, the critical design metric is the levelized cost of energy (LCOE); however, many power electronics design optimizations are performed with efficiency and power density as the primary design goals. Recent work has shown that a new LCOE-focused optimization approach can yield improved system designs balancing cost and energy generation. This paper expands the LCOE optimization approach by considering comprehensive optimization parameters, adding new modeling of inductor cost, extending the semiconductor model to include effects of losses on housing cost, and implementing a genetic algorithm to improve computation efficiency.

41 EE - Solar Energy Technologies Office (EE-4S)↗