Prüfer ⋆–multiplication domains and ⋆–coherence

Abstract The purpose of this paper is to deepen the study of the Prüfer ⋆–mul-tiplication domains, where ⋆ is a semistar operation. For this reason, we introduce the ⋆–domains, as a natural extension of the v-domains. We investigate their close relation with the Prüfer ⋆-multiplication domains. In particular, we obtain a characterization of Prüfer ⋆-multiplication domains in terms of ⋆–domains satisfying a variety of coherent-like conditions. We extend to the semistar setting the notion of -domain introduced by Glaz and Vasconcelos and we show, among the other results that, in the class of the –domains, the Prüfer ⋆-multiplication domains coincide with the ⋆-domains. Keywords: Star and semistar operation, Prüfer (⋆-multiplication) domain, -domain, Localizing system, Coherent domain, Divisorial and invertible ideal Mathematics Subject Classification (2000): 13F05, 13G05, 13E99     

Convergence rate analysis of iteractive algorithms for solving variational inequality problems

 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     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 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.     

A uniqueness result for a Neumann problem involving the critical Sobolev exponent

 In this paper we consider the problem

Semistar-Krull and valuative dimension of integral domains

Given a stable semistar operation of finite type ⋆ on an integral domain D, we show that it is possible to define in a canonical way a stable semistar operation of finite type ⋆[X] on the polynomial ring D[X], such that, if n := ⋆-dim(D), then n+1 ≤ ⋆[X]-dim(D[X]) ≤ 2n+1. We also establish that if D is a ⋆-Noetherian domain or is a Prüfer ⋆-multiplication domain, then ⋆[X]-dim(D[X]) = ⋆- dim(D)+1. Moreover we define the semistar valuative dimension of the domain D, denoted by ⋆-dim _v (D), to be the maximal rank of the ⋆-valuation overrings of D. We show that ⋆-dim _v (D) = n if and only if ⋆[X ₁, . . . , X _n ]-dim(D[X ₁, . . . , X _n ]) = 2n, and that if ⋆-dim _v (D) < ∞ then ⋆[X]-dim _v (D[X]) = ⋆-dim _v (D) + 1. In general ⋆-dim(D) ≤ ⋆-dim _v (D) and equality holds if D is a ⋆-Noetherian domain or is a Prüfer ⋆-multiplication domain. We define the ⋆-Jaffard domains as domains D such that ⋆-dim(D) < ∞ and ⋆-dim(D) = ⋆-dim _v (D). As an application, ⋆-quasi-Prüfer domains are characterized as domains D such that each (⋆, ⋆′)-linked overring T of D, is a ⋆′-Jaffard domain, where ⋆′ is a stable semistar operation of finite type on T. As a consequence of this result we obtain that a Krull domain D, must be a w _D -Jaffard domain.     

Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints

 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     

Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results

 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     

Elementary Abelian <Emphasis Type="Italic">p</Emphasis>-groups of rank greater than or equal to 4<Emphasis Type="Italic">p</Emphasis>−2 are not CI-groups

In this paper we prove that an elementary Abelian p-group of rank 4p−2 is not a CI⁽²⁾-group, i.e. there exists a 2-closed transitive permutation group containing two non-conjugate regular elementary Abelian p-subgroups of rank 4p−2, see Hirasaka and Muzychuk (J. Comb. Theory Ser. A 94(2), 339–362, 2001). It was shown in Hirasaka and Muzychuk (loc cit) and Muzychuk (Discrete Math. 264(1–3), 167–185, 2003) that this is related to the problem of determining whether an elementary Abelian p-group of rank n is a CI-group. As a strengthening of this result we prove that an elementary Abelian p-group E of rank greater or equal to 4p−2 is not a CI-group, i.e. there exist two isomorphic Cayley digraphs over E whose corresponding connection sets are not conjugate in Aut E. This research was supported by a fellowship from the Pacific Institute for the Mathematical Sciences.     

A feasible semismooth asymptotically Newton method for mixed complementarity problems

 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     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

Non-Interior continuation methods for solving semidefinite complementarity problems

 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     

An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity

Infeasible interior point methods have been very popular and effective. In this paper, we propose a predictor–corrector infeasible interior point algorithm for convex quadratic programming, and we prove its convergence and analyze its complexity. The algorithm has the polynomial numerical complexity with O(nL)-iteration.     

Minimal surfaces of rotation in Finsler space with a Randers metric

 We consider Finsler spaces with a Randers metric F=α+β, on the three dimensional real vector space, where α is the Euclidean metric and β=bdx ₃ 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 ₃ 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.     

Extension of primal-dual interior point algorithms to symmetric cones

 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.     

On complexity reduction of Σ<Subscript>1</Subscript> formulas

 For a fixed q  ℕ and a given Σ₁ definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ₀ + ? 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.     

On the Expected Condition Number of Linear Programming Problems

Summary.   Let A be an n×m real matrix and consider the linear conic system

Seshadri-exceptional foliations

 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=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 ℙ³ 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.     

On representations and <Emphasis Type="Italic">K</Emphasis>-theory of the braid groups

 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