A composite step bi-conjugate gradient algorithm for nonsymmetric linear systems

The Bi-Conjugate Gradient (BCG) algorithm is the simplest and most natural generalization of the classical conjugate gradient method for solving nonsymmetric linear systems. It is well-known that the method suffers from two kinds of breakdowns. The first is due to the breakdown of the underlying Lanczos process and the second is due to the fact that some iterates are not well-defined by the Galerkin condition on the associated Krylov subspaces. In this paper, we derive a simple modification of the BCG algorithm, the Composite Step BCG (CSBCG) algorithm, which is able to compute all the well-defined BCG iterates stably, assuming that the underlying Lanczos process does not break down. The main idea is to skip over a step for which the BCG iterate is not defined.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contracts N00014-90J-1695 and N00014-92J-1890, the Department of Energy under contract DE-FG03-87ER25307, the National Science Foundation under contracts ASC 90-03002 and 92-01266, and the Army Research Office under contract DAAL03-91-G-0150. Part of this work was completed during a visit to the Computer Science Dept., The Chinese University of Hong Kong.     

An analysis of the composite step biconjugate gradient method

Summary The composite step biconjugate gradient method (CSBCG) is a simple modification of the standard biconjugate gradient algorithm (BCG) which smooths the sometimes erratic convergence of BCG by computing only a subset of the iterates. We show that 2×2 composite steps can cure breakdowns in the biconjugate gradient method caused by (near) singularity of principal submatrices of the tridiagonal matrix generated by the underlying Lanczos process. We also prove a best approximation result for the method. Some numerical illustrations showing the effect of roundoff error are given.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contracts N00014-90-J-1695 and N00014-92-J-1890, the Department of Energy under, contract DE-FG03-87ER25307, the National Science Foundation under contracts ASC 90-03002 and ASC 92-01266, and the Army Research Office under contract DAAL03-91-G-0150. Part of this work was completed during a visit to the Computer Science Dept. The Chinese University of Hong Kong.     

On completeness of the spectral domain of harmonizable processes

Summary The spectral domain of harmonizable processes is studied and a criterion for its completeness is obtained. It is shown that even for periodically correlated processes the spectral domain need not be complete.This work was funded in part by Office of Naval Research grant N00014-89-J-1824 and in part by US Army Research Office grant DAAL 03-91-G-0238. Part of these results has been presented at the May 1993 AMS meeting in DeKalb; ref. nr. 882-28-69     

Neighborhood filters and PDE’s

Denoising images can be achieved by a spatial averaging of nearby pixels. However, although this method removes noise it creates blur. Hence, neighborhood filters are usually preferred. These filters perform an average of neighboring pixels, but only under the condition that their grey level is close enough to the one of the pixel in restoration. This very popular method unfortunately creates shocks and staircasing effects. In this paper, we perform an asymptotic analysis of neighborhood filters as the size of the neighborhood shrinks to zero. We prove that these filters are asymptotically equivalent to the Perona–Malik equation, one of the first nonlinear PDE’s proposed for image restoration. As a solution, we propose an extremely simple variant of the neighborhood filter using a linear regression instead of an average. By analyzing its subjacent PDE, we prove that this variant does not create shocks: it is actually related to the mean curvature motion. We extend the study to more general local polynomial estimates of the image in a grey level neighborhood and introduce two new fourth order evolution equations.This work has been partially financed by the Centre National d’Etudes Spatiales (CNES), the Office of Naval Research under grant N00014-97-1-0839, the Ministerio de Ciencia y Tecnologia under grant MTM2005-08567. During this work, the first author had a fellowship of the Govern de les Illes Balears for the realization of his PhD.     

Convergence properties of trust region methods for linear and convex constraints

