Decision making under uncertainty: A semi-infinite programming approach

The subject of this paper is the formulation and discussion of a semi-infinite linear vector optimization problem which extends multiple objective linear programming problems to those with an infinite number of objective functions and constraints. Furthermore it generalizes in some way semi-infinite programming. Besides the statement of some immediately derived results which are related to known results in semi-infinite linear programming and vector optimization, the problem mentioned above is interpreted as a decision model, under risk or uncertainty containing continuous random variables. Thus we treat the case of an infinite number of occuring states of nature. These types of problems frequently occur within aspects of decision theory in management science.     

Feasible Method for Generalized Semi-Infinite Programming

In this paper, we analyze the outer approximation property of the algorithm for generalized semi-infinite programming from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). A simple bound on the regularization error is found and used to formulate a feasible numerical method for generalized semi-infinite programming with convex lower-level problems. That is, all iterates of the numerical method are feasible points of the original optimization problem. The new method has the same computational cost as the original algorithm from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). We also discuss the merits of this approach for the adaptive convexification algorithm, a feasible point method for standard semi-infinite programming from Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007).     

On the Continuity of the Optimal Value in Parametric Linear Optimization: Stable Discretization of the Lagrangian Dual of Nonlinear Problems

This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in ⁿ. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05.     

A globally convergent method for semi-infinite linear programming

This paper presents a globally convergent method for solving a general semi-infinite linear programming problem. Some important features of this method include: It can solve a semi-infinite linear program having an unbounded feasible region. It requires an inexact solution to a nonlinear subproblem at each iteration. It allows unbounded index sets and nondifferentiable constraints. The amount of work at each iteration k does not increase with k.     

Robust linear semi-infinite programming duality under uncertainty

In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. We then establish that the closed-convex robust moment cone condition in the case of constraint-wise uncertainty is in fact necessary and sufficient for robust duality. In other words, the robust moment cone is closed and convex if and only if robust duality holds for every linear objective function of the program. In the case of uncertain problems with affinely parameterized data uncertainty, we establish that robust duality is easily satisfied under a Slater type constraint qualification. Consequently, we derive robust forms of the Farkas lemma for systems of uncertain semi-infinite linear inequalities.     

Semi-Infinite Programming Approach to Continuously-Constrained Linear-Quadratic Optimal Control Problems

Consider the class of linear-quadratic (LQ) optimal control problems with continuous linear state constraints, that is, constraints imposed on every instant of the time horizon. This class of problems is known to be difficult to solve numerically. In this paper, a computational method based on a semi-infinite programming approach is given. The LQ optimal control problem is formulated as a positive-quadratic infinite programming problem. This can be done by considering the control as the decision variable, while taking the state as a function of the control. After parametrizing the decision variable, an approximate quadratic semi-infinite programming problem is obtained. It is shown that, as we refine the parametrization, the solution sequence of the approximate problems converges to the solution of the infinite programming problem (hence, to the solution of the original optimal control problem). Numerically, the semi-infinite programming problems obtained above can be solved efficiently using an algorithm based on a dual parametrization method.     

Strong duality for inexact linear programming

In this paper, we apply the Dubovitskii-Milyutin approach to derive strong duality theorems for inexact linear programming problems. Inexact linear programming deals with the standard linear problem in which the data is not well known and it is supposed to lie in certain given convex sets. The case of parametric dependence of the data is particularly analyzed and relations with semi-infinite and

semi-definite programming are also commented.     

An exact penalty function algorithm for semi-infinite programmes

An algorithm for semi-inifinite programming using sequential quadratic programming techniques together with anL exact penalty function is presented, and global convergence is shown. An important feature of the convergence proof is that it does not require an implicit function theorem to be applicable to the semi-infinite constraints; a much weaker assumption concerning the finiteness of the number of global maximizers of each semi-infinite constraint is sufficient. In contrast to proofs based on an implicit function theorem, this result is also valid for a large class ofC ¹ problems.     

Study of a special nonlinear problem arising in convex semi-infinite programming

