Generalized semi-infinite programming: Theory and methods

Generalized semi-infinite optimization problems (GSIP) are considered. The difference between GSIP and standard semi-infinite problems (SIP) is illustrated by examples. By applying the `Reduction Ansatz', optimality conditions for GSIP are derived. Numerical methods for solving GSIP are considered in comparison with methods for SIP. From a theoretical and a practical point of view it is investigated, under which assumptions a GSIP can be transformed into an SIP.     

On generalized semi-infinite optimization and bilevel optimization

The paper studies the connections and differences between bilevel problems (BL) and generalized semi-infinite problems (GSIP). Under natural assumptions (GSIP) can be seen as a special case of a (BL). We consider the so-called reduction approach for (BL) and (GSIP) leading to optimality conditions and Newton-type methods for solving the problems. We show by a structural analysis that for (GSIP)-problems the regularity assumptions for the reduction approach can be expected to hold generically at a solution but for general (BL)-problems not. The genericity behavior of (BL) and (GSIP) is in particular studied for linear problems.     

Lower level duality and the global solution of generalized semi-infinite programs

The reformulation of generalized semi-infinite programs (GSIP) to simpler problems is considered. These reformulations are achieved under the assumption that a duality property holds for the lower level program (LLP). Lagrangian duality is used in the general case to establish the relationship between the GSIP and a related semi-infinite program (SIP). Practical aspects of this reformulation, including how to bound the duality multipliers, are also considered. This SIP reformulation result is then combined with recent advances for the global, feasible solution of SIP to develop a global, feasible point method for the solution of GSIP. Reformulations to finite nonlinear programs, and the practical aspects of solving these reformulations globally, are also discussed. When the LLP is a linear program or second-order cone program, specific duality results can be used that lead to stronger results. Numerical examples demonstrate that the global solution of GSIP is computationally practical via the solution of these duality-based reformulations.     

On Optimality Conditions for Generalized Semi-Infinite Programming Problems

Generalized semi-infinite optimization problems (GSIP) are considered. We generalize the well-known optimality conditions for minimizers of order one in standard semi-infinite programming to the GSIP case. We give necessary and sufficient conditions for local minimizers of order one without the assumption of local reduction. The necessary conditions are derived along the same lines as the first-order necessary conditions for GSIP in a recent paper of Jongen, Rückmann, and Stein (Ref. 1) by assuming the so-called extended Mangasarian–Fromovitz constraint qualification. Using the ideas of a recent paper of Rückmann and Shapiro, we give short proofs of necessary and sufficient optimality conditions for minimizers of order one under the additional assumption of the Mangasarian–Fromovitz constraint qualification at all local minimizers of the so-called lower-level problem.     

On generalized semi-infinite programming

This paper surveys some basic properties of the class of generalized semi-infinite programming problems (GSIP) where the infinite index set of inequality constraints depends on the state variables and all emerging functions are assumed to be continuously differentiable. There exists a wide range of applications which can be modelled as a (GSIP). The paper discusses extensions of the Mangasarian-Fromovitz, Kuhn-Tucker and Abadie constraint qualification to (GSIP) and presents related first order optimality conditions of Fritz-John and Karush-Kuhn-Tucker type. By using directional differentiability properties of the optimal value function of the lower level problem, first and second order necessary and sufficient optimality conditions are discussed. Several examples illustrate the results presented. The work of this author was supported by CONACYT (México) under grant 44003.     

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.     

Application of general semi-infinite programming to lapidary cutting problems

We consider a volume maximization problem arising in gemstone cutting industry. The problem is formulated as a general semi-infinite program (GSIP) and solved using an interior-point method developed by Stein [O. Stein, Bi-level Strategies in Semi-infinite Programming, Kluwer Academic Publishers, Boston, 2003]. It is shown, that the convexity assumption needed for the convergence of the algorithm can be satisfied by appropriate modelling. Clustering techniques are used to reduce the number of container constraints, which is necessary to make the subproblems practically tractable. An iterative process consisting of GSIP optimization and adaptive refinement steps is then employed to obtain an optimal solution which is also feasible for the original problem. Some numerical results based on real-world data are also presented.     

A lifting method for generalized semi-infinite programs based on lower level Wolfe duality

This paper introduces novel numerical solution strategies for generalized semi-infinite optimization problems (GSIP), a class of mathematical optimization problems which occur naturally in the context of design centering problems, robust optimization problems, and many fields of engineering science. GSIPs can be regarded as bilevel optimization problems, where a parametric lower-level maximization problem has to be solved in order to check feasibility of the upper level minimization problem. The current paper discusses several strategies to reformulate this class of problems into equivalent finite minimization problems by exploiting the concept of Wolfe duality for convex lower level problems. Here, the main contribution is the discussion of the non-degeneracy of the corresponding formulations under various assumptions. Finally, these non-degenerate reformulations of the original GSIP allow us to apply standard nonlinear optimization algorithms.     

Semi-infinite programming method for optimal power flow with transient stability and variable clearing time of faults

This paper presents a new nonlinear programming problem arising in the control of power systems, called optimal power flow with transient stability constraint and variable clearing time of faults and abbreviated as OTS-VT. The OTS-VT model is converted into a implicit generalized semi-infinite programming (GSIP) problem. According to the special box structure of the reformulated GSIP, a solution method based on bi-level optimization is proposed. The research in this paper has two contributions. Firstly, it generalizes the OTS study to general optimal power flow with transient stability problems. From the viewpoint of practical applications, the proposed research can improve the decision-making ability in power system operations. Secondly, the reformulation of OTS-VT also provides a new background and a type of GSIP in the research of mathematical problems. Numerical results for two chosen power systems show that the methodology presented in this paper is effective and promising.     

Generalized semi-infinite optimization: A first order optimality condition and examples

We consider a generalized semi-infinite optimization problem (GSIP) of the form (GSIP) min{f(x)‖xεM}, where M={x∈ℝⁿ|h_i(x)=0i=l,...m, G(x,y)⩾0, y∈Y(x)} and all appearing functions are continuously differentiable. Furthermore, we assume that the setY(x) is compact for allx under consideration and the set-valued mappingY(.) is upper semi-continuous. The difference with a standard semi-infinite problem lies in thex-dependence of the index setY. We prove a first order necessary optimality condition of Fritz John type without assuming a constraint qualification or any kind of reduction approach. Moreover, we discuss some geometrical properties of the feasible setM. This work was partially supported by the “Deutsche Forschungsgemeinschaft” through the Graduiertenkolleg “Mathematische Optimierung” at the University of Trier.     

On generalized semi-infinite optimization of genetic networks

Since some years, the emerging area of computational biology is looking for its mathematical foundations. Based on modern contributions given to this area, our paper approaches modeling and prediction of gene-expression patterns by optimization theory, with a special emphasis on generalized semi-infinite optimization. Based on experimental data, nonlinear ordinary differential equations are obtained by the optimization of least-squares errors. The genetic process can be investigated by a time-discretization and a utilization of a combinatorial algorithm to detect the stability regions. We represent the dynamical systems by means of matrices which allow biological-medical interpretations, and by genetic or new gene-environment networks. For evaluating these networks we optimize them under constraints imposed. For controlling the connectedness structure of the network, we introduce GSIP into this modern application field which can lead to important services in medicine and biotechnology, including energy production and material science.      

On Topological Properties of Min-Max Functions

We examine the topological structure of the upper-level set M ^max given by a min-max function φ. It is motivated by recent progress in Generalized Semi-Infinite Programming (GSIP). Generically, M ^max is proven to be the topological closure of the GSIP feasible set (see Guerra-Vázquez et al. 2009; Günzel et al., Cent Eur J Oper Res 15(3):271–280, 2007). We formulate two assumptions (Compactness Condition CC and Sym-MFCQ) which imply that M ^max is a Lipschitz manifold (with boundary). The Compactness Condition is shown to be stable under C ⁰-perturbations of the defining functions of φ. Sym-MFCQ can be seen as a constraint qualification in terms of Clarke’s subdifferential of the min-max function φ. Moreover, Sym-MFCQ is proven to be generic and stable under C ¹-perturbations of the defining functions which fulfill the Compactness Condition. Finally we apply our results to GSIP and conclude that generically the closure of the GSIP feasible set is a Lipschitz manifold (with boundary).     

一类广义半无限规划问题的光滑牛顿算法

本文在广义半无限规划问题的最优解集X处满足某些条件的前提下将广义半无限规划问题转化成KKT系统,通过扰动的FB函数,将KKT系统转化为一组光滑函数方程,设计了一个光滑牛顿算法,证明了算法的全局收敛性,并且在光滑函数解集处满足局部误差界条件下证明了算法具有超线性收敛速率.     

Two-dimensional Green’s functions for semi-infinite isotropic thermoelastic plane

Based on the two-dimensional steady-state governing equations of isotropic thermoelastic material and the compact general solution expressed in three harmonic functions, the corresponding three harmonic functions contain nine undetermined constants are constructed for a line heat source applied in the interior of a semi-infinite thermoelastic plane. All components of thermoelastic field in the semi-infinite plane can be derived by substituting the harmonic functions into the general solution. And the undetermined constants can be obtained by the compatibility conditions, equilibrium conditions and the different boundary conditions for extended Mindlin problem and extended Lorentz problem. Thus, the Green’s functions in above two cases are obtained, and the numerical results are given graphically by contours.     

Interval Methods for Semi-Infinite Programs

A new approach for the numerical solution of smooth, nonlinear semi-infinite programs whose feasible set contains a nonempty interior is presented. Interval analysis methods are used to construct finite nonlinear, or mixed-integer nonlinear, reformulations of the original semi-infinite program under relatively mild assumptions on the problem structure. In certain cases the finite reformulation is exact and can be solved directly for the global minimum of the semi-infinite program (SIP). In the general case, this reformulation is over-constrained relative to the SIP, such that solving it yields a guaranteed feasible upper bound to the SIP solution. This upper bound can then be refined using a subdivision procedure which is shown to converge to the true SIP solution with finite -optimality. In particular, the method is shown to converge for SIPs which do not satisfy regularity assumptions required by reduction-based methods, and for which certain points in the feasible set are subject to an infinite number of active constraints. Numerical results are presented for a number of problems in the SIP literature. The solutions obtained are compared to those identified by reduction-based methods, the relative performances of the nonlinear and mixed-integer nonlinear formulations are studied, and the use of different inclusion functions in the finite reformulation is investigated.     

Interior-point algorithms for semi-infinite programming

In order to study the behavior of interior-point methods on very large-scale linear programming problems, we consider the application of such methods to continuous semi-infinite linear programming problems in both primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite-dimensional) interior-point methods. We find that while many methods are invariant, several, including all those with the currently best complexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our belief that for a method to work well on large-scale linear programming problems, it should be effective on fine discretizations of a semi-infinite problem and it should have a natural extension to the limiting semi-infinite case.Research supported in part by NSF, AFORS and ONR through NSF grant DMS-8920550.     

Dwell-time stability and stabilization conditions for linear positive impulsive and switched systems

Several results regarding the stability and the stabilization of linear impulsive positive systems under arbitrary, constant, minimum, maximum and range dwell-time are obtained. The proposed stability conditions characterize the pointwise decrease of a linear copositive Lyapunov function and are formulated in terms of finite-dimensional or semi-infinite linear programs. To be applicable to uncertain systems and to control design, a lifting approach introducing a clock-variable is then considered in order to make the conditions affine in the matrices of the system. The resulting stability and stabilization conditions are stated as infinite-dimensional linear programs for which three asymptotically exact computational methods are proposed and compared with each other on numerical examples. Similar results are then obtained for linear positive switched systems by exploiting the possibility of reformulating a switched system as an impulsive system. Some existing stability conditions are retrieved and extended to stabilization using the proposed lifting approach. Several examples are finally given for illustration.     

uv-理论在一类半无限最小化问题的应用

Lemarechal,Oustry和Sagastizabal(2000)提出的uv分解理论为解决非光滑函数的高阶展开提供了一种新的途径，并将此理论应用于研究具有有限个约束的非线性规划的精确罚函数．本文将这一研究推广到具有无限约束的一类半无限规划的问题上，并给出了与这类最小化问题的精确罚函数的U-Lagrange函数有关的某些结果．     

Two basic problems in reliability-based structural optimization

Optimization of structures with respect to performance, weight or cost is a well-known application of mathematical optimization theory. However optimization of structures with respect to weight or cost under probabilistic reliability constraints or optimization with respect to reliability under cost/weight constraints has been subject of only very few studies. The difficulty in using probabilistic constraints or reliability targets lies in the fact that modern reliability methods themselves are formulated as a problem of optimization. In this paper two special formulations based on the so-called first-order reliability method (FORM) are presented. It is demonstrated that both problems can be solved by a one-level optimization problem, at least for problems in which structural failure is characterized by a single failure criterion. Three examples demonstrate the algorithm indicating that the proposed formulations are comparable in numerical effort with an approach based on semi-infinite programming but are definitely superior to a two-level formulation.