Semi-infinite optimization: Structure and stability of the feasible set

The problem of the minimization of a functionf: ⁿ under finitely many equality constraints and perhaps infinitely many inequality constraints gives rise to a structural analysis of the feasible setM[H, G]={xⁿ¦H(x)=0,G(x, y)0,yY} with compactY^r. An extension of the well-known Mangasarian-Fromovitz constraint qualification (EMFCQ) is introduced. The main result for compactM[H, G] is the equivalence of the topological stability of the feasible setM[H, G] and the validity of EMFCQ. As a byproduct, we obtain under EMFCQ that the feasible set admits local linearizations and also thatM[H, G] depends continuously on the pair (H, G). Moreover, EMFCQ is shown to be satisfied generically.The authors would like to thank Rainer Hettich and Doug Ward for fruitful discussions. Moreover, the authors are indebted to the anonymous referees for their valuable comments.     

An approximation of feasible sets in semi-infinite optimization

The paper deals with the feasible setM of a semi-infinite optimization problem, i.e.M is a subset of the finite-dimensional Euclidean space and is basically defined by infinitely many inequality constraints. Assuming that the extended Mangasarian-Fromovitz constraint qualification holds at all points fromM, it is shown that the quadratic distance function with respect toM is continuously differentiable on an open neighborhood ofM. If, in addition,M is compact, then the set , which is described by this quadratic distance function, is shown to be an appropriate approximation ofM and the setsM and can be topologically identified via a homeomorphism.     

Multi-objective optimization over convex disjunctive feasible sets using reference points

In this paper we consider the Multiple Objective Optimization Problem (MOOP), where concave functions are to be maximized over a feasible set represented as a union of compact convex sets. To solve this problem we consider two auxiliary scalar optimization problems which use reference points. The first one contains only continuous variables, it has higher dimensionality, however it is convex. The second scalar problem is a mixed integer programming problem. The solutions of both scalar problems determine nondominated points. Some other properties of these problems are also discussed.     

Mercer theorem for RKHS on noncompact sets

Reproducing kernel Hilbert spaces are an important family of function spaces and play useful roles in various branches of analysis and applications including the kernel machine learning. When the domain of definition is compact, they can be characterized as the image of the square root of an integral operator, by means of the Mercer theorem. The purpose of this paper is to extend the Mercer theorem to noncompact domains, and to establish a functional analysis characterization of the reproducing kernel Hilbert spaces on general domains.     

The stability of the solution sets for set optimization problems via improvement sets

ABSTRACT

The aim of this paper is to investigate the stability of the solution sets for set optimization problems via improvement sets. Firstly, we consider the relations among the solution sets for optimization problem with set optimization criterion. Then, the closeness and the convexity of solution sets are discussed. Furthermore, the upper semi-continuity, Hausdorff upper semi-continuity and lower semi-continuity of solution mappings to parametric set optimization problems via improvement sets are established under some suitable conditions. These results extend and develop some recent works in this field.     

Eventual convexity of chance constrained feasible sets

In decision-making problems where uncertainty plays a key role and decisions have to be taken prior to observing uncertainty, chance constraints are a strong modelling tool for defining safety of decisions. These constraints request that a random inequality system depending on a decision vector has to be satisfied with a high probability. The characteristics of the feasible set of such chance constraints depend on the constraint mapping of the random inequality system, the underlying law of uncertainty and the probability level. One characteristic of particular interest is convexity. Convexity can be shown under fairly general conditions on the underlying law of uncertainty and on the constraint mapping, regardless of the probability-level. In some situations, convexity can only be shown when the probability-level is high enough. This is defined as eventual convexity. In this paper, we will investigate further how eventual convexity can be assured for specially structured chance constraints involving Copulae. The Copulae have to exhibit generalized concavity properties. In particular, we will extend recent results and exhibit a clear link between the generalized concavity properties of the various mappings involved in the chance constraint for the result to hold. Various examples show the strength of the provided generalization.     

