Path-following interior point algorithms for the Cartesian <Emphasis Type="Italic">P</Emphasis><Subscript>*</Subscript>(κ)-LCP over symmetric cones

In this paper, we establish a theoretical framework of path-following interior point algorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P _*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P _*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms. This work was supported by National Natural Science Foundation of China (Grant Nos. 10671010, 70841008)     

Nonlinear Spherical Caps and Associated Plate and Membrane Problems

This paper deals with the existence and multiplicity problem of the equilibrium solutions of an elastic spherical cap within nonlinear strain theory. We pose the problem in the form of a three parameter bifurcation problem, one parameter being related to the load, the others to the geometry. When the geometrical parameters are different from zero, the so-called generic case, we revisit the nonuniqueness results, and explore the solutions in the parameter space. Then we analyze the formal limits as the geometrical parameters tend to zero. When the curvature tends to zero, we obtain from the nonlinear shell a von Kármán plate, a new, although natural, result. When the thickness parameter tends to zero, we get a nonlinear membrane problem. A study of the latter gives infinitely many solutions, and we discuss the construction, shapes, and stability in detail. This revised version was published online in August 2006 with corrections to the Cover Date.     

一类线性与框式约束凸规划问题的原始-对偶内点算法

本文对一类具有线性和框式约束的凸规划问题给出了一个原始-对偶内点算法, 该算法可在任一原始-对偶可行内点启动, 并且全局收敛,当初始点靠近中心路径时, 算法成为中心路径跟踪算法。 数值实验表明, 算法对求解大型的这类问题是有效的。     

Global linear convergence of a path-following algorithm for some monotone variational inequality problems

We consider a primal-scaling path-following algorithm for solving a certain class of monotone variational inequality problems. Included in this class are the convex separable programs considered by Monteiro and Adler and the monotone linear complementarity problem. This algorithm can start from any interior solution and attain a global linear rate of convergence with a convergence ratio of 1 ?c/√m, wherem denotes the dimension of the problem andc is a certain constant. One can also introduce a line search strategy to accelerate the convergence of this algorithm.     

A relaxed primal-dual path-following algorithm for linear programming

In this paper, we provide an easily satisfied relaxation condition for the primaldual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts.Partially supported by the North Carolina Supercomputing Center, the 1993 Cray Research Award, and a National Science Council Research Grant of the Republic of China.     

On the entropic perturbation and exponential penalty methods for linear programming

This note points out that the recently proposed exponential penalty approach to linear programming is identical to the well-known entropic perturbation approach. The primal and dual trajectories provided by these two approaches are shown to be equivalent.The work of the first author was supported partially by the North Carolina Supercomputing Center and 1995 Cray Research Grant.     

框式约束凸二次规划问题的内点算法

In this paper,a primal-dual interior point algorithm for convex quadratic progromming problem with box constrains is presented.It can be started at any primal-dual interior feasible point.If the initial point is close to the central path,it becomes a central path-following alogorithm and requires a total of O(√nL)number of iterations,where L is the input length.     

“Comment” on the Reply to the Paper “On the Elber–Karplus Reaction Path-Following Method and Related Procedures”

The flaws in the Reply [1] to our paper [2] have been pointed out. Elber and Karplus (EK) have not disproved our irrefutable global statement that the energy average cannot be minimized which rebuts the theoretical background of EK-type calculations. Another statement of ours has shown that even a curve for which the average energy is locally minimal for all directional perturbations in the sense of classical variational calculus cannot be identical with the reaction path (RP) defined as a steepest descent path (SDP). EK found an error in the early preprint of our theoretical paper [3] and because of this error they qualified our correct variational statement as false for all the SDPs consisting of a straight line each. Mixing global and variational arguments, EK refuted our criticism in a logically incorrect manner. In this Comment we prove that both of our earlier statements invariably remain in force and the criticism included in those has been as well-established and solid as was before.     

Superlinearly Convergent Infeasible-Interior-Point Algorithm for Degenerate LCP

A large-step infeasible path-following method is proposed for solving general linear complementarity problems with sufficient matrices. If the problem has a solution, the algorithm is superlinearly convergent from any positive starting points, even for degenerate problems. The algorithm generates points in a large neighborhood of the central path. Each iteration requires only one matrix factorization and at most three (asymptotically only two) backsolves. It has been recently proved that any sufficient matrix is a P _*()-matrix for some 0. The computational complexity of the algorithm depends on as well as on a feasibility measure of the starting point. If the starting point is feasible or close to being feasible, then the iteration complexity is . Otherwise, for arbitrary positive and large enough starting points, the iteration complexity is O((1 + )² nL). We note that, while computational complexity depends on , the algorithm itself does not.