Global minimization of large-scale constrained concave quadratic problems by separable programming

The global minimization of a large-scale linearly constrained concave quadratic problem is considered. The concave quadratic part of the objective function is given in terms of the nonlinear variablesx R ⁿ , while the linear part is in terms ofy R ^k. For large-scale problems we may havek much larger thann. The original problem is reduced to an equivalent separable problem by solving a multiple-cost-row linear program with 2n cost rows. The solution of one additional linear program gives an incumbent vertex which is a candidate for the global minimum, and also gives a bound on the relative error in the function value of this incumbent. Ana priori bound on this relative error is obtained, which is shown to be 0.25, in important cases. If the incumbent is not a satisfactory approximation to the global minimum, a guaranteed-approximate solution is obtained by solving a single liner zero–one mixed integer programming problem. This integer problem is formulated by a simple piecewise-linear underestimation of the separable problem.This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.Dedicated to Professor George Dantzig in honor of his 70th Birthday.     

The design centering problem as a D.C. programming problem

The following problem is studied: Given a compact setS inR ⁿ and a Minkowski functionalp(x), find the largest positive numberr for which there existsx S such that the set of ally R ⁿ satisfyingp(y–x) r is contained inS. It is shown that whenS is the intersection of a closed convex set and several complementary convex sets (sets whose complements are open convex) this design centering problem can be reformulated as the minimization of some d.c. function (difference of two convex functions) overR ⁿ . In the case where, moreover,p(x) = (x ^T Ax)^1/2, withA being a symmetric positive definite matrix, a solution method is developed which is based on the reduction of the problem to the global minimization of a concave function over a compact convex set.     

Efficiency of Proximal Bundle Methods

We give efficiency estimates for proximal bundle methods for finding f_*min_Xf, where f and X are convex. We show that, for any accuracy <0, these methods find a point x^kX such that f(x^k)–f^* after at most k=O(1/³) objective and subgradient evaluations.     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.     

Almost sure behaviour ofF-valued random fields

Summary LetX _n, n ^d be a field of independent random variables taking values in a semi-normed measurable vector spaceF. For a broad class of fields _n, ^d of positive numbers, the almost sure behaviour of _knX_k/_n, n ^d is studied. The main result allows us to deduce some new and well-known theorems for fields of independentF random variables from related results for fields of independent real random variables.Supported in part by the Youth Science Foundation of China, No. 19001018Supported by the National Natural Science Foundation of China     

On some additive mappings in rings with involution

Summary LetR be a *-ring. We study an additive mappingD: R R satisfyingD(x ²) =D(x)x ^* +xD(x) for allx R.It is shown that, in caseR contains the unit element, the element 1/2, and an invertible skew-hermitian element which lies in the center ofR, then there exists ana R such thatD(x) = ax ^* – xa for allx R. IfR is a noncommutative prime real algebra, thenD is linear. In our main result we prove that a noncommutative prime ring of characteristic different from 2 is normal (i.e.xx ^* =x ^* x for allx R) if and only if there exists a nonzero additive mappingD: R R satisfyingD(x ²) =D(x)x ^* +xD(x) and [D(x), x] = 0 for allx R. This result is in the spirit of the well-known theorem of E. Posner, which states that the existence of a nonzero derivationD on a prime ringR, such that [D(x), x] lies in the center ofR for allx R, forcesR to be commutative.     

Connected and alternating vectors: Polyhedra and algorithms

Given a graphG = (V, E), leta ^S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R ^E: a^sx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb ^k, k K, ofG. WhenG is a tree, the extreme points ofB 0,b ^kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

Method of moments on semigroups

If ( _j ) is a sequence of measures onR ^k having momentss _n ( _j ) of all ordersnN ₀ ^k and if for eachnN ₀ ^k the sequence (s _{n j} )) _jN converges to somet _n R then some subsequence of ( _j ) converges weakly to a measure with moments of all orders satisfyings _n ()=t _n for allnN^0/k . Thisindeterminate method of moments and the continuity theorems in probability theory suggest a common generalization, dealing with a commutative semigroupS, with involution and a neutral element, and measures on the dual semigroupS ^* ofcharacters on S—hermitian multiplicative complex functions not identically zero. In this setting, a continuity theorem holds for measures on the set of bounded characters,⁽²⁾ and an indeterminate method of moments whenS is finitely generated.⁽²⁾ The latter result is generalized in the present paper to the case of arbitraryS. This leads to a generalization of Haviland's criterion for theK-moment problem, and to a continuity theorem for the so-called perfect semigroups.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

The lyapunov equation and the problem of stability for linear bounded discrete-time systems in Hilbert space

This paper is devoted to a study of the properties of the equationA ^*FA–F=–G, where FL() is unknown, AL(), GL() is positive and is a Hilbert space. It is shown that necessary and sufficient (in some sense) conditions for the existence of positive definite solutions of this equation are directly connected with the stability of infinite dimensional linear systemx _k+1=Ax _k . The relationships between stability of such a system and stability of a continuous-time system generated by a strongly continuous semigroup are given also. As an example the case of the delayed system in Rⁿ is considered.This work was supported in part by the Polish Academy of Sciences under the contract Problem Miedzyresortowy I.1, Grupa Tematyczna 3 This paper was written while the author was with the Instytut Automatyki, the same university.     

Piecewise-Convex Maximization Problems: Algorithm and Computational Experiments

