Duality gap of the conic convex constrained optimization problems in normed spaces

In this paper, motivated by a result due to Champion [Math. Program.99, 2004], we introduce a property for a conic quasi-convex vector-valued function in a general normed space. We prove that this property characterizes the zero duality gap for a class of the conic convex constrained optimization problem in the sense that if this property is satisfied and the objective function f is continuous at some feasible point, then the duality gap is zero, and if this property is not satisfied, then there exists a linear continuous function f such that the duality gap is positive. We also present some sufficient conditions for the property The work of this author was partially supported by the National Natural Sciences Grant (No. 10671050) and the Excellent Young Teachers Program of MOE,  P.R.C.     

A {\mathsf{D}}-induced duality and its applications

This paper attempts to extend the notion of duality for convex cones, by basing it on a prescribed conic ordering and a fixed bilinear mapping. This is an extension of the standard definition of dual cones, in the sense that the nonnegativity of the inner-product is replaced by a pre-specified conic ordering, defined by a convex cone , and the inner-product itself is replaced by a general multi-dimensional bilinear mapping. This new type of duality is termed the -induced duality in the paper. We further introduce the notion of -induced polar sets within the same framework, which can be viewed as a generalization of the -induced dual cones and is convenient to use for some practical applications. Properties of the extended duality, including the extended bi-polar theorem, are proven. Furthermore, attention is paid to the computation and approximation of the -induced dual objects. We discuss, as examples, applications of the newly introduced -induced duality concepts in robust conic optimization and the duality theory for multi-objective conic optimization. Research supported in part by the Foundation ‘Vereniging Trustfonds Erasmus Universiteit Rotterdam’ in The Netherlands, and in part by Hong Kong RGC Earmarked Grants CUHK4174/03E and CUHK418406.     

Corrector–predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path

Two corrector–predictor interior point algorithms are proposed for solving monotone linear complementarity problems. The algorithms produce a sequence of iterates in the neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm can be implemented in arithmetic operations, where n is the dimension of the problems, is a constant, and m is the maximum order of the predictor and the corrector. If then both algorithms have iteration complexity. They are superlinearly convergent even for degenerate problems.      

Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

A complete classification of the computational complexity of the fixed-point existence problem for Boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}, is presented. For function classes and graph classes , an ()-system is a Boolean dynamical system such that all local transition functions lie in and the underlying graph lies in . Let be a class of Boolean functions which is closed under composition and let be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If contains the self-dual functions and contains the planar graphs, then the fixed-point existence problem for ()-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If contains the self-dual functions and contains the graphs having vertex covers of size one, then the fixed-point existence problem for ()-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.      

Convex sets with semidefinite representation

We provide a sufficient condition on a class of compact basic semialgebraic sets for their convex hull co(K) to have a semidefinite representation (SDr). This SDr is explicitly expressed in terms of the polynomials g _j that define K. Examples are provided. We also provide an approximate SDr; that is, for every fixed , there is a convex set such that (where B is the unit ball of ), and has an explicit SDr in terms of the g _j ’s. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we provide a simpler explicit SDr when the nonnegative Lagrangian L _f associated with K and any linear is a sum of squares. We also provide an approximate SDr specific to the convex case.      

Efficient robust optimization for robust control with constraints

This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tractable, the number of variables is quadratic in the number of stages or horizon length N and has no apparent exploitable structure, leading to computational time of per iteration of an interior-point method. We focus on the case when the disturbance set is ∞-norm bounded or the linear map of a hypercube, and the cost function involves the minimization of a quadratic cost. Here we make use of state variables to regain a sparse problem structure that is related to the structure of the original problem, that is, the policy optimization problem may be decomposed into a set of coupled finite horizon control problems. This decomposition can then be formulated as a highly structured quadratic program, solvable by primal-dual interior-point methods in which each iteration requires time. This cubic iteration time can be guaranteed using a Riccati-based block factorization technique, which is standard in discrete-time optimal control. Numerical results are presented, using a standard sparse primal-dual interior point solver, that illustrate the efficiency of this approach.     

Chains and antichains in partial orderings

We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is or , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering has the feature that for every , there is an infinite chain or antichain that is relative to , then we have uniform dichotomy: either for all copies of , there is an infinite chain that is relative to , or for all copies of , there is an infinite antichain that is relative to .     

