Semi-infinite programming

A semi-infinite programming problem is an optimization problem in which finitely many variables appear in infinitely many constraints. This model naturally arises in an abundant number of applications in different fields of mathematics, economics and engineering. The paper, which intends to make a compromise between an introduction and a survey, treats the theoretical basis, numerical methods, applications and historical background of the field.     

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.     

Second order optimality conditions for generalized semi-infinite programming problems

We consider generalized semi-infinite programming problems. Second order necessary and sufficient conditionsfor local optimality are given. The conditions are derived under assumptions such that the feasible set can be described by means of a finite number of optimal value functions. Since we do not require a strict complementary condition for the local reduction these functions are only of class C¹ A sufficient condition for optimality is proven under much weaker assumptions.     

Solving air traffic conflict problems via local continuous optimization

This paper first introduces an original trajectory model using B-splines and a new semi-infinite programming formulation of the separation constraint involved in air traffic conflict problems. A new continuous optimization formulation of the tactical conflict-resolution problem is then proposed. It involves very few optimization variables in that one needs only one optimization variable to determine each aircraft trajectory. Encouraging numerical experiments show that this approach is viable on realistic test problems. Not only does one not need to rely on the traditional, discretized, combinatorial optimization approaches to this problem, but, moreover, local continuous optimization methods, which require relatively fewer iterations and thereby fewer costly function evaluations, are shown to improve the performance of the overall global optimization of this non-convex problem.     

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.     

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.     

An interior-point method for semi-infinite programming problems

This work examines the generalization of a certain interior-point method, namely the method of analytic centers, to semi-infinite linear programming problems. We define an analytic center for these problems and an appropriate norm to examine Newton's method for computing this center. A simple algorithm of order zero is constructed and a convergence proof for that algorithm is given. Finally, we describe a more practical implementation of a predictor-corrector method and give some numerical results. In particular we concentrate on practical integration rules that take care of the specific structure of the integrals.     

New results on the equivalence between zero-one programming and continuous concave programming

In this work, we study continuous reformulations of zero-one concave programming problems. We introduce new concave penalty functions and we prove, using general equivalence results here derived, that the obtained continuous problems are equivalent to the original combinatorial problem.     

Sufficient conditions for total ill-posedness in linear semi-infinite optimization

This paper deals with the so-called total ill-posedness of linear optimization problems with an arbitrary (possibly infinite) number of constraints. We say that the nominal problem is totally ill-posed if it exhibits the highest unstability in the sense that arbitrarily small perturbations of the problem’s coefficients may provide both, consistent (with feasible solutions) and inconsistent problems, as well as bounded (with finite optimal value) and unbounded problems, and also solvable (with optimal solutions) and unsolvable problems. In this paper we provide sufficient conditions for the total ill-posedness property exclusively in terms of the coefficients of the nominal problem.     

A homotopy interior point method for semi-infinite programming problems

This paper presents a homotopy interior point method for solving a semi-infinite programming (SIP) problem. For algorithmic purpose, based on bilevel strategy, first we illustrate appropriate necessary conditions for a solution in the framework of standard nonlinear programming (NLP), which can be solved by homotopy method. Under suitable assumptions, we can prove that the method determines a smooth interior path from a given interior point to a point w ^*, at which the necessary conditions are satisfied. Numerical tracing this path gives a globally convergent algorithm for the SIP. Lastly, several preliminary computational results illustrating the method are given.     

A nonsmooth Levenberg–Marquardt method for solving semi-infinite programming problems

In this paper, we first transform the semi-infinite programming problem into the KKT system by the techniques in [D.H. Li, L. Qi, J. Tam, S.Y. Wu, A smoothing Newton method for semi-infinite programming, J. Global. Optim. 30 (2004) 169–194; L. Qi, S.Y. Wu, G.L. Zhou, Semismooth Newton methods for solving semi-infinite programming problems, J. Global. Optim. 27 (2003) 215–232]. Then a nonsmooth and inexact Levenberg–Marquardt method is proposed for solving this KKT system based on [H. Dan, N. Yamashita, M. Fukushima, Convergence properties of the inexact Levenberg–Marquardt method under local error bound conditions, Optimim. Methods Softw., 11 (2002) 605–626]. This method is globally and superlinearly (even quadratically) convergent. Finally, some numerical results are given.     

