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.     

Generalized semi-infinite programming: numerical aspects

Generalized semi-infinite optimization problems (GSIP) are considered. It is investigated how the numerical methods for standard semi-infinite programming (SIP) can be extended to GSIP. Newton methods can be extended immediately. For discretization methods the situation is more complicated. These difficulties are discussed and convergence results for a discretization- and an exchange method are derived under fairly general assumptions on GSIP. The question is answered under which conditions GSIP represents a convex problem.     

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.     

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 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.     

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.     

Derivative evaluation and computational experience with large bilevel mathematical programs

A bilevel program is a mathematical program involving functions defined implicitly as solutions to another mathematical program. We discuss a method for extracting derivative information on the implicit function, which is especially efficient when the lower-level problem has simple bounds on the variables and/or many inactive constraints. Computational experience on problems with up to 230 variables and 30 constraints is presented.Computational support from Robert Bivins and Myron Stein is gratefully acknowledged. We have also appreciated comments from Jon Bard and an anonymous referee. This work was supported in part by the US Department of Energy through the Los Alamos National Laboratory.     

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.     

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.     

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.     

The role of the isotonizing algorithm in Stein’s covariance matrix estimator

Covariance matrix estimation is central to many applications in statistics and allied fields. A useful estimator in this context was proposed by Stein which regularizes the sample covariance matrix by shrinking its eigenvalues together. This estimator can sometimes yield estimates of the eigenvalues that are negative or differ in order from the observed eigenvalues. In order to rectify this problem, Stein also proposed an ad hoc “isotonizing” procedure which pools together eigenvalue estimates in such a way that the original ordering and positivity of the estimates are enforced. From numerical studies, Stein’s “isotonized” estimator is known to have good risk properties in comparison with the maximum likelihood estimator. However, it remains unclear what role is played by the isotonizing procedure in the remarkable risk reductions achieved by Stein’s estimator. Through two distinct lines of investigations, it is established that Stein’s estimator without the isotonizing algorithm gives only modest risk reductions. In cases where the isotonizing algorithm is frequently used, however, Stein’s estimator can lead to significant risk reductions for certain domains of the parameter. In other cases, Stein’s estimator can even yield risk increases, such as when (1) the theoretical eigenvalues are well separated, and/or (2) when the sample size is moderate to large, leading to over-shrinkage.     

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).     

On the Maximum Likelihood Estimation of a Covariance Matrix

For a multivariate normal set-up, it is well known that themaximumlikelihood estimator (MLE) of covariance matrix is neither admissible nor minimax under the Stein loss function. In this paper, we reveal that the MLE based on the Iwasawa parameterization leads to minimaxity with respect to the Stein loss function. Furthermore, a novel class of loss functions is proposed so that the minimum risks of the MLEs are identical in different coordinate systems, Cholesky parameterization and full Iwasawa parameterization. In other words, the MLEs based on these two different parameterizations are characterized by the property of minimaxity, without a Stein paradox. The application of our novel method to the high-dimensional covariance matrix problem is also discussed.     

Stein Neighborhood Bases of Embedded Strongly Pseudoconvex Domains and Approximation of Mappings

In this paper we construct a Stein neighborhood basis for any compact subvariety A with strongly pseudoconvex boundary bA and Stein interior A \ bA in a complex space X. This is an extension of a well known theorem of Siu. When A is a complex curve, our result coincides with the result proved by Drinovec-Drnovšek and Forstnerič. We shall adapt their proof to the higher dimensional case, using also some ideas of Demailly’s proof of Siu’s theorem. For embedded strongly pseudoconvex domain in a complex manifold we also find a basis of tubular Stein neighborhoods. These results are applied to the approximation problem for holomorphic mappings. Research supported by grants ARRS (3311-03-831049), Republic of Slovenia.     

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

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

The asymptotic expansion fo the Stein estimators for the vector case

Summary Charles Stein established the existence of estimators which dominate the maximum likelihood estimators for the problem of simultanously estimating the means of three or more random variables. Since the exact distributions of the Stein estimators are not known and because the distributions are of great importance for people studying confidence sets, it was the purpose of this note to derive the asymptotic distributions, means and variances of the Stein estimators, as well as that of the quadratic loss functions for the vector case. Financially supported by the CSIR and the University of the OFS Research Fund.     

On estimation in multivariate linear calibration with elliptical errors

The estimation problem in multivariate linear calibration with elliptical errors is considered under a loss function which can be derived from the Kullback-Leibler distance. First, we discuss the problem under normal errors and give unbiased estimate of risk of an alternative estimator by means of the Stein and Stein-Haff identities for multivariate normal distribution. From the unbiased estimate of risk, it is shown that a shrinkage estimator improves on the classical estimator under the loss function. Furthermore, from the extended Stein and Stein-Haff identities for our elliptically contoured distribution, the above result under normal errors is extended to the estimation problem under elliptical errors. We show that the shrinkage estimator obtained under normal models is better than the classical estimator under elliptical errors with the above loss function and hence we establish the robustness of the above shrinkage estimator.     

Exponential Stability for Discrete Time Linear Equations Defined by Positive Operators

In this paper the problem of exponential stability of the zero state equilibrium of a discrete-time time-varying linear equation described by a sequence of linear positive operators acting on an ordered finite dimensional Hilbert space is investigated. The class of linear equations considered in this paper contains as particular cases linear equations described by Lyapunov operators or symmetric Stein operators as well as nonsymmetric Stein operators. Such equations occur in connection with the problem of mean square exponential stability for a class of difference stochastic equations affected by independent random perturbations and Markovian jumping as well us in connection with some iterative procedures which allow us to compute global solutions of discrete time generalized symmetric or nonsymmetric Riccati equations. The exponential stability is characterized in terms of the existence of some globally defined and bounded solutions of some suitable backward affine equations (inequalities) or forward affine equations (inequalities).     

Global Maximization of a Generalized Concave Multiplicative Function

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.