Zero duality gap conditions via abstract convexity
- Authors: Bui, Hoa , Burachik, Regina , Kruger, Alexander , Yost, David
- Date: 2022
- Type: Journal article
- Relation: Optimization Vol. 71, no. 4 (2022), p. 811-847
- Relation: https://purl.org/au-research/grants/arc/DP160100854
- Full Text:
- Reviewed:
- Description: Using tools provided by the theory of abstract convexity, we extend conditions for zero duality gap to the context of non-convex and nonsmooth optimization. Mimicking the classical setting, an abstract convex function is the upper envelope of a family of abstract affine functions (being conventional vertical translations of the abstract linear functions). We establish new conditions for zero duality gap under no topological assumptions on the space of abstract linear functions. In particular, we prove that the zero duality gap property can be fully characterized in terms of an inclusion involving (abstract) (Formula presented.) -subdifferentials. This result is new even for the classical convex setting. Endowing the space of abstract linear functions with the topology of pointwise convergence, we extend several fundamental facts of functional/convex analysis. This includes (i) the classical Banach–Alaoglu–Bourbaki theorem (ii) the subdifferential sum rule, and (iii) a constraint qualification for zero duality gap which extends a fact established by Borwein, Burachik and Yao (2014) for the conventional convex case. As an application, we show with a specific example how our results can be exploited to show zero duality for a family of non-convex, non-differentiable problems. © 2021 Informa UK Limited, trading as Taylor & Francis Group.
Generalized bregman envelopes and proximity operators
- Authors: Burachik, Regina , Dao, Minh , Lindstrom, Scott
- Date: 2021
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 190, no. 3 (2021), p. 744-778
- Full Text:
- Reviewed:
- Description: Every maximally monotone operator can be associated with a family of convex functions, called the Fitzpatrick family or family of representative functions. Surprisingly, in 2017, Burachik and Martínez-Legaz showed that the well-known Bregman distance is a particular case of a general family of distances, each one induced by a specific maximally monotone operator and a specific choice of one of its representative functions. For the family of generalized Bregman distances, sufficient conditions for convexity, coercivity, and supercoercivity have recently been furnished. Motivated by these advances, we introduce in the present paper the generalized left and right envelopes and proximity operators, and we provide asymptotic results for parameters. Certain results extend readily from the more specific Bregman context, while others only extend for certain generalized cases. To illustrate, we construct examples from the Bregman generalizing case, together with the natural “extreme” cases that highlight the importance of which generalized Bregman distance is chosen. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
The generalized bregman distance
- Authors: Burachik, Regina , Dao, Minh , Lindstrom, Scott
- Date: 2021
- Type: Text , Journal article
- Relation: SIAM Journal on Optimization Vol. 31, no. 1 (2021), p. 404-424
- Full Text:
- Reviewed:
- Description: Recently, a new kind of distance has been introduced for the graphs of two point-to-set operators, one of which is maximally monotone. When both operators are the subdifferential of a proper lower semicontinuous convex function, this kind of distance specializes under modest assumptions to the classical Bregman distance. We name this new kind of distance the generalized Bregman distance, and we shed light on it with examples that utilize the other two most natural representative functions: the Fitzpatrick function and its conjugate. We provide sufficient conditions for convexity, coercivity, and supercoercivity: properties which are essential for implementation in proximal point type algorithms. We establish these results for both the left and right variants of this new kind of distance. We construct examples closely related to the Kullback-Leibler divergence, which was previously considered in the context of Bregman distances and whose importance in information theory is well known. In so doing, we demonstrate how to compute a difficult Fitzpatrick conjugate function, and we discover natural occurrences of the Lambert \scrW function, whose importance in optimization is of growing interest. © 2021 Society for Industrial and Applied Mathematics
An additive subfamily of enlargements of a maximally monotone operator
- Authors: Burachik, Regina , Martinez-Legaz, Juan , Rezaie, Mahboubeh , Thera, Michel
- Date: 2015
- Type: Text , Journal article
- Relation: Set-Valued and Variational Analysis Vol. 23, no. 4 (2015), p. 643-665
- Full Text:
- Reviewed:
- Description: We introduce a subfamily of additive enlargements of a maximally monotone operator. Our definition is inspired by the early work of Simon Fitzpatrick. These enlargements constitute a subfamily of the family of enlargements introduced by Svaiter. When the operator under consideration is the subdifferential of a convex lower semicontinuous proper function, we prove that some members of the subfamily are smaller than the classical epsilon-subdifferential enlargement widely used in convex analysis. We also recover the epsilon-subdifferential within the subfamily. Since they are all additive, the enlargements in our subfamily can be seen as structurally closer to the epsilon-subdifferential enlargement.
Outer approximation schemes for generalized semi-infinite variational inequality problems
- Authors: Burachik, Regina , Lopes, J.
- Date: 2010
- Type: Text , Journal article
- Relation: Optimization Vol. 59, no. 4 (2010), p. 601-617
- Full Text: false
- Reviewed:
- Description: We introduce and analyse outer approximation schemes for solving variational inequality problems in which the constraint set is as in generalized semi-infinite programming. We call these problems generalized semi-infinite variational inequality problems. First, we establish convergence results of our method under standard boundedness assumptions. Second, we use suitable Tikhonov-like regularizations for establishing convergence in the unbounded case.
An inexact modified subgradient algorithm for nonconvex optimization
- Authors: Burachik, Regina , Kaya, Yalcin , Mammadov, Musa
- Date: 2008
- Type: Text , Journal article
- Relation: Computational Optimization and Applications Vol. , no. (2008), p. 1-24
- Full Text:
- Reviewed:
- Description: We propose and analyze an inexact version of the modified subgradient (MSG) algorithm, which we call the IMSG algorithm, for nonsmooth and nonconvex optimization over a compact set. We prove that under an approximate, i.e. inexact, minimization of the sharp augmented Lagrangian, the main convergence properties of the MSG algorithm are preserved for the IMSG algorithm. Inexact minimization may allow to solve problems with less computational effort. We illustrate this through test problems, including an optimal bang-bang control problem, under several different inexactness schemes. © 2008 Springer Science+Business Media, LLC.
- Description: C1
On abstract convexity and set valued analysis
- Authors: Burachik, Regina , Rubinov, Alex
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of Nonlinear and Convex Analysis Vol. 9, no. 1 (2008), p. 105-123
- Full Text: false
- Reviewed:
- Description: Given a set L subset of R-X of functions defined on X, we consider abstract monotone (or, for short, L-monotone) multivalued operators T : X paired right arrows L. We extend the definition of enlargement of monotone operators to this framework and study semicontinuity properties of these mappings. We prove that sequential outer semicontinuity, which holds for maximal monotone operators and their enlargements in the classical case (i.e., when L = X* and X is a Banach space), holds also in our abstract setting. We also show through examples that some properties, known to hold in the classical case, may no longer be valid in the abstract setting. One of these properties is the maximality of the subdifferential and another one is the lack of inner semicontinuity of (point-to-set) monotone operators in the interior of their domain. We also focus on the structure of both the abstract subdifferential and the abstract epsilon-subdifferential. This is a key question in abstract convexity because these sets may be very large for certain choices of L and therefore it is important to be able to represent them by means of some special elements of the set of "affine" functions induced by L.
Abstract convexity and augmented Lagrangians
- Authors: Burachik, Regina , Rubinov, Alex
- Date: 2007
- Type: Text , Journal article
- Relation: SIAM Journal on Optimization Vol. 18, no. 2 (2007), p. 413-436
- Full Text: false
- Reviewed:
- Description: The ultimate goal of this paper is to demonstrate that abstract convexity provides a natural language and a suitable framework for the examination of zero duality gap properties and exact multipliers of augmented Lagrangians. We study augmented Lagrangians in a very general setting and formulate the main definitions and facts describing the augmented Lagrangian theory in terms of abstract convexity tools. We illustrate our duality scheme with an application to stochastic semiinfinite optimization. © 2007 Society for Industrial and Applied Mathematics.
- Description: C1
- Description: 2003005362
An update rule and a convergence result for a penalty function method
- Authors: Burachik, Regina , Kaya, Yalcin
- Date: 2007
- Type: Text , Journal article
- Relation: Journal of Industrial & Management Optimization Vol. 3, no. 2 (2007), p. 381-398
- Full Text:
- Reviewed:
- Description: We use a primal-dual scheme to devise a new update rule for a penalty function method applicable to general optimization problems, including nonsmooth and nonconvex ones. The update rule we introduce uses dual information in a simple way. Numerical test problems show that our update rule has certain advantages over the classical one. We study the relationship between exact penalty parameters and dual solutions. Under the differentiability of the dual function at the least exact penalty parameter, we establish convergence of the minimizers of the sequential penalty functions to a solution of the original problem. Numerical experiments are then used to illustrate some of the theoretical results.
- Description: C1
- Description: 2003004886
Necessary and sufficient conditions for stable conjugate duality
- Authors: Burachik, Regina , Jeyakumar, Vaithilingam , Wu, Zhiyou
- Date: 2006
- Type: Text , Journal article
- Relation: Journal of Nonlinear Analysis Vol. 64, no. 9 (2006), p. 1998-2005
- Full Text:
- Reviewed:
- Description: The conjugate duality, which states that infx∈X φ(x, 0) = maxv∈Y ' −φ∗(0,v), whenever a regularity condition on φ is satisfied, is a key result in convex anal¬ysis and optimization, where φ : X × Y → IR ∪{+∞} is a convex function, X and Y are Banach spaces, Y ' is the continuous dual space of Y and φ∗ is the Fenchel-Moreau conjugate of φ. In this paper, we establish a necessary and sufficient condition for the stable conjugate duality, ∗ ∗ ∈ X' inf {φ(x, 0) + x ∗(x)} = max {−φ ∗(−x ,v)}, ∀x, x∈Xv∈Y ' and obtain a new global dual regularity condition, which is much more general than the popularly known interior-point type conditions, for the conjugate duality. As a consequence we present an epigraph closure condition which is necessary and sufficient for a stable Fenchel-Rockafellar duality theorem. In the case where one of the functions involved in the duality is a polyhedral convex function, we also provide generalized interior-point conditions for the epigraph closure condition. Moreover, we show that a stable Fenchel’s duality for sublinear functions holds whenever a subdifferential sum formula for the functions holds. As applications, we give general sufficient conditions for a minimax theorem, a subdifferential composition formula and for duality results of convex programming problems.
- Description: C1
- Description: 2003003596
On a modified subgradient algorithm for dual problems via sharp augmented Lagrangian
- Authors: Burachik, Regina , Gasimov, Rafail , Ismayilova, Nergiz , Kaya, Yalcin
- Date: 2006
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 34, no. 1 (2006), p. 55-78
- Full Text: false
- Reviewed:
- Description: We study convergence properties of a modified subgradient algorithm, applied to the dual problem defined by the sharp augmented Lagrangian. The primal problem we consider is nonconvex and nondifferentiable, with equality constraints. We obtain primal and dual convergence results, as well as a condition for existence of a dual solution. Using a practical selection of the step-size parameters, we demonstrate the algorithm and its advantages on test problems, including an integer programming and an optimal control problem
- Description: C1
- Description: 2003002552
A dual condition for the convex subdifferential sum formula with applications
- Authors: Burachik, Regina , Jeyakumar, Vaithilingam
- Date: 2005
- Type: Text , Journal article
- Relation: Journal of Convex Analysis Vol. 12, no. 2 (2005), p. 279-290
- Full Text: false
- Reviewed:
- Description: C1
- Description: 2003002555
On the absence of duality gap for Lagrange-type functions
- Authors: Rubinov, Alex , Burachik, Regina
- Date: 2005
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 1, no. 1 (2005), p. 33-38
- Full Text:
- Reviewed:
- Description: Given a generic dual program we discuss the absence of duality gap for a family of Lagrange-type functions. We obtain necessary conditions that become sufficient ones under some additional assumptions. We also give examples of Lagrangetype functions for which this sufficient conditions hold.
- Description: C1
- Description: 2003001425
Maximal monotonicity, conjugation and the duality product
- Authors: Burachik, Regina , Svaiter, B.F.
- Date: 2003
- Type: Text , Journal article
- Relation: Proceedings of the American Mathematical Society Vol. 131, no. 8 (2003), p. 2379-2383
- Full Text: false
- Reviewed:
- Description: Recently, the authors studied the connection between each maximal monotone operator T and a family H(T) of convex functions. Each member of this family characterizes the operator and satisfies two particular inequalities. The aim of this paper is to establish the converse of the latter fact. Namely, that every convex function satisfying those two particular inequalities is associated to a unique maximal monotone operator.
- Description: C1
- Description: 2003002558