Generalized semi-infinite programming: A tutorial

This tutorial presents an introduction to generalized semi-infinite programming (GSIP) which in recent years became a vivid field of active research in mathematical programming. A GSIP problem is characterized by an infinite number of inequality constraints, and the corresponding index set depends additionally on the decision variables. There exist a wide range of applications which give rise to GSIP models; some of them are discussed in the present paper. Furthermore, geometric and topological properties of the feasible set and, in particular, the difference to the standard semi-infinite case are analyzed. By using first-order approximations of the feasible set corresponding constraint qualifications are developed. Then, necessary and sufficient first- and second-order optimality conditions are presented where directional differentiability properties of the optimal value function of the so-called lower level problem are used. Finally, an overview of numerical methods is given.     

On equivalent stability properties in semi-infinite optimization

This paper studies noncompact feasible sets of a semi-infinite optimization problem which are defined by finitely many equality constraints and infinitely many inequality constraints. The main result is the equivalence of the overall validity of the Extended Mangasarian Fromovitz Constraint Qualification with certain (topological) stability conditions. Furthermore, two perturbation theorems being of independent interest are presented.This work was supported by the Deutsche Forschungsgemeinschaft under grant Gu 304/1-2.     

Topological stability of linear semi-infinite inequality systems

In this note, we analyze the relationship between the lower semicontinuity of the feasible set mapping for linear semi-infinite inequality systems and the so-called topological stability, which is held when the solution sets of all the systems obtained by sufficiently small perturbations of the data are homeomorphic to each other. This topological stability and its relation with the Mangasarian-Fromovitz constraints qualification have been studied deeply by Jongen et al. in Ref. 1. The main difference of our approach is that we are not assuming any kind of structure for the index set and, consequently, any particular property for the functional dependence between the inequalities and the associated indices. In addition, we deal with systems whose solution sets are not necessarily bounded.This work has been supported partially by the DGICYT of Spain, Grant PB93-0943, by Generalitat Valenciana, Grant GV-2219/94, and by IVEI, Grant 003/026.The authors would like to thank J. E. Martínez Legaz for his valuable comments.     

Dimension and finite reduction in linear semi-infinite programming

In the first part, different characterizations for the dimension of the feasible set in linear semi-infinite programming are provided. They involve the corresponding dimensions of some parameter sets, as the consequent inequalities cone and its lineality subspace. The remaining sections of the paper deal with Farkas–Minkowski systems. The third section is devoted to establish some results concerning the optimal set and its dimension, exploiting its strong relation with a particular parameter cone

associated with the corresponding unstable constraints. The last section approaches the finite reducibility problem. We have intended to characterize those finite subproblems with the same optimal value as the original problem, by means of a simplc dual analysis, based on the main results derived before.     

Feasible directions algorithms for optimization problems with equality and inequality constraints

In this paper two algorithms, of the feasible-directions and dual feasible-directions type, are presented for optimization problems with equality and inequality constraints. An associated problem, having only inequality constraints, is defined, and shown to be equivalent to the original problem if a certain parameter is sufficiently large. The algorithms solve the associated problem, but incorporate a method for automatically increasing this parameter in order to ensure global convergence to a solution to the original problem. Any feasible directions algorithm can be similarly modified to enable it to handle equality constraints.Research sponsored by the US Army Research Office — Durham, Contract DAHCO4-73-C-0025 and the National Science Foundation Grant GK-37572.     

The almost chebyshev property in linear semi-infinite programming

We consider a linear semi-infinite programming problem where the index set of the constraints is compact and the constraint functions are continuous on it. The set of all continuous functions on this index set as right hand sides are the parameter set. We investigate how large various unicity sets are.We state a condition on the objective function vector and the “matrix” of the problem which characterizes when the set of a parameters with a non-unique optimal point is a set of the first Baire category in the solvability set. This is the case if and only if the unicity set is a dense subset of the solvability set. Under the same assumptions it is even true that the interior of the strong unicity set is I also dense. If the index set of the constraints contains a dense subset with the property that each point1 is a G ₈-set, then the parameters of the strong unicity set, such that the optimal point satisfies the linear independence constraint qualification, are also dense.

We apply our results to a characterization of a unique continuous selection for the optimal set I mapping and to a one-sided L ₁-approximation problem     

Nonsmooth semi-infinite programming problems with mixed constraints

We consider a nonsmooth semi-infinite programming problem with a feasible set defined by inequality and equality constraints and a set constraint. First, we study some alternative theorems which involve linear and sublinear functions and a convex set and we propose several generalizations of them. Then, alternative theorems are applied to obtain, under different constraint qualifications, several necessary optimality conditions in the type of Fritz-John and Karush-Kuhn-Tucker.     

Upper Semicontinuity of the Feasible Set Mapping for Linear Inequality Systems

In this paper we characterize the upper semicontinuity of the feasible set mapping at a consistent linear semi-infinite system (LSIS, in brief). In our context, no standard hypothesis is required in relation to the set indexing the constraints and, consequently, the functional dependence between the linear constraints and their associated indices has no special property. We consider, as parameter space, the set of all LSIS having the same index set, endowed with an extended metric to measure the size of the perturbations. We introduce the concept of reinforced system associated with our nominal system. Then, the upper semicontinuity property of the feasible set mapping at the nominal system is characterized looking at the feasible sets of both systems. The fact that this characterization depends only on the nominal system, not involving systems in a neighbourhood, is remarkable. We also provide a necessary and sufficient condition for the aimed property exclusively in terms of the coefficients of the system.     

