Search NASA⌕ Search

SEARCH · Search NASA

Results for “Search algorithm”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1998

A Globally Convergent Augmented Lagrangian Pattern Search Algorithm for Optimization with General Constraints and Simple Bounds

We give a pattern search adaptation of an augmented Lagrangian method due to Conn, Gould, and Toint. The algorithm proceeds by successive bound constrained minimization of an augmented Lagrangian. In the pattern search adaptation we solve this subproblem approximately using a bound constrained pattern search method. The stopping criterion proposed by Conn, Gould, and Toint for the solution of this subproblem requires explicit knowledge of derivatives. Such information is presumed absent in pattern search methods; however, we show how we can replace this with a stopping criterion based on the pattern size in a way that preserves the convergence properties of the original algorithm. In this way we proceed by successive, inexact, bound constrained minimization without knowing exactly how inexact the minimization is. So far as we know, this is the first provably convergent direct search method for general nonlinear programming.

Lewis, Robert Michael↗
NASA NTRS1996

Pattern Search Algorithms for Bound Constrained Minimization

We present a convergence theory for pattern search methods for solving bound constrained nonlinear programs. The analysis relies on the abstract structure of pattern search methods and an understanding of how the pattern interacts with the bound constraints. This analysis makes it possible to develop pattern search methods for bound constrained problems while only slightly restricting the flexibility present in pattern search methods for unconstrained problems. We prove global convergence despite the fact that pattern search methods do not have explicit information concerning the gradient and its projection onto the feasible region and consequently are unable to enforce explicitly a notion of sufficient feasible decrease.

Lewis, Robert Michael↗
NASA NTRS2009

Tactical Synthesis Of Efficient Global Search Algorithms

Algorithm synthesis transforms a formal specification into an efficient algorithm to solve a problem. Algorithm synthesis in Specware combines the formal specification of a problem with a high-level algorithm strategy. To derive an efficient algorithm, a developer must define operators that refine the algorithm by combining the generic operators in the algorithm with the details of the problem specification. This derivation requires skill and a deep understanding of the problem and the algorithmic strategy. In this paper we introduce two tactics to ease this process. The tactics serve a similar purpose to tactics used for determining indefinite integrals in calculus, that is suggesting possible ways to attack the problem.

Nedunuri, Srinivas↗
NASA NTRS1997

When Gravity Fails: Local Search Topology

Local search algorithms for combinatorial search problems frequently encounter a sequence of states in which it is impossible to improve the value of the objective function; moves through these regions, called {\em plateau moves), dominate the time spent in local search. We analyze and characterize {\em plateaus) for three different classes of randomly generated Boolean Satisfiability problems. We identify several interesting features of plateaus that impact the performance of local search algorithms. We show that local minima tend to be small but occasionally may be very large. We also show that local minima can be escaped without unsatisfying a large number of clauses, but that systematically searching for an escape route may be computationally expensive if the local minimum is large. We show that plateaus with exits, called benches, tend to be much larger than minima, and that some benches have very few exit states which local search can use to escape. We show that the solutions (i.e. global minima) of randomly generated problem instances form clusters, which behave similarly to local minima. We revisit several enhancements of local search algorithms and explain their performance in light of our results. Finally we discuss strategies for creating the next generation of local search algorithms.

Frank, Jeremy↗
NASA NTRS1991

Phase retrieval for the Hubble Space Telescope using iterative propagation algorithms

Phase retrieval algorithms, including the iterative transform algorithm and gradient search algorithms, were generalized to include the effects of propagation through a complicated optical system and to discount the effects of bad CCD pixels. For the gradient search algorithms, analytic gradients were derived that greatly speed up the computation over finite difference methods. For the Hubble Space Telescope (HST), the aperture function was reconstructed and the phase errors were retrieved. This information is useful to design correction optics for the telescope and for the deconvolution of blurred images from the HST.

Fienup, J. R.↗
NASA NTRS2010

Exhaustive Versus Randomized Searchers for Nonlinear Optimization in 21st Century Computing: Solar Application

