ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Thu, 09 Feb 2023 05:36:52 GMT2023-02-09T05:36:52Z50651- Comparison of MSSOR versus ILU(0) preconditioners for Biot's FEM consolidation equationshttps://scholarbank.nus.edu.sg/handle/10635/74107Title: Comparison of MSSOR versus ILU(0) preconditioners for Biot's FEM consolidation equations
Authors: Phoon, K.K.; Chaudhary, K.B.; Toh, K.C.
Abstract: Numerical performance of two different preconditioning approaches, modified SSOR (MSSOR) preconditioner and incomplete factorization with zero fill-in (ILU0) preconditioner, is compared for the iterative solution of symmetric indefinite linear systems arising from finite element discretization of the Biot's consolidation equations. Numerical results show that the nodal ordering affect the performance of ILU0 whereas MSSOR is less affected. The statistics proposed by Chow and Saad (1997) is demonstrated to be useful in diagnosing the failure of ILU factorization. The stabilized ILU0 coupled with symmetric quasi-minimal residual (SQMR) method is about 10-50% efficient time-wise (especially in the heterogeneous soil condition) than MSSOR-preconditioned system. However, the determination of a proper stabilization parameter (thresh value) for the replacement of smaller pivots is largely problem dependant. The optimal balance can only be identified through numerical experiments - a luxury that practitioners can ill-afford and completely self-defeating if the goal is to solve a problem in a shortest time.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/741072008-01-01T00:00:00Z
- Infeasible potential reduction algorithms for semidefinite programminghttps://scholarbank.nus.edu.sg/handle/10635/103419Title: Infeasible potential reduction algorithms for semidefinite programming
Authors: Zhao, X.-Y.; Toh, K.-C.
Abstract: We design infeasible potential reduction algorithms for primal semidefinite programming (SDP) problems that simultaneously seek feasibility and optimality. The algorithms are based on those in [Anstre- icher, Math. Prog. 52 (1991), pp.429-439] and [Todd, Math. Prog. 59 (1993), pp.133-150] for linear programming. Because a dual algorithm is expected to be computationally advantageous for large sparse problems, we also propose a dual infeasible potential reduction algorithm for dual SDP problems. We analyze the convergence of the algorithms, and implement them to compare their relative performance. © 2012 Yokohama Publishers.
Mon, 01 Oct 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1034192012-10-01T00:00:00Z
- GMRES vs. ideal GMREShttps://scholarbank.nus.edu.sg/handle/10635/103347Title: GMRES vs. ideal GMRES
Authors: Toh, K.-C.
Abstract: The GMRES algorithm minimizes ∥p(A)b∥ over polynomials p of degree n normalized at z = 0. The ideal GMRES problem is obtained if one considers minimization of ∥p(A)∥ instead. The ideal problem forms an upper bound for the worst-case true problem, where the GMRES norm ∥pb(A)b∥ is maximized over b. In work not yet published, Faber, Joubert, Knill, and Manteuffel have shown that this upper bound need not be attained, constructing a 4 × 4 example in which the ratio of the true to ideal GMRES norms is 0.9999. Here, we present a simpler 4 × 4 example in which the ratio approaches zero when a certain parameter tends to zero. The same example also leads to the same conclusion for Arnoldi vs. ideal Arnoldi norms.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1033471997-01-01T00:00:00Z
- From potential theory to matrix iterations in six stepshttps://scholarbank.nus.edu.sg/handle/10635/103305Title: From potential theory to matrix iterations in six steps
Authors: Driscoll, T.A.; Toh, K.-C.; Trefethen, L.N.
Abstract: The theory of the convergence of Krylov subspace iterations for linear systems of equations (conjugate gradients, biconjugate gradients, GMRES, QMR, Bi-CGSTAB, and so on) is reviewed. For a computation of this kind, an estimated asymptotic convergence factor ρ ≤ 1 can be derived by solving a problem of potential theory or conformal mapping. Six approximations are involved in relating the actual computation to this scalar estimate. These six approximations are ; discussed in a systematic way and illustrated by a sequence of examples computed with tools of numerical conformal mapping and semidefinite programming.
Tue, 01 Sep 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1033051998-09-01T00:00:00Z
- An analytic center cutting plane method for semidefinite feasibility problemshttps://scholarbank.nus.edu.sg/handle/10635/44210Title: An analytic center cutting plane method for semidefinite feasibility problems
Authors: Sun, J.; Toh, K.-C.; Zhao, G.
Abstract: Semidefinite feasibility problems arise in many areas of operations research. The abstract form of these problems can be described as finding a point in a nonempty bounded convex body Γ in the cone of symmetric positive semidefinite matrices. Assume that Γ is defined by an oracle, which for any given m × m symmetric positive semidefinite matrix Ŷ either confirms that Ŷ ε Γ or returns a cut, i.e., a symmetric matrix A such that Γ is in the half-space {Y : A · Y ≤ A · Ŷ}. We study an analytic center cutting plane algorithm for this problem. At each iteration, the algorithm computes an approximate analytic center of a working set defined by the cutting plane system generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise the new cutting plane returned by the oracle is added into the system. As the number of iterations increases, the working set shrinks and the algorithm eventually finds a solution to the problem. All iterates generated by the algorithm are positive definite matrices. The algorithm has a worst-case complexity of O* (m3/ε2) on the total number of cuts to be used, where ε is the maximum radius of a ball contained by Γ.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442102002-01-01T00:00:00Z
- On the implementation of SDPT3 (version 3.1) - A MATLAB software package for semidefinite-quadratic-linear programminghttps://scholarbank.nus.edu.sg/handle/10635/104601Title: On the implementation of SDPT3 (version 3.1) - A MATLAB software package for semidefinite-quadratic-linear programming
Authors: Toh, K.C.; Tütüncü, R.H.; Todd, M.J.
Abstract: This code is designed to solve conic programming problems whose constraint cone is a product of semidefinite cones, second-order cones, nonnegative orthants and Euclidean spaces. It employs a primaldual predictor-corrector path-following method, with either the HKM or the NT search direction. The basic code is written in MATLAB, but key subroutines in Fortran and C are incorporated via a Mex interface. Routines are provided to read in problems in either SDPA or SeDuMi format. Sparsity and block diagonal structure are exploited, but the latter needs to be given explicitly or detected via a subroutine that is provided. Various techniques to improve the efficiency and stablility of the algorithm are incorporated. For example, step-lengths associated with semidefinite cones are calculated via the Lanczos method. Numerical experiments show that this general purpose code can solve 80% of a total of about 300 problems to an accuracy of at least 10 -6 in relative duality gap and infeasibilities. © 2004 IEEE.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1046012004-01-01T00:00:00Z
- The Chebyshev polynomials of a matrixhttps://scholarbank.nus.edu.sg/handle/10635/104262Title: The Chebyshev polynomials of a matrix
Authors: Toh, K.-C.; Trefethen, L.N.
Abstract: A Chebyshev polynomial of a square matrix A is a monic polynomial p of specified degree that minimizes; p(A); 2. The study of such polynomials is motivated by the analysis of Krylov subspace iterations in numerical linear algebra. An algorithm is presented for computing these polynomials based on reduction to a semidefinite program which is then solved by a primal-dual interior point method. Examples of Chebyshev polynomials of matrices are presented, and it is noted that if A is far from normal, the lemniscates of these polynomials tend to approximate pseudospectra of A.
Thu, 01 Oct 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1042621998-10-01T00:00:00Z
- The Kreiss matrix theorem on a general complex domainhttps://scholarbank.nus.edu.sg/handle/10635/104310Title: The Kreiss matrix theorem on a general complex domain
Authors: Toh, K.-C.; Trefethen, L.N.
Abstract: Let A be a bounded linear operator in a Hilbert space H with spectrum A (A). The Kreiss matrix theorem gives bounds based on the resolvent norm ∥ (2I - A)-1 ∥ for ∥An ∥if A (A) is in the unit disk or for ∥etA∥ if A(A) is in the left half-plane. We generalize these results to a complex domain Ω, giving bounds for ∥ Fn (A) ∥ if A (A) ⊂ Ω, where Fn denotes the nth Faber polynomial associated with Ω. One of our bounds takes the form K̄ (Ω) ≤ 2 sup ∥ Fn (A) ∥, ∥ Fn (A) ∥ ≤ 2 e (n +) K̄(Ω), n where K̄(Ω) is the "Kreiss constant" defined by K̄(Ω) = inf { C : ∥ (zI - A)-1 ∥ ≤ C/dist(z, Ω) ∀ z ∉ Ω}. By means of an inequality due originally to Bernstein, the second inequality can be extended to general polynomials pn. In the case where H is finite-dimensional, say, dim(H) = N, analogous results are also established in which ∥ Fn (A)∥ is bounded in terms of N instead of n when the boundary of Ω is twice continuously differentiable.
Sun, 01 Aug 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1043101999-08-01T00:00:00Z
- Fast iterative solution of large undrained soil-structure interaction problemshttps://scholarbank.nus.edu.sg/handle/10635/65585Title: Fast iterative solution of large undrained soil-structure interaction problems
Authors: Phoon, K.-K.; Chan, S.-H.; Toh, K.-C.; Lee, F.-H.
Abstract: In view of rapid developments in iterative solvers, it is timely to re-examine the merits of using mixed formulation for incompressible problems. This paper presents extensive numerical studies to compare the accuracy of undrained solutions resulting from the standard displacement formulation with a penalty term and the two-field mixed formulation. The standard displacement and two-field mixed formulations are solved using both direct and iterative approaches to assess if it is cost-effective to achieve more accurate solutions. Numerical studies of a simple footing problem show that the mixed formulation is able to solve the incompressible problem 'exactly', does not create pressure and stress instabilities, and obviate the need for an ad hoc penalty number. In addition, for large-scale problems where it is not possible to perform direct solutions entirely within available random access memory, it turns out that the larger system of equations from mixed formulation also can be solved much more efficiently than the smaller system of equations arising from standard formulation by using the symmetric quasi-minimal residual (SQMR) method with the generalized Jacobi (GJ) preconditioner. Iterative solution by SQMR with GJ preconditioning also is more elegant, faster, and more accurate than the popular Uzawa method. © 2003 John Wiley and Sons, Ltd.
Sat, 01 Mar 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/655852003-03-01T00:00:00Z
- An efficient diagonal preconditioner for finite element solution of Biot's consolidation equationshttps://scholarbank.nus.edu.sg/handle/10635/65118Title: An efficient diagonal preconditioner for finite element solution of Biot's consolidation equations
Authors: Phoon, K.K.; Toh, K.C.; Chan, S.H.; Lee, F.H.
Abstract: Finite element simulations of very large-scale soil-structure interaction problems (e.g. excavations, tunnelling, pile-rafts, etc.) typically involve the solution of a very large, ill-conditioned, and indefinite Biot system of equations. The traditional preconditioned conjugate gradient solver coupled with the standard Jacobi (SJ) preconditioner can be very inefficient for this class of problems. This paper presents a robust generalized Jacobi (GJ) preconditioner that is extremely effective for solving very large-scale Biot's finite element equations using the symmetric quasi-minimal residual method. The GJ preconditioner can be formed, inverted, and implemented within an 'element-by-element' framework as readily as the SJ preconditioner. It was derived as a diagonal approximation to a theoretical form, which can be proven mathematically to possess an attractive eigenvalue clustering property. The effectiveness of the GJ preconditioner over a wide range of soil stiffness and permeability was demonstrated numerically using a simple three-dimensional footing problem. This paper casts a new perspective on the potentialities of the simple diagonal preconditioner, which has been commonly perceived as being useful only in situations where it can serve as an approximate inverse to a diagonally dominant coefficient matrix. Copyright © 2002 John Wiley & Sons, Ltd.
Thu, 10 Oct 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/651182002-10-10T00:00:00Z
- A polynomial-time inexact primal-dual infeasible path-following algorithm for convex quadratic SDPhttps://scholarbank.nus.edu.sg/handle/10635/102728Title: A polynomial-time inexact primal-dual infeasible path-following algorithm for convex quadratic SDP
Authors: Li, L.; Toh, K.-C.
Abstract: Convex quadratic semidefinite programming (QSDP) has been widely applied in solving engineering and scientific problems such as nearest correlation problems and nearest Euclidean distance matrix problems. In this paper, we study an inexact primal-dual infeasible path-following algorithm for QSDP problems of the form: minX{1/2 X • Q(X) + C • X: A(X) = b, X ≥ 0}, where Q is a self-adjoint positive semidefinite linear operator on Sn, b ∈ Rm, and A is a linear map from Sn to Rm. This algorithm is designed for the purpose of using an iterative solver to compute an approximate search direction at each iteration. It does not require feasibility to be maintained even if some iterates happened to be feasible. By imposing mild conditions on the inexactness of the computed directions, we show that the algorithm can find an ∈-solution in O(n2 ln(1/∈)) iterations. © Yokohama Publishers.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027282011-01-01T00:00:00Z
- A proximal point algorithm for sequential feature extraction applicationshttps://scholarbank.nus.edu.sg/handle/10635/102738Title: A proximal point algorithm for sequential feature extraction applications
Authors: Doan, X.V.; Toh, K.-C.; Vavasis, S.
Abstract: We propose a proximal point algorithm to solve the LAROS problem, that is, the problem of finding a "large approximately rank-one submatrix." This LAROS problem is used to sequentially extract features in data. We also develop new stopping criteria for the proximal point algorithm, which is based on the duality conditions of ε-optimal solutions of the LAROS problem, with a theoretical guarantee. We test our algorithm with two image databases and show that we can use the LAROS problem to extract appropriate common features from these images. © 2013 Society for Industrial and Applied Mathematics.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027382013-01-01T00:00:00Z
- Analytic center cutting-plane method with deep cuts for semidefinite feasibility problemshttps://scholarbank.nus.edu.sg/handle/10635/102860Title: Analytic center cutting-plane method with deep cuts for semidefinite feasibility problems
Authors: Chua, S.K.; Toh, K.C.; Zhao, G.Y.
Abstract: An analytic center cutting-plane method with deep cuts for semidefinite feasibility problems is presented. Our objective in these problems is to find a point in a nonempty bounded convex set Γ in the cone of symmetric positive-semidefinite matrices. The cutting plane method achieves this by the following iterative scheme. At each iteration, a query point Ŷ that is an approximate analytic center of the current working set is chosen. We assume that there exists an oracle which either confirms that Ŷ ∈ Γ or returns a cut A ∈ S m such that {Y ∈ S m: A• Y ≤ A• Ŷ - ξ} ⊃Γ, where ξ ≥ 0. Ŷ ∉ Γ, an approximate analytic center of the new working set, defined by adding the new cut to the preceding working set, is then computed via a primal Newton procedure. Assuming that Γ contains a ball with radius ε > 0, the algorithm obtains eventually a point in Γ, with a worst-case complexity of O*(m 3/ε 2) on the total number of cuts generated.
Mon, 01 Nov 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028602004-11-01T00:00:00Z
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problemshttps://scholarbank.nus.edu.sg/handle/10635/102811Title: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
Authors: Toh, K.-C.; Yun, S.
Abstract: The affine rank minimization problem, which consists of finding a matrix of minimum rank subject to linear equality constraints, has been proposed in many areas of engineering and science. A specific rank minimization problem is the matrix completion problem, in which we wish to recover a (low-rank) data matrix from incomplete samples of its entries. A recent convex relaxation of the rank minimization problem minimizes the nuclear norm instead of the rank of the matrix. Another possible model for the rank minimization problem is the nuclear norm regularized linear least squares problem. This regularized problem is a special case of an unconstrained nonsmooth convex optimization problem, in which the objective function is the sum of a convex smooth function with Lipschitz continuous gradient and a convex function on a set of matrices. In this paper, we propose an accelerated proximal gradient algorithm, which terminates in O(1/??) iterations with an ε-optimal solution, to solve this unconstrained nonsmooth convex optimization problem, and in particular, the nuclear norm regularized linear least squares problem. We report numerical results for solving large-scale randomly generated matrix completion problems. The numerical results suggest that our algorithm is efficient and robust in solving large-scale random matrix completion problems. In particular, we are able to solve random matrix completion problems with matrix dimensions up to 105 each in less than 10 minutes on a modest PC. © 2010 Yokohama Publishers.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028112010-01-01T00:00:00Z
- Primal-dual path-following algorithms for determinant maximization problems with linear matrix inequalitieshttps://scholarbank.nus.edu.sg/handle/10635/103971Title: Primal-dual path-following algorithms for determinant maximization problems with linear matrix inequalities
Authors: Toh, K.-C.
Abstract: Primal-dual path-following algorithms are considered for determinant maximization problem (maxdet-problem). These algorithms apply Newton's method to a primal-dual central path equation similar to that in semidefinite programming (SDP) to obtain a Newton system which is then symmetrized to avoid nonsymmetric search direction. Computational aspects of the algorithms are discussed, including Mehrotra-type predictor-corrector variants. Focusing on three different symmetrizations, which leads to what are known as the AHO, H..K..M and NT directions in SDP, numerical results for various classes of maxdet-problem are given. The computational results show that the proposed algorithms are efficient, robust and accurate.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1039711999-01-01T00:00:00Z
- Inference of spatial organizations of chromosomes using semi-definite embedding approach and Hi-C datahttps://scholarbank.nus.edu.sg/handle/10635/43253Title: Inference of spatial organizations of chromosomes using semi-definite embedding approach and Hi-C data
Authors: Zhang, Z.; Li, G.; Toh, K.-C.; Sung, W.-K.
Abstract: For 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.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432532013-01-01T00:00:00Z
- On the Nesterov-Todd direction in semidefinite programminghttps://scholarbank.nus.edu.sg/handle/10635/103817Title: On the Nesterov-Todd direction in semidefinite programming
Authors: Todd, M.J.; Toh, K.C.; Tütüncü, R.H.
Abstract: We study different choices of search direction for primal-dual interior-point methods for semidefinite programming problems. One particular choice we consider comes from a specialization of a class of algorithms developed by Nesterov and Todd for certain convex programming problems. We discuss how the search directions for the Nesterov-Todd (NT) method can be computed efficiently and demonstrate how they can be viewed as Newton directions. This last observation also leads to convenient computation of accelerated steps, using the Mehrotra predictor-corrector approach, in the NT framework. We also provide an analytical and numerical comparison of several methods using different search directions, and suggest that the method using the NT direction is more robust than alternative methods.
Sat, 01 Aug 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1038171998-08-01T00:00:00Z
- Fast iterative solution of large soil-structure interaction problems in varied ground conditionshttps://scholarbank.nus.edu.sg/handle/10635/75135Title: Fast iterative solution of large soil-structure interaction problems in varied ground conditions
Authors: Chaudhary, K.B.; Phoon, K.K.; Toh, K.C.
Abstract: Many geotechnical problems involve a wide range of materials with vast difference in stiffness and permeability resulting in an ill-conditioned system. Existing practical preconditioners perform poorly for such problems while incomplete factorization preconditioners may show signs of instability. Recent advances in preconditioning show that the inexact block diagonal preconditioners are much less sensitive to any difference in such material properties for the iterative solution of soil-structure interaction problems. This paper highlights the general applicability of such preconditioners to large-scale geotechnical problems in realistic ground conditions with the help of a user defined solver interface in the commercial GeoFEA software. The practical observation is that nonhomogeneous soil and structural elements do not impose a problem for the new preconditioners. In fact, they can be even more effective as the system accumulates more and more stiff soil and/or structural elements.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/751352011-01-01T00:00:00Z
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)https://scholarbank.nus.edu.sg/handle/10635/162533Title: SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
Authors: Defeng Sun; Kim-Chuan Toh; Yancheng Yuan; Xinyuan Zhao
Fri, 22 Feb 2019 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1625332019-02-22T00:00:00Z
- SDPT3 - a MATLAB software package for semidefinite programming, version 1.3https://scholarbank.nus.edu.sg/handle/10635/104081Title: SDPT3 - a MATLAB software package for semidefinite programming, version 1.3
Authors: Toh, K.C.; Todd, M.J.; Tütüncü, R.H.
Abstract: This software package is a MATLAB implementation of infeasible path-following algorithms for solving standard semidefinite programs (SDP). Mehrotra-type predictor-corrector variants are included. Analogous algorithms for the homogeneous formulation of the standard SDP are also implemented. Four types of search directions are available, namely, the AHO, HKM, NT, and GT directions. A few classes of SDP problems are included as well. Numerical results for these classes show that our algorithms are fairly efficient and robust on problems with dimensions of the order of a hundred.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1040811999-01-01T00:00:00Z
- A Newton-bracketing method for a simple conic optimization problemhttps://scholarbank.nus.edu.sg/handle/10635/191913Title: A Newton-bracketing method for a simple conic optimization problem
Authors: Sunyoung Kim; Masakazu Kojima; Kim-Chuan Toh
Wed, 01 Jul 2020 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1919132020-07-01T00:00:00Z
- A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycentershttps://scholarbank.nus.edu.sg/handle/10635/169192Title: A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
Authors: Yang, Lei; Li, Jia; Sun Defeng; Toh, Kim-Chuan
Abstract: In 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.
Mon, 01 Jan 2018 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1691922018-01-01T00:00:00Z
- Symmetric indefinite preconditioners for FE solution of Biot's consolidation problemhttps://scholarbank.nus.edu.sg/handle/10635/74391Title: Symmetric indefinite preconditioners for FE solution of Biot's consolidation problem
Authors: Chen, X.; Phoon, K.-K.; Toh, K.-C.
Abstract: The finite element discretization of time-dependent Biot's coupled consolidation equations typically gives rise to large symmetric indefinite linear systems. This paper reviews several symmetric indefinite preconditioners developed recently which can be used in conjunction with symmetric iterative methods such as SQMR or PCG. A numerical example shows that SQMR methods preconditioned by the proposed preconditioners are significantly more efficient time-wise than direct solution methods such as multifrontal solver (MA47, HSL2000) for large-scale symmetric indefinite linear systems. Copyright ASCE 2006.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/743912006-01-01T00:00:00Z
- A newton-cg augmented lagrangian method for semidefinite programminghttps://scholarbank.nus.edu.sg/handle/10635/102695Title: A newton-cg augmented lagrangian method for semidefinite programming
Authors: Zhao, X.-Y.; Sun, D.; Toh, K.-C.
Abstract: We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive definiteness of the generalized Hessian of the objective function in these inner problems, a key property for ensuring the efficiency of using an inexact semismooth Newton-CG method to solve the inner problems, is equivalent to the constraint nondegeneracy of the corresponding dual problems. Numerical experiments on a variety of large-scale SDP problems with the matrix dimension n up to 4, 110 and the number of equality constraints m up to 2, 156, 544 show that the proposed method is very efficient. We are also able to solve the SDP problem fap36 (with n = 4, 110 and m = 1, 154, 467) in the Seventh DIMACS Implementation Challenge much more accurately than in previous attempts. Copyright © 2010, Society for Industrial and Applied Mathematics.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026952010-01-01T00:00:00Z
- Block constrained versus generalized Jacobi preconditioners for iterative solution of large-scale Biot's fem equationshttps://scholarbank.nus.edu.sg/handle/10635/84705Title: Block constrained versus generalized Jacobi preconditioners for iterative solution of large-scale Biot's fem equations
Authors: Phoon, K.K.; Toh, K.C.; Chen, X.
Abstract: Generalized Jacobi (GJ) diagonal preconditioner coupled with symmetric quasi-minimal residual (SQMR) method has been demonstrated to be efficient for solving the 2 × 2 block linear system of equations arising from discretized Biot's consolidation equations. However, one may further improve the performance by employing a more sophisticated non-diagonal preconditioner. This paper proposes to employ a block constrained preconditioner Pc that uses the same 2 × 2 block matrix but its (1, 1) block is replaced by a diagonal approximation. Numerical results on a series of 3-D footing problems show that the SQMR method preconditioned by Pc is about 55% more efficient time-wise than the counterpart preconditioned by GJ when the problem size increases to about 180,000 degrees of freedom. Over the range of problem sizes studied, the Pc-preconditioned SQMR method incurs about 20% more memory than the GJ-preconditioned counterpart. The paper also addresses crucial computational and storage issues in constructing and storing P c efficiently to achieve superior performance over GJ on the commonly available PC platforms. © 2004 Elsevier Ltd. All rights reserved.
Mon, 01 Nov 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/847052004-11-01T00:00:00Z
- Block preconditioners for symmetric indefinite linear systemshttps://scholarbank.nus.edu.sg/handle/10635/65243Title: Block preconditioners for symmetric indefinite linear systems
Authors: Toh, K.-C.; Phoon, K.-K.; Chan, S.-H.
Abstract: This 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.
Mon, 28 Jun 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/652432004-06-28T00:00:00Z
- A probabilistic model for minmax regret in combinatorial optimizationhttps://scholarbank.nus.edu.sg/handle/10635/102736Title: A probabilistic model for minmax regret in combinatorial optimization
Authors: Natarajan, K.; Shi, D.; Toh, K.-C.
Abstract: In this paper, we propose a new probabilistic model for minimizing the anticipated regret in combinatorial optimization problems with distributional uncertainty in the objective coefficients. The interval uncertainty representation of data is supplemented with information on the marginal distributions. As a decision criterion, we minimize the worst-case conditional value at risk of regret. The proposed model includes the interval data minmax regret model as a special case. For the class of combinatorial optimization problems with a compact convex hull representation, a polynomial sized mixed-integer linear program is formulated when (a) the range and mean are known, and (b) the range, mean, and mean absolute deviation are known; and a mixed-integer second order cone program is formulated when (c) the range, mean, and standard deviation are known. For the subset selection problem of choosing K elements of maximum total weight out of a set of N elements, the probabilistic regret model is shown to be solvable in polynomial time in the instances (a) and (b) above. This extends the current known polynomial complexity result for minmax regret subset selection with range information only. © 2014 INFORMS.
Wed, 01 Jan 2014 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027362014-01-01T00:00:00Z
- Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programminghttps://scholarbank.nus.edu.sg/handle/10635/103964Title: Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming
Authors: Chai, J.-S.; Toh, K.-C.
Abstract: We 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.
Sun, 01 Apr 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1039642007-04-01T00:00:00Z
- An accelerated proximal gradient algorithm for frame-based image restoration via the balanced approachhttps://scholarbank.nus.edu.sg/handle/10635/102810Title: An accelerated proximal gradient algorithm for frame-based image restoration via the balanced approach
Authors: Shen, Z.; Toh, K.-C.; Yun, S.
Abstract: Frame-based image restoration by using the balanced approach has been developed over the last decade. Many recently developed algorithms for image restoration can be viewed as an acceleration of the proximal forward-backward splitting algorithm. Accelerated proximal (APG) algorithms studied by Nesterov, Nemirovski, and others have been demonstrated to be efficient in solving various regularized convex optimization problems arising in compressed sensing, machine learning, and control. In this paper, we adapt the APG algorithm to solve the ℓ1-regularized linear least squares problem in the balanced approach in frame-based image restoration. This algorithm terminates in O(1/√j{cyrillic, ukrainian}) iterations with an j{cyrillic, ukrainian}-optimal solution, and we demonstrate that this single algorithmic framework can universally handle several image restoration problems, such as image deblurring, denoising, inpainting, and cartoon-texture decomposition. Our numerical results suggest that the APG algorithms are efficient and robust in solving large-scale image restoration problems. The algorithms we implemented are able to restore 512 × 512 images in various image restoration problems in less than 50 seconds on a modest PC. We also compare the numerical performance of our proposed algorithms applied to image restoration problems by using one frame-based system with that by using cartoon and texture systems for image deblurring, denoising, and inpainting. © by SIAM.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028102011-01-01T00:00:00Z
- Solving second order cone programming via a reduced augmented system approachhttps://scholarbank.nus.edu.sg/handle/10635/104149Title: Solving second order cone programming via a reduced augmented system approach
Authors: Cai, Z.; Toh, K.-C.
Abstract: The standard Schur complement equation-based implementation of interior-point methods for second order cone programming may encounter stability problems in the computation of search directions, and as a consequence, accurate approximate optimal solutions are sometimes not attainable. Based on the eigenvalue decomposition of the (1,1) block of the augmented equation, a reduced augmented equation approach is proposed to ameliorate the stability problems. Numerical experiments show that the new approach can achieve more accurate approximate optimal solutions than the Schur complement equation-based approach. © 2006 Society for Industrial and Applied Mathematics.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1041492006-01-01T00:00:00Z
- Efficient algorithms for the smallest enclosing ball problemhttps://scholarbank.nus.edu.sg/handle/10635/114324Title: Efficient algorithms for the smallest enclosing ball problem
Authors: Zhou, G.; Tohemail, K.-C.; Sun, J.
Abstract: Consider 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.
Tue, 01 Feb 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1143242005-02-01T00:00:00Z
- Solving semidefinite-quadratic-linear programs using SDPT3https://scholarbank.nus.edu.sg/handle/10635/104150Title: Solving semidefinite-quadratic-linear programs using SDPT3
Authors: Tütüncü, R.H.; Toh, K.C.; Todd, M.J.
Abstract: This paper discusses computational experiments with linear optimization problems involving semidefinite, quadratic, and linear cone constraints (SQLPs). Many test problems of this type are solved using a new release of SDPT3, a MATLAB implementation of infeasible primal-dual path-following algorithms. The software developed by the authors uses Mehrotra-type predictor-corrector variants of interior-point methods and two types of search directions: the HKM and NT directions. A discussion of implementation details is provided and computational results on problems from the SDPLIB and DIMACS Challenge collections are reported.
Sat, 01 Feb 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1041502003-02-01T00:00:00Z
- Superlinear convergence of a Newton-type algorithm for monotone equationshttps://scholarbank.nus.edu.sg/handle/10635/104224Title: Superlinear convergence of a Newton-type algorithm for monotone equations
Authors: Zhou, G.; Toh, K.C.
Abstract: We consider the problem of finding solutions of systems of monotone equations. The Newton-type algorithm proposed in Ref. 1 has a very nice global convergence property in that the whole sequence of iterates generated by this algorithm converges to a solution, if it exists. Superlinear convergence of this algorithm is obtained under a standard nonsingularity assumption. The nonsingularity condition implies that the problem has a unique solution; thus, for a problem with more than one solution, such a nonsingularity condition cannot hold. In this paper, we show that the superlinear convergence of this algorithm still holds under a local error-bound assumption that is weaker than the standard nonsingularity condition. The local error-bound condition may hold even for problems with nonunique solutions. As an application, we obtain a Newton algorithm with very nice global and superlinear convergence for the minimum norm solution of linear programs. © 2005 Springer Science+Business Media, Inc.
Fri, 01 Apr 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1042242005-04-01T00:00:00Z
- A note on the calculation of step-lengths in interior-point methods for semidefinite programminghttps://scholarbank.nus.edu.sg/handle/10635/102713Title: A note on the calculation of step-lengths in interior-point methods for semidefinite programming
Authors: Toh, K.-C.
Abstract: In each iteration of an interior-point method for semidefinite programming, the maximum step-length that can be taken by the iterate while maintaining the positive semidefiniteness constraint needs to be estimated. In this note, we show how the maximum step-length can be estimated via the Lanczos iteration, a standard iterative method for estimating the extremal eigenvalues of a matrix. We also give a posteriori error bounds for the estimate. Numerical results on the performance of the proposed method against two commonly used methods for calculating step-lengths (backtracking via Cholesky factorizations and exact eigenvalues computations) are included.
Fri, 01 Mar 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027132002-03-01T00:00:00Z
- A block coordinate gradient descent method for regularized convex separable optimization and covariance selectionhttps://scholarbank.nus.edu.sg/handle/10635/102605Title: A block coordinate gradient descent method for regularized convex separable optimization and covariance selection
Authors: Yun, S.; Tseng, P.; Toh, K.-C.
Abstract: We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ1-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated asBCGD)for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n3/ε) iterations with an ε-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807-1827, 2009; SIAM J Matrix Anal Appl 31:2000-2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for largescale covariance selection problems with constraints. © Springer and Mathematical Optimization Society 2011.
Sat, 01 Oct 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026052011-10-01T00:00:00Z
- Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithmhttps://scholarbank.nus.edu.sg/handle/10635/104148Title: Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm
Authors: Wang, C.; Sun, D.; Toh, K.-C.
Abstract: We 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.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1041482010-01-01T00:00:00Z
- Comparison between iterative solution of symmetric and non-symmetric forms of Biot's FEM equations using the generalized Jacobi preconditionerhttps://scholarbank.nus.edu.sg/handle/10635/65314Title: Comparison between iterative solution of symmetric and non-symmetric forms of Biot's FEM equations using the generalized Jacobi preconditioner
Authors: Toh, K.-C.; Phoon, K.-K.
Abstract: Finite element discretization of Biot's consolidation equations can produce a symmetric indefinite system (commonly used in geomechanics) or a non-symmetric system. While this difference appears to be minor, however, it will require the selection of entirely different Krylov subspace solvers with potentially significant impact on solution efficiency. The former is solved using the symmetric quasi-minimal residual whereas the latter is solved using the popular bi-conjugate gradient stabilized. This paper presents an extensive comparison of the symmetric and non-symmetric forms by varying the time step, size of the spatial domain, choice of physical units, and left versus left-right preconditioning. The generalized Jacobi (GJ) preconditioner is able to handle the non-symmetric version of Biot's finite element method equation, although there are no practical incentives to do so. The convergence behaviour of GJ-preconditioned systems and its relation to the spectral condition number or the complete spectrum are studied to clarify the concept of ill-conditioning within the context of iteration solvers. Copyright © 2007 John Wiley & Sons, Ltd.
Wed, 25 Jun 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/653142008-06-25T00:00:00Z
- A proximal point algorithm for log-determinant optimization with group Lasso regularizationhttps://scholarbank.nus.edu.sg/handle/10635/102737Title: A proximal point algorithm for log-determinant optimization with group Lasso regularization
Authors: Yang, J.; Sun, D.; Toh, K.-C.
Abstract: We consider the covariance selection problem where variables are clustered into groups and the inverse covariance matrix is expected to have a blockwise sparse structure. This problem is realized via penalizing the maximum likelihood estimation of the inverse covariance matrix by group Lasso regularization. We propose to solve the resulting log-determinant optimization problem with the classical proximal point algorithm (PPA). At each iteration, as it is difficult to update the primal variables directly, we first solve the dual subproblem by an inexact semismooth Newton-CG method and then update the primal variables by explicit formulas based on the computed dual variables. We also propose to accelerate the PPA by an inexact generalized Newton's method when the iterate is close to the solution. Theoretically, we prove that at the optimal solution, the nonsingularity of the generalized Hessian matrices of the dual subproblem is equivalent to the constraint nondegeneracy condition for the primal problem. Global and local convergence results are also presented for the proposed PPA. Moreover, based on the augmented Lagrangian function of the dual problem we derive an alternating direction method (ADM), which is easily implementable and is demonstrated to be efficient for random problems. Numerical results, including comparisons with the ADM on both synthetic and real data, are presented to demonstrate that the proposed Newton-CG based PPA is stable and efficient and, in particular, outperforms the ADM when high accuracy is required. © 2013 Society for Industrial and Applied Mathematics.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027372013-01-01T00:00:00Z
- An inexact interior point method for L1-regularized sparse covariance selectionhttps://scholarbank.nus.edu.sg/handle/10635/102842Title: An inexact interior point method for L1-regularized sparse covariance selection
Authors: Li, L.; Toh, K.-C.
Abstract: Sparse covariance selection problems can be formulated as logdeterminant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal-dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal-dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms. © Springer and Mathematical Optimization Society 2010.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028422010-01-01T00:00:00Z
- A modified SSOR preconditioner for sparse symmetric indefinite linear systems of equationshttps://scholarbank.nus.edu.sg/handle/10635/54428Title: A modified SSOR preconditioner for sparse symmetric indefinite linear systems of equations
Authors: Chen, X.; Toh, K.C.; Phoon, K.K.
Abstract: The standard SSOR preconditioner is ineffective for the iterative solution of the symmetric indefinite linear systems arising from finite element discretization of the Biot's consolidation equations. In this paper, a modified block SSOR preconditioner combined with the Eisenstat-trick implementation is proposed. For actual implementation, a pointwise variant of this modified block SSOR preconditioner is highly recommended to obtain a compromise between simplicity and effectiveness. Numerical experiments show that the proposed modified SSOR preconditioned symmetric QMR solver can achieve faster convergence than several effective preconditioners published in the recent literature in terms of total runtime. Moreover, the proposed modified SSOR preconditioners can be generalized to non-symmetric Biot's systems. Copyright © 2005 John Wiley & Sons, Ltd.
Sun, 05 Feb 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/544282006-02-05T00:00:00Z
- Fast Algorithms for Large-Scale Generalized Distance Weighted Discriminationhttps://scholarbank.nus.edu.sg/handle/10635/144831Title: Fast Algorithms for Large-Scale Generalized Distance Weighted Discrimination
Authors: Xin Yee Lam; J. S. Marron; Defeng Sun; Kim-Chuan Toh
Thu, 17 May 2018 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1448312018-05-17T00:00:00Z
- Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problemshttps://scholarbank.nus.edu.sg/handle/10635/104538Title: Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems
Authors: Freund, R.M.; Ordóñez, F.; Toh, K.-C.
Abstract: We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the sample correlation (CORR) between these measures and IPM iteration counts (solved using the software SDPT3) when these measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.901), and provides a very good explanation of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations. © Springer-Verlag 2007.
Thu, 01 Mar 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1045382007-03-01T00:00:00Z
- Partitioned versus global Krylov subspace iterative methods for FE solution of 3-D Biot's problemhttps://scholarbank.nus.edu.sg/handle/10635/65968Title: Partitioned versus global Krylov subspace iterative methods for FE solution of 3-D Biot's problem
Authors: Chen, X.; Phoon, K.K.; Toh, K.C.
Abstract: Finite element analysis of 3-D Biot's consolidation problem needs fast solution of discretized large 2 × 2 block symmetric indefinite linear systems. In this paper, partitioned iterative methods and global Krylov subspace iterative methods are investigated and compared. The partitioned iterative methods considered include stationary partitioned iteration and non-stationary Prevost's PCG procedure. The global Krylov subspace methods considered include MINRES and Symmetric QMR (SQMR). Two efficient preconditioners are proposed for global methods. Numerical experiments based on a pile-group problem and simple footing problems with varied soil profiles are carried out. Numerical results show that when used in conjunction with suitable preconditioners, global Krylov subspace iterative methods are more promising for large-scale computations, and further improvement could be possible if significant differences in the solid material properties are addressed in these preconditioned iterative methods. © 2007 Elsevier B.V. All rights reserved.
Tue, 01 May 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/659682007-05-01T00:00:00Z
- Computation of condition numbers for linear programming problems using Peña's methodhttps://scholarbank.nus.edu.sg/handle/10635/103020Title: Computation of condition numbers for linear programming problems using Peña's method
Authors: Chai, J.-S.; Toh, K.-C.
Abstract: We present the computation of the condition numbers for linear programming (LP) problems from the NETLIB suite. The method of Peña [Peña, J., 1998, Computing the distance to infeasibility: theoretical and practical issues. Technical report, Center for Applied Mathematics, Cornell University.] was used to compute the bounds on the distance to ill-posedness ?( d ) of a given problem instance with data d, and the condition number was computed as C ( d )?=?? d ?/?( d ). We discuss the efficient implementation of Peñas method and compare the tightness of the estimates on C ( d ) computed by Peñas method to that computed by the method employed by Ordóñez and Freund [Ordóñez, F. and Freund, R.M., 2003, Computational experience and the explanatory value of condition measures for linear optimization. SIAM Journal on Optimization, 14, 307-333.]. While Peñas method is generally much cheaper, the bounds provided are generally not as tight as those computed by Ordóñez and Freund. As a by-product, we use the computational results to study the correlation between log C ( d ) and the number of interior-point method iterations taken to solve a LP problem instance. Our computational findings on the preprocessed problem instances from NETLIB suite are consistent with those reported by Ordóñez and Freund.
Thu, 01 Jun 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1030202006-06-01T00:00:00Z
- Semidefinite programming approaches for sensor network localization with noisy distance measurementshttps://scholarbank.nus.edu.sg/handle/10635/104092Title: Semidefinite programming approaches for sensor network localization with noisy distance measurements
Authors: Biswas, P.; Liang, T.-C.; Toh, K.-C.; Ye, Y.; Wang, T.-C.
Abstract: A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node by communicating with its neighbors. We describe a general semidefinite programming (SDP)-based approach for solving the graph realization problem, of which the sensor network localization problems is a special case. We investigate the performance of this method on problems with noisy distance data. Error bounds are derived from the SDP formulation. The sources of estimation error in the SDP formulation are identified. The SDP solution usually has a rank higher than the underlying physical space which, when projected onto the lower dimensional space, generally results in high estimation error. We describe two improvements to ameliorate such a difficulty. First, we propose a regularization term in the objective function that can help to reduce the rank of the SDP solution. Second, we use the points estimated from the SDP solution as the initial iterate for a gradient-descent method to further refine the estimated points. A lower bound obtained from the optimal SDP objective value can be used to check the solution quality. Experimental results are presented to validate our methods and show that they outperform existing SDP methods. © 2006 IEEE.
Sun, 01 Oct 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1040922006-10-01T00:00:00Z
- Inexact block diagonal preconditioners to mitigate the effects of relative differences in material stiffnesseshttps://scholarbank.nus.edu.sg/handle/10635/59090Title: Inexact block diagonal preconditioners to mitigate the effects of relative differences in material stiffnesses
Authors: Chaudhary, K.B.; Phoon, K.-K.; Toh, K.-C
Abstract: Finite-element analysis of many soil-structure interaction problems involves material zones of widely differing stiffnesses. The large relative differences in material stiffnesses usually result in an ill-conditioned system for which practical preconditioners become ineffective for the iterative solution of such systems. The study suggests that a block diagonal preconditioner can exploit such differences. However, the theoretical preconditioner is expensive for practical use. Less costly block diagonal preconditioners are numerically evaluated for various inexact forms of the blocks in conjunction with conjugate gradient solver. The study includes analysis of two representative soil-structure interaction problems and proposes two simplified block diagonal preconditioners that effectively mitigate such material ill conditionings. © 2013 American Society of Civil Engineers.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/590902013-01-01T00:00:00Z
- A Distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformationhttps://scholarbank.nus.edu.sg/handle/10635/102634Title: A Distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation
Authors: Biswas, P.; Toh, K.-C.; Ye, Y.
Abstract: We 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.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026342007-01-01T00:00:00Z
- Solving some large scale semidefinite programs via the conjugate residual methodhttps://scholarbank.nus.edu.sg/handle/10635/104151Title: Solving some large scale semidefinite programs via the conjugate residual method
Authors: Toh, K.-C.; Kojima, M.
Abstract: Most current implementations of interior-point methods for semidefinite programming use a direct method to solve the Schur complement equation (SCE) MΔy = h in computing the search direction. When the number of constraints is large, the problem of having insufficient memory to store M can be avoided if an iterative method is used instead. Numerical experiments have shown that the conjugate residual (CR) method typically takes a huge number of steps to generate a high accuracy solution. On the other hand, it is difficult to incorporate traditional preconditioners into the SCE, except for block diagonal preconditioners. We decompose the SCE into a 2 × 2 block system by decomposing Δy (similarly for h) into two orthogonal components with one lying in a certain subspace that is determined from the structure of M. Numerical experiments on semidefinite programming problems arising from the Lovász θ-function of graphs and MAXCUT problems show that high accuracy solutions can be obtained with a moderate number of CR steps using the proposed equation.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1041512002-01-01T00:00:00Z
- An introduction to a class of matrix cone programminghttps://scholarbank.nus.edu.sg/handle/10635/102845Title: An introduction to a class of matrix cone programming
Authors: Ding, C.; Sun, D.; Toh, K.-C.
Abstract: In this paper, we define a class of linear conic programming (which we call matrix cone programming or MCP) involving the epigraphs of five commonly used matrix norms and the well studied symmetric cone. MCP has recently been found to have many important applications, for example, in nuclear norm relaxations of affine rank minimization problems. In order to make the defined MCP tractable and meaningful, we must first understand the structure of these epigraphs. So far, only the epigraph of the Frobenius matrix norm, which can be regarded as a second order cone, has been well studied. Here, we take an initial step to study several important properties, including its closed form solution, calm Bouligand-differentiability and strong semismoothness, of the metric projection operator over the epigraph of the l1,\,l-\infty , spectral or operator, and nuclear matrix norm, respectively. These properties make it possible to apply augmented Lagrangian methods, which have recently received a great deal of interests due to their high efficiency in solving large scale semidefinite programming, to this class of MCP problems. The work done in this paper is far from comprehensive. Rather it is intended as a starting point to call for more insightful research on MCP so that it can serve as a basic tool to solve more challenging convex matrix optimization problems in years to come. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
Wed, 01 Jan 2014 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028452014-01-01T00:00:00Z
- Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splittinghttps://scholarbank.nus.edu.sg/handle/10635/126644Title: Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting
Authors: Peng, J.; Zhu, T.; Luo, H.; Toh, K.-C.
Abstract: Quadratic assignment problems (QAPs) are known to be among the most challenging discrete optimization problems. Recently, a new class of semi-definite relaxation models for QAPs based on matrix splitting has been proposed (Mittelmann and Peng, SIAM J Optim 20:3408-3426, 2010 ; Peng et al., Math Program Comput 2:59-77, 2010). In this paper, we consider the issue of how to choose an appropriate matrix splitting scheme so that the resulting relaxation model is easy to solve and able to provide a strong bound. For this, we first introduce a new notion of the so-called redundant and non-redundant matrix splitting and show that the relaxation based on a non-redundant matrix splitting can provide a stronger bound than a redundant one. Then we propose to follow the minimal trace principle to find a non-redundant matrix splitting via solving an auxiliary semi-definite programming problem. We show that applying the minimal trace principle directly leads to the so-called orthogonal matrix splitting introduced in (Peng et al., Math Program Comput 2:59-77, 2010). To find other non-redundant matrix splitting schemes whose resulting relaxation models are relatively easy to solve, we elaborate on two splitting schemes based on the so-called one-matrix and the sum-matrix. We analyze the solutions from the auxiliary problems for these two cases and characterize when they can provide a non-redundant matrix splitting. The lower bounds from these two splitting schemes are compared theoretically. Promising numerical results on some large QAP instances are reported, which further validate our theoretical conclusions. © 2014 Springer Science+Business Media New York.
Wed, 01 Jan 2014 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1266442014-01-01T00:00:00Z