非线性规划的摄动可行方向法

本文提出了二类新的摄动可行方向法,发展和完善了这类方法.新方法形式简单而且不必用Polak程序.适当选择算法中有关参数可减少计算量,还可加快算法的收敛速度.     

Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs

A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255.     

Complex conjugate gradient methods

Linear systems with complex coefficients arise from various physical problems. Examples are the Helmholtz equation and Maxwell equations approximated by finite difference or finite element methods, that lead to large sparse linear systems. When the continuous problem is reduced to integral equations, after discretization, one obtains a dense linear system. The resulting matrices are generally non-Hermitian but, most of the time, symmetric and consequently the classical conjugate gradient method cannot be directly applied. Usually, these linear systems have to be solved with a large number of unknowns because, for instance, in electromagnetic scattering problems the mesh size must be related to the wave length of the incoming wave. The higher the frequency of the incoming wave, the smaller the mesh size must be. When one wants to solve 3D-problems, it is no longer practical to use direct method solvers, because of the huge memory they need. So iterative methods are attractive for this kind of problems, even though their convergence cannot be always guaranteed with theoretical results. In this paper we derive several methods from a unified framework and we numerically compare these algorithms on some test problems.     

Application of stochastic optimal control to the suboptimal design of thrust-mass profiles

Stochastic optimal control techniques are applied to compare the performance of identical medium-range air-to-air missiles which have different thrust-mass profiles. The measure of the performance is the probability of reaching a lock-on-point with a favorable range of guidance and flight parameters, during a fixed time interval [0,t _f ], given that, during the flight, the trajectories of the missile are subjected to a variety of constraints including dynamic pressure constraints.     

Bounding multi-stage stochastic programs from above

The purpose of this paper is to present general approaches for bounding some multi-stage stochastic programs from above. The results are based on restricting the solution set, such that the remaining multi-stage stochastic program is easy to solve. An example where the methods can be applied is presented.Supported in part by NATO Collaborative Research Grant No. 0785/87.     

Job selection and sequencing on a single machine in a random environment

We examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified initiation costs and terminal revenues, the objective is to select a subset of the jobs and sequence the selected jobs such that the expected profit is maximized. The job selection aspect considered by us marks a clear departure from the pure sequencing focus found in the traditional scheduling literature. In this paper, we assume an exponentially distributed deadline and do not allow preemption. Even under these conditions, the selection and sequencing problem remains quite difficult (unlike its pure sequencing counterpart); we in fact conjecture that the problem is NP-hard. However, we show that the problem can be efficiently solved as long as the cost parameter is agreeable or an approximate solution is acceptable. To this end, we describe several solution properties, present dynamic programming algorithms (one of which exhibits a pseudo-polynomial time worst-case complexity), and propose a fully-polynomial time approximation scheme. In addition, we study a number of special cases which can be solved in polynomial time. Finally, we summarize our work and discuss an extension where the jobs are precedence related.     

Sensitivity analysis of the greatest eigenvalue of a symmetric matrix via the ɛ-subdifferential of the associated convex quadratic form

LetA(·) be ann × n symmetric affine matrix-valued function of a parameteruR ^m , and let (u) be the greatest eigenvalue ofA(u). Recently, there has been interest in calculating (u), the subdifferential of atu, which is useful for both the construction of efficient algorithms for the minimization of (u) and the sensitivity analysis of (u), namely, the perturbation theory of (u). In this paper, more generally, we investigate the Legendre-Fenchel conjugate function of (·) and the -subdifferential (u) of atu. Then, we discuss relations between the set (u) and some perturbation bounds for (u).The author is deeply indebted to Professor J. B. Hiriart-Urruty who suggested this study and provided helpful advice and constant encouragement. The author also thanks the referees and the editors for their substantial help in the improvement of this paper.     

Fubini theorem for anticipating stochastic integrals in Hilbert space

Let (X,l,) be a measure space, letW be a cylindrical Hilbert-Wiener process, and let be an anticipating integrable process-valued function onX. We prove, under natural assumptions on, that there exists a measurable version Y_x,x X, of the anticipating integral of(x) such that the integral _x Y_x(dx) is a version of the anticipating integral of _X (x)(dx). We apply this anticipating Fubini theorem to study solutions of a class of stochastic evolution equations in Hilbert space.     

Constrained minimax approximation and optimal preconditioned for Toeplitz matrices

A good preconditioner is extremely important in order for the conjugate gradients method to converge quickly. In the case of Toeplitz matrices, a number of recent studies were made to relate approximation of functions to good preconditioners. In this paper, we present a new result relating the quality of the Toeplitz preconditionerC for the Toeplitz matrixT to the Chebyshev norm (f– g)/f, wheref and g are the generating functions forT andC, respectively. In particular, the construction of band-Toeplitz preconditioners becomes a linear minimax approximation problem. The case whenf has zeros (but is nonnegative) is especially interesting and the corresponding approximation problem becomes constrained. We show how the Remez algorithm can be modified to handle the constraints. Numerical experiments confirming the theoretical results are presented.     

一阶最优性条件研究

本对由Botsko的关于多变量函数取极值的一阶导数检验条件定理^[1]进行了分析研究，给出了更实用而简捷的差别条件。最后，举出若干例子予以说明。