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.     

Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems

This paper is devoted to the study of nonsmooth generalized semi-infinite programming problems in which the index set of the inequality constraints depends on the decision vector and all emerging functions are assumed to be locally Lipschitz. We introduce a constraint qualification which is based on the Mordukhovich subdifferential. Then, we derive a Fritz–John type necessary optimality condition. Finally, interrelations between the new and the existing constraint qualifications such as the Mangasarian–Fromovitz, linear independent, and the Slater are investigated.     

Stability and augmented Lagrangian duality in nonconvex semi-infinite programming

In this paper the pseudo-Lipschitz property of the constraint set mapping and the Lipschitz property of the optimal value function of parametric nonconvex semi-infinite optimization problems are obtained under suitable conditions on the limiting subdifferential and the limiting normal cone. Then we derive sufficient conditions for the strong duality of nonconvex semi-infinite optimality problems and a criterion for exact penalty representations via an augmented Lagrangian approach. Examples are given to illustrate the obtained results.     

A semi-infinite programming algorithm for solving optimal power flow with transient stability constraints

This paper proposes a new algorithm for solving a type of complicated optimal power flow (OPF) problems in power systems, i.e., OPF problems with transient stability constraints (OTS). The OTS is converted into a semi-infinite programming (SIP) via some suitable function analysis. Then based on the KKT system of the reformulated SIP, a smoothing quasi-Newton algorithm is presented in which the numerical integration is used. The convergence of the algorithm is established. An OTS problem in power system is tested, which shows that the proposed algorithm is promising.     

Duality for semi-definite and semi-infinite programming

In this article, we study semi-definite and semi-infinite programming problems (SDSIP), which includes semi-infinite linear programs and semi-definite programs as special cases. We establish that a uniform duality between the homogeneous (SDSIP) and its Lagrangian-type dual problem is equivalent to the closedness condition of certain cone. Moreover, this closedness condition was assured by a generalized canonically closedness condition and a Slater condition. Corresponding results for the nonhomogeneous (SDSIP) problem were obtained by transforming it into an equivalent homogeneous (SDSIP) problem.     

An algorithm for semi-infinite transportation problems

In this paper we consider a class of semi-infinite transportation problems. We develop an algorithm for this class of semi-infinite transportation problems. The algorithm is a primal dual method which is a generalization of the classical algorithm for finite transportation problems. The most important aspect of our paper is that we can prove the convergence result for the algorithm. Finally, we implement some examples to illustrate our algorithm.     

Minimizing measures of risk by saddle point conditions

The minimization of risk functions is becoming a very important topic due to its interesting applications in Mathematical Finance and Actuarial Mathematics. This paper addresses this issue in a general framework. Many types of risk function may be involved. A general representation theorem of risk functions is used in order to transform the initial optimization problem into an equivalent one that overcomes several mathematical caveats of risk functions. This new problem involves Banach spaces but a mean value theorem for risk measures is stated, and this simplifies the dual problem. Then, optimality is characterized by saddle point properties of a bilinear expression involving the primal and the dual variable. This characterization is significantly different if one compares it with previous literature. Furthermore, the saddle point condition very easily applies in practice. Four applications in finance and insurance are presented.     

Discretization in semi-infinite programming: the rate of convergence

The discretization approach for solving semi-infinite optimization problems is considered. We are interested in the convergence rate of the error between the solution of the semi-infinite problem and the solution of the discretized program depending on the discretization mesh-size. It will be shown how this rate depends on whether the minimizer is strict of order one or two and on whether the discretization includes boundary points of the index set in a specific way. This is done for ordinary and for generalized semi-infinite problems. Received: November 21, 2000 / Accepted: May 2001?Published online September 17, 2001     

An optimization algorithm based on chaotic behavior and fractal nature

