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.     

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.     

Constraint qualifications and optimality conditions for nonconvex semi-infinite and infinite programs

The paper concerns the study of new classes of nonlinear and nonconvex optimization problems of the so-called infinite programming that are generally defined on infinite-dimensional spaces of decision variables and contain infinitely many of equality and inequality constraints with arbitrary (may not be compact) index sets. These problems reduce to semi-infinite programs in the case of finite-dimensional spaces of decision variables. We extend the classical Mangasarian–Fromovitz and Farkas–Minkowski constraint qualifications to such infinite and semi-infinite programs. The new qualification conditions are used for exact calculations of the appropriate normal cones to sets of feasible solutions for these programs by employing advanced tools of variational analysis and generalized differentiation. In the further development we derive first-order necessary optimality conditions for infinite and semi-infinite programs, which are new in both finite-dimensional and infinite-dimensional settings.     

Lagrange multiplier rules for non-differentiable DC generalized semi-infinite programming problems

This paper aims to study a broad class of generalized semi-infinite programming problems with (upper and lower level) objectives given as the difference of two convex functions, and (lower level) constraints described by a finite number of convex inequalities and a set constraints. First, we are interested in some various lower level constraint qualifications for the problem. Then, the results are used to establish efficient upper estimate of certain subdifferential of value functions. Finally, we apply the obtained subdifferential estimates to derive necessary optimality conditions for the problem.     

Necessary Conditions in Nonsmooth Minimization via Lower and Upper Subgradients

The paper concerns first-order necessary optimality conditions for problems of minimizing nonsmooth functions under various constraints in infinite-dimensional spaces. Based on advanced tools of variational analysis and generalized differential calculus, we derive general results of two independent types called lower subdifferential and upper subdifferential optimality conditions. The former ones involve basic/limiting subgradients of cost functions, while the latter conditions are expressed via Fréchet/regular upper subgradients in fairly general settings. All the upper subdifferential and major lower subdifferential optimality conditions obtained in the paper are new even in finite dimensions. We give applications of general optimality conditions to mathematical programs with equilibrium constraints deriving new results for this important class of intrinsically nonsmooth optimization problems.     

Necessary and sufficient constraint qualifications for solvability of systems of infinite convex inequalities

In this paper we present constraint qualifications which completely characterize the Farkas–Minkowski and the locally Farkas–Minkowski convex (possibly infinite) inequality systems posed in topological vector spaces. The number of constraints and the dimension of the linear space are arbitrary (possibly infinite). The constraint qualifications considered in this paper are expressed in terms of the solvability of certain parametric convex (linear) systems and the uniform strong duality or the uniform min–max duality relative to the Lagrange (Haar) dual problems of suitable convex (linear) parametric optimization problems.     

α-Well-posedness for Nash Equilibria and For Optimization Problems with Nash Equilibrium Constraints

We present the concepts of α-well-posedness for parametric noncooperative games and for optimization problems with constraints defined by parametric Nash equilibria. We investigate some classes of functions that ensure these types of well-posedness and the connections with α-well-posedness for variational inequalities and optimization problems with variational inequality constraints.     

Subdifferential estimate of the directional derivative,optimality criterion and separation principles

We provide an inequality relating the radial directional derivative and the subdifferential of proper lower semicontinuous functions, which extends the known formula for convex functions. We show that this property is equivalent to other subdifferential properties of Banach spaces, such as controlled dense subdifferentiability, optimality criterion, mean value inequality and separation principles. As an application, we obtain a first-order sufficient condition for optimality, which extends the known condition for differentiable functions in finite-dimensional spaces and which amounts to the maximal monotonicity of the subdifferential for convex lower semicontinuous functions. Finally, we establish a formula describing the subdifferential of the sum of a convex lower semicontinuous function with a convex inf-compact function in terms of the sum of their approximate ?-subdifferentials. Such a formula directly leads to the known formula relating the directional derivative of a convex lower semicontinuous function to its approximate ?-subdifferential.     

Minimal convex majorants of functions and Demyanov–Rubinov exhaustive super(sub)differentials

ABSTRACT

The primary goal of the paper is to establish characteristic properties of (extended) real-valued functions defined on normed vector spaces that admit the representation as the lower envelope (the pointwise infimum) of their minimal (with respect of the pointwise ordering) convex majorants. The results presented in the paper generalize and extend the well-known Demyanov-Rubinov characterization of upper semicontinuous positively homogeneous functions as the lower envelope of exhaustive families of continuous sublinear functions to larger classes of (not necessarily positively homogeneous) functions defined on arbitrary normed spaces. As applications of the above results, we introduce, for nonsmooth functions, a new notion of the Demyanov-Rubinov exhaustive subdifferential at a given point, and show that it generalizes a number of known notions of subdifferentiability, in particular, the Fenchel-Moreau subdifferential of convex functions, the Dini-Hadamard (directional) subdifferential of directionally differentiable functions, and the Φ-subdifferential in the sense of the abstract convexity theory. Some applications of Demyanov-Rubinov exhaustive subdifferentials to extremal problems are considered.     

Subdifferential of the supremum function: moving back and forth between continuous and non-continuous settings

In this paper we establish general formulas for the subdifferential of the pointwise supremum of convex functions, which cover and unify both the compact continuous and the non-compact non-continuous settings. From the non-continuous to the continuous setting, we proceed by a compactification-based approach which leads us to problems having compact index sets and upper semi-continuously indexed mappings, giving rise to new characterizations of the subdifferential of the supremum by means of upper semicontinuous regularized functions and an enlarged compact index set. In the opposite sense, we rewrite the subdifferential of these new regularized functions by using the original data, also leading us to new results on the subdifferential of the supremum. We give two applications in the last section, the first one concerning the nonconvex Fenchel duality, and the second one establishing Fritz-John and KKT conditions in convex semi-infinite programming.

     

