Search

We give some complements to Nitica, V. and Singer, I., 2007, Max-plus convex sets and max-plus semispaces, I.Optimization, 56, 171–205. We show that the theories of max-plus convexity in and -convexity in are equivalent, and we deduce some consequences. We show that max-plus convexity in Rn is a multi-order convexity. We give simpler proofs, using only the definition of max-plus segments, of the results of loc. cit. on max-plus semispaces. We show that unless ≤ is a total order onA, the results ofloc. cit. on semispaces cannot be generalized in a natural way to the framework ofAn =(An , ≤, ⊗), whereA:=M∪ {−∞}, withM=(M,≤,⊗) being a lattice ordered group and −∞ a “least element’ adjoined toM.

We extend some recent results on radiant and normal sets in , increasing positively homogeneous and increasing co-radiant functions plus-radiant and downward sets in , topical and sub-topical functions to the unifying framework of subsets of An and functions f:An → where A=(A,≤, ⊗ ) is a conditionally complete lattice ordered group and is the minimal enlargement of A. For results involving closedness, continuity and semi-continuity, we assume that the lattice A is continuous and we use the order topology on An and A.

We extend the results of Rubinov and Glover on the separation of normal subsets of , and those of Martinez-Legaz, Rubinov and Singer on the separation of downward subsets of , to the unifying framework of subsets of An , where A is a continuous conditionally complete lattice ordered group. We also extend earlier results of the second author on the characterizations of conjugations of type Lau of functions , to the framework of functions , where is the canonical enlargement of A. These extensions are based on the notions and results of the theory of continuous lattices, generalized in an earlier work of the first author and here, to the conditionally complete case, in particular the way below order relation ≪, and the Scott and Lawson topologies. We also introduce the “way above order relation ≫”, and consider the “bi-Scott topology” on A, introduced previously by the first author, which under our continuity assumption on A, turns out to be equal to the order topology; moreover, we show that for this topol...

Applying for the additive min-type coupling function $$ \varphi (x, w) = \mathop {\min }\limits_{1 \le i \le n} (x_1 + w_i )\quad (x = (x_i ), w = (w_i ) \in {\shadR}^n ) $$ the techniques from abstract convex analysis, developed in [I. Singer (1997). Abstract Convex Analysis . Wiley-Interscience, New York], we show that the conjugate of type Lau f L ( } ) of f with respect to } has the simple expression $ f^{L(\varphi )} (w) = - f( - w)\, (w \in {\shadR}^n ) $ if and only if f is increasing and upper semi-continuous. As a consequence, we obtain that for topical (i.e., increasing additively homogeneous) functions f the Fenchel-Moreau conjugate of f with respect to } and the conjugate of type Lau of f with respect to } coincide.

For the reverse convex infimization problem (P) inf f(X\G)where G convex subset of a locally convex space X and is a function, we.carry ouexplicitly one of the main ideas of our previous paper [11], namely, we obtain some new Lagrangian duality theorems for (P) from the surrogate duality theorems and of our recen paper [16].

Let Xbe a setW set of extended-real valued functions on Xand 0 an element of Xsuch that w(0) = 0 for all win W. We give a general theory of dual representations, without any extra parameters, of various hulls for extended-real valued functions on X satisfying f(0)= inf f(X\{0})We use the unifying framework of quasi-convex functions with respect to families of subsets of Xand a condition generalizing the bipolar theorem. Our results contain, as particular cases, some recent results of Thach (1991, 1993) and Rubinov and Glover (1996) on W-pseudo-affine and W-quasi-coaffine hulls.We also give some results in the converse direction. These yield, in particular, that the bipolar theorem is equivalent to a certain property of the lower semi-continuous quasi-convex hulls of functions on locally convex spaces

We give duality theorems and dual characterizations of optimal solutions for abstract quasi-convex supremization problems and infimization problems with abstract reverse convex constraint sets. Our main tools are dualities between families of subsets, conjugations of type Lau associated to them, and subdifferentials with respect to conjugations of type Lau. These tools permit us to give explicitly the relation between.the constraint sets, and the relation between the objective functions, of the primal problem and the dual problem. As applications, we obtain duality theorems for quasi-convex supremization and reverse convex infimization in locally convex spaces and, in particular, for worst and best approximation in normed linear spaces.

Main result: For each closed convex subset C of a Banach space X and each x ¬∈ C there exists an equivalent norm on X for which x has a unique nearest point in C.

Recently Deutsch, Li and Swetits [2] have studied, in Hilbert space, a dual problem (Qm ) to the primal problem (P) of minimization of a special class of convex functions f over the intersection of m closed convex sets, where m is finite. In the first part of this paper we obtain, in a locally convex space, some results on problem (Qm ) and on its relations with the usual Lagrangian dual problem (Q) to (P) (studied in [9]), in the case when (P) has a solution. In the second part we give some applications to duality for the distance to the intersection of m closed convex sets in a normed linear space, in the case when a nearest point exists. Most of our results seem to be new even in the particular cases studied in [9] (the case m = 1), [l] (duality formulas for the distance to the intersection of m closed half-spaces in a normed linear space) and [2].

We present some results extending d.c. duality theory to the generalized convex setting.Given a binary operation ∗ on the extended real line, we consider the problem of minimizingƒ∗–hwithƒ and h being functions defined on an arbitrary set. For this problem. we obtain results which encompass, as particular cases, some well known duality theorems for the infimum of the difference of two functions and the infimum of the maximum of two functions, as well as some well known formulae for the conjugate of the difference of two functions and the conjugate of type Lau of the maximum of two functions. Instead of considering the Fenchel conjugation operator, our results are expressed with the aid of dualities which are associated to the operation ∗.We also study. for such dualities, the corresponding generalized subdifferential