On feasible sets defined through Chebyshev approximation

LetZ be a compact set of the real space with at leastn + 2 points;f,h1,h2:Z continuous functions,h1,h2 strictly positive andP(x,z),x(x ₀,...,x _n ) ⁿ⁺¹,z , a polynomial of degree at mostn. Consider a feasible setM {x ⁿ⁺¹z Z, –h ₂(z) P(x, z)–f(z)h ₁(z)}. Here it is proved the null vector 0 of ⁿ⁺¹ belongs to the compact convex hull of the gradients ± (1,z,...,z ⁿ ), wherez Z are the index points in which the constraint functions are active for a givenx* M, if and only ifM is a singleton.This work was partially supported by CONACYT-MEXICO.     

Study on chaos induced by turbulent maps in noncompact sets

This paper is concerned with chaos induced by strictly turbulent maps in noncompact sets of complete metric spaces. Two criteria of chaos for such types of maps are established, and then a criterion of chaos, characterized by snap-back repellers in complete metric spaces, is obtained. All the maps presented in this paper are proved to be chaotic either in the sense of both Li–Yorke and Wiggins or in the sense of both Li–Yorke and Devaney. The results weaken the assumptions in some existing criteria of chaos. Several illustrative examples are provided with computer simulation.     

Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals

This paper studies the representation of a positive polynomial f(x) on a noncompact semialgebraic set S={x∈Rⁿ:g₁(x)≥0,…,g_s(x)≥0} modulo its KKT (Karush-Kuhn-Tucker) ideal. Under the assumption that the minimum value of f(x) on S is attained at some KKT point, we show that f(x) can be represented as sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)>0 on S; furthermore, when the KKT ideal is radical, we argue that f(x) can be represented as a sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)≥0 on S. This is a generalization of results in [J. Nie, J. Demmel, B. Sturmfels, Minimizing polynomials via sum of squares over the gradient ideal, Mathematical Programming (in press)], which discusses the SOS representations of nonnegative polynomials over gradient ideals.     

ON THE MINIMUM FEASIBLE GRAPH FOR FOUR SETS

ＯＮＴＨＥＭＩＮＩＭＵＭＦＥＡＳＩＢＬＥＧＲＡＰＨＦＯＲＦＯＵＲＳＥＴＳＸＵＹＩＮＦＥＮＧＡＮＤＦＵＸＩＡＯＢＩＮＧＡｂｓｔｒａｃｔ：ＧｉｖｅｎａｃｏｍｐｌｅｔｅｇｒａｐｈｗｉｔｈｖｅｒｔｅｘｓｅｔＸａｎｄｓｕｂｓｅｔｓＸ＿１，Ｘ＿２，．．．，Ｘ＿ｎ...     

Bilevel optimization: on the structure of the feasible set

We consider bilevel optimization from the optimistic point of view. Let the pair (x, y) denote the variables. The main difficulty in studying such problems lies in the fact that the lower level contains a global constraint. In fact, a point (x, y) is feasible if y solves a parametric optimization problem L(x). In this paper we restrict ourselves to the special case that the variable x is one-dimensional. We describe the generic structure of the feasible set M. Moreover, we discuss local reductions of the bilevel problem as well as corresponding optimality criteria. Finally, we point out typical problems that appear when trying to extend the ideas to higher dimensional x-dimensions. This will clarify the high intrinsic complexity of the general generic structure of the feasible set M and corresponding optimality conditions for the bilevel problem U.     

Continuity of the feasible solution sets of probabilistic constrained programs

In this paper, we show the continuity of the feasibility set with respect to the reliability levels and with respect to the distribution of the random elements of a stochastic program with probabilistic constraints. Continuity is then used to obtain stability results for this type of stochastic program. An easy criterion is given for checking the conditions which guarantee the continuity of the feasibility set.The author wishes to thank Professor R. Wets for his comments.