共查询到20条相似文献,搜索用时 25 毫秒
1.
The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs)
into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application
of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods
to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based)
log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed
algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems.
Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective
for problems with a large number of constraints.
Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002
RID="†"
ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired
in part with support from NSF Grant DMS-9872009.
RID="⋆"
ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426
RID="⋆⋆"
ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113
RID="⋆⋆⋆"
ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339.
Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton
methods.
Mathematics Subject Classification (1991): 90C06, 90C27, 90C30. 相似文献
2.
一个光滑化函数的两个性质 总被引:1,自引:0,他引:1
本文考虑文[6]中提出的光滑化函数,证明了:该光滑化函数拥有两个在求解变分不等式和互补问题的非内部连续化算法的全局线性和局部超线性(或二次)收敛性分析中非常有用的两个性质。 相似文献
3.
Chen and Tseng (Math Program 95:431?C474, 2003) extended non-interior continuation methods for solving linear and nonlinear complementarity problems to semidefinite complementarity problems (SDCP), in which a system of linear equations is exactly solved at each iteration. However, for problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a version of one of the non-interior continuation methods for monotone SDCP presented by Chen and Tseng that incorporates inexactness into the linear system solves. Only one system of linear equations is inexactly solved at each iteration. The global convergence and local superlinear convergence properties of the method are given under mild conditions. 相似文献
4.
Stephen J. Wright 《Mathematical Programming》2003,95(1):137-160
In the vicinity of a solution of a nonlinear programming problem at which both strict complementarity and linear independence
of the active constraints may fail to hold, we describe a technique for distinguishing weakly active from strongly active
constraints. We show that this information can be used to modify the sequential quadratic programming algorithm so that it
exhibits superlinear convergence to the solution under assumptions weaker than those made in previous analyses.
Received: December 18, 2000 / Accepted: January 14, 2002 Published online: September 27, 2002
RID="★"
ID="★" Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of
Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.
Key words. nonlinear programming problems – degeneracy – active constraint identification – sequential quadratic programming 相似文献
5.
Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem 总被引:3,自引:0,他引:3
Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior
continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be
globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a
linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm,
we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For
non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature
in order to achieve global linear convergence results of the algorithms. 相似文献
6.
Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints 总被引:2,自引:0,他引:2
Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable
Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex
subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems
an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a H?lder
one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the
global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional
variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique.
Received: April 2002 / Accepted: December 2002
Published online: March 21, 2003
RID="⋆"
ID="⋆" This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 01–01–00587.
Key Words. global optimization – multiextremal constraints – local tuning – index approach 相似文献
7.
A feasible semismooth asymptotically Newton method for mixed complementarity problems 总被引:2,自引:0,他引:2
Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research
on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible
region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region.
As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods.
In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges
to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method,
which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior
to doing (curved) line searches.
As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration.
The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must
be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates
being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical
results are reported on all problems from the MCPLIB collection [8].
Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002
RID="★"
ID="★" This work was supported in part by the Australian Research Council.
Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence
AMS subject classifications. 90C33, 90C30, 65H10 相似文献
8.
Kazuhide Nakata Katsuki Fujisawa Mituhiro Fukuda Masakazu Kojima Kazuo Murota 《Mathematical Programming》2003,95(2):303-327
In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over
all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods.
This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different
ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP
having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix
completion itself in a primal-dual interior-point method. The current article presents the details of their implementations.
We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational
formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient
for some problems.
Received: March 18, 2001 / Accepted: May 31, 2001 Published online: October 9, 2002
RID="⋆"
ID="⋆"The author was supported by The Ministry of Education, Culture, Sports, Science and Technology of Japan.
Key Words. semidefinite programming – primal-dual interior-point method – matrix completion problem – clique tree – numerical results
Mathematics Subject Classification (2000): 90C22, 90C51, 05C50, 05C05 相似文献
9.
Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior
continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be
globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a
linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm,
we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For
non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature
in order to achieve global linear convergence results of the algorithms. 相似文献
10.
In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by
Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The
machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as
the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption
is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities
for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions.
Received: April 2000 / Accepted: May 2002
Published online: March 28, 2003
RID="⋆"
ID="⋆" Part of this research was conducted when the first author was a postdoctoral associate at Center for Computational
Optimization at Columbia University.
RID="⋆⋆"
ID="⋆⋆" Research supported in part by the U.S. National Science Foundation grant CCR-9901991 and Office of Naval Research
contract number N00014-96-1-0704. 相似文献
11.
12.
Convergence rate analysis of iteractive algorithms for solving variational inequality problems 总被引:3,自引:0,他引:3
M.V. Solodov 《Mathematical Programming》2003,96(3):513-528
We present a unified convergence rate analysis of iterative methods for solving the variational inequality problem. Our results
are based on certain error bounds; they subsume and extend the linear and sublinear rates of convergence established in several
previous studies. We also derive a new error bound for $\gamma$-strictly monotone variational inequalities. The class of algorithms
covered by our analysis in fairly broad. It includes some classical methods for variational inequalities, e.g., the extragradient,
matrix splitting, and proximal point methods. For these methods, our analysis gives estimates not only for linear convergence
(which had been studied extensively), but also sublinear, depending on the properties of the solution. In addition, our framework
includes a number of algorithms to which previous studies are not applicable, such as the infeasible projection methods, a
separation-projection method, (inexact) hybrid proximal point methods, and some splitting techniques. Finally, our analysis
covers certain feasible descent methods of optimization, for which similar convergence rate estimates have been recently obtained
by Luo [14].
Received: April 17, 2001 / Accepted: December 10, 2002
Published online: April 10, 2003
RID="⋆"
ID="⋆" Research of the author is partially supported by CNPq Grant 200734/95–6, by PRONEX-Optimization, and by FAPERJ.
Key Words. Variational inequality – error bound – rate of convergence
Mathematics Subject Classification (2000): 90C30, 90C33, 65K05 相似文献
13.
Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider
both linear and semidefinite relaxations for the equipartition problem and present numerical results on real data from France
Telecom networks with up 900 nodes, and also on randomly generated problems.
Received: August 8, 2001 / Accepted: November 9, 2001 Published online: December 9, 2002
RID="★★"
ID="★★" This research was carried out while this author was working at France Telecom R & D, 38–40 rue du Général Leclerc,
F-92794 Issy-Les-Moulineaux Cedex 9, France.
RID="★"
ID="★" This author greatfully acknowledges financial support from the Austrian Science Foundation FWF Project P12660-MAT.
Key words. graph partitioning – semidefinite programming 相似文献
14.
The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that
restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair
of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics.
Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002
RID="★"
ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired
in part with support from NSF Grant DMS-9872009.
Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous
optimization heuristics – nonlinear programming
Mathematics Subject Classification (2000): 90C06, 90C27, 90C30 相似文献
15.
In this paper, we analyze a unique continuation problem for the linearized Benjamin-Bona-Mahony equation with space-dependent
potential in a bounded interval with Dirichlet boundary conditions. The underlying Cauchy problem is a characteristic one.
We prove two unique continuation results by means of spectral analysis and the (generalized) eigenvector expansion of the
solution, instead of the usual Holmgren-type method or Carleman-type estimates. It is found that the unique continuation property
depends very strongly on the nature of the potential and, in particular, on its zero set, and not only on its boundedness
or integrability properties.
Received: 6 December 2001 / Revised version: 13 June 2002 / Published online: 10 February 2003
RID="⋆"
ID="⋆" Supported by a Postdoctoral Fellowship of the Spanish Education and Culture Ministry, the Foundation for the Author
of National Excellent Doctoral Dissertation of P.R. China (Project No: 200119), and the NSF of China under Grant 19901024
RID="⋆⋆"
ID="⋆⋆" Supported by grant PB96-0663 of the DGES (Spain) and the EU TMR Project "Homogenization and Multiple Scales".
Mathematics Subject Classification (2000): 35B60, 47A70, 47B07 相似文献
16.
Ju-liangZhang Xiang-sunZhang Yong-meiSu 《应用数学学报(英文版)》2004,20(4):557-572
In this paper, we analyze the global and local convergence properties of two predictor-corrector smoothing methods, which are based on the framework of the method in [1], for monotone linear complementarity problems (LCPs). The difference between the algorithm in [1] and our algorithms is that the neighborhood of smoothing central path in our paper is different to that in [1]. In addition, the difference between Algorithm 2.1 and the algorithm in [1] exists in the calculation of the predictor step. Comparing with the results in [1],the global and local convergence of the two methods can be obtained under very mild conditions. The global convergence of the two methods do not need the boundness of the inverse of the Jacobian. The superlinear convergence of Algorithm 2.1‘ is obtained under the assumption of nonsingularity of generalized Jacobian of Φ(x,y) at the limit point and Algorithm 2.1 obtains superlinear convergence under the assumption of strict complementarity at the solution. The efficiency of the two methods is tested by numerical experiments. 相似文献
17.
Andreas Fischer 《Mathematical Programming》2002,94(1):91-124
An iterative framework for solving generalized equations with nonisolated solutions is presented. For generalized equations
with the structure , where is a multifunction and F is single-valued, the framework covers methods that, at each step, solve subproblems of the type . The multifunction approximates F around s. Besides a condition on the quality of this approximation, two other basic assumptions are employed to show Q-superlinear
or Q-quadratic convergence of the iterates to a solution. A key assumption is the upper Lipschitz-continuity of the solution
set map of the perturbed generalized equation . Moreover, the solvability of the subproblems is required. Conditions that ensure these assumptions are discussed in general
and by means of several applications. They include monotone mixed complementarity problems, Karush-Kuhn-Tucker systems arising
from nonlinear programs, and nonlinear equations. Particular results deal with error bounds and upper Lipschitz-continuity
properties for these problems.
Received: November 2001 / Accepted: November 2002 Published online: December 9, 2002
Key Words. generalized equation – nonisolated solutions – Newton's method – superlinear convergence – upper Lipschitz-continuity – mixed
complementarity problem – error bounds
Mathematics Subject Classification (1991): 90C30, 65K05, 90C31, 90C33 相似文献
18.
本文对于P0函数非线性互补问题提出了一个基于Kanzow光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性.特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Jacobi阵是Lipschitz连续的.文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的.本文提出的方法在每一次迭代只须解一个线性方程式组. 相似文献
19.
Aifan Ling 《Numerical Algorithms》2016,73(1):219-244
In this paper, an inexact non-interior continuation method is proposed for semidefinite Programs. By a matrix mapping, the primal-dual optimal condition can be inverted into a smoothed nonlinear system of equations. A linear system of equations with residual vector is eventually driven by solving the smoothed nonlinear system of equations and finally solved by the conjugate residual method. The global and locally superlinear convergence are verified. Numerical results and comparisons indicate that the proposed methods are very promising and comparable to several interior-point and other exact non-interior continuation methods. 相似文献
20.
Summary. Impedance tomography seeks to recover the electrical conductivity distribution inside a body from measurements of current
flows and voltages on its surface. In its most general form impedance tomography is quite ill-posed, but when additional a-priori
information is admitted the situation changes dramatically. In this paper we consider the case where the goal is to find a
number of small objects (inhomogeneities) inside an otherwise known conductor. Taking advantage of the smallness of the inhomogeneities,
we can use asymptotic analysis to design a direct (i.e., non-iterative) reconstruction algorithm for the determination of
their locations. The viability of this direct approach is documented by numerical examples.
Received May 28, 2001 / Revised version received March 15, 2002 / Published online July 18, 2002
RID="⋆"
ID="⋆" Supported by the Deutsche Forschungsgemeinschaft (DFG) under grant HA 2121/2-3
RID="⋆⋆"
ID="⋆⋆" Supported by the National Science Foundation under grant DMS-0072556
Mathematics Subject Classification (2000): 65N21, 35R30, 35C20 相似文献