On a trust region method without exact Jacobian matrices

Automatic differentiation (AD) provides a possibility to evaluate exact derivative information within working accuracy. Here, we present an approach for equality constrained optimization that is based essentially on AD by computing only direct sensitivities and adjoints of first and second order. Employing this information, we generate approximations of the required derivative matrices using the STR1 update instead of computing the full constraint Jacobian or the full Lagrangian Hessian at each iteration explicitly. Hence, this approach avoids the forming and factoring of the exact constraint Jacobian that is often required in each iteration step. In order to globalize this provable local convergent method, the algorithm was embedded in a trust-region framework. We apply a composite-step method similar to the Byrd-Omojokun approach that is well suited for the available information from the approximated matrices. For that purpose, the normal step is given by the dogleg method whereas a generalized CG-iteration is applied to compute the tangential step. Here, the fact that only inexact information of the constraint Jacobian is available forms the main difference to other existing algorithms, where often a factorization of the exact Jacobian is used. Numerical results are shown for an equality constrained problem of the CUTE set and a PDE-based optimization problem. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An economic interpretation of exact penalty functions using sensitivity analysis

It has already been demonstrated that under some assumptions, a local minimum of a constrained problem is also a local unconstrained minimum of a function which is called an exact penalty function. Here, we present the same result with a new demonstration. By using sensitivity analysis, we give an economic interpretation for exact penalty functions.     

Algebraic algorithms for the analysis of mechanical trusses

Infinite periodic lattices can be used as models for analyzing and understanding various properties of mechanical truss constructions with periodic structures. For infinite lattices, the problems of connectivity and stability are nontrivial from the mathematical point of view and have not been addressed adequately in the literature. In this paper, we will present a set of algebraic algorithms, which are based on ideal theory, to solve such problems.

For the understanding of the notion ``complicated three-dimensional lattices', it is essential to have this paper with colored figures.

     

EEG source analysis using space mapping techniques

The electroencephalogram (EEG) measures potential differences, generated by electrical activity in brain tissue, between scalp electrodes. The EEG potentials can be calculated by the quasi-static Poisson equation in a certain head model. It is well known that the electrical dipole (source) which best fits the measured EEG potentials is obtained by an inverse problem. The dipole parameters are obtained by finding the global minimum of the relative residual energy (RRE). For the first time, the space mapping technique (SM technique) is used for minimizing the RRE. The SM technique aims at aligning two different simulation models: a fine model, accurate but CPU-time expensive, and a coarse model, computationally fast but less accurate than the fine one. The coarse model is a semi-analytical model, the so-called three-shell concentric sphere model. The fine model numerically solves the Poisson equation in a realistic head model. If we use the aggressive space mapping (ASM) algorithm, the errors on the dipole location are too large. The hybrid aggressive space mapping (HASM) on the other hand has better convergence properties, yielding a reduction in dipole location errors. The computational effort of HASM is greater than ASM but smaller than using direct optimization techniques.     

Partitioned matrices satisfying certain null space properties

Partitioned matrices satisfying certain null space properties for all leading principal submatrices are shown to be equivalent to a sequence of generalized Schur complements satisfying the same null space properties with respect to their (1, 1) entry. It is shown that a matrix with these null space properties has nonsingular principal submatrices of all orders less than or equal to its rank. Also, a theorem of Carlson, Haynsworth, and Markham concerning the quotient property for Schur complements is extended.     

Wavelet representations and Fock space on positive matrices

We show that every biorthogonal wavelet determines a representation by operators on Hilbert space satisfying simple identities, which captures the established relationship between orthogonal wavelets and Cuntz-algebra representations in that special case. Each of these representations is shown to have tractable finite-dimensional co-invariant doubly cyclic subspaces. Further, motivated by these representations, we introduce a general Fock-space Hilbert space construction which yields creation operators containing the Cuntz-Toeplitz isometries as a special case.     

Instability of statistical factor analysis

Factor analysis, a popular method for interpreting multivariate data, models the covariance among variables as being due to a small number (, ) of hidden variables. A factor analysis of can be thought of as an ordered or unordered collection, , of linearly independent lines in . Let be the collection of data sets for which is defined. The ``singularities' of are those data sets, , in the closure, , at which the limit, , does not exist. is unstable near its singularities.