Some NP-complete problems in linear programming

Degeneracy checking in linear programming is NP-complete. So is the problem of checking whether there exists a basic feasible solution with a specified objective value.     

Sensitivity method for basis inverse representation in multistage stochastic linear programming problems

A version of the simplex method for solving stochastic linear control problems is presented. The method uses a compact basis inverse representation that extensively exploits the original problem data and takes advantage of the supersparse structure of the problem. Computational experience indicates that the method is capable of solving large problems.This research was supported by Programs CPBP02.15 and RPI.02.     

Disjunctive cuts for continuous linear bilevel programming

This work shows how disjunctive cuts can be generated for a bilevel linear programming problem (BLP) with continuous variables. First, a brief summary on disjunctive programming and bilevel programming is presented. Then duality theory is used to reformulate BLP as a disjunctive program and, from there, disjunctive programming results are applied to derive valid cuts. These cuts tighten the domain of the linear relaxation of BLP. An example is given to illustrate this idea, and a discussion follows on how these cuts may be incorporated in an algorithm for solving BLP.     

Some nondifferentiable multiobjective programming problems

In this paper it is shown that a relaxation defining the class of generalized d-V-type-I functions leads to a new class of multi-objective problems which preserves the sufficient optimality and duality results in the scalar non-differentiable case, and avoids the major difficulty of verifying that the inequality holds for the same kernel function. The results obtained in this paper generalize and extend the previously known results in this area.     

Directional derivatives for the value-function in semi-infinite programming

For the problemP(λ): Maximizec ^T z subject toz∈Z(λ), whereZ(λ) is defined by an in general infinite set of linear inequalities, it is shown that the value-function has directional derivatives at every point such thatP( ) and its dual are both superconsistent. To compute these directional derivatives a min-max-formula, well-known in convex programming, is derived. In addition, it is shown that derivatives can be obtained more easily by a limit-process using only convergent selections of solutions ofP(λ _n ), λ _n → and their duals.     

Some programming problems for teaching foundations of group theory

This paper contains some programming problems which can be suggested for students starting to learn group theory. These problems are related to important notations such as subgroup, coset, normal divisor, symmetric group, normalizer, centralizer, homomorphism and automorphism. Carefully selected problems provide a successful understanding of the basic themes of finite group theory.     

An iterative approach to solve multiobjective linear fractional programming problems

This paper suggests an iterative parametric approach for solving multiobjective linear fractional programming (MOLFP) problems which only uses linear programming to obtain efficient solutions and always converges to an efficient solution. A numerical example shows that this approach performs better than some existing algorithms. Randomly generated MOLFP problems are also solved to demonstrate the performance of new introduced algorithm.     

Homotopy perturbation method for linear programming problems

In this paper, He’s homotopy perturbation method (HPM) is applied for solving linear programming (LP) problems. This paper shows that some recent findings about this topic cannot be applied for all cases. Furthermore, we provide the correct application of HPM for LP problems. The proposed method has a simple and graceful structure. Finally, a numerical example is displayed to illustrate the proposed method.     

A norm-relaxed method of feasible directions for finely discretized problems from semi-infinite programming

In this paper, a class of finely discretized Semi-Infinite Programming (SIP) problems is discussed. Combining the idea of the norm-relaxed Method of Feasible Directions (MFD) and the technique of updating discretization index set, we present a new algorithm for solving the Discretized Semi-Infinite (DSI) problems from SIP. At each iteration, the iteration point is feasible for the discretized problem and an improved search direction is computed by solving only one direction finding subproblem, i.e., a quadratic program, and some appropriate constraints are chosen to reduce the computational cost. A high-order correction direction can be obtained by solving another quadratic programming subproblem with only equality constraints. Under weak conditions such as Mangasarian–Fromovitz Constraint Qualification (MFCQ), the proposed algorithm possesses weak global convergence. Moreover, the superlinear convergence is obtained under Linearly Independent Constraint Qualification (LICQ) and other assumptions. In the end, some elementary numerical experiments are reported.