Family of optimally conditioned quasi-Newton updates for unconstrained optimization

In this note, a general optimal conditioning problem for updates which satisfy the quasi-Newton equation is solved. The new solution is a family of updates which contains other known optimally conditioned updates but also includes new formulas of increased rank. A new factorization formula for the Broyden family and some preliminary numerical results are also given.     

On the generation of updates for quasi-Newton methods

We present a unified technique for updating approximations to Jacobian or Hessian matrices when any linear structure can be imposed. The updates are derived by variational means, where an operator-weighted Frobenius norm is used, and are finally expressed as solutions of linear equations and/or unconstrained extrema. A certain behavior of the solutions is discussed for certain perturbations of the operator and the constraints. Multiple secant relations are then considered. For the nonsparse case, an explicit family of updates is obtained including Broyden, DFP, and BFGS. For the case where some of the matrix elements are prescribed, explicit solutions are obtained if certain conditions are satisfied. When symmetry is assumed, we show, in addition, the connection with the DFP and BFGS updates.This work was partially supported by a grant from Control Data     

James Spaces Over Partially Ordered Index-Sets

We study the connections between the linear topological structure of James spaces generated by a partially ordered index-set and the set-theoretic properties of that set.     

Benders' decomposition for the constrainedl 1-problem

A constrainedl ₁-problem, involving linear functions only, is considered, and the application of the Benders decomposition method to the solution of the same is discussed. This approach, in principle, seems to be promising and is also applicable to the unconstrained case. Certain small illustrative examples are also presented.This work was done while the first author was visiting the Numerical Optimisation Centre at the Hatfield Polytechnic under the auspices of the British Council and he wishes to acknowledge the excellent research facilities provided by the Polytechnic during the period of his stay. Thanks are also due to Dr. M. C. Bartholomew-Biggs for his valuable comments at various stages of the preparation of this report.     

Fitting hyperplanes by minimizing orthogonal deviations

Hyperplanes withm + 1 parameters are fitted by minimizing the sum of weighted orthogonal deviations to a set ofN points. There is no inverse regression incompatibility. For unweighted orthogonall ₁-fits essentially the same number of points are on either side of an optimal hyperplane. The criterion function is neither convex, nor concave, nor even differentiable. The main result is that each orthogonall _p -fit interpolates at leastm + 1 points, for 0 <p 1. This enables the combinatorial strategy of systematically trying all possible hyperplanes which interpolatem + 1 data points.     

Note on multidimensional empirical processes for φ-mixing random vectors

In 1974, Sen proved weak convergence of the empirical processes (in the J₁-topology on D^p[0, 1]) for a stationary φ-mixing sequence of stochastic p( 1)-vectors. In this note, we show that Sen's theorem on weak convergence of the multidimensional empirical process for a stationary φ-mixing sequence of stochastic vectors remains true under a less restrictive condition on the mixing constants {φ_n}, i.e., φ_n = O(n^−1−δ) for some δ > 0.     

A methodology for modelling travel distances by Bias estimation

Round norms τl _p, p ∈ (1,2] and block norms have been utilised for modelling actual distances in transportation networks. A geometric setting will permit the establishment of a relationship between bias of the road network distance and trajectory deviations, which will be used to separate the set of origin-destination pairs into two samples and also to analyse each sample using regression, thus obtaining several types of estimators. What will be demonstrated in this paper is that these functions can be combined through either a weighted sum, or by means of the introduction of the expected distance concept applied to the bias, to obain distance predicting functions for the region considered.     

An algorithm for fitting circular arcs to data using the <Emphasis Type=Italic>l</Emphasis><Subscript><Emphasis Type=Italic>1</Emphasis></Subscript> norm

There are many applications of fitting circular arcs to data. We have for example, system control, using a computer controlled cutting machine, approximating hulls of boats, drawing and image techniques. Out of these applications comes the least squares norm to be the most commonly used criterion. This paper examines how the l ₁ norm is used which seems to be more appropriate than the use of least squares in the context of wild points in the data. An algorithm and different methods to determine the starting points are developed. However, numerical examples are given to help illustrate these methods.      