We present a simple multi-dimensional exhaustive search method to obtain, in a reasonable time, the optimal solution of a nonlinear programming problem. It is more relevant in the present day non-mainframe computing scenario where an estimated 95% computing resources remains unutilized and computing speed touches petaflops. While the processor speed is doubling every 18 months, the band width is doubling every 12 months, and the hard disk space is doubling every 9 months. A randomized search algorithm or, equivalently, an evolutionary search method is often used instead of an exhaustive search algorithm. The reason is that a randomized approach is usually polynomial-time, i.e., fast while an exhaustive search method is exponential-time i.e., slow. We discuss the increasing importance of exhaustive search in optimization with the steady increase of computing power for solving many real-world problems of reasonable size. We also discuss the computational error and complexity of the search algorithm focusing on the fact that no measuring device can usually measure a quantity with an accuracy greater than 0.005%. We stress the fact that the quality of solution of the exhaustive search - a deterministic method - is better than that of randomized search. In 21 st century computing environment, exhaustive search cannot be left aside as an untouchable and it is not always exponential. We also describe a possible application of these algorithms in improving the efficiency of solar cells - a real hot topic - in the current energy crisis. These algorithms could be excellent tools in the hands of experimentalists and could save not only large amount of time needed for experiments but also could validate the theory against experimental results fast.

Sen, Syamal K.↗
NASA NTRS2021

Comparison of Type 2 versus Type 3 Carrier Tracking Loops under High Dynamic Signal Conditions

Virtually all deep-space missions today and in the past employed Type 2 tracking loops in their spacecraft receivers. This was acceptable since the uplink from a single ground antenna makes use of very accurate trajectory information where the radiated frequency is Doppler compensated. However, in the desire to conserve ground resources, the technique of Multiple Uplinks per Antenna (MUPA) is being considered when using a single ground antenna to uplink to a constellation of spacecraft within its beam. This single frequency technique requires the use of non-standard signal acquisition techniques since the constellation may realize different orbits and trajectories around a planetary body leading to varying Doppler offsets and dynamics at each member spacecraft. In such a case, a Type 2 tracking loop may not suffice. An earlier study discussed the various methods for acquiring signals in spacecraft receivers with uncompensated Doppler at the uplink station. In the earlier study, three methods of achieving acquisition and lock were discussed for signals with large Doppler frequency offsets as well as high dynamics; 1) a step-and-sweep signal search algorithm, 2) an FFT signal search algorithm, and, 3) on-board tuning of the signal using uploaded trajectory information or lookup tables. On-board tuning appeared a feasible solution given the trend towards utilizing software-defined radios (SDRs). In the absence of on-board tuning, a search algorithm (e.g., step-and-sweep or FFT) could be utilized in the SDR. One such consideration is in the design of the tracking loop filter, where a Type 3 loop may be more amenable to handling large uncompensated Doppler effects. This report presents an analysis of comparing performance of Type 2 versus Type 3 carrier tracking loops when acquiring and tracking signals with large Doppler dynamics.

Abraham, Douglas↗
NASA NTRS2020

Search Tree Pruning for Progressive Neural Architecture Search

Our neural architecture search algorithm progressively searches a tree of neural network architectures. Child nodes are created by inserting new layers determined by a transition graph into a parent network up to a maximum depth and pruned when performance is worse than its parent. This increases efficiency but makes the algorithm greedy. Simpler networks are successfully found before more complex ones that can achieve benchmark performance similar to other top-performing networks.

Deanna Flynn↗
DOE OSTI2024

Rapidly convergent quantum Monte Carlo using a Chebyshev projector