In this paper, we propose a new optimization technique by modifying a chaos optimization algorithm (COA) based on the fractal theory. We first implement the weighted gradient direction-based chaos optimization in which the chaotic property is used to determine the initial choice of the optimization parameters both in the starting step and in the mutations applied when a convergence to local minima occurred. The algorithm is then improved by introducing a method to determine the optimal step size. This method is based on the fact that the sensitive dependence on the initial condition of a root finding technique (such as the Newton–Raphson search technique) has a fractal nature. From all roots (step sizes) found by the implemented technique, the one that most minimizes the cost function is employed in each iteration. Numerical simulation results are presented to evaluate the performance of the proposed algorithm.     

Stability of the intersection of solution sets of semi-infinite systems

Many mathematical programming models arising in practice present a block structure in their constraint systems. Consequently, the feasibility of these problems depends on whether the intersection of the solution sets of each of those blocks is empty or not. The existence theorems allow to decide when the intersection of non-empty sets in the Euclidean space, which are the solution sets of systems of (possibly infinite) inequalities, is empty or not. In those situations where the data (i.e., the constraints) can be affected by some kind of perturbations, the problem consists of determining whether the relative position of the sets is preserved by sufficiently small perturbations or not. This paper focuses on the stability of the non-empty (empty) intersection of the solutions of some given systems, which can be seen as the images of set-valued mappings. We give sufficient conditions for the stability, and necessary ones as well; in particular we consider (semi-infinite) convex systems and also linear systems. In this last case we discuss the distance to ill-posedness.     

Integrated simulation and optimization models for tracking international fixed income indices

Portfolio managers in the international fixed income markets must address jointly the interest rate risk in each market and the exchange rate volatility across markets. This paper develops integrated simulation and optimization models that address these issues in a common framework. Monte Carlo simulation procedures generate jointly scenarios of interest and exchange rates and, thereby, scenarios of holding period returns of the available securities. The portfolio manager’s risk tolerance is incorporated either through a utility function or a (modified) mean absolute deviation function. The optimization models prescribe asset allocation weights among the different markets and also resolve bond-picking decisions. Therefore several interrelated decisions are cast in a common framework. Two models – an expected utility maximization and a mean absolute deviation minimization – are implemented and tested empirically in tracking a composite index of the international bond markets. Backtesting over the period January 1997 to July 1998 illustrate the efficacy of the optimization models in dealing with uncertainty and tracking effectively the volatile index. Of particular interest is the empirical demostration that the integrative models generate portfolios that dominate the portfolios obtained using classical disintegrated approaches. Received: November 24, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Stability in convex semi-infinite programming and rates of convergence of optimal solutions of discretized finite subproblems

We consider convex semiinfinite programming (SIP) problems with an arbitrary fixed index set T. The article analyzes the relationship between the upper and lower semicontinuity (lsc) of the optimal value function and the optimal set mapping, and the so-called Hadamard well-posedness property (allowing for more than one optimal solution). We consider the family of all functions involved in some fixed optimization problem as one element of a space of data equipped with some topology, and arbitrary perturbations are premitted as long as the perturbed problem continues to be convex semiinfinite. Since no structure is required for T, our results apply to the ordinary convex programming case. We also provide conditions, not involving any second order optimality one, guaranteeing that the distance between optimal solutions of the discretized subproblems and the optimal set of the original problem decreases by a rate which is linear with respect to the discretization mesh-size.     

A Minimax Theorem Without Compactness Hypothesis

The object of this short note is the proof of a minimax theorem which does not require compactness conditions and is motivated by a problem of optimal investment; the application to the economic problem is illustrated.     

Stochastic optimal control of ultradiffusion processes with application to dynamic portfolio management

We consider theoretical and approximation aspects of the stochastic optimal control of ultradiffusion processes in the context of a prototype model for the selling price of a European call option. Within a continuous-time framework, the dynamic management of a portfolio of assets is effected through continuous or point control, activation costs, and phase delay. The performance index is derived from the unique weak variational solution to the ultraparabolic Hamilton–Jacobi equation; the value function is the optimal realization of the performance index relative to all feasible portfolios. An approximation procedure based upon a temporal box scheme/finite element method is analyzed; numerical examples are presented in order to demonstrate the viability of the approach.     

