Existence of Solution of Minimax Inequalities, Equilibria in Games and Fixed Points Without Convexity and Compactness Assumptions

This paper characterizes the existence of equilibria in minimax inequalities without assuming any form of quasiconcavity of functions and convexity or compactness of choice sets. A new condition, called “local dominatedness property”, is shown to be necessary and further, under some mild continuity condition, sufficient for the existence of equilibrium. We then apply the basic result obtained in the paper to generalize the existing theorems on the existence of saddle points, fixed points, and coincidence points without convexity or compactness assumptions. As an application, we also characterize the existence of pure strategy Nash equilibrium in games with discontinuous and non-quasiconcave payoff functions and nonconvex and/or noncompact strategy spaces.     

Poor convexity and Nash equilibria in games

This paper considers two-person non-zero-sum games on the unit square with payoff functions having a new property called poor convexity. This property describes “something between” the classical convexity and quasi-convexity. It is proved that various types of such games have Nash equilibria with a very simple structure, consisting of the players’ mixed strategies with at most two-element supports. Since poor convexity is a basic notion in the paper, also a theory of poorly convex functions is also developed.     

A note on disjoint arborescences

Recently Kamiyama, Katoh, and Takizawa have shown a theorem on packing arc-disjoint arborescences that is a proper extension of Edmonds’ theorem on disjoint spanning branchings. We show a further extension of their theorem, which makes clear an essential rôle of a reachability condition played in the theorem. The right concept required for the further extension is “convexity” instead of “reachability”.     

Existence of fixed points for mappings of finite sets

We show that the existence theorem for zeros of a vector field (fixed points of a mapping) holds in the case of a “convex” finite set X and a “continuous” vector field (a self-mapping) directed inwards into the convex hull co X of X. The main goal is to give correct definitions of the notions of “continuity” and “convexity”. We formalize both these notions using a reflexive and symmetric binary relation on X, i.e., using a proximity relation. Continuity (we shall say smoothness) is formulated with respect to any proximity relation, and an additional requirement on the proximity (we shall call it the acyclicity condition) transforms X into a “convex” set. If these two requirements are satisfied, then the vector field has a zero (i.e., a fixed point).     

Progressive Decoupling of Linkages in Optimization and Variational Inequalities with Elicitable Convexity or Monotonicity

Algorithms for problem decomposition and splitting in optimization and the solving of variational inequalities have largely depended on assumptions of convexity or monotonicity. Here, a way of “eliciting” convexity or monotonicity is developed which can get around that limitation. It supports a procedure called the progressive decoupling algorithm, which is derived from the proximal point algorithm through passing to a partial inverse, localizing and rescaling. In the optimization setting, elicitability of convexity corresponds to a new and very general kind of second-order sufficient condition for a local minimum. Applications are thereby opened up to problem decomposition and splitting even in nonconvex optimization, moreover with augmented Lagrangians for subproblems assisting in the implementation.

     

Note on an extension of “Davidon” methods to nondifferentiable functions

Some properties of “Davidon”, or variable metric, methods are studied from the viewpoint of convex analysis; they depend on the convexity of the function to be minimized rather than on its being approximately quadratic. An algorithm is presented which generalizes the variable metric method, and its convergence is shown for a large class of convex functions.     

Gauss-Lucas theorems for entire functions on CM

A Gauss-Lucas theorem is proved for multivariate entire functions, using a natural notion of separate convexity to obtain sharp results. Previous work in this area is mostly restricted to univariate entire functions (of genus no greater than one unless “realness” assumptions are made). The present work applies to multivariate entire functions whose sections can be written as a monomial times a canonical product of arbitrary genus. A connection is made with the Levy-Steinitz theorem for conditionally convergent vector series, a result generalizing Riemann’s well-known theorem for conditionally convergent real number series.     

Effective permeability of the boundary of a domain

Let u be a solution of the Laplace equation in a boilnded domain Ω in R ⁿ whose boundary consists of two disjoint surfaces λ₀ and λ₁. On λ₁ u satisfies a Dirichlet boundary condition, whereas on Λ₀ u satisfies the impermeability condition ?u/?n = 0 ever3 where except on m, small “holes” λ, separated from one another by distance of older of magnitude ε. and u= O on the holes. In this paper wr study the effective periwabilitv of the surface λ₀as ε→0.     

Convexity Conditions and the Legendre-Fenchel Transform for the Product of Finitely Many Positive Definite Quadratic Forms

While the product of finitely many convex functions has been investigated in the field of global optimization, some fundamental issues such as the convexity condition and the Legendre-Fenchel transform for the product function remain unresolved. Focusing on quadratic forms, this paper is aimed at addressing the question: When is the product of finitely many positive definite quadratic forms convex, and what is the Legendre-Fenchel transform for it? First, we show that the convexity of the product is determined intrinsically by the condition number of so-called ‘scaled matrices’ associated with quadratic forms involved. The main result claims that if the condition number of these scaled matrices are bounded above by an explicit constant (which depends only on the number of quadratic forms involved), then the product function is convex. Second, we prove that the Legendre-Fenchel transform for the product of positive definite quadratic forms can be expressed, and the computation of the transform amounts to finding the solution to a system of equations (or equally, finding a Brouwer’s fixed point of a mapping) with a special structure. Thus, a broader question than the open “Question 11” in Hiriart-Urruty (SIAM Rev. 49, 225–273, 2007) is addressed in this paper.     