Let be the direct sum of the lines in . determines a -plane bundle, , over a subset, , of . If 1$"> and is rich enough, ordered or, at least if or 3, unordered, must have a singularity at some data set in . The proofs are applications of algebraic topology. Examples are provided.

     

An exact global optimization method for deriving weights from pairwise comparison matrices

Some multiple-criteria decision making methods rank actions by associating weights to the different criteria or actions, which are pairwise compared via a positive reciprocal matrix A. There is a vast literature on proposals of different mathematical-programming methods to infer weights from such matrix A. However, it is seldom observed that such optimization problems may be multimodal, thus the standard local-search resolution techniques suggested may be trapped in local optima, yielding a wrong ranking of alternatives. In this note we show that standard tools of global optimization based on interval analysis, lead to globally optimal weights in reasonable time.     

Semigroup of matrices acting on the max-plus projective space

We investigate the action of semigroups of d×d matrices with entries in the max-plus semifield on the max-plus projective space. Recall that semigroups generated by one element with projectively bounded image are projectively finite and thus contain idempotent elements.In terms of orbits, our main result states that the image of a minimal orbit by an idempotent element of the semigroup with minimal rank has at most d! elements. Moreover, each idempotent element with minimal rank maps at least one orbit onto a singleton.This allows us to deduce the central limit theorem for stochastic recurrent sequences driven by independent random matrices that take countably many values, as soon as the semigroup generated by the values contains an element with projectively bounded image.     

On reduction of block matrices in a Hilbert space

We study the problem of the reduction of self-adjoint block matrices B = (B _ij ) with given graph by a group of unitary block diagonal matrices. Under the condition that the matrices B ² and B ⁴ are orthoscalar, we describe the graphs of block matrices for which this problem is a problem of *-finite, *-tame, or *-wild representation type.     

Local convergence analysis for the REQP algorithm using conjugate basis matrices

The REQP algorithm solves constrained minimization problems using a sequential quadratic programming technique based on the properties of penalty functions. The convergence of REQP has been studied elsewhere (Refs. 1, 2). This paper uses a novel approach to the analysis of the method near to the solution, based on the use of conjugate subspaces. The stepp taken by a constrained minimization algorithm can be thought of as having two components,h in the subspace tangential to the constraints andv in the subspace spanned by the constraint normals. It is usual forh andv to be orthogonal components. Recently, Dixon (Ref. 3) has suggested constructingp from components which are not orthogonal. That is, we writep=h + v, whereh is in the subspace tangential to the constraints and wherev andh are conjugate with respect to the Hessian of the Lagrangian function. By looking at the conjugate components of the REQP search directions, it is possible to simplify the analysis of the behavior near the solution and to obtain new results about the local rate of convergence of the method.This work was supported by a SERC Studentship (TTN).     

Regions of exact convergence of the USSOR method applied on generalized consistently ordered matrices

Summary. Using the theory of nonnegative matrices and regular splittings, exact convergence and divergence domains of the Unsymmetric Successive Overrelaxation (USSOR) method, as it pertains to the class of Generalized Consistently Ordered (GCO) matrices, are determined. Our recently derived upper bounds, for the convergence of the USSOR method, re also used as effective tools. Received October 17, 1993 / Revised version received December 19, 1994     

On universally decodable matrices for space–time coding

The notion of universally decodable matrices (UDMs) was recently introduced by Tavildar and Viswanath while studying slow-fading channels. It turns out that the problem of constructing UDMs is tightly connected to the problem of constructing maximum-distance separable codes. In this paper, we first study the properties of UDMs in general and then we discuss an explicit construction of a class of UDMs, a construction which can be seen as an extension of Reed–Solomon codes. In fact, we show that this extension is, in a sense to be made more precise later on, unique. Moreover, the structure of this class of UDMs allows us to answer some open conjectures by Tavildar, Viswanath, and Doshi in the positive, and it also allows us to formulate an efficient decoding algorithm for this class of UDMs. It turns out that our construction yields a coding scheme that is essentially equivalent to a class of codes that was proposed by Rosenbloom and Tsfasman. Moreover, we point out connections to so-called repeated-root cyclic codes.