Robust utility maximization with limited downside risk in incomplete markets

In this article we consider the portfolio selection problem of an agent with robust preferences in the sense of Gilboa and Schmeidler [Itzhak Gilboa, David Schmeidler, Maxmin expected utility with non-unique prior, Journal of Mathematical Economics 18 (1989) 141–153] in an incomplete market. Downside risk is constrained by a robust version of utility-based shortfall risk. We derive an explicit representation of the optimal terminal wealth in terms of certain worst case measures which can be characterized as minimizers of a dual problem. This dual problem involves a three-dimensional analogue of f$f$-divergences which generalize the notion of relative entropy.     

Price Operators Analysis in L p -Spaces

An integral type representation and various extension theorems for monotone linear operators in L _p -spaces are considered in relation to market price modelling. As application, a characterization of the existence of a risk-neutral probability measure equivalent to the applied underlying one is provided in terms of the given prices. These results are in the line of the fundamental theorem of asset pricing. Here, in particular, the risk-neutral probability measure considered has the advantage of having its density laying in pre-considered upper and lower bounds.     

Stochastic optimization algorithms for barrier dividend strategies

This work focuses on finding optimal barrier policy for an insurance risk model when the dividends are paid to the share holders according to a barrier strategy. A new approach based on stochastic optimization methods is developed. Compared with the existing results in the literature, more general surplus processes are considered. Precise models of the surplus need not be known; only noise-corrupted observations of the dividends are used. Using barrier-type strategies, a class of stochastic optimization algorithms are developed. Convergence of the algorithm is analyzed; rate of convergence is also provided. Numerical results are reported to demonstrate the performance of the algorithm.     

Infinitely Many Securities and the Fundamental Theorem of Asset Pricing

Several authors have pointed out the possible absence of martingale measures for static arbitrage free markets with an infinite number of available securities. Accordingly, the literature constructs martingale measures by generalizing the concept of arbitrage (free lunch, free lunch with bounded risk, etc.) or introducing the theory of large financial markets. This paper does not modify the definition of arbitrage and addresses the caveat by drawing on projective systems of probability measures. Thus we analyze those situations for which one can provide a projective system of σ–additive measures whose projective limit may be interpreted as a risk-neutral probability of an arbitrage free market. Hence the Fundamental Theorem of Asset Pricing is extended so that it can apply for models with infinitely many assets. Partially funded by the Spanish Ministry of Science and Education (ref: BEC2003 – 09067 –C04 – 03) and Comunidad Autonoma de Madrid (ref: s – 0505/tic/000230).     

Linear bilevel programming with interval coefficients

In this paper, we address linear bilevel programs when the coefficients of both objective functions are interval numbers. The focus is on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. We prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range.     

A path to the Arrow–Debreu competitive market equilibrium

We present polynomial-time interior-point algorithms for solving the Fisher and Arrow–Debreu competitive market equilibrium problems with linear utilities and n players. Both of them have the arithmetic operation complexity bound of )) for computing an -equilibrium solution. If the problem data are rational numbers and their bit-length is L, then the bound to generate an exact solution is O(n ⁴ L) which is in line with the best complexity bound for linear programming of the same dimension and size. This is a significant improvement over the previously best bound )) for approximating the two problems using other methods. The key ingredient to derive these results is to show that these problems admit convex optimization formulations, efficient barrier functions and fast rounding techniques. We also present a continuous path leading to the set of the Arrow–Debreu equilibrium, similar to the central path developed for linear programming interior-point methods. This path is derived from the weighted logarithmic utility and barrier functions and the Brouwer fixed-point theorem. The defining equations are bilinear and possess some primal-dual structure for the application of the Newton-based path-following method. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday. This author was supported in part by NSF Grants DMS-0306611 and DMS-0604513. The author would like to thank Curtis Eaves, Osman Güler, Kamal Jain and Mike Todd for insightful discussions on this subject, especially on their mathematical references and economic interpretations of the fixed-point model presented in this paper.