Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming

We present an analysis of the full-Newton step infeasible interior-point algorithm for semidefinite optimization, which is an extension of the algorithm introduced by Roos [C. Roos, A full-Newton step 𝒪(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16 (2006), pp. 1110–1136] for the linear optimization case. We use the proximity measure σ(V)?=?‖I???V ²‖ to overcome the difficulty of obtaining an upper bound of updated proximity after one full-Newton step, where I is an identity matrix and V is a symmetric positive definite matrix. It turns out that the complexity analysis of the algorithm is simplified and the iteration bound obtained is improved slightly.     

On strongly almost trivial embeddings of graphs

We present four new classes of graphs, two of which every member has a strongly almost trivial embedding, and the other two of which every member has no strongly almost trivial embeddings. We show that the property that a graph has a strongly almost trivial embedding and the property that a graph has no strongly almost trivial embeddings are not inherited by minors. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

一种改进的无约束非光滑优化问题的信赖域算法

本文提出了一种新的求解无约束非光滑优化问题的信赖域算法,并证明了该算法的迭代点列的任何聚点都是的问题的稳定点。     

A rational Arnoldi approach for ill-conditioned linear systems

For the solution of full-rank ill-posed linear systems a new approach based on the Arnoldi algorithm is presented. Working with regularized systems, the method theoretically reconstructs the true solution by means of the computation of a suitable function of matrix. In this sense, the method can be referred to as an iterative refinement process. Numerical experiments arising from integral equations and interpolation theory are presented. Finally, the method is extended to work in connection with the standard Tikhonov regularization with the right-hand side contaminated by noise.     

Parallel computation of two-point boundary-value problems via particular solutions

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm–1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.Dedicated to the Memory of Professor Jan M. SkowronskiThis paper, based on Refs. 1–3, is a much condensed version of the material contained in these references.The technical assistance of the Research Center on Parallel Computation of Rice University, Houston, Texas is gratefully acknowledged.     

Guaranteeing total balance in Metropolis algorithm Monte Carlo simulations

The condition of detailed balance has long been used as a proxy for the more difficult-to-prove condition of total balance, which along with ergodicity is required to guarantee convergence of a Markov Chain Monte Carlo (MCMC) simulation to the correct probability distribution. However, some simple-to-program update schemes such as the sequential and checkerboard Metropolis algorithms are known not to satisfy detailed balance for such common systems as the Ising model.     

Q-superlinear convergence of the iterates in primal-dual interior-point methods

Sufficient conditions are given for the Q-superlinear convergence of the iterates produced by primal-dual interior-point methods for linear complementarity problems. It is shown that those conditions are satisfied by several well known interior-point methods. In particular it is shown that the iteration sequences produced by the simplified predictor–corrector method of Gonzaga and Tapia, the simplified largest step method of Gonzaga and Bonnans, the LPF+ algorithm of Wright, the higher order methods of Wright and Zhang, Potra and Sheng, and Stoer, Wechs and Mizuno are Q-superlinearly convergent. Received: February 9, 2000 / Accepted: February 20, 2001?Published online May 3, 2001     

Adjustment of Residual Stresses in Unsymmetric Fiber-Reinforced Composites Using Genetic Algorithms

During the manufacturing process of multilayered fiber-reinforced composites with variable fiber orientations, residual stresses build up in these composites due to the directional expansion of single unidirectionally reinforced layers. Depending on the laminate lay-up, the inhomogeneous residual stresses, which are caused by thermal effects, moisture absorption, and chemical shrinkage, can lead to large multistable out-of-plane deformations. Instead of avoiding these curvatures, they can be advantageously used for technical applications following the near-net-shape technology. In order to adjust the deformations to the technical requirements, genetic algorithms in combination with a nonlinear calculation method have been developed, which can purposefully adapt the laminate lay-up depending on the loading and process parameters.     

Velocity measurement for moving surfaces using spatial filtering method based on area image sensor

The idea of using spatial filtering method to measure velocity of vehicles for an inertial navigation system is put forward. Corresponding optical system, including a 532 nm solid-state laser as active illumination, is established. A 17.92 mm × 14.34 mm area charge coupled device (CCD) is employed both as detector and as spatial filter. The spatial filtering characteristics are theoretically analyzed using a power spectral density function. The spatial filtering operation of CCD is performed fully by software. Therefore, the parameters of the spatial filter, such as the size and the number of spatial period, are changeable. In addition, the CCD is arranged as two differential spatial filters without any other additional elements. Experiments are carried out to examine the feasibility of CCD as two differential spatial filters and the influence of the number of spatial period on the signal frequency. The results indicate that the more number of spatial period the more accurate measurements can be obtained, and show that the relation between signal frequency and velocity has good linearity. So this velocimeter is suitable to provide velocity information for a vehicle self-contained inertial navigation system.