Additive maps preserving the minimum and surjectivity moduli of operators

Let be a complex Hilbert space and let be the algebra of all bounded linear operators on . We characterize additive maps from onto itself preserving different spectral quantities such as the minimum modulus, the surjectivity modulus, and the maximum modulus of operators. Received: 15 July 2008     

Sums of random symmetric matrices and quadratic optimization under orthogonality constraints

Let B _i be deterministic real symmetric m × m matrices, and ξ _i be independent random scalars with zero mean and “of order of one” (e.g., ). We are interested to know under what conditions “typical norm” of the random matrix is of order of 1. An evident necessary condition is , which, essentially, translates to ; a natural conjecture is that the latter condition is sufficient as well. In the paper, we prove a relaxed version of this conjecture, specifically, that under the above condition the typical norm of S _N is : for all Ω > 0 We outline some applications of this result, primarily in investigating the quality of semidefinite relaxations of a general quadratic optimization problem with orthogonality constraints , where F is quadratic in X = (X ₁,... ,X _k ). We show that when F is convex in every one of X _j , a natural semidefinite relaxation of the problem is tight within a factor slowly growing with the size m of the matrices . Research was partly supported by the Binational Science Foundation grant #2002038.     

Generalized hexagons and Singer geometries

In this paper, we consider a set of lines of with the properties that (1) every plane contains 0, 1 or q + 1 elements of , (2) every solid contains no more than q ² + q + 1 and no less than q + 1 elements of , and (3) every point of is on q + 1 members of , and we show that, whenever (4) q ≠ 2 (respectively, q = 2) and the lines of through some point are contained in a solid (respectively, a plane), then is necessarily the set of lines of a regularly embedded split Cayley generalized hexagon in , with q even. We present examples of such sets not satisfying (4) based on a Singer cycle in , for all q.      

Scaling Limit for Subsystems and Doplicher–Roberts Reconstruction

Given an inclusion of (graded) local nets, we analyse the structure of the corresponding inclusion of scaling limit nets , giving conditions, fulfilled in free field theory, under which the unicity of the scaling limit of implies that of the scaling limit of . As a byproduct, we compute explicitly the (unique) scaling limit of the fixpoint nets of scalar free field theories. In the particular case of an inclusion of local nets with the same canonical field net , we find sufficient conditions which entail the equality of the canonical field nets of . Work supported by MIUR, GNAMPA-INDAM, the EU and SNS. Submitted: August 29, 2008. Accepted: March 23, 2009.     

Finite lattices as relative congruence lattices of finite algebras

Let A be a finite algebra and a quasivariety. By A is meant the lattice of congruences θ on A with . For any positive integer n, we give conditions on a finite algebra A under which for any n-element lattice L there is a quasivariety such that . The author was supported by INTAS grant 03-51-4110.     

Supersaturation For Ramsey-Turán Problems

For an l-graph , the Turán number is the maximum number of edges in an n-vertex l-graph containing no copy of . The limit is known to exist [8]. The Ramsey–Turán density is defined similarly to except that we restrict to only those with independence number o(n). A result of Erdős and Sós [3] states that as long as for every edge E of there is another edge E′of for which |E∩E′|≥2. Therefore a natural question is whether there exists for which . Another variant proposed in [3] requires the stronger condition that every set of vertices of of size at least εn (0<ε<1) has density bounded below by some threshold. By definition, for every . However, even is not known for very many l-graphs when l>2. We prove the existence of a phenomenon similar to supersaturation for Turán problems for hypergraphs. As a consequence, we construct, for each l≥3, infinitely many l-graphs for which . We also prove that the 3-graph with triples 12a, 12b, 12c, 13a, 13b, 13c, 23a, 23b, 23c, abc, satisfies . The existence of a hypergraph satisfying was conjectured by Erdős and Sós [3], proved by Frankl and R?dl [6], and later by Sidorenko [14]. Our short proof is based on different ideas and is simpler than these earlier proofs. * Research supported in part by the National Science Foundation under grants DMS-9970325 and DMS-0400812, and an Alfred P. Sloan Research Fellowship. † Research supported in part by the National Science Foundation under grants DMS-0071261 and DMS-0300529.     

