ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Mon, 23 Sep 2019 05:05:43 GMT2019-09-23T05:05:43Z50621- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Polynomiality of an inexact infeasible interior point algorithm for semidefinite programminghttps://scholarbank.nus.edu.sg/handle/10635/103947Title: Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming
Authors: Zhou, G.; Toh, K.-C.
Abstract: In this paper we present a primal-dual inexact infeasible interior-point algorithm for semidefinite programming problems (SDP). This algorithm allows the use of search directions that are calculated from the defining linear system with only moderate accuracy, and does not require feasibility to be maintained even if the initial iterate happened to be a feasible solution of the problem. Under a mild assumption on the inexactness, we show that the algorithm can find an ε-approximate solution of an SDP in O(n 2 ln(1/ε)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang. © Springer-Verlag 2003.
Mon, 01 Mar 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1039472004-03-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
- 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
- Some new search directions for primal-dual interior point methods in semidefinite programminghttps://scholarbank.nus.edu.sg/handle/10635/104169Title: Some new search directions for primal-dual interior point methods in semidefinite programming
Authors: Toh, K.-C.
Abstract: Search directions for primal-dual path-following methods for semidefinite programming (SDP) are proposed. These directions have the properties that (1) under certain nondegeneracy and strict complementarity assumptions, the Jacobian matrix of the associated symmetrized Newton equation has a bounded condition number along the central path in the limit as the barrier parameter μ tends to zero; and (2) the Schur complement matrix of the symmetrized Newton equation is symmetric and the cost for computing this matrix is 2mn3 + 0.5m2n2 flops, where n and m are the dimension of the matrix and vector variables of the semidefinite program, respectively. These two properties imply that a path-following method using the proposed directions can achieve the high accuracy typically attained by methods employing the direction proposed by Alizadeh, Haeberly, and Overton (currently the best search direction in terms of accuracy), but each iteration requires at most half the amount of flops (to leading order).
Sat, 01 Jul 2000 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1041692000-07-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
- 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 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
- 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
- Axisymmetric lower-bound limit analysis using finite elements and second-order cone programminghttps://scholarbank.nus.edu.sg/handle/10635/90913Title: Axisymmetric lower-bound limit analysis using finite elements and second-order cone programming
Authors: Tang, C.; Toh, K.-C.; Phoon, K.-K.
Abstract: In 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.
Wed, 01 Jan 2014 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/909132014-01-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
- 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
- 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
- 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
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDPhttps://scholarbank.nus.edu.sg/handle/10635/102841Title: An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
Authors: Jiang, K.; Sun, D.; Toh, K.-C.
Abstract: The accelerated proximal gradient (APG) method, first proposed by Nesterov for minimizing smooth convex functions, later extended by Beck and Teboulle to composite convex objective functions, and studied in a unifying manner by Tseng, has proven to be highly efficient in solving some classes of large scale structured convex optimization (possibly nonsmooth) problems, including nuclear norm minimization problems in matrix completion and l 1 minimization problems in compressed sensing. The method has superior worst-case iteration complexity over the classical projected gradient method and usually has good practical performance on problems with appropriate structures. In this paper, we extend the APG method to the inexact setting, where the subproblem in each iteration is solved only approximately, and show that it enjoys the same worst-case iteration complexity as the exact counterpart if the subproblems are progressively solved to sufficient accuracy. We apply our inexact APG method to solve large scale convex quadratic semidefinite programming (QSDP) problems of the form min{1/2〈x, Q(x)〉 + 〈c, x〉 | A (x) = b, x ≻ 0}, where Q,A are given linear maps and b, c are given data. The subproblem in each iteration is solved by a semismooth Newton-CG (SSNCG) method with warm-start using the iterate from the previous iteration. Our APG-SSNCG method is demonstrated to be efficient for QSDP problems whose positive semidefinite linear maps Q are highly ill-conditioned or rank deficient. © 2012 Society for Industrial and Applied Mathematics.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028412012-01-01T00: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
- 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
- Solving large scale semidefinite programs via an iterative solver on the augmented systemshttps://scholarbank.nus.edu.sg/handle/10635/104147Title: Solving large scale semidefinite programs via an iterative solver on the augmented systems
Authors: Toh, K.-C.
Abstract: The search directions in an interior-point method for large scale semidefinite programming (SDP) can be computed by applying a Krylov iterative method to either the Schur complement equation (SCE) or the augmented equation. Both methods suffer from slow convergence as interior-point iterates approach optimality. Numerical experiments have shown that a diagonally preconditioned conjugate residual method on the SCE typically takes a huge number of steps to converge. However, it is difficult to incorporate cheap and effective preconditioners into the SCE. This paper proposes to apply the preconditioned symmetric quasi-minimal residual (PSQMR) method to a reduced augmented equation that is derived from the augmented equation by utilizing the eigenvalue structure of the interior-point iterates. Numerical experiments on SDP problems arising from maximum clique and selected SDPLIB (SDP Library) problems show that moderately accurate solutions can be obtained with a modest number of PSQMR steps using the proposed preconditioned reduced augmented equation. An SDP problem with 127600 constraints is solved in about 6.5 hours to an accuracy of 10 -6 in relative duality gap.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1041472004-01-01T00:00:00Z
- A multiple-cut analytic center cutting plane method for semidefinite feasibility problemshttps://scholarbank.nus.edu.sg/handle/10635/44200Title: A multiple-cut analytic center cutting plane method for semidefinite feasibility problems
Authors: Toh, K.-C.; Zhao, G.; Sun, J.
Abstract: We consider the problem of finding a point in a nonempty bounded convex body F in the cone of symmetric positive semidefinite matrices S+ m. Assume that Γ is defined by a separating oracle, which, for any given m × m symmetric matrix Ŷ, either confirms that Ŷ ∈ Γ or returns several selected cuts, i.e., a number of symmetric matrices Ai, i = 1,...,p, p ≤ pmax, such that Γ is in the polyhedron {Y ∈ S+ m | Ai • Y ≤ Ai • Ŷ, i = 1, ⋯,p}. We present a multiple-cut analytic center cutting plane algorithm. Starting from a trivial initial point, the algorithm generates a sequence of positive definite matrices which are approximate analytic centers of a shrinking polytope in S+ m. The algorithm terminates with a point in F within O(m3pmax/ε2) Newton steps (to leading order), where e is the maximum radius of a ball contained in Γ.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442002002-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
- 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
- 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 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
- Globally and quadratically convergent algorithm for minimizing the sum of Euclidean normshttps://scholarbank.nus.edu.sg/handle/10635/103346Title: Globally and quadratically convergent algorithm for minimizing the sum of Euclidean norms
Authors: Zhou, G.; Toh, K.C.; Sun, D.
Abstract: For the problem of minimizing the sum of Euclidean norms (MSN), most existing quadratically convergent algorithms require a strict complementarity assumption. However, this assumption is not satisfied for a number of MSN problems. In this paper, we present a globally and quadratically convergent algorithm for the MSN problem. In particular, the quadratic convergence result is obtained without assuming strict complementarity. Examples without strictly complementary solutions are given to show that our algorithm can indeed achieve quadratic convergence. Preliminary numerical results are reported.
Sat, 01 Nov 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1033462003-11-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
- Preconditioned IDR(s) iterative solver for non-symmetric linear system associated with FEM analysis of shallow foundationhttps://scholarbank.nus.edu.sg/handle/10635/91147Title: Preconditioned IDR(s) iterative solver for non-symmetric linear system associated with FEM analysis of shallow foundation
Authors: Tran, H.H.T.; Toh, K.C.; Phoon, K.K.
Abstract: Non-associated flow rule is essential when the popular Mohr-Coulomb model is used to model nonlinear behavior of soil. The global tangent stiffness matrix in nonlinear finite element analysis becomes non-symmetric when this non-associated flow rule is applied. Efficient solution of this large-scale non-symmetric linear system is of practical importance. The standard Krylov solver for a non-symmetric solver is Bi-CGSTAB. The Induced Dimension Reduction [IDR(s)] solver was proposed in the scientific computing literature relatively recently. Numerical studies of a drained strip footing problem on homogenous soil layer show that IDR(s=6) is more efficient than Bi-CGSTAB when the preconditioner is the incomplete factorization with zero fill-in of global stiffness matrix Kep (ILU(0)-Kep). Iteration time is reduced by 40% by using IDR(s=6) with ILU(0)-Kep. To further reduce computational cost, the global stiffness matrix Kep is divided into two parts. The first part is the linear elastic stiffness matrix Ke, which is formed only once at the beginning of solution step. The second part is a low-rank matrix Δ, which is re-formed at each Newton-Raphson iteration. Numerical studies show that IDR(s=6) with this ILU(0)-Ke preconditioner is more time effective than IDR(s=6) with ILU(0)-Kep when the percentage of yielded Gauss points in the mesh is less than 15%. The total computation time is reduced by 60% when all the recommended optimizing methods are used. © 2013 John Wiley & Sons, Ltd.
Tue, 10 Dec 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/911472013-12-10T00:00:00Z
- On the implementation of a log-barrier progressive hedging method for multistage stochastic programshttps://scholarbank.nus.edu.sg/handle/10635/103807Title: On the implementation of a log-barrier progressive hedging method for multistage stochastic programs
Authors: Liu, X.; Toh, K.-C.; Zhao, G.
Abstract: A progressive hedging method incorporated with self-concordant barrier for solving multistage stochastic programs is proposed recently by Zhao [G. Zhao, A Lagrangian dual method with self-concordant barrier for multistage stochastic convex nonlinear programming, Math. Program. 102 (2005) 1-24]. The method relaxes the nonanticipativity constraints by the Lagrangian dual approach and smoothes the Lagrangian dual function by self-concordant barrier functions. The convergence and polynomial-time complexity of the method have been established. Although the analysis is done on stochastic convex programming, the method can be applied to the nonconvex situation. We discuss some details on the implementation of this method in this paper, including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method. © 2010 Elsevier B.V. All rights reserved.
Sat, 15 May 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1038072010-05-15T00:00:00Z
- An implementable proximal point algorithmic framework for nuclear norm minimizationhttps://scholarbank.nus.edu.sg/handle/10635/102836Title: An implementable proximal point algorithmic framework for nuclear norm minimization
Authors: Liu, Y.-J.; Sun, D.; Toh, K.-C.
Abstract: The 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.
Fri, 01 Jun 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028362012-06-01T00:00:00Z
- 3D chromosome modeling with semi-definite programming and Hi-C datahttps://scholarbank.nus.edu.sg/handle/10635/113916Title: 3D chromosome modeling with semi-definite programming 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 while 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 three-dimensional (3D) chromosomal structure within the nucleus. With the available Hi-C data, our next challenge is to model the 3D chromosomal structure from the 3C-derived data computationally. This article 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. Further, we develop a measure called consensus index to indicate if the Hi-C data corresponds to a single structure or a mixture of structures. To the best of our knowledge, ChromSDE is the only method that 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 Mary Ann Liebert, Inc.
Fri, 01 Nov 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1139162013-11-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
- 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
- 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
- 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