Optimality and duality for proper and isolated efficiencies in multiobjective optimization

We use some advanced tools of variational analysis and generalized differentiation such as the nonsmooth version of Fermat’s rule, the limiting/Mordukhovich subdifferential of maximum functions, and the sum rules for the Fréchet subdifferential and for the limiting one to establish necessary conditions for (local) properly efficient solutions and (local) isolated minimizers of a multiobjective optimization problem involving inequality and equality constraints. Sufficient conditions for the existence of such solutions are also provided under assumptions of (local) convex/affine functions or $L$-invex-infine functions defined in terms of the limiting subdifferential of locally Lipschitz functions. In addition, we propose a type of Wolfe dual problems and examine weak/strong duality relations under $L$-invexity-infineness hypotheses.     

Stability in disjunctive linear optimization I: continuity of the feasible set

The aim of this paper is to study the continuous dependence of the feasible set of a disjunctive semi-infinite linear optimization problem on all involved parameters (matrix and right-hand side). The feasible set of such an optimization problem is the union of (a. possible infinite number of) convex sets, which each is described by a finite or an infinite number of strict and non-strict linear inequalities. We derive necessary and sufficient conditions for the upper- and lower-semi-continuity, and the closedness of the feasible-set-mapping Z Especially, the compactness of the boundary of the feasible set and the closedness of Z are equivalent to the upper-semi-continuity of Zwhile the lower semi-continuity of Z is equivalent to a certain constraint qualification. This constraint qualification is a strengthened kind of Slater condition, rrom tuese investigations, we derive known results in parametric semi-infinite optimization and parametric integer programming.     

DC Optimization Approach to Metric Regularity of Convex Multifunctions with Applications to Infinite Systems

The paper develops a new approach to the study of metric regularity and related well-posedness properties of convex set-valued mappings between general Banach spaces by reducing them to unconstrained minimization problems with objectives given as the difference of convex (DC) functions. In this way, we establish new formulas for calculating the exact regularity bound of closed and convex multifunctions and apply them to deriving explicit conditions ensuring well-posedness of infinite convex systems described by inequality and equality constraints.     

Approximate convexity and submonotonicity

It is shown that a locally Lipschitz function is approximately convex if, and only if, its Clarke subdifferential is a submonotone operator. Consequently, in finite dimensions, the class of locally Lipschitz approximately convex functions coincides with the class of lower-C¹ functions. Directional approximate convexity is introduced and shown to be a natural extension of the class of lower-C¹ functions in infinite dimensions. The following characterization is established: a multivalued operator is maximal cyclically submonotone if, and only if, it coincides with the Clarke subdifferential of a locally Lipschitz directionally approximately convex function, which is unique up to a constant. Furthermore, it is shown that in Asplund spaces, every regular function is generically approximately convex.     

A note about linear inequality systems and duality

The optimization of a linear function on a closed convex set,F, can be stated as a linear semi-infinite program, sinceF is the solution set of (usually) infinite linear inequality systems, the so-called linear representations ofF. The duality properties of these programs are analyzed when the linear representation ofF ranges in some well known classes of linear inequality systems. This paper provides propositions on the duality diagrams of Farkas-Minkowski, canonically closed, compact and closed systems. Converse statements are also given.

---

Zusammenfassung Die Optimierung einer linearen Funktion auf einer konvexen abgeschlossenen MengeF kann als semi-infinites lineares Programm aufgefaßt werden, daF als Durchschnitt (unendlich) vieler Halbräume dargestellt werden kann. Es werden Dualitätseigenschaften dieser Programme untersucht, wobei von verschiedenen linearen Darstellungen fürF ausgegangen wird. Die Arbeit enthält Sätze über Dualitätsbeziehungen von Farkas-Minkowski, kanonisch abgeschlossene, kompakte und abgeschlossene Systeme. Es werden auch umgekehrte Beziehungen angegeben.

     

Parametric Borwein-Preiss variational principle and applications

A parametric version of the Borwein-Preiss smooth variational principle is presented, which states that under suitable assumptions on a given convex function depending on a parameter, the minimum point of a smooth convex perturbation of it depends continuously on the parameter. Some applications are given: existence of a Nash equilibrium and a solution of a variational inequality for a system of partially convex functions, perturbed by arbitrarily small smooth convex perturbations when one of the functions has a non-compact domain; a parametric version of the Kuhn-Tucker theorem which contains a parametric smooth variational principle with constraints; existence of a continuous selection of a subdifferential mapping depending on a parameter.

The tool for proving this parametric smooth variational principle is a useful lemma about continuous -minimizers of quasi-convex functions depending on a parameter, which has independent interest since it allows direct proofs of Ky Fan's minimax inequality, minimax equalities for quasi-convex functions, Sion's minimax theorem, etc.

     

Sufficient global optimality conditions for weakly convex minimization problems

In this paper, we present sufficient global optimality conditions for weakly convex minimization problems using abstract convex analysis theory. By introducing (L,X)-subdifferentials of weakly convex functions using a class of quadratic functions, we first obtain some sufficient conditions for global optimization problems with weakly convex objective functions and weakly convex inequality and equality constraints. Some sufficient optimality conditions for problems with additional box constraints and bivalent constraints are then derived.      

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000