Given a symmetric and positive (semi)definite $n$-by-$n$ matrix $M$ and a vector, in this paper, we consider the matrix splitting method for solving the second-order cone linear complementarity problem (SOCLCP). The matrix splitting method is among the most widely used approaches for large scale and sparse classical linear complementarity problems (LCP), and its linear convergence … Read more
We study a first-order method to find the minimum cross-sectional area ellipsoidal cylinder containing a finite set of points. This problem arises in optimal design in statistics when one is interested in a subset of the parameters. We provide convex formulations of this problem and its dual, and analyze a method based on the Frank-Wolfe … Read more
We present a simple, first-order approximation algorithm for the support vector classification problem. Given a pair of linearly separable data sets and $\epsilon \in (0,1)$, the proposed algorithm computes a separating hyperplane whose margin is within a factor of $(1-\epsilon)$ of that of the maximum-margin separating hyperplane. We discuss how our algorithm can be extended … Read more
The idea of a finite collection of closed sets having “strongly regular intersection” at a given point is crucial in variational analysis. We show that this central theoretical tool also has striking algorithmic consequences. Specifically, we consider the case of two sets, one of which we assume to be suitably “regular” (special cases being convex … Read more
Shor’s r-algorithm is an iterative method for unconstrained optimization, designed for minimizing nonsmooth functions, for which its reported success has been considerable. Although some limited convergence results are known, nothing seems to be known about the algorithm’s rate of convergence, even in the smooth case. We study how the method behaves on convex quadratics, proving … Read more
We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slaters condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function. This “agumented primal-dual function” or “apd-function” is restricted to an affine set in the primal-dual space. The evaluation of the function and its … Read more
We show the linear convergence of a simple first-order algorithm for the minimum-volume enclosing ellipsoid problem and its dual, the D-optimal design problem of statistics. Computational tests confirm the attractive features of this method. CitationOptimization Methods and Software 23 (2008), 5–19. ArticleDownload View PDF
We prove that if two smooth manifolds intersect transversally, then the method of alternating projections converges locally at a linear rate. We bound the speed of convergence in terms of the angle between the manifolds, which in turn we relate to the modulus of metric regularity for the intersection problem, a natural measure of conditioning. … Read more
This note, attempts to further Pan’s second-order quasi-Newton methods(\cite{panqn}). To complement the numerical implementation, the linear convergence of a rank-one second-order update and the least change property are presented. Citation1,Department of Mathematics, Southeast University, Nanjing, 210096, P.R.China.