On one-sided strong Arens irregularity

We present a natural class of Banach algebras which are one-sided strongly Arens irregular. More precisely, for any non-compact, second countable locally compact group , we show that the convolution algebras of nuclear operators on , as introduced and studied by the author in [3], [6], are left but not right strongly Arens irregular. For Heinz K?nig, in admiration and friendship     

Homotopy Categories for Simply Connected Torsion Spaces

For each n > 1 and each multiplicative closed set of integers S, we study closed model category structures on the pointed category of topological spaces, where the classes of weak equivalences are classes of maps inducing isomorphism on homotopy groups with coefficients in determined torsion abelian groups, in degrees higher than or equal to n. We take coefficients either on all the cyclic groups with s ∈ S, or in the abelian group where is the group of fractions of the form with s ∈ S. In the first case, for n > 1 the localized category is equivalent to the ordinary homotopy category of (n − 1)-connected CW-complexes whose homotopy groups are S-torsion. In the second case, for n > 1 we obtain that the localized category is equivalent to the ordinary homotopy category of (n − 1)-connected CW-complexes whose homotopy groups are S-torsion and the nth homotopy group is divisible. These equivalences of categories are given by colocalizations , obtained by cofibrant approximations on the model structures. These colocalization maps have nice universal properties. For instance, the map is final (in the homotopy category) among all the maps of the form Y → X with Y an (n − 1)-connected CW-complex whose homotopy groups are S-torsion and its nth homotopy group is divisible. The spaces , are constructed using the cones of Moore spaces of the form M(T, k), where T is a coefficient group of the corresponding structure of models, and homotopy colimits indexed by a suitable ordinal. If S is generated by a set P of primes and S ^p is generated by a prime p ∈ P one has that for n > 1 the category is equivalent to the product category . If the multiplicative system S is generated by a finite set of primes, then localized category is equivalent to the homotopy category of n-connected Ext-S-complete CW-complexes and a similar result is obtained for .     

Variationally harmonic maps with general boundary conditions: Boundary regularity

Let and be Riemannian manifolds, compact without boundary. We develop a definition of a variationally harmonic map with respect to a general boundary condition of the kind u(x)∊Γ(x) for a.e. , where are given submanifolds depending smoothly on x. The given definition of variationally harmonic maps is slightly more restrictive, but also more natural than the usual definition of stationary harmonic maps. After deducing an energy monotonicity formula, it is possible to derive a regularity theory for variationally harmonic maps with general boundary data. The results include full boundary regularity in the Dirichlet boundary case Γ(x) = {g(x)} for if does not carry a nonconstant harmonic 2-sphere.     

$${\mathcal{M}}$$ -decomposability and symmetric unimodal densities in one dimension

In this paper, we introduce the notion of -decomposability of probability density functions in one dimension. Using -decomposability, we derive an inequality that applies to all symmetric unimodal densities. Our inequality involves only the standard deviation of the densities concerned. The concept of -decomposability can be used as a non-parametric criterion for mode-finding and cluster analysis.     

Solutions of affine stochastic functional differential equations in the state space

We consider solutions of affine stochastic functional differential equations on . The drift of these equations is specified by a functional defined on a general function space which is only described axiomatically. The solutions are reformulated as stochastic processes in the space . By representing such a process in the bidual space of we establish that the transition functions of this process form a generalized Gaussian Mehler semigroup on . This way the process is characterized completely on since it is Markovian. Moreover we derive a sufficient and necessary condition on the underlying space such that the transition functions are even an Ornstein-Uhlenbeck semigroup. We exploit this result to associate a Cauchy problem in the function space to the stochastic functional differential equation.      

Non-free isometric immersions of Riemannian manifolds

Let (V, g) be a Riemannian manifold and let be the isometric immersion operator which, to a map , associates the induced metric on V, where denotes the Euclidean scalar product in . By Nash–Gromov implicit function theorem is infinitesimally invertible over the space of free maps. In this paper we study non-free isometric immersions . We show that the operator (where denotes the space of C ^∞- smooth quadratic forms on ) is infinitesimally invertible over a non-empty open subset of and therefore is an open map in the respective fine topologies.