Kim Chuan Toh
Email Address
mattohkc@nus.edu.sg
65 results
Publication Search Results
Now showing 1 - 10 of 65
Publication Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming(2007-04) Chai, J.-S.; Toh, K.-C.; MATHEMATICSWe propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. Apreconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. © Springer Science+Business Media, LLC 2007.Publication A Distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation(2007) Biswas, P.; Toh, K.-C.; Ye, Y.; MATHEMATICSWe propose a distributed algorithm for solving Euclidean metric realization problems arising from large 3-D graphs, using only noisy distance information and without any prior knowledge of the positions of any of the vertices. In our distributed algorithm, the graph is first subdivided into smaller subgraphs using intelligent clustering methods. Then a semidefinite programming relaxation and gradient search method are used to localize each subgraph. Finally, a stitching algorithm is used to find affine maps between adjacent clusters, and the positions of all points in a global coordinate system are then derived. In particular, we apply our method to the problem of finding the 3-D molecular configurations of proteins ba.sed on a. limited number of given pairwise distances between atoms. The protein molecules, all with known molecular configurations, are taken from the Protein Data Bank. Our algorithm is able to reconstruct reliably and efficiently the configurations of large protein molecules from a limited number of pairwise distances corrupted by noise, without incorporating domain knowledge such as the minimum separation distance constraints derived from van der Waals interactions. © 2008 Society for Industrial and Applied Mathematics.Publication Efficient algorithms for the smallest enclosing ball problem(2005-02) Zhou, G.; Tohemail, K.-C.; Sun, J.; DECISION SCIENCES; MATHEMATICSConsider the problem of computing the smallest enclosing ball of a set of m balls in ℛ n. Existing algorithms are known to be inefficient when n > 30. In this paper we develop two algorithms that are particularly suitable for problems where n is large. The first algorithm is based on log-exponential aggregation of the maximum function and reduces the problem into an unconstrained convex program. The second algorithm is based on a second-order cone programming formulation, with special structures taken into consideration. Our computational experiments show that both methods are efficient for large problems, with the product mn on the order of 10 7. Using the first algorithm, we are able to solve problems with n = 100 and m = 512,000 in about 1 hour.Publication SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)(Taylor & Francis, 2019-02-22) Defeng Sun; Kim-Chuan Toh; Yancheng Yuan; Xinyuan Zhao; MATHEMATICS; DEPARTMENT OF COMPUTER SCIENCEPublication Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm(2010) Wang, C.; Sun, D.; Toh, K.-C.; MATHEMATICSWe propose a Newton-CG primal proximal point algorithm (PPA) for solving large scale log-determinant optimization problems. Our algorithm employs the essential ideas of PPA, the Newton method, and the preconditioned CG solver. When applying the Newton method to solve the inner subproblem, we find that the log-determinant term plays the role of a smoothing term as in the traditional smoothing Newton technique. Focusing on the problem of maximum likelihood sparse estimation of a Gaussian graphical model, we demonstrate that our algorithm performs favorably compared to existing state-of-the-art algorithms and is much preferred when a high quality solution is required for problems with many equality constraints. © 2010 Society for Industrial and Applied Mathematics.Publication Block preconditioners for symmetric indefinite linear systems(2004-06-28) Toh, K.-C.; Phoon, K.-K.; Chan, S.-H.; CIVIL ENGINEERING; MATHEMATICSThis paper presents a systematic theoretical and numerical evaluation of three common block preconditioners in a Krylov subspace method for solving symmetric indefinite linear systems. The focus is on large-scale real world problems where block approximations are a practical necessity. The main illustration is the performance of the block diagonal, constrained, and lower triangular preconditioners over a range of block approximations for the symmetric indefinite system arising from large-scale finite element discretization of Biot's consolidation equations. This system of equations is of fundamental importance to geomechanics. Numerical studies show that simple diagonal approximations to the (1,1) block K and inexpensive approximations to the Schur complement matrix S may not always produce the most spectacular time savings when K is explicitly available, but is able to deliver reasonably good results on a consistent basis. In addition, the block diagonal preconditioner with a negative (2,2) block appears to be reasonably competitive when compared to the more complicated ones. These observation are expected to remain valid for coefficient matrices whereby the (1,1) block is sparse, diagonally significant (a notion weaker than diagonal dominance), moderately well-conditioned, and has a much larger block size than the (2,2) block. © 2004 John Wiley and Sons, Ltd.Publication An implementable proximal point algorithmic framework for nuclear norm minimization(2012-06) Liu, Y.-J.; Sun, D.; Toh, K.-C.; MATHEMATICSThe nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature. © 2011 Springer and Mathematical Optimization Society.Publication Axisymmetric lower-bound limit analysis using finite elements and second-order cone programming(2014) Tang, C.; Toh, K.-C.; Phoon, K.-K.; MATHEMATICS; CIVIL & ENVIRONMENTAL ENGINEERINGIn this paper, the formulation of a lower-bound limit analysis for axisymmetric problems by means of finite elements leads to an optimization problem with a large number of variables and constraints. For the Mohr-Coulomb criterion, it is shown that these axisymmetric problems can be solved by second-order cone programming (SOCP). First, a brief introduction to SOCP is given and how axisymmetric lowerbound limit analysis can be formulated in this way is described. Through the use of an efficient toolbox (MOSEK or SDPT3), large-scale SOCP problems can be solved in minutes on a desktop computer. The method is then applied to estimate the collapse load of circular footings and uplift capacity of single or multiplate circular anchors. By comparing the present analysis with the results reported in the literature, it is shown that the results obtained from the proposed method are accurate and computationally more efficient than the numerical lower-bound limit analysis incorporated with linear programming. © 2014 American Society of Civil Engineers.Publication A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters(2018) Yang, Lei; Li, Jia; Sun Defeng; Toh, Kim-Chuan; Dr Yang Lei; INST OF OPERATIONS RESEARCH & ANALYTICS; MATHEMATICSIn this paper, we consider the problem of computing a Wasserstein barycenter for a set of discrete probability distributions with finite supports, which finds many applications in areas such as statistics, machine learning and image processing. When the support points of the barycenter are pre-specified, this problem can be modeled as a linear program (LP) whose problem size can be extremely large. To handle this large-scale LP, we analyse the structure of its dual problem, which is conceivably more tractable and can be reformulated as a well-structured convex problem with 3 kinds of block variables and a coupling linear equality constraint. We then adapt a symmetric Gauss-Seidel based alternating direction method of multipliers (sGS-ADMM) to solve the resulting dual problem and establish its global convergence and global linear convergence rate. As a critical component for efficient computation, we also show how all the subproblems involved can be solved exactly and efficiently. This makes our method suitable for computing a Wasserstein barycenter on a large dataset, without introducing an entropy regularization term as is commonly practiced. In addition, our sGS-ADMM can be used as a subroutine in an alternating minimization method to compute a barycenter when its support points are not pre-specified. Numerical results on synthetic datasets and image datasets demonstrate that our method is highly competitive for solving large-scale problems, in comparison to two existing representative methods and the commercial software Gurobi.Publication Inference of spatial organizations of chromosomes using semi-definite embedding approach and Hi-C data(2013) Zhang, Z.; Li, G.; Toh, K.-C.; Sung, W.-K.; MATHEMATICS; COMPUTER SCIENCEFor a long period of time, scientists studied genomes assuming they are linear. Recently, chromosome conformation capture (3C) based technologies, such as Hi-C, have been developed that provide the loci contact frequencies among loci pairs in a genome-wide scale. The technology unveiled that two far-apart loci can interact in the tested genome. It indicated that the tested genome forms a 3D chromsomal structure within the nucleus. With the available Hi-C data, our next challenge is to model the 3D chromosomal structure from the 3C-dervied data computationally. This paper presents a deterministic method called ChromSDE, which applies semi-definite programming techniques to find the best structure fitting the observed data and uses golden section search to find the correct parameter for converting the contact frequency to spatial distance. To the best of our knowledge, ChromSDE is the only method which can guarantee recovering the correct structure in the noise-free case. In addition, we prove that the parameter of conversion from contact frequency to spatial distance will change under different resolutions theoretically and empirically. Using simulation data and real Hi-C data, we showed that ChromSDE is much more accurate and robust than existing methods. Finally, we demonstrated that interesting biological findings can be uncovered from our predicted 3D structure. © 2013 Springer-Verlag.