Duality and optimality conditions for generalized equilibrium problems involving DC functions

We consider a generalized equilibrium problem involving DC functions which is called (GEP). For this problem we establish two new dual formulations based on Toland-Fenchel-Lagrange duality for DC programming problems. The first one allows us to obtain a unified dual analysis for many interesting problems. So, this dual coincides with the dual problem proposed by Martinez-Legaz and Sosa (J Glob Optim 25:311–319, 2006) for equilibrium problems in the sense of Blum and Oettli. Furthermore it is equivalent to Mosco’s dual problem (Mosco in J Math Anal Appl 40:202–206, 1972) when applied to a variational inequality problem. The second dual problem generalizes to our problem another dual scheme that has been recently introduced by Jacinto and Scheimberg (Optimization 57:795–805, 2008) for convex equilibrium problems. Through these schemes, as by products, we obtain new optimality conditions for (GEP) and also, gap functions for (GEP), which cover the ones in Antangerel et al. (J Oper Res 24:353–371, 2007, Pac J Optim 2:667–678, 2006) for variational inequalities and standard convex equilibrium problems. These results, in turn, when applied to DC and convex optimization problems with convex constraints (considered as special cases of (GEP)) lead to Toland-Fenchel-Lagrange duality for DC problems in Dinh et al. (Optimization 1–20, 2008, J Convex Anal 15:235–262, 2008), Fenchel-Lagrange and Lagrange dualities for convex problems as in Antangerel et al. (Pac J Optim 2:667–678, 2006), Bot and Wanka (Nonlinear Anal to appear), Jeyakumar et al. (Applied Mathematics research report AMR04/8, 2004). Besides, as consequences of the main results, we obtain some new optimality conditions for DC and convex problems.     

Conjugate duality in vector optimization and some applications to the vector variational inequality

The aim of this paper is to extend the so-called perturbation approach in order to deal with conjugate duality for constrained vector optimization problems. To this end we use two conjugacy notions introduced in the past in the literature in the framework of set-valued optimization. As a particular case we consider a vector variational inequality which we rewrite in the form of a vector optimization problem. The conjugate vector duals introduced in the first part allow us to introduce new gap functions for the vector variational inequality. The properties in the definition of the gap functions are verified by using the weak and strong duality theorems.     

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.     

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

Estimates of Deviations from Exact Solutions of Elliptic Variational Inequalities

In this paper, we present a method of deriving majorants of the difference between exact solutions of elliptic type variational inequalities and functions lying in the admissible functional class of the problem under consideration. We analyze three classical problems associated with stationary variational inequalities: the problem with two obstacles, the elastoplastic torsion problem and the problem with friction type boundary conditions. The majorants are obtained by a modification of the duality technique earlier used by the author for variational problems with uniformly convex functionals. These majorants naturally reflects properties of exact solutions and possess necessary continuity conditions. Bibliography: 15 titles.     

EXISTENCE AND DUALITY OF IMPLICIT VECTOR VARIATIONAL PROBLEMS*

In this paper, we consider implicit vector variational problems which contain vector equilibrium problems and vector variational inequalities as special cases. The existence of solutions of implicit vector variational problems and vector equilibrium problems have been established. As a special case, we derive some existence results for a solution of vector variational inequalities. We also study the duality of implicit vector variational problems and discuss the relationship between solutions of dual and primal problems. Our results on duality contains known results in the literature as special cases.

     

A Scalarization Approach for Vector Variational Inequalities with Applications

We consider an approach to convert vector variational inequalities into an equivalent scalar variational inequality problem with a set-valued cost mapping. Being based on this property, we give an equivalence result between weak and strong solutions of set-valued vector variational inequalities and suggest a new gap function for vector variational inequalities. Additional examples of applications in vector optimization, vector network equilibrium and vector migration equilibrium problems are also given Mathematics Subject Classification(2000). 49J40, 65K10, 90C29     

Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization

The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces. Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999     

Gap functions for generalized vector equilibrium problems via conjugate duality and applications

In this article, gap functions for a generalized vector equilibrium problem (GVEP) with explicit constraints are investigated. Under a concept of supremum/infimum of a set, defined in terms of a closure of the set, three kinds of conjugate dual problems are investigated by considering the different perturbations to GVEP. Then, gap functions for GVEP are established by using the weak and strong duality results. As application, the proposed approach is applied to construct gap functions for a vector optimization problem and a generalized vector variational inequality problem.     

Perturbation approach to generalized Nash equilibrium problems with shared constraints

This paper aims to consider an application of conjugate duality in convex optimization to the generalized Nash equilibrium problems with shared constraints and nonsmooth cost functions. Sufficient optimality conditions for the problems regarding to players are rewritten as inclusion problems and the maximal monotonicity of set-valued mappings generated by the subdifferentials of functions from data of GNEP is proved. Moreover, some assertions dealing with solutions to GNEP are obtained and applications of splitting algorithms to the oligopolistic market equilibrium models are presented.     

Gap Functions and Lyapunov Functions

Equilibrium problems play a central role in the study of complex and competitive systems. Many variational formulations of these problems have been presented in these years. So, variational inequalities are very useful tools for the study of equilibrium solutions and their stability. More recently a dynamical model of equilibrium problems based on projection operators was proposed. It is designated as globally projected dynamical system (GPDS). The equilibrium points of this system are the solutions to the associated variational inequality (VI) problem. A very popular approach for finding solution of these VI and for studying its stability consists in introducing the so-called "gap-functions", while stability analysis of an equilibrium point of dynamical systems can be made by means of Lyapunov functions. In this paper we show strict relationships between gap functions and Lyapunov functions.     

