Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

Minimax theorems for scalar set-valued mappings with nonconvex domains and applications

In this paper, by virtue of the separation theorem of convex sets, we prove a minimax theorem, a cone saddle point theorem and a Ky Fan minimax theorem for a scalar set-valued mapping under nonconvex assumptions of its domains, respectively. As applications, we obtain an existence result for the generalized vector equilibrium problem with a set-valued mapping. Simultaneously, we also obtain some generalized Ky Fan minimax theorems for set-valued mappings, in which the minimization and the maximization of set-valued mappings are taken in the sense of vector optimization.     

Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers

In this paper, under the existence of a certificate of nonnegativity of the objective function over the given constraint set, we present saddle-point global optimality conditions and a generalized Lagrangian duality theorem for (not necessarily convex) polynomial optimization problems, where the Lagrange multipliers are polynomials. We show that the nonnegativity certificate together with the archimedean condition guarantees that the values of the Lasserre hierarchy of semidefinite programming (SDP) relaxations of the primal polynomial problem converge asymptotically to the common primal–dual value. We then show that the known regularity conditions that guarantee finite convergence of the Lasserre hierarchy also ensure that the nonnegativity certificate holds and the values of the SDP relaxations converge finitely to the common primal–dual value. Finally, we provide classes of nonconvex polynomial optimization problems for which the Slater condition guarantees the required nonnegativity certificate and the common primal–dual value with constant multipliers and the dual problems can be reformulated as semidefinite programs. These classes include some separable polynomial programs and quadratic optimization problems with quadratic constraints that admit certain hidden convexity. We also give several numerical examples that illustrate our results.     

Ekeland's variational principle, minimax theorems and existence of nonconvex equilibria in complete metric spaces

In this paper, we introduce the concept of τ-function which generalizes the concept of w-distance studied in the literature. We establish a generalized Ekeland's variational principle in the setting of lower semicontinuous from above and τ-functions. As applications of our Ekeland's variational principle, we derive generalized Caristi's (common) fixed point theorems, a generalized Takahashi's nonconvex minimization theorem, a nonconvex minimax theorem, a nonconvex equilibrium theorem and a generalized flower petal theorem for lower semicontinuous from above functions or lower semicontinuous functions in the complete metric spaces. We also prove that these theorems also imply our Ekeland's variational principle.     

Minimax inequalities equivalent to the Fan-Knaster-Kuratowski-Mazurkiewicz theorems

The purpose of this note is to give further generalizations of the Ky Fan minimax inequality by relaxing the compactness and convexity of sets and the quasi-concavity of the functional and to show that our minimax inequalities are equivalent to the Fan-Knaster-Kuratowski-Mazurkiewicz (FKKM) theorem and a modified FKKM theorem given in this note.     

Two-function upward-downward minimax theorems

Two-function upward-downward minimax theorems are derived which contain Simons upward-downward minimax theorem as well as Domokos minimax theorem as special cases. Here the convexity assumptions on two functions are given by mixing up their values as means proposed by Lin and Quan.     

Fan—Ha截口定理

为了进一步研究极小极大不等式，本文进一步削弱了极小极大定理中的闭性条件与凸性条件，利用反证法与有限交性质将Fan-Ha截口定理以及极小极大定理推广为H-空间上更一般的形式．     

A Fixed Point Theorem and Some Generalized Ky Fan's Minimax Inequalities

In this paper, we establish a fixed point theorem for set-valued mapping on a topological vector space without "local convexity". And we also establish some generalized Ky Fan's minimax inequalities for set-value vector mappings, which are the generalization of some previous results.     

Unified approach to some geometric results in variational analysis

Based on a study of a minimization problem, we present the following results applicable to possibly nonconvex sets in a Banach space: an approximate projection result, an extended extremal principle, a nonconvex separation theorem, a generalized Bishop-Phelps theorem and a separable point result. The classical result of Dieudonné (on separation of two convex sets in a finite-dimensional space) is also extended to a nonconvex setting.     

Weakly Convex Sets and Their Properties

