On the sufficiency of finite support duals in semi-infinite linear programming

We consider semi-infinite linear programs with countably many constraints indexed by the natural numbers. When the constraint space is the vector space of all real valued sequences, we show that the finite support (Haar) dual is equivalent to the algebraic Lagrangian dual of the linear program. This settles a question left open by Anderson and Nash (1987). This result implies that if there is a duality gap between the primal linear program and its finite support dual, then this duality gap cannot be closed by considering the larger space of dual variables that define the algebraic Lagrangian dual. However, if the constraint space corresponds to certain subspaces of all real-valued sequences, there may be a strictly positive duality gap with the finite support dual, but a zero duality gap with the algebraic Lagrangian dual.     

Primal-dual stability in continuous linear optimization

Any linear (ordinary or semi-infinite) optimization problem, and also its dual problem, can be classified as either inconsistent or bounded or unbounded, giving rise to nine duality states, three of them being precluded by the weak duality theorem. The remaining six duality states are possible in linear semi-infinite programming whereas two of them are precluded in linear programming as a consequence of the existence theorem and the non-homogeneous Farkas Lemma. This paper characterizes the linear programs and the continuous linear semi-infinite programs whose duality state is preserved by sufficiently small perturbations of all the data. Moreover, it shows that almost all linear programs satisfy this stability property.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

On the Lebesgue property of monotone convex functions

The Lebesgue property (order-continuity) of a monotone convex function on a solid vector space of measurable functions is characterized in terms of (1) the weak inf-compactness of the conjugate function on the order-continuous dual space, (2) the attainment of the supremum in the dual representation by order-continuous linear functionals. This generalizes and unifies several recent results obtained in the context of convex risk measures.     

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.     

Separation of convex sets by extreme hyperplanes

The problem of separation of convex sets by extreme hyperplanes (functionals) in normed linear spaces is examined. The concept of a bar (a closed set of special form) is introduced; it is shown that a bar is characterized by the property that any point not lying in it can be separated from it by an extreme hyperplane. In two-dimensional spaces, in spaces with strictly convex dual, and in the space of continuous functions, any two bars are extremely separated. This property is shown to fail in the space of summable functions. A number of examples and generalizations are given.     

Duality gap in convex programming

In this paper, we consider general convex programming problems and give a sufficient condition for the equality of the infimum of the original problem and the supremum of its ordinary dual. This condition may be seen as a continuity assumption on the constraint sets (i.e. on the sublevel sets of the constraint function) under linear perturbation. It allows us to generalize as well as treat previous results in a unified framework. Our main result is in fact based on a quite general constraint qualification result for quasiconvex programs involving a convex objective function proven in the setting of a real normed vector space.Mathematics Subject Classification (2000):90C25, 90C26, 90C30, 90C31     

Maximal Monotone Multifunctions of Brøndsted–Rockafellar Type

We consider whether the “inequality-splitting” property established in the Brøndsted–Rockafellar theorem for the subdifferential of a proper convex lower semicontinuous function on a Banach space has an analog for arbitrary maximal monotone multifunctions. We introduce the maximal monotone multifunctions of type (ED), for which an “inequality-splitting” property does hold. These multifunctions form a subclass of Gossez"s maximal monotone multifunctions of type (D); however, in every case where it has been proved that a multifunction is maximal monotone of type (D) then it is also of type (ED). Specifically, the following maximal monotone multifunctions are of type (ED): ? ultramaximal monotone multifunctions, which occur in the study of certain nonlinear elliptic functional equations; ? single-valued linear operators that are maximal monotone of type (D); ? subdifferentials of proper convex lower semicontinuous functions; ? “subdifferentials” of certain saddle-functions. We discuss the negative alignment set of a maximal monotone multifunction of type (ED) with respect to a point not in its graph – a mysterious continuous curve without end-points lying in the interior of the first quadrant of the plane. We deduce new inequality-splitting properties of subdifferentials, almost giving a substantial generalization of the original Brøndsted–Rockafellar theorem. We develop some mathematical infrastructure, some specific to multifunctions, some with possible applications to other areas of nonlinear analysis: ? the formula for the biconjugate of the pointwise maximum of a finite set of convex functions – in a situation where the “obvious” formula for the conjugate fails; ? a new topology on the bidual of a Banach space – in some respects, quite well behaved, but in other respects, quite pathological; ? an existence theorem for bounded linear functionals – unusual in that it does not assume the existence of any a priori bound; ? the 'big convexification" of a multifunction.

     