On the functions with pseudoconvex sublevel sets and optimality conditions

A new class of generalized convex functions, called the functions with pseudoconvex sublevel sets, is defined. They include quasiconvex ones. A complete characterization of these functions is derived. Further, it is shown that a continuous function admits pseudoconvex sublevel sets if and only if it is quasiconvex. Optimality conditions for a minimum of the nonsmooth nonlinear programming problem with inequality, equality and a set constraints are obtained in terms of the lower Hadamard directional derivative. In particular sufficient conditions for a strict global minimum are given where the functions have pseudoconvex sublevel sets.     

Constraint qualifications and optimality conditions for nonconvex semi-infinite and infinite programs

The paper concerns the study of new classes of nonlinear and nonconvex optimization problems of the so-called infinite programming that are generally defined on infinite-dimensional spaces of decision variables and contain infinitely many of equality and inequality constraints with arbitrary (may not be compact) index sets. These problems reduce to semi-infinite programs in the case of finite-dimensional spaces of decision variables. We extend the classical Mangasarian–Fromovitz and Farkas–Minkowski constraint qualifications to such infinite and semi-infinite programs. The new qualification conditions are used for exact calculations of the appropriate normal cones to sets of feasible solutions for these programs by employing advanced tools of variational analysis and generalized differentiation. In the further development we derive first-order necessary optimality conditions for infinite and semi-infinite programs, which are new in both finite-dimensional and infinite-dimensional settings.     

Analytical Linear Inequality Systems and Optimization

In many interesting semi-infinite programming problems, all the constraints are linear inequalities whose coefficients are analytical functions of a one-dimensional parameter. This paper shows that significant geometrical information on the feasible set of these problems can be obtained directly from the given coefficient functions. One of these geometrical properties gives rise to a general purification scheme for linear semi-infinite programs equipped with so-called analytical constraint systems. It is also shown that the solution sets of such kind of consistent systems form a transition class between polyhedral convex sets and closed convex sets in the Euclidean space of the unknowns.     

Equilibrium constrained optimization problems

We consider equilibrium constrained optimization problems, which have a general formulation that encompasses well-known models such as mathematical programs with equilibrium constraints, bilevel programs, and generalized semi-infinite programming problems. Based on the celebrated KKM lemma, we prove the existence of feasible points for the equilibrium constraints. Moreover, we analyze the topological and analytical structure of the feasible set. Alternative formulations of an equilibrium constrained optimization problem (ECOP) that are suitable for numerical purposes are also given. As an important first step for developing efficient algorithms, we provide a genericity analysis for the feasible set of a particular ECOP, for which all the functions are assumed to be linear.     

Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization,reverse convex constraints,DC-programming,and Lipschitzian optimization

A crucial problem for many global optimization methods is how to handle partition sets whose feasibility is not known. This problem is solved for broad classes of feasible sets including convex sets, sets defined by finitely many convex and reverse convex constraints, and sets defined by Lipschitzian inequalities. Moreover, a fairly general theory of bounding is presented and applied to concave objective functions, to functions representable as differences of two convex functions, and to Lipschitzian functions. The resulting algorithms allow one to solve any global optimization problem whose objective function is of one of these forms and whose feasible set belongs to one of the above classes. In this way, several new fields of optimization are opened to the application of global methods.     

The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets

A numerical solution method for semi-infinite optimization problems with arbitrary, not necessarily box-shaped, index sets is presented. Following the ideas of Floudas and Stein (SIAM J Optim 18:1187?C1208, 2007), convex relaxations of the lower level problem are adaptively constructed and then reformulated as mathematical programs with complementarity constraints and solved. Although the index set is arbitrary, this approximation produces feasible iterates for the original problem. The convex relaxations and needed parameters are constructed with ideas of the ??BB method of global optimization and interval methods. It is shown that after finitely many steps an ${\epsilon}$ -stationary point of the original semi-infinite problem is reached. A numerical example illustrates the performance of the proposed method.     

On the Complexity of Equalizing Inequalities

We study two approaches to replace a finite mathematical programming problem with inequality constraints by a problem that contains only equality constraints. The first approach lifts the feasible set into a high-dimensional space by the introduction of quadratic slack variables. We show that then not only the number of critical points but also the topological complexity of the feasible set grow exponentially. On the other hand, the second approach bases on an interior point technique and lifts an approximation of the feasible set into a space with only one additional dimension. Here only Karush–Kuhn–Tucker points with respect to the positive and negative objective function in the original problem give rise to critical points of the smoothed problem, so that the number of critical points as well as the topological complexity can at most double.     

Feasibility in reverse convex mixed-integer programming

In this paper we address the problem of the infeasibility of systems defined by reverse convex inequality constraints, where some or all of the variables are integer. In particular, we provide a polynomial algorithm that identifies a set of all constraints critical to feasibility (CF), that is constraints that may affect a feasibility status of the system after some perturbation of the right-hand sides. Furthermore, we will investigate properties of the irreducible infeasible sets and infeasibility sets, showing in particular that every irreducible infeasible set as well as infeasibility sets in the considered system, are subsets of the set CF of constraints critical to feasibility.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.