We consider convex problems of semi-infinite programming (SIP) using an approach based on the implicit optimality criterion. This criterion allows one to replace optimality conditions for a feasible solution x ⁰ of the convex SIP problem by such conditions for x ⁰ in some nonlinear programming (NLP) problem denoted by NLP(I(x ⁰)). This nonlinear problem, constructed on the base of special characteristics of the original SIP problem, so-called immobile indices and their immobility orders, has a special structure and a diversity of important properties. We study these properties and use them to obtain efficient explicit optimality conditions for the problem NLP(I(x ⁰)). Application of these conditions, together with the implicit optimality criterion, gives new efficient optimality conditions for convex SIP problems. Special attention is paid to SIP problems whose constraints do not satisfy the Slater condition and to problems with analytic constraint functions for which we obtain optimality conditions in the form of a criterion. Comparison with some known optimality conditions for convex SIP is provided.     

Extending the mixed algebraic-analysis Fourier–Motzkin elimination method for classifying linear semi-infinite programmes

Motivated by a recent Basu–Martin–Ryan paper, we obtain a reduced primal-dual pair of a linear semi-infinite programming problem by applying an amended Fourier–Motzkin elimination method to the linear semi-infinite inequality system. The reduced primal-dual pair is equivalent to the original one in terms of consistency, optimal values and asymptotic consistency. Working with this reduced pair and reformulating a linear semi-infinite programme as a linear programme over a convex cone, we reproduce all the theorems that lead to the full eleven possible duality state classification theory. Establishing classification results with the Fourier–Motzkin method means that the two classification theorems for linear semi-infinite programming, 1969 and 1974, have been proved by new and exciting methods. We also show in this paper that the approach to study linear semi-infinite programming using Fourier–Motzkin elimination is not purely algebraic, it is mixed algebraic-analysis.     

A primal—dual potential reduction method for problems involving matrix inequalities

We describe a potential reduction method for convex optimization problems involving matrix inequalities. The method is based on the theory developed by Nesterov and Nemirovsky and generalizes Gonzaga and Todd's method for linear programming. A worst-case analysis shows that the number of iterations grows as the square root of the problem size, but in practice it appears to grow more slowly. As in other interior-point methods the overall computational effort is therefore dominated by the least-squares system that must be solved in each iteration. A type of conjugate-gradient algorithm can be used for this purpose, which results in important savings for two reasons. First, it allows us to take advantage of the special structure the problems often have (e.g., Lyapunov or algebraic Riccati inequalities). Second, we show that the polynomial bound on the number of iterations remains valid even if the conjugate-gradient algorithm is not run until completion, which in practice can greatly reduce the computational effort per iteration.We describe in detail how the algorithm works for optimization problems withL Lyapunov inequalities, each of sizem. We prove an overallworst-case operation count of O(m ^5.5L^1.5). Theaverage-case complexity appears to be closer to O(m ⁴L^1.5). This estimate is justified by extensive numerical experimentation, and is consistent with other researchers' experience with the practical performance of interior-point algorithms for linear programming.This result means that the computational cost of extending current control theory based on the solution of Lyapunov or Riccatiequations to a theory that is based on the solution of (multiple, coupled) Lyapunov or Riccatiinequalities is modest.Supported by the Belgian National Fund for Scientific Research (NFWO). Research supported in part by the Belgian program on Interuniversity Attraction Poles (IUAP 17 and 50) initiated by the Belgian State, Prime Minister's Office, Science Policy Programming.Research supported in part by AFOSR (under F49620-92-J-0013), NSF (under ECS-9222391) and ARPA (under F49620-93-1-0085).     

Optimality criteria without constraint qualifications for linear semidefinite problems

We consider two closely related optimization problems: a problem of convex semi-infinite programming with multidimensional index set and a linear problem of semi-definite programming. In the study of these problems we apply the approach suggested in our recent paper [14] and based on the notions of immobile indices and their immobility orders. For the linear semi-definite problem, we define the subspace of immobile indices and formulate the first-order optimality conditions in terms of a basic matrix of this subspace. These conditions are explicit, do not use constraint qualifications, and have the form of a criterion. An algorithm determining a basis of the subspace of immobile indices in a finite number of steps is suggested. The optimality conditions obtained are compared with other known optimality conditions.     

Detecting “dense” columns in interior point methods for linear programs