Cyclic vectors and cellular indecomposable operators on Qp spaces

We identify the functions whose polynomial multiples are weak* dense in Q p spaces and prove that if | f (z) | ≥ | g(z) | and g is cyclic in Q p , then f is cyclic in Q p . We also show that the multiplication operator M z on Q p spaces is cellular indecomposable.     

The complexity of anl p method for discrete Tchebycheff approximation in exact arithmetic

A discrete Tchebycheff problem is approximated by a sequence ofl _p norm problems. This is an algorithm to be used if a large number of variables is involved as is the case in the approximation of a function of several variables by a polynomial. The complexity of this procedure is investigated and a lower bound for the number of steps to reach ε-optimality is established. Supported by NIH Grant RR01243 at the University of Washington     

Direct solution of an optimal layout problem for isotropic heat conductors with a volume fraction constraint

This paper considers the problem of the optimal layout of two isotropic heat conductors on a plane subject to a constraint on the overall volume fraction of the better conductor. The problem is solved initially using the traditionalG _m -closure technique. Later, the utility of the direct relaxation technique introduced in Ref. 1 is illustrated as we apply it to verify the original results.This paper is dedicated with gratitude by the author to his advisor K. A. Lurie. The author wishes to acknowledge discussions with D. Clomenil.     

A Variation of an Extremal Theorem Due to Woodall

We consider a variation of an extremal theorem due to Woodall [12, or 1, Chapter 3] as follows: Determine the smallest even integer (₃C₁,n), such that every n-term graphic sequence = (d₁, d₂,..., d_n) with term sum () = d₁ + d₂ + ... + d_n (₃C₁,n) has a realization G containing a cycle of length r for each r = 3,4,...,l. In this paper, the values of (₃C_l,n) are determined for l = 2m – 1,n 3m – 4 and for l = 2m,n 5m – 7, where m 4.AMS Mathematics subject classification (1991) 05C35Project supported by the National Natural Science Foundation of China (Grant No. 19971086) and the Doctoral Program Foundation of National Education Department of China     

Conic Formulation for l p -Norm Optimization

In this paper, we formulate the l _p -norm optimization problem as a conic optimization problem, derive its duality properties (weak duality, zero duality gap, and primal attainment) using standard conic duality and show how it can be solved in polynomial time applying the framework of interior-point algorithms based on self-concordant barriers.     

Stable modification of explicitLU factors for simplex updates

This paper presents a method for modifying anLU factorization of a matrixA when a Simplex update is performed onA. At each stage of the algorithm, two options are allowed, and in one of these a row permutation ofL is made so that theLU structure is always maintained. The expanding file of operators used in other methods is not required. The result, of an error analysis is presented in which the error is bounded by the growth in the partial sums ofLU. Various pivotal strategies which minimize a growth bound are discussed and an example is given in which the worst case for growth occurs repeatedly. Numerical results from experiments on ill-conditioned problems show no tendency for error growth.     

Controller design to optimize a composite performance measure

This paper studies a mixed objective problem of minimizing a composite measure of thel ₁, ₂, andl -norms together with thel -norm of the step response of the closed loop. This performance index can be used to generate Pareto-optimal solutions with respect to the individual measures. The problem is analyzed for discrete-time, single-input single-output (SISO), linear time-invariant systems. It is shown via Lagrange duality theory that the problem can be reduced to a convex optimization problem with a priori known dimension. In addition, continuity of the unique optimal solution with respect to changes in the coefficients of the linear combination that defines the performance measure is estabilished.This research was supported by the National Science Foundation under Grants No. ECS-92-04309, ECS-92-16690 and ECS-93-08481.     

Controlled dual perturbations for l p -programming