In this paper, the notion of a weakly convex set is introduced. Sharp estimates for the weak convexity constants of the sum and difference of such sets are given. It is proved that, in Hilbert space, the smoothness of a set is equivalent to the weak convexity of the set and its complement. Here, by definition, the smoothness of a set means that the field of unit outward normal vectors is defined on the boundary of the set; this vector field satisfies the Lipschitz condition. We obtain the minimax theorem for a class of problems with smooth Lebesgue sets of the goal function and strongly convex constraints. As an application of the results obtained, we prove the alternative theorem for program strategies in a linear differential quality game.     

广义Minimax不等式及不动点定理

最近,许多作者推广了著名的Ky Fan的minimax不等式.本文提出了T-对角凸凹性条件,发展了这一方面的主要结果.其次,我们讨论了一些不动点问题,推广了Fan-Glicksberg不动点定理.     

New Generalized R-KKM Type Theorems in General Topological Spaces and Applications

In this paper, some new generalized R-KKM type theorems for generalized R-KKM mappings with finitely closed values and with finitely open values are established in noncompact topological spaces without any convexity structure under much weaker assumptions. As applications, some new minimax inequalities, saddle point theorem and equilibrium existence theorem for equilibrium problems with lower and upper bounds are established in general noncompact topological spaces. These theorems unify and generalize many known results in the literature.     

On maximal element theorems,variants of Ekeland’s variational principle and their applications

In this paper, we establish several different versions of generalized Ekeland’s variational principle and maximal element theorem for τ$\tau$-functions in ?$?$ complete metric spaces. The equivalence relations between maximal element theorems, generalized Ekeland’s variational principle, generalized Caristi’s (common) fixed point theorems and nonconvex maximal element theorems for maps are also proved. Moreover, we obtain some applications to a nonconvex minimax theorem, nonconvex vectorial equilibrium theorems and convergence theorems in complete metric spaces.     

Generalized KKM-type theorems for weakly generalized KKM mapping with some applications

In this paper, we establish some new generalized KKM-type theorems based on weakly generalized KKM mapping without any convexity structure in topological spaces. As applications, some minimax inequalities and an existence theorem of equilibrium points for an abstract generalized vector equilibrium problem are proved in topological spaces. The results presented in this paper unify and generalize some known results in recent literature.     

Minimax theorems for set-valued maps without continuity assumptions

We introduce several classes of set-valued maps with new generalized convexity properties. We also obtain minimax theorems for set-valued maps which satisfy these convexity assumptions and which are not continuous. Our method consists of the use of a fixed point theorem for weakly naturally quasiconcave set-valued maps, defined on a simplex in a topological vector space, or of a constant selection of quasiconvex set-valued maps.     

Separation theorems for nonconvex sets and application in optimization

The aim of this paper is to present separation theorems for two disjoint closed sets, without convexity condition. First, a separation theorem for a given closed cone and a point outside from this cone, is proved and then it is used to prove a separation theorem for two disjoint sets. Illustrative examples are provided to highlight the important aspects of these theorems. An application to optimization is also presented to prove optimality condition for a nonconvex optimization problem.     

Minimax inequalities and fixed points of expansive set-valued mappings with noncompact and nonconvex domains and ranges in topological spaces

Some minimax inequalities involving two bifunctions with noncompact and nonconvex domains are first proved in finite continuous topological spaces (in short, FC$FC$-spaces) without convexity structure. As applications some new Fan–Browder type fixed point theorems for expansive set-valued maps with noncompact and nonconvex domains and ranges are obtained in general topological spaces. These results generalize some known results in the recent literature.     

On minimax optimization problems

We give a short proof that in a convex minimax optimization problem ink dimensions there exist a subset ofk + 1 functions such that a solution to the minimax problem with thosek + 1 functions is a solution to the minimax problem with all functions. We show that convexity is necessary, and prove a similar theorem for stationary points when the functions are not necessarily convex but the gradient exists for each function.     

Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations

In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples.     

Theorems of the Alternative for Multivalued Mappings and Applications to Mixed Convex\Concave Systems of Inequalities

We provide a purely algebraic theorem of the alternative (and its topological variant) involving multivalued mappings under relaxed convexity assumptions. Various more or less classical applications are given, specially for nonconvex quadratic systems. In the second part of the paper we introduce an alternative formulation for a mixed convex\concave statement. The theory is applied to systems of mixed convex\concave inequalities.