On multivariate logarithmic polynomials and their properties

In the paper, the author introduces a new notion “multivariate logarithmic polynomial”, establishes two recurrence relations, an explicit formula, and an identity for multivariate logarithmic polynomials by virtue of the Faà di Bruno formula and two identities for the Bell polynomials of the second kind in terms of the Stirling numbers of the first and second kinds, and constructs some determinantal inequalities, some product inequalities, and logarithmic convexity for multivariate logarithmic polynomials by virtue of some properties of completely monotonic functions.     

A Liouville Type Theorem for Special Lagrangian Equations with Constraints

We derive a Liouville type result for special Lagrangian equations with certain “convexity” and restricted linear growth assumptions on the solutions.     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Complete settling of the multiplier conjecture for the case of n=3pr

In this paper we improve the character approach to the multiplier conjecture that we presented after 1992, and thus we have made considerable progress in the case of n = 3n₁. We prove that in the case of n = 3n₁ Second multiplier theorem remains true if the assumption “n₁ > λ” is replaced by “(n₁, λ) = 1”. Consequentially we prove that if we let D be a (v, k, λ)-difference set in an abelian group G, and n = 3p^r for some prime p, (p,v) = 1, then p is a numerical multiplier of D.     

Gårding's Theory of Hyperbolic Polynomials

This paper presents a simple, self‐contained account of Gårding's theory of hyperbolic polynomials, together with a recent convexity result of Bauschke‐Güler‐Lewis‐Sendov and an inequality of Gurvits. This account begins by establishing some new results. The first concerns the existence of a pointwise arrangement of the eigenvalues so that they become global real analytic functions. The second asserts that the associated “branches” are independent of the choice of hyperbolic direction. © 2013 Wiley Periodicals, Inc.     

On farthest points of sets

For a convex closed bounded set in a Banach space, we study the existence and uniqueness problem for a point of this set that is the farthest point from a given point in space. In terms of the existence and uniqueness of the farthest point, as well as the Lipschitzian dependence of this point on a point in space, we obtain necessary and su.cient conditions for the strong convexity of a set in several infinite-dimensional spaces, in particular, in a Hilbert space. A set representable as the intersection of closed balls of a fixed radius is called a strongly convex set. We show that the condition “for each point in space that is sufficiently far from a set, there exists a unique farthest point of the set” is a criterion for the strong convexity of a set in a finite-dimensional normed space, where the norm ball is a strongly convex set and a generating set.     

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems

In this paper, the Iri-Imai algorithm for solving linear and convex quadratic programming is extended to solve some other smooth convex programming problems. The globally linear convergence rate of this extended algorithm is proved, under the condition that the objective and constraint functions satisfy a certain type of convexity, called the harmonic convexity in this paper. A characterization of this convexity condition is given. The same convexity condition was used by Mehrotra and Sun to prove the convergence of a path-following algorithm.The Iri-Imai algorithm is a natural generalization of the original Newton algorithm to constrained convex programming. Other known convergent interior-point algorithms for smooth convex programming are mainly based on the path-following approach.     

The generalized continuum hypothesis revisited

We can reformulate the generalized continuum problem as: for regular κ<λ we have λ to the power κ is λ, We argue that the reasonable reformulation of the generalized continuum hypothesis, considering the known independence results, is “for most pairs κ<λ of regular cardinals, λ to the revised power of κ is equal to λ”. What is the revised power? λ to the revised power of κ is the minimal cardinality of a family of subsets of λ each of cardinality κ such that any other subset of λ of cardinality κ is included in the union of strictly less than κ members of the family. We still have to say what “for most” means. The interpretation we choose is: for every λ, for every large enoughK < ? _w . Under this reinterpretation, we prove the Generalized Continuum Hypothesis.     

The extension problem for functions with zero weighted spherical means

We study functions on a sphere with a pricked point having zero integrals with a given weight over all admissible “hemispheres”. We find a condition under which the point is a removable set for such a class of functions. We show that this condition cannot be dropped or substantially weakened.     

The affine representation theorem for abstract convex geometries

A convex geometry is a combinatorial abstract model introduced by Edelman and Jamison which captures a combinatorial essence of “convexity” shared by some objects including finite point sets, partially ordered sets, trees, rooted graphs. In this paper, we introduce a generalized convex shelling, and show that every convex geometry can be represented as a generalized convex shelling. This is “the representation theorem for convex geometries” analogous to “the representation theorem for oriented matroids” by Folkman and Lawrence. An important feature is that our representation theorem is affine-geometric while that for oriented matroids is topological. Thus our representation theorem indicates the intrinsic simplicity of convex geometries, and opens a new research direction in the theory of convex geometries.