排序方式: 共有27条查询结果,搜索用时 15 毫秒
1.
2.
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
as BCGD) 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/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-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 large-scale covariance selection problems with constraints. 相似文献
3.
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.
This research has been partially supported through the MIT-Singapore Alliance. 相似文献
4.
Summary.
It is well known that the zeros of a polynomial are equal to
the
eigenvalues of the associated companion matrix . In this paper
we take a
geometric view of the conditioning of these two problems and of the stability of
algorithms for polynomial zerofinding. The
is the set of zeros of all polynomials obtained by
coefficientwise perturbations of of size ;
this is a subset of the
complex plane considered earlier by Mosier, and is bounded by a
certain generalized lemniscate. The
is another subset of
defined as the set of eigenvalues of matrices
with ; it is bounded by a
level curve of the resolvent
of $A$. We find that if $A$ is first balanced in the usual EISPACK sense, then
and
are usually quite close to one another. It follows that the Matlab
ROOTS algorithm of balancing the companion matrix, then computing its eigenvalues, is a stable
algorithm for polynomial zerofinding. Experimental comparisons with the
Jenkins-Traub (IMSL) and
Madsen-Reid (Harwell) Fortran codes confirm that these three algorithms have roughly
similar stability properties.
Received June 15, 1993 相似文献
5.
Guanglu Zhou Kim-Chuan Toh Gongyun Zhao 《Computational Optimization and Applications》2004,27(3):269-283
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. 相似文献
6.
Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming 总被引:3,自引:0,他引:3
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(n2ln(1/)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang.Research supported in part by the Singapore-MIT alliance, and NUS Academic Research Grant R-146-000-032-112.Mathematics Subject Classification (1991): 90C05, 90C30, 65K05 相似文献
7.
In this paper, we present a two-phase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality and inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNAL-Phase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNAL-Phase II, we design an augmented Lagrangian method (ALM) wherein the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R-(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our two-phase algorithm is highly efficient and robust in obtaining accurate solutions. The software reviewed as part of this submission was given the DOI (Digital Object Identifier) https://doi.org/10.5281/zenodo.1206980. 相似文献
8.
Sparse covariance selection problems can be formulated as log-determinant (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. 相似文献
9.
Kim-Chuan Toh 《Computational Optimization and Applications》1999,14(3):309-330
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. 相似文献
10.
Naohiko Arima Sunyoung Kim Masakazu Kojima Kim-Chuan Toh 《Computational Optimization and Applications》2017,66(3):453-479
The Lagrangian-doubly nonnegative (DNN) relaxation has recently been shown to provide effective lower bounds for a large class of nonconvex quadratic optimization problems (QAPs) using the bisection method combined with first-order methods by Kim et al. (Math Program 156:161–187, 2016). While the bisection method has demonstrated the computational efficiency, determining the validity of a computed lower bound for the QOP depends on a prescribed parameter \(\epsilon > 0\). To improve the performance of the bisection method for the Lagrangian-DNN relaxation, we propose a new technique that guarantees the validity of the computed lower bound at each iteration of the bisection method for any choice of \(\epsilon > 0\). It also accelerates the bisection method. Moreover, we present a method to retrieve a primal-dual pair of optimal solutions of the Lagrangian-DNN relaxation using the primal-dual interior-point method. As a result, the method provides a better lower bound and substantially increases the robustness as well as the effectiveness of the bisection method. Computational results on binary QOPs, multiple knapsack problems, maximal stable set problems, and quadratic assignment problems illustrate the robustness of the proposed method. In particular, a tight bound for QAPs with size \(n=50\) could be obtained. 相似文献