ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Sat, 08 Aug 2020 20:57:39 GMT2020-08-08T20:57:39Z50641- 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
- 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
- An inexact primal-dual path following algorithm for convex quadratic SDPhttps://scholarbank.nus.edu.sg/handle/10635/104535Title: An inexact primal-dual path following algorithm for convex quadratic SDP
Authors: Toh, K.-C.
Abstract: We propose primal-dual path-following Mehrotra-type predictor-corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: equation presented, where Q is a self-adjoint positive semidefinite linear operator on Sn, b R m , and A is a linear map from SSn to R m . At each interior-point iteration, the search direction is computed from a dense symmetric indefinite linear system (called the augmented equation) of dimension m + n(n + 1)/2. Such linear systems are typically very large and can only be solved by iterative methods. We propose three classes of preconditioners for the augmented equation, and show that the corresponding preconditioned matrices have favorable asymptotic eigenvalue distributions for fast convergence under suitable nondegeneracy assumptions. Numerical experiments on a variety of QSDPs with n up to 1600 are performed and the computational results show that our methods are efficient and robust. © 2007 Springer-Verlag.
Sat, 01 Mar 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1045352008-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
- 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
- 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
- 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
- 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
- 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
- Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problemshttps://scholarbank.nus.edu.sg/handle/10635/103065Title: Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems
Authors: Zhou, G.; Toh, K.-C.; Zhao, G.
Abstract: Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves ε-feasibility and ε-complementarity in at most O(n 2 ln(1/ε)) iterations with a properly chosen starting point.
Mon, 01 Mar 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1030652004-03-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
- 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
- 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
- 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 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
- 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
- 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
- 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
- Performance of zero-level fill-in preconditioning techniques for iterative solutions with geotechnical applicationshttps://scholarbank.nus.edu.sg/handle/10635/59159Title: Performance of zero-level fill-in preconditioning techniques for iterative solutions with geotechnical applications
Authors: Chen, X.; Phoon, K.-K.; Toh, K.-C.
Abstract: Biot's symmetric indefinite linear systems of equations are commonly encountered in finite-element computations of geotechnical problems. The development of efficient solution methods for Biot's linear systems of equations is of practical importance to geotechnical software packages. In conjunction with the Krylov-subspace iterative method symmetric quasi-minimal residual (SQMR), some zero-level fillin incomplete factorization preconditioning techniques including a symmetric successive overrelaxation (SSOR) type method and several zerolevel incomplete LU 1/2ILU(0) methods are investigated and compared for Biot's symmetric indefinite linear systems of equations. Numerical experiments are carried out based on three practical geotechnical problems. Numerical results indicate that ILU(0) preconditioners are classical and generally efficient when adequately stabilized. However, the tunnel problem provides a counterexample demonstrating that ILU(0) preconditioners cannot be fully stabilized by preliminary scaling, reordering, making use of perturbed matrices, or dynamically selecting pivots. Compared with the investigated ILU(0) preconditioners, the recently proposed modified SSOR preconditioner is less efficient but is robust over the range of problems studied. © 2012 American Society of Civil Engineers.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/591592012-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
- 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 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
- 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
- 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
- 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 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
- 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
- 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
- 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
- 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 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
- 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
- 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
- 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
- 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
- Effective block diagonal preconditioners for Biot's consolidation equations in piled-raft foundationshttps://scholarbank.nus.edu.sg/handle/10635/59027Title: Effective block diagonal preconditioners for Biot's consolidation equations in piled-raft foundations
Authors: Chaudhary, K.B.; Phoon, K.K.; Toh, K.C.
Abstract: The finite element (FE) simulation of large-scale soil-structure interaction problems (e.g. piled-raft, tunnelling, and excavation) typically involves structural and geomaterials with significant differences in stiffness and permeability. The symmetric quasi-minimal residual solver coupled with recently developed generalized Jacobi, modified symmetric successive over-relaxation (MSSOR), or standard incomplete LU factorization (ILU) preconditioners can be ineffective for this class of problems. Inexact block diagonal preconditioners that are inexpensive approximations of the theoretical form are systematically evaluated for mitigating the coupled adverse effects because of such heterogeneous material properties (stiffness and permeability) and because of the percentage of the structural component in the system in piled-raft foundations. Such mitigation led the proposed preconditioners to offer a significant saving in runtime (up to more than 10 times faster) in comparison with generalized Jacobi, modified symmetric successive over-relaxation, and ILU preconditioners in simulating piled-raft foundations. © 2012 John Wiley & Sons, Ltd.
Mon, 10 Jun 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/590272013-06-10T00: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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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