During the iterations of interior point methods symmetric indefinite systems are decomposed by LD̂L ^T factorization. This step can be performed in a special way where the symmetric indefinite system is transformed to a positive definite one, called the normal equations system. This approach proved to be efficient in most of the cases and numerically reliable, due to the positive definite property. It has been recognized, however, that in case the linear program contains “dense” columns, this approach results in an undesirable fill–in during the computations and the direct factorization of the symmetric indefinite system is more advantageous. The paper describes a new approach to detect cases where the system of normal equations is not preferable for interior point methods and presents a new algorithm for detecting the set of columns which is responsible for the excessive fill–in in the matrix AA ^T . By solving large–scale linear programming problems we demonstrate that our heuristic is reliable in practice. This work was supported in part by the Hungarian Scientific Research Fund OTKA K60480.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

Partially finite convex programming,Part II: Explicit lattice models

In Part I of this work we derived a duality theorem for partially finite convex programs, problems for which the standard Slater condition fails almost invariably. Our result depended on a constraint qualification involving the notion ofquasi relative interior. The derivation of the primal solution from a dual solution depended on the differentiability of the dual objective function: the differentiability of various convex functions in lattices was considered at the end of Part I. In Part II we shall apply our results to a number of more concrete problems, including variants of semi-infinite linear programming,L ¹ approximation, constrained approximation and interpolation, spectral estimation, semi-infinite transportation problems and the generalized market area problem of Lowe and Hurter (1976). As in Part I, we shall use lattice notation extensively, but, as we illustrated there, in concrete examples lattice-theoretic ideas can be avoided, if preferred, by direct calculation.     

Stability of the primal-dual partition in linear semi-infinite programming

We analyse the primal-dual states in linear semi-infinite programming (LSIP), where we consider the primal problem and the so called Haar's dual problem. Any linear programming problem and its dual can be classified as bounded, unbounded or inconsistent, giving rise to nine possible primal-dual states, which are reduced to six by the weak duality property. Recently, Goberna and Todorov have studied this partition and its stability in continuous LSIP in a series of papers [M.A. Goberna and M.I. Todorov, Primal, dual and primal-dual partitions in continuous linear semi-infinite programming, Optimization 56 (2007), pp. 617–628; M.A. Goberna and M.I. Todorov, Generic primal-dual solvability in continuous linear semi-infinite programming, Optimization 57 (2008), pp. 239–248]. In this article we consider the general case, with no continuity assumptions, discussing the maintenance of the primal-dual state of the problem by allowing small perturbations of the data. We characterize the stability of all of the six possible primal-dual states through necessary and sufficient conditions which depend on the data, and can be easily checked, showing some differences with the continuous case. These conditions involve the strong Slater constraint qualification, and some distinguished convex sets associated to the data.     

An Approximation Approach to Non-strictly Convex Quadratic Semi-infinite Programming

We present in this paper a numerical method for solving non-strictly-convex quadratic semi-infinite programming including linear semi-infinite programming. The proposed method transforms the problem into a series of strictly convex quadratic semi-infinite programming problems. Several convergence results and a numerical experiment are given.     

An Approximation Approach to Non-strictly Convex Quadratic Semi-infinite Programming

We present in this paper a numerical method for solving non-strictly-convex quadratic semi-infinite programming including linear semi-infinite programming. The proposed method transforms the problem into a series of strictly convex quadratic semi-infinite programming problems. Several convergence results and a numerical experiment are given.     

Understanding linear semi-infinite programming via linear programming over cones

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.     

Efficient dynamic programming implementations of Newton's method for unconstrained optimal control problems

Naive implementations of Newton's method for unconstrainedN-stage discrete-time optimal control problems with Bolza objective functions tend to increase in cost likeN ³ asN increases. However, if the inherent recursive structure of the Bolza problem is properly exploited, the cost of computing a Newton step will increase only linearly withN. The efficient Newton implementation scheme proposed here is similar to Mayne's DDP (differential dynamic programming) method but produces the Newton step exactly, even when the dynamical equations are nonlinear. The proposed scheme is also related to a Riccati treatment of the linear, two-point boundary-value problems that characterize optimal solutions. For discrete-time problems, the dynamic programming approach and the Riccati substitution differ in an interesting way; however, these differences essentially vanish in the continuous-time limit.This work was supported by the National Science Foundation, Grant No. DMS-85-03746.