We develop a convergence theory for convex and linearly constrained trust region methods which only requires that the step between iterates produce a sufficient reduction in the trust region subproblem. Global convergence is established for general convex constraints while the local analysis is for linearly constrained problems. The main local result establishes that if the sequence converges to a nondegenerate stationary point then the active constraints at the solution are identified in a finite number of iterations. As a consequence of the identification properties, we develop rate of convergence results by assuming that the step is a truncated Newton method. Our development is mainly geometrical; this approach allows the development of a convergence theory without any linear independence assumptions.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.Work supported in part by the National Science Foundation grant DMS-8803206 and by the Air Force Office of Scientific Research grant AFSOR-860080.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

Error analysis of a pairwise summation algorithm to compute the sample variance

Summary We give an error analysis of an algorithm for computing the sample variance due to Chan, Golub, and LeVeque [The American Statistician 7 (1983), pp. 242–247]. It is shown that this algorithm is numerically stable. The algorithm computes the sample variance (and the sample mean) using just one pass through the sample data. It is amenable to pairwise summation and thus requires onlyO(logn) parallel steps.Research supported by the Air Force Office of Scientific Research under grant no. AFOSR-88-0161 and by the Office of Naval Research under grant no. N00024-85-C-6041     

Optimization with unary functions

Most nonlinear programming problems consist of functions which are sums of unary functions of linear functions. Advantage can be taken of this form to calculate second and higher order derivatives easily and at little cost. Using these, high order optimization techniques such as Halley's method can be utilized to accelerate the rate of convergence to the solution. These higher order derivatives can also be used to compute second order sensitivity information. These techniques are applied to the solution of the classical chemical equilibrium problem.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research and by the Office of Naval Research grant N00014-86-K0052.Supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research.     

Sample-path optimization of convex stochastic performance functions

In this paper we propose a method for optimizing convex performance functions in stochastic systems. These functions can include expected performance in static systems and steady-state performance in discrete-event dynamic systems; they may be nonsmooth. The method is closely related to retrospective simulation optimization; it appears to overcome some limitations of stochastic approximation, which is often applied to such problems. We explain the method and give computational results for two classes of problems: tandem production lines with up to 50 machines, and stochastic PERT (Program Evaluation and Review Technique) problems with up to 70 nodes and 110 arcs. Sponsored by the National Science Foundation under grant number CCR-9109345, by the Air Force Systems Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAL03-92-G-0408, and by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Sponsored by a Wisconsin/Hilldale Research Award, by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144, and the Air Force Systems Command, USAF, under grant number F49620-93-1-0068. Sponsored by the National Science Foundation under grant number DDM-9201813.     

Implementation of a continuation method for normal maps

This paper presents an implementation of a nonsmooth continuation method of which the idea was originally put forward by Alexander et al. We show how the method can be computationally implemented and present numerical results for variational inequality problems in up to 96 variables. The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAH04-95-1-0149, and by the National Science Foundation under grant number CCR-9109345. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

An algorithm for nonlinear optimization using linear programming and equality constrained subproblems

This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza [10]. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the ₁ penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr [1, 15] test set.This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported in part by the EPSRC grant GR/R46641.These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579 and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004.Report OTC 2002/4, Optimization Technology CenterTo Roger Fletcher, with respect and admiration     

Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013. A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

On the convergence of Newton iterations to non-stationary points

We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, the interaction between the Newton direction and the merit function can prevent the iterates from escaping such non-stationary points. The unconstrained minimization problem is also studied, and conditions under which false convergence cannot occur are presented. Several examples illustrating failure of Newton iterations for constrained optimization are also presented. The paper also shows that a class of line search feasible interior methods cannot exhibit convergence to non-stationary points. This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported by Department of Energy grant DE-FG02-87ER25047-A004.This author was supported by National Science Foundation grant CCR-9987818 and Department of Energy grant DE-FG02-87ER25047-A004.     

A reduction method for variational inequalities

