共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
Issues of implementation of an object-oriented library for parallel interior-point methods are addressed. The solver can
easily exploit any special structure of the underlying optimization problem. In particular, it allows a nested embedding of structures and by
this means very complicated real-life optimization problems can be modelled. The efficiency of the solver is illustrated on
several problems arising in the optimization of networks. The sequential implementation outperforms the state-of-the-art commercial
optimization software. The parallel implementation achieves speed-ups of about 3.1-3.9 on 4-processors parallel systems and
speed-ups of about 10-12 on 16-processors parallel systems.
Received: December 4, 2000 / Accepted: January 2003
Published online: April 10, 2003
RID="⋆"
ID="⋆" Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/M68169. 相似文献
3.
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. 相似文献
4.
In this paper we consider the problem
where B is a ball in R
n
. For a small d>0, we show the uniqueness (up to rotation) of the one-bubbling solution which concentrates at a point of the boundary.
Received: 12 December 2001 / Published online: 10 February 2003
RID="⋆"
ID="⋆" Supported by M.U.R.S.T., project: ``Variational methods and nonlinear differential equations'
RID="⋆⋆"
ID="⋆⋆" Partial supported by National Center for Theoretical Sciences of NSC, Taiwan
Mathematics Subject Classification (2000): 35J60 相似文献
5.
We show that knowing the displacement-to-traction map associated to the equations of isotropic elastodynamics with residual
stress we can determine the lens maps of compressional and shear waves. We derive several consequences of this for the inverse
problem of determining the residual stress and the Lamé parameters from the displacement-to-traction map.
Received: 6 December 2001 / Revised version: 29 October 2002 /
Published online: 8 April 2003
RID="⋆"
ID="⋆" The author thanks the Department of Mathematics at the University of Washington for its hospitality during his visit
in fall 2000.
RID="⋆⋆"
ID="⋆⋆" Partly supported by NSF grant DMS-0070488 and a John Simon Guggenheim fellowship. The author also thanks MSRI for
partial support and for providing a very stimulating environment during the inverse problems program in fall 2001. 相似文献
6.
Let Γ be the fundamental group of the complement of a K(Γ, 1) hyperplane arrangement (such as Artin's pure braid group) or more generally a homologically toroidal group as defined below.
The triviality of bundles arising from orthogonal representations of Γ is characterized completely as follows. An orthogonal
representation gives rise to a trivial bundle if and only if the representation factors through the spinor groups. Furthermore,
the subgroup of elements in the complex K-theory of BΓ which arises from complex unitary representations of Γ is shown to be trivial. In the case of real K-theory, the subgroup of elements which arises from real orthogonal representations of Γ is an elementary abelian 2-group,
which is characterized completely in terms of the first two Stiefel-Whitney classes of the representation.
In addition, quadratic relations in the cohomology algebra of the pure braid groups which correspond precisely to the Jacobi
identity for certain choices of Poisson algebras are shown to give the existence of certain homomorphisms from the pure braid
group to generalized Heisenberg groups. These cohomology relations correspond to non-trivial Spin representations of the pure
braid groups which give rise to trivial bundles.
Received: 6 February 2002 / Revised version: 19 September 2002 /
Published online: 8 April 2003
RID="⋆"
ID="⋆" Partially supported by the NSF
RID="⋆⋆"
ID="⋆⋆" Partially supported by grant LEQSF(1999-02)-RD-A-01 from the Louisiana Board of Regents, and by grant MDA904-00-1-0038
from the National Security Agency
RID="⋆"
ID="⋆" Partially supported by the NSF
Mathematics Subject Classification (2000): 20F36, 32S22, 55N15, 55R50 相似文献
7.
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 相似文献
8.
The set of all group relaxations of an integer program contains certain special members called Gomory relaxations. A family
of integer programs with a fixed coefficient matrix and cost vector but varying right hand sides is a Gomory family if every
program in the family can be solved by one of its Gomory relaxations. In this paper, we characterize Gomory families. Every
TDI system gives a Gomory family, and we construct Gomory families from matrices whose columns form a Hilbert basis for the
cone they generate. The existence of Gomory families is related to the Hilbert covering problems that arose from the conjectures
of Seb?. Connections to commutative algebra are outlined at the end.
Received: May 17, 2001 / Accepted: February 7, 2002
Published online: April 24, 2003
RID="⋆"
ID="⋆" Research partially supported by NSF grant DMS-0100141. 相似文献
9.
For a fixed q ℕ and a given Σ1 definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ0 + ? exp and a non standard d M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers.
Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002
RID="⋆"
ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.
RID="⋆"
ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. 相似文献
10.
We consider Finsler spaces with a Randers metric F=α+β, on the three dimensional real vector space, where α is the Euclidean metric and β=bdx
3
is a 1-form with norm b,0≤b<1. By using the notion of mean curvature for immersions in Finsler spaces introduced by Z. Shen, we get the ordinary differential
equation that characterizes the minimal surfaces of rotation around the x
3
axis. We prove that for every b,0≤b<1, there exists, up to homothety, a unique forward complete minimal surface of rotation. The surface is embedded, symmetric
with respect to a plane perpendicular to the rotation axis and it is generated by a concave plane curve. Moreover, for every
there are non complete minimal surfaces of rotation, which include explicit minimal cones.
Received: 30 November 2001 / Published online: 10 February 2003
RID="⋆"
ID="⋆" Partially supported by CAPES
RID="⋆⋆"
ID="⋆⋆" Partially supported by CNPq and PROCAD. 相似文献
11.
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 相似文献
12.
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 相似文献
13.
We shall give, in an optimal form, a sufficient numerical condition for the finiteness of the fundamental group of the smooth
locus of a normal K3 surface. We shall moreover prove that, if the normal K3 surface is elliptic and the above fundamental
group is not finite, then there is a finite covering which is a complex torus.
Received: 13 April 2001 / Published online: 16 October 2002
RID="⋆"
ID="⋆" Supported by Korea Research Foundation Grant(KRF-2001-041-D00025)
Mathematics Subject Classification (2000): 14J28 相似文献
14.
The maximal Seshadri number μ(L) of an ample line bundle L on a smooth projective variety X measures the local positivity of the line bundle L at a general point of X. By refining the method of Ein-Küchle-Lazarsfeld, lower bounds on μ(L) are obtained in terms of L
n
, n=dim(X), for a class of varieties. The main idea is to show that if a certain lower bound is violated, there exists a non-trivial
foliation on the variety whose leaves are covered by special curves. In a number of examples, one can show that such foliations
must be trivial and obtain lower bounds for μ(L). The examples include the hyperplane line bundle on a smooth surface in ℙ3 and ample line bundles on smooth threefolds of Picard number 1.
Received: 29 June 2001 / Published online: 16 October 2002
RID="⋆"
ID="⋆" Supported by Grant No. 98-0701-01-5-L from the KOSEF.
RID="⋆⋆"
ID="⋆⋆" Supported by Grant No. KRF-2001-041-D00025 from the KRF. 相似文献
15.
16.
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 相似文献
17.
Non-Interior continuation methods for solving semidefinite complementarity problems 总被引:13,自引:0,他引:13
There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity
problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric
positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed
Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and
local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported.
Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002
RID="⋆"
ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273.
Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear
convergence 相似文献
18.
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 相似文献
19.
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 相似文献
20.
We study the problem of scheduling a set of n independent parallel tasks on m processors, where in addition to the processing time there is a size associated with each task indicating that the task can
be processed on any subset of processors of the given size. Based on a linear programming formulation, we propose an algorithm
for computing a preemptive schedule with minimum makespan, and show that the running time of the algorithm depends polynomially
on m and only linearly on n. Thus for any fixed m, an optimal preemptive schedule can be computed in O(n) time. We also present extensions of this approach to other (more general) scheduling problems with malleable tasks, due dates
and maximum lateness minimization.
Received: November 1999 / Accepted: November 2002 Publication online: December 19, 2002
RID="⋆"
ID="⋆" This work was done while the authors were associated with the research institutes IDSIA Lugano and MPII Saarbrücken
and were supported in part by the Swiss Office Fédéral de l'éducation et de la Science project n 97.0315 titled ``Platform'
and by EU ESPRIT LTR Project No. 20244 (ALCOM-IT) 相似文献