Comments on: Farkas’ Lemma: three decades of generalizations for mathematical optimization

In these comments on the excellent survey by Dinh and Jeyakumar, we briefly discuss some recently developed topics and results on applications of extended Farkas’ lemma(s) and related qualification conditions to problems of variational analysis and optimization, which are not fully reflected in the survey. They mainly concern: Lipschitzian stability of feasible solution maps for parameterized semi-infinite and infinite programs with linear and convex inequality constraints indexed by arbitrary sets; optimality conditions for nonsmooth problems involving such constraints; evaluating various subdifferentials of optimal value functions in DC and bilevel infinite programs with applications to Lipschitz continuity of value functions and optimality conditions; calculating and estimating normal cones to feasible solution sets for nonlinear smooth as well as nonsmooth semi-infinite, infinite, and conic programs with deriving necessary optimality conditions for them; calculating coderivatives of normal cone mappings for convex polyhedra in finite and infinite dimensions with applications to robust stability of parameterized variational inequalities. We also give some historical comments on the original Farkas’ papers.     

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.     

Locally Farkas-Minkowski linear inequality systems

This paper introduces thelocally Farkas-Minkowski (LFM) linear inequality systems in a finite dimensional Euclidean space. These systems are those ones that satisfy that any consequence of the system that is active at some solution point is also a consequence of some finite subsystem. This class includes the Farkas-Minkowski systems and verifies most of the properties that these systems possess. Moreover, it contains the locally polyhedral systems, which are the natural external representation of quasi-polyhedral sets. TheLFM systems appear to be the natural external representation of closed convex sets. A characterization based on their properties under the union of systems is provided. In linear semi-infinite programming, theLFM property is the more general constraint qualification such that the Karush-Kuhn-Tucker condition characterizes the optimal points. Furthermore, the pair of Haar dual problems has no duality gap.     

Nash-type equilibria on Riemannian manifolds: A variational approach

Motivated by Nash equilibrium problems on ‘curved’ strategy sets, the concept of Nash–Stampacchia equilibrium points is introduced via variational inequalities on Riemannian manifolds. Characterizations, existence, and stability of Nash–Stampacchia equilibria are studied when the strategy sets are compact/noncompact geodesic convex subsets of Hadamard manifolds, exploiting two well-known geometrical features of these spaces both involving the metric projection map. These properties actually characterize the non-positivity of the sectional curvature of complete and simply connected Riemannian spaces, delimiting the Hadamard manifolds as the optimal geometrical framework of Nash–Stampacchia equilibrium problems. Our analytical approach exploits various elements from set-valued and variational analysis, dynamical systems, and non-smooth calculus on Riemannian manifolds. Examples are presented on the Poincaré upper-plane model and on the open convex cone of symmetric positive definite matrices endowed with the trace-type Killing form.     

Multiobjective DC programs with infinite convex constraints

New results are established for multiobjective DC programs with infinite convex constraints (MOPIC) that are defined on Banach spaces (finite or infinite dimensional) with objectives given as the difference of convex functions. This class of problems can also be called multiobjective DC semi-infinite and infinite programs, where decision variables run over finite-dimensional and infinite-dimensional spaces, respectively. Such problems have not been studied as yet. Necessary and sufficient optimality conditions for the weak Pareto efficiency are introduced. Further, we seek a connection between multiobjective linear infinite programs and MOPIC. Both Wolfe and Mond-Weir dual problems are presented, and corresponding weak, strong, and strict converse duality theorems are derived for these two problems respectively. We also extend above results to multiobjective fractional DC programs with infinite convex constraints. The results obtained are new in both semi-infinite and infinite frameworks.     

Numerical treatment of an asset price model with non-stochastic uncertainty

In contrast to stochastic differential equation models used for the calculation of the term structure of interest rates, we develop an approach based on linear dynamical systems under non-stochastic uncertainty with perturbations. The uncertainty is described in terms of known feasible sets of varying parameters. Observations are used in order to estimate these parameters by minimizing the maximum of the absolute value of measurement errors, which leads to a linear or nonlinear semi-infinite programming problem. A regularized logarithmic barrier method for solving (ill-posed) convex semi-infinite programming problems is suggested. In this method a multi-step proximal regularization is coupled with an adaptive discretization strategy in the framework of an interior point approach. A special deleting rule permits one to use only a part of the constraints of the discretized problems. Convergence of the method and its stability with respect to data perturbations in the cone of convexC ¹-functions are studied. On the basis of the solutions of the semi-infinite programming problems a technical trading system for future contracts of the German DAX is suggested and developed. Supported by the Stiftung Rheinland/Pfalz für Innovation, No. 8312-386261/307.     

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.     

γ-Active Constraints in Convex Semi-Infinite Programming