Continuing our papers [4] - [7], where we have given an axiomatic approach to unperturbational dual problems, we study here perturbational dual problems. we give some characterizations of various classes of perturbations and the associated marginal functions and of various classes of perturbational dual objective functions and the associated Lagrangians, regarded as functions of their natural variables and of the primal parameters

For constrained primal infimization problems, we give some characterizations of the surrogate dual objective functions, regarded as functions of three variables (namely, of the primal constraint set, the primal objective function and the dual variable). We also give some results on surrogate constraint mappings

We introduce and study dualities △:[Rbar]x → [Rbar]w (i.e., mappings f e [Rbar]x → f △ e [Rbar]w such that for all {fi }ie1 ∈ Rx and all index sets I), which satisfy the additional condition and their duals, which are characterized as those dualities △*:Rx → Rw for which , where ⊥ and ⊺ are two new binary operations on [Rbar], which we introduce here. Furthermore, we give a characterization of those Δ which are also conjugations. Some applications are also mentioned.

We study dualities between two complete lattices Eand Fi.e., mappings △:E→ F satisfying for all {x i } ieI ⊆E and all index sets I including the empty set I = O. We give characterizations and representations of dualities △, and some results on the dual △* F→Eof △ and on the associated hull operator △*△:E→Ein the general case and in various particular eases. Among several applications, we devote special attention to Fenchel-Moreau conjugations.

Let G be a non-empty subset of a real locally convex space F and h:F→[rbar] a functional. We give necessary and sufficient conditions in order that goeG should satisfy h(go)=inf h(G) and that there should hold one of the formulae of (weak or stronq) duality of [5], [6] for inf h(G). The conditions are similar to those of [5], [6], but involve some additional level sets of h.

We introduce some new abstract Pontryagin maximum principles (PMP's) for linear systems, corresponding to our formulae of Lagrangian duality and surrogate duality of [7] and [10]. §1 is concerned with PMP's for linear systems and their study by passing to F/Ker u. §2 is devoted to the equivalent setting of PMP's involving only one space X and their study via the primal functional corresponding to perturbations by translations.

We consider the optimization problem inf h(G),_where G≠O is a subset of a real locally convex space F and h:F→[Rbar].§1 contains a unified approach to the necessary and sufficient conditions of [l3]–[l5] and of §§2–3. In §§2–3 we give conditions for the validity of duality formulae involving half-spaces (closed or open), unions of strips and unions of closed strips, containing G. In §4 we show some relations between the minimization of h and hq (the quasi-convex hull of h) on G and ∞ G, or ∞[bbar] G and we determine . In §5 we consider duality formulae involving nonlinear functionals.

We consider the optimization problem (P), α =inf h(G),, where G≠ O is a subset of a locally convex space Fand h:F→ R, “embedded” into a family of optimization problems where Xis a locally convex space and φ:F× X→ R.For surrogate dual, respectively. Lagrangian dual problems (Q), β = sup λ(X *), to (P),, defined with the aid of this embedding, we give necessary and sufficient conditions for α = β,involving functionals φ e X *and level sets of f, respectively of [ftilde](x,t), = f(x), + t(xe X,te R),, or involving surrogate e-subdifferentials (which we introduce here),, respectively e-subdifferentials of f(e ≧ 0),. We give applications to, optimization problems perturbed by multifunctions and to optimization problems for systems, obtaining conditions for surrogate duality in terms of functionals φ e X *and the level sets of h.

For a locally convex space E and f :E→R¯, we introduce and study surrogate conjugate functionals of f, which en¬compass the quasi-conjugates [1] , pseudo-conjugates [2] and semi-conjugates [3] of f. Also, we introduce and study surro¬gate convexity of sets GcE and of functionals f:E→R¯ and show their connections with surrogate conjugation and with W-conve-xity of sets [4] and of functionals [5], where WcR¯E. We outline some further developments (surrogate conjugates at a point, surrogate subdifferentials) and an application to optimization. A basic role is played by the concept of a universally defined multifunction A:RXE*→2E

Using our theorems (of [12]) on separation of convex sets by linear operators, in the sense of the lexi-cographical order on Rn, we prove some theorems of surrogate duality for vector optimization problems with convex constraints (but no regularity assumption), where the surrogate constraint sets are generalized half-spaces and the surrogate multipliers are linear operators, or isomorphisms, or isometries. In the cae of inequality constraints, we prove that the surrogate multipliers can be taken lexicographically non-negative isometries or non-negative (in the usual order) linear isomorphisms.

For in § 2 we introduce and study “tight extensions” fD : [0, 1]n → R, defined on each n-simplex Di of a triangulation D of [0,1]n, with all vertices in {0,1}n, as the unique affine function which interpolates f at the vertices of Di. In § 3 we study convexity of tight extensions. In §4 we show the existence of polyhedral convex (generally, non-tight) extensions. As applications, in §5 we give some duality theorems for minimization and maximization of submodular functions and in §6 (Appendix) we obtain new insight into the “greedy solutions” of a certain linear maximization problem.

Continuing our program of extension of some results of approximation theory to optimization theory, we show that for a (finite and) continuous convex functional fon a locally convex space Eand a convex subset Gof Ewith G≠E, either closed or with Int G≠⊘ Such that inf f(G)≦ inf f(E\G), the problem of computing inf f:(E\G), and if Int G≠⊘ and inf f(G)