Duality for almost convex optimization problems via the perturbation approach

We deal with duality for almost convex finite dimensional optimization problems by means of the classical perturbation approach. To this aim some standard results from the convex analysis are extended to the case of almost convex sets and functions. The duality for some classes of primal-dual problems is derived as a special case of the general approach. The sufficient regularity conditions we need for guaranteeing strong duality are proved to be similar to the ones in the convex case. The research of the first and third authors was partially supported by DFG (German Research Foundation), project WA 922/1. The research of the second author was supported by the grant PN II, ID 523/2007.     

Duality and uniqueness of convex solutions to stationary Hamilton-Jacobi equations

Value functions for convex optimal control problems on infinite time intervals are studied in the framework of duality. Hamilton-Jacobi characterizations and the conjugacy of primal and dual value functions are of main interest. Close ties between the uniqueness of convex solutions to a Hamilton-Jacobi equation, the uniqueness of such solutions to a dual Hamilton-Jacobi equation, and the conjugacy of primal and dual value functions are displayed. Simultaneous approximation of primal and dual infinite horizon problems with a pair of dual problems on finite horizon, for which the value functions are conjugate, leads to sufficient conditions on the conjugacy of the infinite time horizon value functions. Consequently, uniqueness results for the Hamilton-Jacobi equation are established. Little regularity is assumed on the cost functions in the control problems, correspondingly, the Hamiltonians need not display any strict convexity and may have several saddle points.

     

Infimal convolution, c-subdifferentiability, and Fenchel duality in evenly convex optimization

In this paper we deal with strong Fenchel duality for infinite-dimensional optimization problems where both feasible set and objective function are evenly convex. To this aim, via perturbation approach, a conjugation scheme for evenly convex functions, based on generalized convex conjugation, is used. The key is to extend some well-known results from convex analysis, involving the sum of the epigraphs of two conjugate functions, the infimal convolution and the sum formula of ??-subdifferentials for lower semicontinuous convex functions, to this more general framework.     

Lagrangian Duality and Cone Convexlike Functions

In this paper, we consider first the most important classes of cone convexlike vector-valued functions and give a dual characterization for some of these classes. It turns out that these characterizations are strongly related to the closely convexlike and Ky Fan convex bifunctions occurring within minimax problems. Applying the Lagrangian perturbation approach, we show that some of these classes of cone convexlike vector-valued functions show up naturally in verifying strong Lagrangian duality for finite-dimensional optimization problems. This is achieved by extending classical convexity results for biconjugate functions to the class of so-called almost convex functions. In particular, for a general class of finite-dimensional optimization problems, strong Lagrangian duality holds if some vector-valued function related to this optimization problem is closely K-convexlike and satisfies some additional regularity assumptions. For K a full-dimensional convex cone, it turns out that the conditions for strong Lagrangian duality simplify. Finally, we compare the results obtained by the Lagrangian perturbation approach worked out in this paper with the results achieved by the so-called image space approach initiated by Giannessi.     

General infinite dimensional duality and applications to evolutionary network equilibrium problems

In this paper the authors present an infinite dimensional duality theory for optimization problems and evolutionary variational inequalities where the constraint sets are given by inequalities and equalities. The difficulties arising from the structure of the constraint set are overcome by means of generalized constraint qualification assumptions based on the concept of quasi relative interior of a convex set. An application to a general evolutionary network model, which includes as special cases traffic, spatial price and financial equilibrium problems, concludes the paper.     

Global Approximation of Solutions of Time-Dependent Variational Inequalities

We consider a class of parametric variational inequalities where both the operator and the convex set depend on time. This kind of variational inequalities are useful to model many time dependent equilibrium problems. We study the Lipschitz continuity of the solutions with respect to the time parameter and construct approximations for them which minimize the average worst case error. Some improved estimates of the Lipschitz constant for this class of problems are given. In order to illustrate our procedure, we study a classical network equilibrium problem.     

Strong KKT conditions and weak sharp solutions in convex-composite optimization

Using variational analysis techniques, we study convex-composite optimization problems. In connection with such a problem, we introduce several new notions as variances of the classical KKT conditions. These notions are shown to be closely related to the notions of sharp or weak sharp solutions. As applications, we extend some results on metric regularity of inequalities from the convex case to the convex-composite case.     

Equilibrium programming using proximal-like algorithms

We compute constrained equilibria satisfying an optimality condition. Important examples include convex programming, saddle problems, noncooperative games, and variational inequalities. Under a monotonicity hypothesis we show that equilibrium solutions can be found via iterative convex minimization. In the main algorithm each stage of computation requires two proximal steps, possibly using Bregman functions. One step serves to predict the next point; the other helps to correct the new prediction. To enhance practical applicability we tolerate numerical errors. Research supported partly by the Norwegian Research Council, project: Quantec 111039/401.     

Variational convergence of bivariate functions: lopsided convergence

We explore convergence notions for bivariate functions that yield convergence and stability results for their maxinf (or minsup) points. This lays the foundations for the study of the stability of solutions to variational inequalities, the solutions of inclusions, of Nash equilibrium points of non-cooperative games and Walras economic equilibrium points, of fixed points, of solutions to inclusions, the primal and dual solutions of convex optimization problems and of zero-sum games. These applications will be dealt with in a couple of accompanying papers.