Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem

This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path-following algorithm proposed by the authors for the LCP. If the LCP has a unique non-degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.Supported by Grant-in-Aids for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.     

On Some Properties of Generalized Proximal Point Methods for Variational Inequalities

We discuss here generalized proximal point methods applied to variational inequality problems. These methods differ from the classical point method in that a so-called Bregman distance substitutes for the Euclidean distance and forces the sequence generated by the algorithm to remain in the interior of the feasible region, assumed to be nonempty. We consider here the case in which this region is a polyhedron (which includes linear and nonlinear programming, monotone linear complementarity problems, and also certain nonlinear complementarity problems), and present two alternatives to deal with linear equality constraints. We prove that the sequences generated by any of these alternatives, which in general are different, converge to the same point, namely the solution of the problem which is closest, in the sense of the Bregman distance, to the initial iterate, for a certain class of operators. This class consists essentially of point-to-point and differentiable operators such that their Jacobian matrices are positive semidefinite (not necessarily symmetric) and their kernels are constant in the feasible region and invariant through symmetrization. For these operators, the solution set of the problem is also a polyhedron. Thus, we extend a previous similar result which covered only linear operators with symmetric and positive-semidefinite matrices.     

A Note on the Recursive and Parallel Structure of the Birge and Qi Factorization for Tree Structured Linear Programs

In this note, we derive the complete recursive structure of the Birge and Qi factorization for interior point methods (IPM) for tree structured linear programs as they appear in multistage stochastic programs. This recursive structure allows for an elegant implementation on parallel hardware, since multiple versions of the same program may be run on on different processors. Our preliminary computational experiment, conducted on a Beowulf cluster, demonstrates the scalability of this approach.     

Cone angle radial profiles

Various methodologies have been reported in the literature for the evaluation of the size of a ligand or organic functional group, with the Tolman cone angle methodology proving to be most popular in inorganic chemistry. A procedure to extend the Tolman concept to the measurement of a ligand size, as a profile over a radial distance from the metal (apex), has been developed. The representation of the Tolman cone angle as a function of distance from the metal is termed a cone angle radial profile (CARP). CARPs for PH₃, PMe₃, PEt₃ and PPh₃ have been determined and are described. CARPs for molecules containing the constrained phosphite ligands P(OCH₂)₃CMe, as determined in actual structures (Cambridge Structural Database), have also been evaluated and indicate the invariant shape of the ligand in the different metal environments. The influence of the choice of the H atom van der Waals radius in steric measurements is also discussed.     

Multiple centrality corrections in a primal-dual method for linear programming

A modification of the (infeasible) primal-dual interior point method is developed. The method uses multiple corrections to improve the centrality of the current iterate. The maximum number of corrections the algorithm is encouraged to make depends on the ratio of the efforts to solve and to factorize the KKT systems. For any LP problem, this ratio is determined right after preprocessing the KKT system and prior to the optimization process. The harder the factorization, the more advantageous the higher-order corrections might prove to be.The computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real-life LP models arising from applications. The use of multiple centrality corrections gives on the average a 25% to 40% reduction in the number of iterations compared with the widely used second-order predictor-corrector method. This translates into 20% to 30% savings in CPU time.Supported by the Fonds National de la Recherche Scientifique Suisse, Grant #12-34002.92.     

Phase synthesis of a holographic metrological diffraction grating of unlimited length

A breakthrough in the technology of measuring systems of submicrometre and subsecond precision was made possible by the invention of holographic phase aperture synthesis of highly regular interference structures. The practical fulfilment of holographic phase aperture synthesis requires development of the following new optical methods: (1) synthesis of the aperture by out of phase auxiliary holographic diffraction gratings; (2) high-precision analysis of the phase structure of the interference field; (3) automatic control of the aperture synthesis process using two-frequency modulation of the interference field; (4) an adaptive interferometer for aperture synthesis. This paper is devoted to the above methods.     

Optical mode characterization of single photons prepared by means of conditional measurements on a biphoton state

A detailed theoretical analysis of the spatiotemporal mode of a single photon prepared via conditional measurements on a photon pair generated in the process of parametric down-conversion is presented. The maximum efficiency of coupling the photon into a transform-limited classical optical mode is calculated and ways for its optimization are determined. An experimentally feasible technique of generating the optimally matching classical mode is proposed. The theory is applied to a recent experiment on pulsed homodyne tomography of the single-photon Fock state [A.I. Lvovsky et al., Phys. Rev. Lett. 87, 050402 (2001)]. Received 16 July 2001     

Geometrical measurements of fibre-optic starter tubes using a novel optical technique

A novel optical technique is described for making geometrical measurements on silica starter tubes. The measurement takes place in an air medium and uses a collimated source and spatial filtering to image the set of transmitted rays onto a CCTV system. An analysis relates this line structure observed to the geometry of the starter tube.     

A modified predictor-corrector method for linear programming

In the predictor-corrector method of Mizuno, Todd and Ye [1], the duality gap is reduced only at the predictor step and is kept unchanged during the corrector step. In this paper, we modify the corrector step so that the duality gap is reduced by a constant fraction, while the predictor step remains unchanged. It is shown that this modified predictor-corrector method retains the iteration complexity as well as the local quadratic convergence property.     

A logarithmic barrier cutting plane method for convex programming

The paper presents a logarithmic barrier cutting plane algorithm for convex (possibly non-smooth, semi-infinite) programming. Most cutting plane methods, like that of Kelley, and Cheney and Goldstein, solve a linear approximation (localization) of the problem and then generate an additional cut to remove the linear program's optimal point. Other methods, like the central cutting plane methods of Elzinga-Moore and Goffin-Vial, calculate a center of the linear approximation and then adjust the level of the objective, or separate the current center from the feasible set. In contrast to these existing techniques, we develop a method which does not solve the linear relaxations to optimality, but rather stays in the interior of the feasible set. The iterates follow the central path of a linear relaxation, until the current iterate either leaves the feasible set or is too close to the boundary. When this occurs, a new cut is generated and the algorithm iterates. We use the tools developed by den Hertog, Roos and Terlaky to analyze the effect of adding and deleting constraints in long-step logarithmic barrier methods for linear programming. Finally, implementation issues and computational results are presented. The test problems come from the class of numerically difficult convex geometric and semi-infinite programming problems.This work was completed under the support of a research grant of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.