Dynamic optimization problems with bounded terminal conditions

Bounded terminal conditions of nonlinear optimization problems are converted to equality terminal conditions via the Valentine's device. In so doing, additional unknown parameters are introduced into the problem. The transformed problems can still be easily solved using the sequential gradient-restoration algorithm (SGRA) via a simple augmentation of the unknown parameter vector . Three example problems with bounded terminal conditions are solved to verify this technique.This research was supported in part by the National Aeronautics and Space Administration under NASA Grant No. NCC 2-106.     

On the statistical mechanics of the traveling salesman problem

We consider the statistical mechanics of the traveling salesman problem (TSP) and develop some representations to study it. In one representation the mean field theory has a simple form and brings out some of the essential features of the problem. It shows that the system has spontaneous symmetry breaking at any nonzero temperature. In general the phase progressively changes as one decreases the temperature. At low temperatures the mean field theory solution is very sensitive to any small perturbations, due to the divergence of some local susceptibilities. This critical region extends down to zero temperature. We perform the quenched average for a nonmetric TSP in the second representation and the resulting problem is more complicated than the infinite-range spin-glass problem, suggesting that the free energy landscape may be more complex. The role played by frustration in this problem appears explicitly through the localization property of a random matrix, which resembles the tight binding matrix of an electron in a random lattice.     

Complex and tropical counts via positive characteristic

We study two classical families of enumerative problems: inflection lines of plane curves and theta-hyperplanes of canonical curves. In these problems the complex counts and the tropical counts disagree. Each problem suggests a prime with special behavior. On the one hand, we analyze the reduction modulo these special primes, and we prove that the complex solutions coalesce in uniform clusters. On the other hand, we observe that the counts in special characteristic and in tropical geometry match.     

含有陡峭势阱和凹凸非线性项的Kirchhoff型问题的多重正解*

在这篇文章中, 作者研究涉及凹凸非线性项的Kirchhoff型问题-(a + b ∫R3|▽u|²dx) Δu + λV (x)u = μf(x)|u|^q?2u + |u|^p?2u, x ∈ R³,u ∈ H¹(R³),其中a,b > 0 是常数, λ, μ > 0 是参数, 1 < q < 2, 4 < p < 6 且 V 是一个非负连续位势. 在f(x) 和 V 的合适条件下,此问题正解的存在性和集中性能够通过Nehari 流形和Ekeland 变分原理得到.     

Lack of dissipativity is not symplecticness

We show that, when numerically integrating Hamiltonian problems, nondissipative numerical methods do not in general share the advantages possessed by symplectic integrators. Here a numerical method is called nondissipative if, when applied with a small stepsize to the test equationdy/dt = iy, real, has amplification factors of unit modulus. We construct a fourth order, nondissipative, explicit Runge-Kutta-Nyström procedure with small error constants. Numerical experiments show that this scheme does not perform efficiently in the numerical integration of Hamiltonian problems.This research has been supported by project DGICYT PB92-254.     

Stochastic on-line knapsack problems

Different classes of on-line algorithms are developed and analyzed for the solution of {0, 1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value isO(log^3/2 n). An(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.Corresponding author.Partially supported by the Basic Research Action of the European Communities under Contract 3075 (Alcom).Partially supported by research project Models and Algorithms for Optimization of the Italian Ministry of University and Scientific and Technological Research (MURST 40%).     

Real-time onboard wind and windshear determination,part 2: Detection

This paper is concerned with windshear detection in connection with real-time wind identification (Ref. 1). It presents a comparative evaluation of two techniques, one based on the shear/downdraft factor and one based on the wind difference index. The comparison is done with reference to a particular microburst, that which caused the 1985 crash of Flight Delta 191 at Dallas-Fort Worth International Airport.The shear/downdraft factor has the merit of combining the effects of the shear and the downdraft into a single entity. However, its effectiveness is hampered by the fact that, in a real situation, the windshear is accompanied by free-stream turbulence, which tends to blur the resulting signal. In turn, this results in undesirable nuisance warnings if the magnitude of the shear factor due to free-stream turbulence is temporarily larger than that due to true windshear. Therefore, proper filtering is necessary prior to using the shear/downdraft factor in detection and guidance. One effective way for achieving this goal is to average the shear/downdraft factor over a specified time interval . The effect of on the average shear/downdraft factor is studied.     

Real-time onboard wind and windshear determination,part 1: Identification

Standard wind identification techniques employed in the analysis of aircraft accidents are post-facto techniques; they are processed after the event has taken place and are based on the complete time histories of the DFDR/ATCR data along the entire trajectory. By contrast, real-time wind identification techniques are processed while the event is taking place; they are based solely on the knowledge of the preceding time histories of the DFDR/ATCR data.In this paper, a real-time wind identification technique is developed. First, a 3D-kinematic approach is employed in connection with the DFDR/ATCR data covering the time interval preceding the present time instant. The aircraft position, inertial velocity, and accelerometer bias are determined by matching the flight trajectory computed from the DFDR data with the flight trajectory available from the ATCR data. This leads to a least-square problem, which is solved analytically every seconds, with / small.With the inertial velocity and accelerometer bias known, an extrapolation process takes place so as to predict the inertial velocity profile over the subsequent -subinterval. At the end of this subinterval, the extrapolated inertial velocity and the newly identified inertial velocity are statistically reconciled and smoothed. Then, the process of identification, extrapolation, reconciliation, and smoothing is repeated. Subsequently, the wind is computed as the difference between the inertial velocity and the airspeed, which is available from the DFDR data. With the wind identified, windshear detection can take place (Ref. 1).As an example, the real-time wind identification technique is applied to Flight Delta 191, which crashed at Dallas-Fort Worth International Airport on August 2, 1985. The numerical results show that the wind obtained via real-time identification is qualitatively and quantitatively close to the wind obtained via standard identification. This being the case, it is felt that real-time wind identification can be useful in windhsear detection and guidance, above all if the shear/downdraft factor signal is replaced by the wind difference signal (Ref. 1).This paper and its companion (Ref. 1) are based on Refs. 2–4.This research was supported by the Aviation Research and Education Foundation and by Texas Advanced Technology Program, Grant No. TATP-003604020.     

Lower semicontinuous solutions of the Bellman equation for the minimum time problem

The minimum time problem associated with a nonlinear control system is considered, and the unicity of the lower semicontinuous solution of the corresponding Bellman equation is investigated. A main tool in our approach is the Kruzkov transformation that enables us to work on ⁿ –{0}, where {0} is the target set, instead of the unknown reachable set.This research was carried out while the first author was visiting the Department of Mathematics, University of Genova, Genova, Italy.     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.