l _p -programming is a common generalization of linear programming, quadratically constrained quadratic programming,l _p -constrainedl _p -approximation, and multiple criteria compromise programming. It is a type of convex programming with objective function and inequality constraints expressed by means ofl _p -norms. The dual program established by Peterson and Ecker is a maximization problem with a concave, upper-semicontinuous objective function over a set of constraints that are essentially linear. In developing a dual method for this problem, we face two major difficulties. One is the non-differentiability of the dual objective function and the other one is an efficient dual-to-primal conversion.In this paper, we introduce a mechanism to construct a suitably perturbed dual program with a differentiable concave objective function over linear constraints. Solving this well-constructed perturbed dual program, we can obtain an-optimal dual solution for an arbitrarily small number. Moreover, we show a way of constructing a linear program based on this dual solution. Then an-optimal primal solution can be obtained by solving the dual of this simple linear program.

---

Zusammenfassung Diel _p -Optimierung ist eine Verallgemeinerung, die die lineare Optimierung, quadratische Optimierung mit quadratischen Restriktionen,l _p -Approximation mitl _p -Restriktionen, wie auch Vektoroptimierung umfaßt. Es handelt sich dabei um konvexe Optimierungsaufgaben, bei denen Zielfunktions- und Ungleichungsrestriktionen mittelsl _p -Normen ausgedrückt werden. Das duale Problem nach Peterson and Eckert ist ein Maximierungsproblem mit einer konkaven oberhalb-halbstetigen Zielfunktion über einer Menge von im wesentlichen linearen Restrictionen. Bei der Entwicklung einer dualen Lösungsmethode treten zwei Hauptschwierigkeiten auf: Die eine ist die Nicht-Differenzierbarkeit der dualen Zielfunktion, die andere besteht darin, eine effiziente Übertragung der dualen Lösung in eine primale zu finden.In dieser Arbeit führen wir eine Methode ein, die es gestattet, ein entsprechendes gestörtes duales Programm mit differenzierbarer konkaver Zielfunktion und linearen Restriktion aufzustellen. Bei der Lösung dieses wohl-strukturierten, gestörten dualen Problems erhalten wir eine-optimale Duallösung für beliebig kleines. Ferner zeigen wir einen Weg auf, wie, basierend auf dieser Duallösung, ein lineares Programm formuliert werden kann. Löst man das Dualproblem dieses einfachen linearen Programms, so erhält man eine-optimale Lösung für das Ausgangsproblem.

     

Dolbeault Cohomology for G2-Manifolds

Cocalibrated G₂-manifolds are seven-dimensional Riemannian manifolds with a distinguished 3-form which is coclosed. For such a manifold M, S. Salamon in Riemannian Geometry and Holonomy Groups (Longman, 1989) defined a differential complex related with the G₂-structure of M.In this paper we study the cohomology of this complex;it is treated as an analogue of a Dolbeault cohomologyof complex manifolds. For compact G₂-manifoldswhose holonomy group is a subgroup of G₂ special propertiesare proved. The cohomology of any cocalibrated G₂-nilmanifold \K is also studied.     

Reliability Approximation for Markov Chain Imbeddable Systems

In the present article, a simple method is developed for approximating the reliability of Markov chain imbeddable systems. The approximating formula reduces the problem to the reliability assessment of smaller systems with structure similar to the original systems. Two specific reliability structures which have attracted considerable research interest recently (r-within-consecutive-k-out-of-n system and two dimensional r-within-k₁ × k₂-out-of-n₁ × n₂ system) are studied by the new approach and numerical calculations are carried out, which reveal the high quality of our approximations. Several possible extensions and generalizations are also presented in brief.     

Abelian and Tauberian theorems for a new trigonometric method of summation

We first introduce a new trigonometric method of summation and then prove some Abelian and Tauberian theorems for this method.     

Constructions for Octonion and Exceptional Jordan Algebras

In this note we reverse theusual process of constructing the Lie algebras of types G ₂and F ₄ as algebras of derivations of the splitoctonions or the exceptional Jordan algebra and instead beginwith their Dynkin diagrams and then construct the algebras togetherwith an action of the Lie algebras and associated Chevalley groups.This is shown to be a variation on a general construction ofall standard modules for simple Lie algebras and it is well suitedfor use in computational algebra systems. All the structure constantswhich occur are integral and hence the construction specialisesto all fields, without restriction on the characteristic, avoidingthe usual problems with characteristics 2 and 3.