In this article, we extend the definition of γ-active constraints for linear semi-infinite programming to a definition applicable to convex semi-infinite programming, by two approaches. The first approach entails the use of the subdifferentials of the convex constraints at a point, while the second approach is based on the linearization of the convex inequality system by means of the convex conjugates of the defining functions. By both these methods, we manage to extend the results on γ-active constraints from the linear case to the convex case.     

Locally polyhedral linear inequality systems

Linear systems of an arbitrary number of inequalities provide external representations for the closed convex sets in the Euclidean space. In particular, the locally polyhedral systems introduced in this paper are the natural linear representation for quasipolyhedral sets (those subsets of the Euclidean space whose nonempty intersections with polytopes are polytopes). For these systems the geometrical properties of the solution set are investigated, and their extreme points and edges are characterized. The class of locally polyhedral systems includes the quasipolyhedral systems, introduced by Marchi, Puente, and Vera de Serio in order to generalize the Weyl property of finite linear inequality systems.     

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.     

Constructible Convex Sets

We investigate when closed convex sets can be written as countable intersections of closed half-spaces in Banach spaces. It is reasonable to consider this class to comprise the constructible convex sets since such sets are precisely those that can be defined by a countable number of linear inequalities, hence are accessible to techniques of semi-infinite convex programming. We also explore some model theoretic implications. Applications to set convergence are given as limiting examples.     

An outcome space approach for generalized convex multiplicative programs

This paper addresses the problem of minimizing an arbitrary finite sum of products of two convex functions over a convex set. Nonconvex problems in this form constitute a class of generalized convex multiplicative problems. Convex analysis results allow to reformulate the problem as an indefinite quadratic problem with infinitely many linear constraints. Special properties of the quadratic problem combined with an adequate outer approximation procedure for handling its semi-infinite constrained set enable an efficient constraint enumeration global optimization algorithm for generalized convex multiplicative programs. Computational experiences illustrate the proposed approach.     

Condition numbers and error bounds in convex programming

After a brief survey on condition numbers for linear systems of equalities, we analyse error bounds for convex functions and convex sets. The canonical representation of a convex set is defined. Other representations of a convex set by a convex function are compared with the canonical representation. Then, condition numbers are introduced for convex sets and their convex representations.     

Depth-Optimized Convexity Cuts

This paper presents a general, self-contained treatment of convexity or intersection cuts. It describes two equivalent ways of generating a cut—via a convex set or a concave function—and a partial-order notion of cut strength. We then characterize the structure of the sets and functions that generate cuts that are strongest with respect to the partial order. Next, we specialize this analytical framework to the case of mixed-integer linear programming (MIP). For this case, we formulate two kinds of the deepest cut generation problem, via sets or via functions, and subsequently consider some special cases which are amenable to efficient computation. We conclude with computational tests of one of these procedures on a large set of MIPLIB problems.     

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.     

A Branch-and-Bound Approach for Solving a Class of Generalized Semi-infinite Programming Problems

A nonconvex generalized semi-infinite programming problem is considered, involving parametric max-functions in both the objective and the constraints. For a fixed vector of parameters, the values of these parametric max-functions are given as optimal values of convex quadratic programming problems. Assuming that for each parameter the parametric quadratic problems satisfy the strong duality relation, conditions are described ensuring the uniform boundedness of the optimal sets of the dual problems w.r.t. the parameter. Finally a branch-and-bound approach is suggested transforming the problem of finding an approximate global minimum of the original nonconvex optimization problem into the solution of a finite number of convex problems.     

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.     

Reachability analysis of linear systems using support functions

This work is concerned with the algorithmic reachability analysis of continuous-time linear systems with constrained initial states and inputs. We propose an approach for computing an over-approximation of the set of states reachable on a bounded time interval. The main contribution over previous works is that it allows us to consider systems whose sets of initial states and inputs are given by arbitrary compact convex sets represented by their support functions. We actually compute two over-approximations of the reachable set. The first one is given by the union of convex sets with computable support functions. As the representation of convex sets by their support function is not suitable for some tasks, we derive from this first over-approximation a second one given by the union of polyhedrons. The overall computational complexity of our approach is comparable to the complexity of the most competitive available specialized algorithms for reachability analysis of linear systems using zonotopes or ellipsoids. The effectiveness of our approach is demonstrated on several examples.     

Voronoi cells via linear inequality systems

The theory and methods of linear algebra are a useful alternative to those of convex geometry in the framework of Voronoi cells and diagrams, which constitute basic tools of computational geometry. As shown by Voigt and Weis in 2010, the Voronoi cells of a given set of sites T, which provide a tesselation of the space called Voronoi diagram when T is finite, are solution sets of linear inequality systems indexed by T. This paper exploits systematically this fact in order to obtain geometrical information on Voronoi cells from sets associated with T (convex and conical hulls, tangent cones and the characteristic cones of their linear representations). The particular cases of T being a curve, a closed convex set and a discrete set are analyzed in detail. We also include conclusions on Voronoi diagrams of arbitrary sets.