The multireference coupled-cluster Monte Carlo (MR-CCMC) algorithm is a determinant-based quantum Monte Carlo (QMC) algorithm that is conceptually similar to Full Configuration Interaction QMC (FCIQMC). It has been shown to offer a balanced treatment of both static and dynamic correlation while retaining polynomial scaling, although application to large systems with significant strong correlation remained impractical. In this paper, we document recent algorithmic advances that enable rapid convergence and a more black-box approach to the multireference problem. These include a logarithmically scaling metric-tree-based excitation acceptance algorithm to search for determinants connected to the reference space at the desired excitation level and a symmetry-screening procedure for the reference space. We show that, for moderately sized reference spaces, the new search algorithm brings about an approximately 8-fold acceleration of one MR-CCMC iteration, while the symmetry screening procedure reduces the number of active reference space determinants with essentially no loss of accuracy. We also introduce a stochastic implementation of an approximate wall projector, which is the infinite imaginary time limit of the exponential projector, using a truncated expansion of the wall function in Chebyshev polynomials. Notably, this wall-Chebyshev projector can be used to accelerate any projector-based QMC algorithm. We show that it requires significantly fewer applications of the Hamiltonian to achieve the same statistical convergence. We benchmark these acceleration methods on the beryllium and carbon dimers, using initiator FCIQMC and MR-CCMC with basis sets up to cc-pVQZ quality.

Zhao, Zijun↗
NASA NTRS2008

Efficient Algorithm for Rectangular Spiral Search

An algorithm generates grid coordinates for a computationally efficient spiral search pattern covering an uncertain rectangular area spanned by a coordinate grid. The algorithm does not require that the grid be fixed; the algorithm can search indefinitely, expanding the grid and spiral, as needed, until the target of the search is found. The algorithm also does not require memory of coordinates of previous points on the spiral to generate the current point on the spiral.

Brugarolas, Paul↗
NASA NTRS2004

Robust local search for spacecraft operations using adaptive noise

Randomization is a standard technique for improving the performance of local search algorithms for constraint satisfaction. However, it is well-known that local search algorithms are constraints satisfaction. However, it is well-known that local search algorithms are to the noise values selected. We investigate the use of an adaptive noise mechanism in an iterative repair-based planner/scheduler for spacecraft operations. Preliminary results indicate that adaptive noise makes the use of randomized repair moves safe and robust; that is, using adaptive noise makes it possible to consistently achieve, performance comparable with the best tuned noise setting without the need for manually tuning the noise parameter.

planning↗
NASA NTRS2009

Analysis of Sting Balance Calibration Data Using Optimized Regression Models

Calibration data of a wind tunnel sting balance was processed using a search algorithm that identifies an optimized regression model for the data analysis. The selected sting balance had two moment gages that were mounted forward and aft of the balance moment center. The difference and the sum of the two gage outputs were fitted in the least squares sense using the normal force and the pitching moment at the balance moment center as independent variables. The regression model search algorithm predicted that the difference of the gage outputs should be modeled using the intercept and the normal force. The sum of the two gage outputs, on the other hand, should be modeled using the intercept, the pitching moment, and the square of the pitching moment. Equations of the deflection of a cantilever beam are used to show that the search algorithm s two recommended math models can also be obtained after performing a rigorous theoretical analysis of the deflection of the sting balance under load. The analysis of the sting balance calibration data set is a rare example of a situation when regression models of balance calibration data can directly be derived from first principles of physics and engineering. In addition, it is interesting to see that the search algorithm recommended the same regression models for the data analysis using only a set of statistical quality metrics.

Ulbrich, Norbert↗
NASA NTRS2010

Analysis of Sting Balance Calibration Data Using Optimized Regression Models

Calibration data of a wind tunnel sting balance was processed using a candidate math model search algorithm that recommends an optimized regression model for the data analysis. During the calibration the normal force and the moment at the balance moment center were selected as independent calibration variables. The sting balance itself had two moment gages. Therefore, after analyzing the connection between calibration loads and gage outputs, it was decided to choose the difference and the sum of the gage outputs as the two responses that best describe the behavior of the balance. The math model search algorithm was applied to these two responses. An optimized regression model was obtained for each response. Classical strain gage balance load transformations and the equations of the deflection of a cantilever beam under load are used to show that the search algorithm s two optimized regression models are supported by a theoretical analysis of the relationship between the applied calibration loads and the measured gage outputs. The analysis of the sting balance calibration data set is a rare example of a situation when terms of a regression model of a balance can directly be derived from first principles of physics. In addition, it is interesting to note that the search algorithm recommended the correct regression model term combinations using only a set of statistical quality metrics that were applied to the experimental data during the algorithm s term selection process.

