On the complexity of following the central path of linear programs by linear extrapolation II

A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, ) of steps needed to go from an initial pointx(R) to a final pointx(), R>>0, by an integral of the local weighted curvature of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constm log(R/), where < 1/2 e.g. = 1/4 or = 3/8 (note that = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only for 1/3.As a byproduct, many analytical and structural properties of the primal—dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.On leave from the Institute of Mathematics, Eötvös University Budapest, H-1080 Budapest, Hungary.     

Lattice disorder in silicon induced by 2.0 MeV Cu+ irradiation

The effect of 2.0 MeV Cu⁺ irradiation on Si(100) crystal has been studied by the Rutherford backscattering/channeling technique. Analysis of the lattice disorder distribution has been performed under 100 direction of tilting off from the target normal: 7°, 30°, and 45° as well as different doses. The lattice disorder distributions in Si(100) have been compared with TRIM'89 simulation. The results show that the lattice disorder distributions in Si(100) under different irradiation angles seem to be in good agreement with TRIM'89 simulation. When the dose increases up to 8.7×10¹⁴ ions/cm², the defect concentration increases leading to the formation of an amorphous layer.