The almost chebyshev property in linear semi-infinite programming

We consider a linear semi-infinite programming problem where the index set of the constraints is compact and the constraint functions are continuous on it. The set of all continuous functions on this index set as right hand sides are the parameter set. We investigate how large various unicity sets are.We state a condition on the objective function vector and the “matrix” of the problem which characterizes when the set of a parameters with a non-unique optimal point is a set of the first Baire category in the solvability set. This is the case if and only if the unicity set is a dense subset of the solvability set. Under the same assumptions it is even true that the interior of the strong unicity set is I also dense. If the index set of the constraints contains a dense subset with the property that each point1 is a G ₈-set, then the parameters of the strong unicity set, such that the optimal point satisfies the linear independence constraint qualification, are also dense.

We apply our results to a characterization of a unique continuous selection for the optimal set I mapping and to a one-sided L ₁-approximation problem     

Normal convergence using Malliavin calculus with applications and examples

We prove the chain rule in the more general framework of the Wiener–Poisson space, allowing us to obtain the so-called Nourdin–Peccati bound. From this bound, we obtain a second-order Poincaré-type inequality that is useful in terms of computations. For completeness we survey these results on the Wiener space, the Poisson space, and the Wiener–Poisson space. We also give several applications to central limit theorems with relevant examples: linear functionals of Gaussian subordinated fields (where the subordinated field can be processes like fractional Brownian motion or the solution of the Ornstein–Uhlenbeck SDE driven by fractional Brownian motion), Poisson functionals in the first Poisson chaos restricted to infinitely many “small” jumps (particularly fractional Lévy processes), and the product of two Ornstein–Uhlenbeck processes (one in the Wiener space and the other in the Poisson space). We also obtain bounds for their rate of convergence to normality.     

Post-optimality sensitivity analysis in abstract spaces with applications to continuous-time programming problems

The programming problem under consideration consists in maximizing a concave objective functional, subject to convex operator inequality contraints. The assumptions include the existence of an optimum solution, Fréchet differentiability of all operators involved, and the existence of the topological complement of the null space of the Fréchet derivative of the constraint operator. It is shown that the rate of change of the optimum value of the objective functional due to the perturbation is measured by the dual. The optimum values of the primal variables are locally approximated as linear functions of the perturbation; the theory of generalized inverse operators is used in the approximation. We give an approximation to the primal variables if the problem is perturbed. The results are specialized for some continuous-time and finite-dimensional cases. Two examples for finite-dimensional problems are given. We apply the theory to the continuous-time linear programming problem and prove some continuity results for the optimal primal and dual objective functionals.The authors are indebted to the Natural Sciences and Engineering Research Council of Canada for financial support through Grants A4109 and A7329, respectively. They would also like to thank the referee for his comments.     

A Diophantine duality applied to the KAM and Nekhoroshev theorems

In this paper, we use geometry of numbers to relate two dual Diophantine problems. This allows us to focus on simultaneous approximations rather than small linear forms. As a consequence, we develop a new approach to the perturbation theory for quasi-periodic solutions dealing only with periodic approximations and avoiding classical small divisors estimates. We obtain two results of stability, in the spirit of the KAM and Nekhoroshev theorems, in the model case of a perturbation of a constant vector field on the $n$ -dimensional torus. Our first result, which is a Nekhoroshev type theorem, is the construction of a “partial” normal form, that is a normal form with a small remainder whose size depends on the Diophantine properties of the vector. Then, assuming our vector satisfies the Bruno–Rüssmann condition, we construct an “inverted” normal form, recovering the classical KAM theorem of Kolmogorov, Arnold and Moser for constant vector fields on torus.     