Ulbrich, N.↗
NASA NTRS2018

Multiple Uplinks Per Antenna (MUPA) Signal Acquisition Schemes

The Deep Space Network (DSN) currently makes use of the technique of Multiple Spacecraft per Antenna (MSPA) where a single antenna is used to track multiple spacecraft downlinks within its beam, such as in the case of multiple spacecraft orbiting Mars at 8.4 GHz (X-band). It is desired to extend this technique to the uplink where a single station is used to send a signal to multiple spacecraft in order to make more efficient use of ground resources. This would be applicable to numerous smallsat constellations being considered for future missions or to future spacecraft at Venus, Mars, or more distant destinations that are all within the half-power beamwidth of a single 34-m diameter antenna. In one scheme, each spacecraft’s command sequences would be time multiplexed onto a single uplink frequency. Each spacecraft would lock onto the uplink signal and would accept only commands intended for it via special identifier codes. Each spacecraft would also emit a downlink signal to the ground that is coherent with the uplink signal but would have its own allocated frequency channel and identifier information. A couple of key challenges associated with using this technique need to be addressed. Because of the single uplink frequency, coherent turnaround for two-way Doppler and ranging would not conform to established ratios, thus the radios employed by the spacecraft would need to be capable of variable turnaround ratios. In addition, because of the different orbits or spacecraft trajectories, the relative Doppler shifts and rates can be large with respect to the common uplink signal whose frequency would lie at the centroid of the frequencies of the expected received signals of the constellation. This would be problematic with standard analog spacecraft radios whose acquisition bandwidths are relatively small (~1.7 kHz) relative to the large frequency offsets (~100 kHz) expected using the single frequency uplink technique. With the advent of software defined radios (SDRs), signal frequency search algorithms can be utilized within the flight software and/or programmable hardware (e.g., FPGAs) that can easily acquire and track signals with large frequency offsets and varying dynamics. Such techniques could include FFT search algorithms, step-and-sweep search algorithms, or onboard frequency steering making use of trajectory vectors uplinked to each member spacecraft. Other challenges include mitigation of potential interference between received signals. We have identified several software defined radios that are in different stages of development and whose key parameters have been tabulated. We have examined each radio’s capabilities with respect to acquiring and tracking signals with large frequency offsets. Such analyses made use of previous studies supplemented with specially designed tests using both simulation tools and/or existing testbeds. We have compared signal acquisition times computed from provided algorithms along with measured values derived from tests using existing hardware and simulation tools for the purpose of conducting tradeoff studies between the various radio designs and software/firmware programming approaches.

Abraham, Douglas S.↗
NASA NTRS2009

Regression Model Optimization for the Analysis of Experimental Data

A candidate math model search algorithm was developed at Ames Research Center that determines a recommended math model for the multivariate regression analysis of experimental data. The search algorithm is applicable to classical regression analysis problems as well as wind tunnel strain gage balance calibration analysis applications. The algorithm compares the predictive capability of different regression models using the standard deviation of the PRESS residuals of the responses as a search metric. This search metric is minimized during the search. Singular value decomposition is used during the search to reject math models that lead to a singular solution of the regression analysis problem. Two threshold dependent constraints are also applied. The first constraint rejects math models with insignificant terms. The second constraint rejects math models with near-linear dependencies between terms. The math term hierarchy rule may also be applied as an optional constraint during or after the candidate math model search. The final term selection of the recommended math model depends on the regressor and response values of the data set, the user s function class combination choice, the user s constraint selections, and the result of the search metric minimization. A frequently used regression analysis example from the literature is used to illustrate the application of the search algorithm to experimental data.

Ulbrich, N.↗