A function F : Rⁿ R is called a piecewise convex function if it can be decomposed into F(x)=min{f _j(x) j M}, where f _j :Rⁿ R is convex for all j M={1,2...,m}. In this article, we provide an algorithm for solving F(x) subject to xD, which is based on global optimality conditions. We report first computational experiments on small examples and open up some issues to improve the checking of optimality conditions.     

Grouped coordinate minimization using Newton's method for inexact minimization in one vector coordinate

Letf(x,y) be a function of the vector variablesx R ⁿ andy R ^m. The grouped (variable) coordinate minimization (GCM) method for minimizingf consists of alternating exact minimizations in either of the two vector variables, while holding the other fixed at the most recent value. This scheme is known to be locally,q-linearly convergent, and is most useful in certain types of statistical and pattern recognition problems where the necessary coordinate minimizers are available explicitly. In some important cases, the exact minimizer in one of the vector variables is not explicitly available, so that an iterative technique such as Newton's method must be employed. The main result proved here shows that a single iteration of Newton's method solves the coordinate minimization problem sufficiently well to preserve the overall rate of convergence of the GCM sequence.The authors are indebted to Professor R. A. Tapia for his help in improving this paper.     

New lower semicontinuity results for polyconvex integrals

Summary We study integral functionals of the formF(u, )= f(u)dx, defined foru C¹(;R ^k), R ⁿ . The functionf is assumed to be polyconvex and to satisfy the inequalityf(A) c₀¦(A)¦ for a suitable constant c₀ > 0, where (A) is then-vector whose components are the determinants of all minors of thek×n matrixA. We prove thatF is lower semicontinuous onC ¹(;R ^k) with respect to the strong topology ofL ¹(;R ^k). Then we consider the relaxed functional , defined as the greatest lower semicontinuous functional onL ¹(;R ^k ) which is less than or equal toF on C¹(;R ^k). For everyu BV(;R ^k) we prove that (u,) f(u)dx+c₀¦D^su¦(), whereDu=u dx+D^su is the Lebesgue decomposition of the Radon measureDu. Moreover, under suitable growth conditions onf, we show that (u,)= f(u)dx for everyu W^1,p(;R ^k), withp min{n,k}. We prove also that the functional (u, ) can not be represented by an inte- gral for an arbitrary functionu BV_loc(R ⁿ;R ^k). In fact, two examples show that, in general, the set function (u, ) is not subadditive whenu BV_loc(R ⁿ;R ^k), even ifu W _loc ^1,p (R ⁿ;R ^k) for everyp < min{n,k}. Finally, we examine in detail the properties of the functionsu BV(;R ^k) such that (u, )= f(u)dx, particularly in the model casef(A)=¦(A)¦.     

Waterman classes and triangular sums of double Fourier series

Let ^a ={nln^a (n+1)}, where a R. The following results are established: For every &fnof ^a BV ((- ]²), the triangular partial sums of its Fourier series are uniformly bounded if a = -1, and converge everywhere if a < -1.For every a>0, there exists &fnof ^a BV ((- ]²) such that the triangular partial sums of its Fourier series are unbounded at the point (0;0).     

Lusin's condition (N) for the space mappings W 1, n under analytic assumptions

We give a sufficient analytic condition in order that a mapping fW ¹, ⁿ (;R ⁿ) satisfies Lusin's condition (N).     

Necessary and sufficient condition of the existence of global Hopf bifurcation for Hamiltonian systems

ForH C ² (,R) where 0 R ²ⁿ ,H (0)=0 and detH(0)0, the paper proves that there is a global Hopf bifurcation fromx=0 for Hamiltonian systemx=JH(x) iffJH(0)possesses purely imaginary eigenvalues. The work improves the corresponding result of J.C.Alexander and J. Yorke (Amer. J. Math., 100 (1978), 263–292).     

The caratheodory number for thek-core

Thek-core of the setS ⁿ is the intersection of the convex hull of all setsA S with ¦SA¦<-k. The Caratheodory number of thek-core is the smallest integerf (d,k) with the property thatx core _{kS, S} ⁿ implies the existence of a subsetT S such thatx core_kT and ¦T¦f (d, k). In this paper various properties off(d, k) are established.Research of this author was partially supported by Hungarian National Science Foundation grant no. 1812.     

On the existence of wave operators for the Klein-Gordon equation

The problem of existence of wave operators for the Klein-Gordon equation ( _t ² –+²+iV_1t+V₂)u(x,t)=0 (x R ⁿ,t R, n3, >0) is studied where V₁ and V₂ are symmetric operators in L₂(R ⁿ) and it is shown that conditions similar to those of Veseli-Weidmann (Journal Functional Analysis 17, 61–77 (1974)) for a different class of operators are also sufficient for the Klein-Gordon equation.     

Knaster's problem on continuous maps of a sphere into Euclidean space

A survey of known results and additional new ones on Knaster's problem: on the standard sphere S^n–1Rⁿ find configurations of points A₁, , A_k, such that for any continuous map fS^n–1R^m one can find a rotation a of the sphere S^n–1 such that f(a(A₁)==f(a(A_k)) and some problems closely connected with it. We study the connection of Knaster's problem with equivariant mappings, with Dvoretsky's theorem on the existence of an almost spherical section of a multidimensional convex body, and we also study the set {a S0(n)f(a(A₁))==f(a(A_k))} of solutions of Knaster's problem for a fixed configuration of points A₁, , A_kS^n–1 and a map fS^n–1R^m in general position. Unsolved problems are posed.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 167, pp. 169–178, 1987.