Geometry of optimality conditions and constraint qualifications: The convex case

The cones of directions of constancy are used to derive: new as well as known optimality conditions; weakest constraint qualifications; and regularization techniques, for the convex programming problem. In addition, the badly behaved set of constraints, i.e. the set of constraints which causes problems in the Kuhn—Tucker theory, is isolated and a computational procedure for checking whether a feasible point is regular or not is presented.This research was supported by the National Research Council of Canada and le Gouvernement du Quebec and is part of the author's Ph.D. Dissertation done at McGill University, Montreal, Que., under the guidance of Professor S. Zlobec.     

A nonconvex separation property in Banach spaces

We establish, in infinite dimensional Banach space, a nonconvex separation property for general closed sets that is an extension of Hahn-Banach separation theorem. We provide some consequences in optimization, in particular the existence of singular multipliers and show the relation of our property with the extremal principle of Mordukhovich. Received October 1997/Revised version February 1998     

Outer Γ-Convexity in Vector Spaces

A subset S of some vector space X is said to be outer Γ-convex w.r.t. some given balanced subset Γ ? X if for all x ₀, x ₁ ? S there exists a closed subset Λ ? [0,1] such that {x _λ | λ ? Λ} ? S and [x ₀, x ₁] ? {x _λ | λ ? Λ} + 0.5 Γ, where x _λ: = (1 ? λ)x ₀ + λ x ₁. A real-valued function f:D → ? defined on some convex D ? X is called outer Γ-convex if for all x ₀, x ₁ ? D there exists a closed subset Λ ? [0,1] such that [x ₀, x ₁] ? {x _λ | λ ? Λ} + 0.5 Γ and f(x _λ) ≤ (1 ? λ)f(x ₀) + λ f(x ₁) holds for all λ ? Λ. Outer Γ-convex functions possess some similar optimization properties as these of convex functions, e.g., lower level sets of outer Γ-convex functions are outer Γ-convex and Γ-local minimizers are global minimizers. Some properties of outer Γ-convex sets and functions are presented, among others a simplex property of outer Γ-convex sets, which is applied for establishing a separation theorem and for proving the existence of modified subgradients of outer Γ-convex functions.     

OPTIMALITY CONDITIONS AND DUALITY MODELS FOR A CLASS OF NONSMOOTH CONTINUOUS-TIME GENERALIZED FRACTIONAL PROGRAMMING PROBLEMS

Abstract

Both parametric and parameter-free stationary-point-type and saddle-point-type necessary and sufficient optimality conditions are established for a class of nonsmooth continuous-time generalized fractional programming problems with Volterra-type integral inequality and nonnegativity constraints. These optimality criteria are then utilized for constructing ten parametric and parameter-free Wolfe-type and Lagrangian-type dual problems and for proving weak, strong, and strict converse duality theorems. Furthermore, it is briefly pointed out how similar optimality and duality results can be obtained for two important special cases of the main problem containing arbitrary norms and square roots of positive semidefinite quadratic forms. All the results developed here are also applicable to continuous-time programming problems with fractional, discrete max, and conventional objective functions, which are special cases of the main problem studied in this paper.     

A non-smooth model for signalized road network design problems

A signalized road network is considered where the set of link capacity expansions and signal setting variables are simultaneously determined. This paper addresses a new optimization scheme for a signalized road network design problem (SRNDP). A SRNDP can be formulated as a mathematical program with equilibrium constraints (MPEC) where user equilibrium is expressed as a variational inequality problem. Due to non-differentiability of the perturbed solutions in equilibrium constraints, a non-smooth model is established. A bundle subgradient projection (BSP) method is presented with global convergence. Numerical calculations are conducted on a real data city road network and large-scale grid networks where promising results are obtained.     

A subgradient algorithm for certain minimax and minisum problems

We present a subgradient algorithm for minimizing the maximum of a finite collection of functions. It is assumed that each function is the sum of a finite collection of basic convex functions and that the number of different subgradient sets associated with nondifferentiable points of each basic function is finite on any bounded set. Problems belonging to this class include the linear approximation problem and both the minimax and minisum problems of location theory. Convergence of the algorithm to an epsilon-optimal solution is proven and its effectiveness is demonstrated by solving a number of location problems and linear approximation problems.This research was partially supported by the Army Research Office, Triangle Park, NC, under contract number DAH-CO4-75-G-0150, and by NSF grants ENG 16-24294 and ENG 75-10225.     

Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions

We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart of the Karush-Kuhn-Tucker condition for convex programs. This work is supported by the Alexander von Humboldt fellowship (1982/83), West Germany.     

Model spaces for risk measures

We show how risk measures originally defined in a model free framework in terms of acceptance sets and reference assets imply a meaningful underlying probability structure. Hereafter we construct a maximal domain of definition of the risk measure respecting the underlying ambiguity profile. We particularly emphasise liquidity effects and discuss the correspondence between properties of the risk measure and the structure of this domain as well as subdifferentiability properties.     

Conjugate Maps,Subgradients and Conjugate Duality in Set-Valued Optimization

Using the concept of supremum/infimum of a set, defined in terms of the closure of the set, we introduce the notions of conjugate and biconjugate maps as well as that of subgradients of a set-valued map. Conjugate duality results are also established for a set-valued optimization problem.     

Pshenichnyi's theorem for vector minimization

Analogues of Pshenichnyi's necessary and sufficient condition for minima in convex programming problems are given for the case where the objective function is vector-valued.