This paper explains a method by which the number of variables in a variational inequality having a certain form can be substantially reduced by changing the set over which the variational inequality is posed. The method applies in particular to certain economic equilibrium problems occurring in applications. We explain and justify the method, and give examples of its application, including a numerical example in which the solution time for the reduced problem was approximately 2% of that for the problem in its original form. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number F49620-95-1-0222, and by the U.S. Army Research Office under grant number DAAH04-95-1-0149. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

The principal pivoting method revisited

The principal pivoting method (PPM) for the linear complementarity problem (LCP) is shown to be applicable to the class of LCPs involving the newly identified class of sufficient matrices.Research partially supported by the National Science Foundation grant DMS-8800589, U.S. Department of Energy grant DE-FG03-87ER25028 and Office of Naval Research grant N00014-89-J-1659.Dedicated to George B. Dantzig on the occasion of his 75th birthday.     

Robust convex quadratically constrained programs

In this paper we study robust convex quadratically constrained programs, a subset of the class of robust convex programs introduced by Ben-Tal and Nemirovski [4]. In contrast to [4], where it is shown that such robust problems can be formulated as semidefinite programs, our focus in this paper is to identify uncertainty sets that allow this class of problems to be formulated as second-order cone programs (SOCP). We propose three classes of uncertainty sets for which the robust problem can be reformulated as an explicit SOCP and present examples where these classes of uncertainty sets are natural. Research partially supported by DOE grant GE-FG01-92ER-25126, NSF grants DMS-94-14438, CDA-97-26385, DMS-01-04282 and ONR grant N000140310514.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

The dimension of cycle-free orders

The existence of a four-dimensional cycle-free order is proved. This answers a question of Ma and Spinrad. Two similar problems are also discussed.Research partially supported by Office of Naval Research grant N00014-90-J-1206Research partially supported by the National Science Foundation under grant DMS     

Conditions for finite moments of waiting times inG/G/1 queues

We find conditions for E(W ) to be finite whereW is the stationary waiting time random variable in a stableG/G/1 queue with dependent service and inter-arrival times.Supported in part by KBN under grant 640/2/9, and at the Center for Stochastic Processes, Department of Statistics at the University of North Carolina Chapel Hill by the Air Force Office of Scientific Research Grant No. 91-0030 and the Army Research Office Grant No. DAAL09-92-G-0008.     

Controlled Markov processes on the infinite planning horizon: Weighted and overtaking cost criteria

Stochastic control problems for controlled Markov processes models with an infinite planning horizon are considered, under some non-standard cost criteria. The classical discounted and average cost criteria can be viewed as complementary, in the sense that the former captures the short-time and the latter the long-time performance of the system. Thus, we study a cost criterion obtained as weighted combinations of these criteria, extending to a general state and control space framework several recent results by Feinberg and Shwartz, and by Krass et al. In addition, a functional characterization is given for overtaking optimal policies, for problems with countable state spaces and compact control spaces; our approach is based on qualitative properties of the optimality equation for problems with an average cost criterion.Research partially supported by the Engineering Foundation under grant RI-A-93-10, in part by the National Science Foundation under grant NSF-INT 9201430, and in part by a grant from the AT&T Foundation.Research partially supported by the Air Force Office of Scientific Research under Grant F49620-92-J-0045, and in part by the National Science Foundation under Grant CDR-8803012.     

Marginal values and second-order necessary conditions for optimality

Second-order necessary conditions in nonlinear programming are derived by a new method that does not require the usual sort of constraint qualification. In terms of the multiplier vectors appearing in such second-order conditions, an estimate, is obtained for the generalized subgradients of the optimal, value function associated with a parameterized nonlinear programming problem. This yields estimates for ‘marginal values’ with respect to the parameters. The main theoretical tools are the augmented Lagrangian and, despite the assumption of second-order smoothness of objective constraints, the subdifferential calculus that has recently been developed for nonsmooth, nonconvex functions. Research sponsored in part by the Air Force Office of Scientific, Research, Air Force Systems Command United States Air Force, under grant No. F4960-82-k-0012.