Frames for vector spaces and affine spaces

A finite frame for a finite dimensional Hilbert space is simply a spanning sequence. We show that the linear functionals given by the dual frame vectors do not depend on the inner product, and thus it is possible to extend the frame expansion (and other elements of frame theory) to any finite spanning sequence for a vector space. The corresponding coordinate functionals generalise the dual basis (the case when the vectors are linearly independent), and are characterised by the fact that the associated Gramian matrix is an orthogonal projection. Existing generalisations of the frame expansion to Banach spaces involve an analogue of the frame bounds and frame operator.The potential applications of our results are considerable. Whenever there is a natural spanning set for a vector space, computations can be done directly with it, in an efficient and stable way. We illustrate this with a diverse range of examples, including multivariate spline spaces, generalised barycentric coordinates, and vector spaces over the rationals, such as the cyclotomic fields.     

Strong Duality and Dual Pricing Properties in Semi-Infinite Linear Programming: A non-Fourier–Motzkin Elimination Approach

Following the idea of the conjecture for semi-infinite programming in a paper by Kortanek and Zhang, recently published in Optimization, in this paper we show that the Fourier–Motzkin elimination is not needed in the study of the strong duality and dual pricing properties for semi-infinite programming. We also prove several new results on the strong duality and dual pricing properties. Specifically, we propose a new subspace, under which the strong duality property holds. We give a necessary and sufficient condition for the dual pricing property to hold under this subspace, which is further used to examine the examples presented in the Basu–Martin–Ryan paper.     

Tractability of Tensor Product Linear Operators

This paper deals with the worst case setting for approximating multivariate tensor product linear operators defined over Hilbert spaces. Approximations are obtained by using a number of linear functionals from a given class of information. We consider the three classes of information: the class of all linear functionals, the Fourier class of inner products with respect to given orthonormal elements, and the standard class of function values. We wish to determine which problems are tractable and which are strongly tractable. The complete analysis is provided for approximating operators of rank two or more. The problem of approximating linear functionals is fully analyzed in the first two classes of information. For the third class of standard information we show that the possibilities are very rich. We prove that tractability of linear functionals depends on the given space of functions. For some spaces all nontrivial normed linear functionals are intractable, whereas for other spaces all linear functionals are tractable. In “typical” function spaces, some linear functionals are tractable and some others are not.     

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.     

Partially finite convex programming,Part I: Quasi relative interiors and duality theory

We study convex programs that involve the minimization of a convex function over a convex subset of a topological vector space, subject to a finite number of linear inequalities. We develop the notion of the quasi relative interior of a convex set, an extension of the relative interior in finite dimensions. We use this idea in a constraint qualification for a fundamental Fenchel duality result, and then deduce duality results for these problems despite the almost invariable failure of the standard Slater condition. Part II of this work studies applications to more concrete models, whose dual problems are often finite-dimensional and computationally tractable.     

Dual Clifford modules

A relationship between the space dual to the realification of a module over a Clifford algebra and the realification of the dual of this module is established. This relationship is completely analogous to a similar classical relationship between the space dual to the realification of a complex vector space and the realification of the dual of the given space. On the basis of this relationship, questions concerning extension of linear functionals on Clifford modules, in particular, a counterpart of the Hahn–Banach theorem, are considered.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

Analytical Linear Inequality Systems and Optimization

In many interesting semi-infinite programming problems, all the constraints are linear inequalities whose coefficients are analytical functions of a one-dimensional parameter. This paper shows that significant geometrical information on the feasible set of these problems can be obtained directly from the given coefficient functions. One of these geometrical properties gives rise to a general purification scheme for linear semi-infinite programs equipped with so-called analytical constraint systems. It is also shown that the solution sets of such kind of consistent systems form a transition class between polyhedral convex sets and closed convex sets in the Euclidean space of the unknowns.