Aggregate subgradient method for nonsmooth DC optimization
- Authors: Bagirov, Adil , Taheri, Sona , Joki, Kaisa , Karmitsa, Napsu , Mäkelä, Marko
- Date: 2021
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 15, no. 1 (2021), p. 83-96
- Relation: http://purl.org/au-research/grants/arc/DP190100580
- Full Text:
- Reviewed:
- Description: The aggregate subgradient method is developed for solving unconstrained nonsmooth difference of convex (DC) optimization problems. The proposed method shares some similarities with both the subgradient and the bundle methods. Aggregate subgradients are defined as a convex combination of subgradients computed at null steps between two serious steps. At each iteration search directions are found using only two subgradients: the aggregate subgradient and a subgradient computed at the current null step. It is proved that the proposed method converges to a critical point of the DC optimization problem and also that the number of null steps between two serious steps is finite. The new method is tested using some academic test problems and compared with several other nonsmooth DC optimization solvers. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.
Chebyshev multivariate polynomial approximation and point reduction procedure
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2021
- Type: Text , Journal article
- Relation: Constructive Approximation Vol. 53, no. 3 (2021), p. 529-544
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We apply the methods of nonsmooth and convex analysis to extend the study of Chebyshev (uniform) approximation for univariate polynomial functions to the case of general multivariate functions (not just polynomials). First of all, we give new necessary and sufficient optimality conditions for multivariate approximation, and a geometrical interpretation of them which reduces to the classical alternating sequence condition in the univariate case. Then, we present a procedure for verification of necessary and sufficient optimality conditions that is based on our generalization of the notion of alternating sequence to the case of multivariate polynomials. Finally, we develop an algorithm for fast verification of necessary optimality conditions in the multivariate polynomial case. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.
Constraint reduction reformulations for projection algorithms with applications to wavelet construction
- Authors: Dao, Minh , Dizon, Neil , Hogan, Jeffrey , Tam, Matthew
- Date: 2021
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 190, no. 1 (2021), p. 201-233
- Full Text:
- Reviewed:
- Description: We introduce a reformulation technique that converts a many-set feasibility problem into an equivalent two-set problem. This technique involves reformulating the original feasibility problem by replacing a pair of its constraint sets with their intersection, before applying Pierra’s classical product space reformulation. The step of combining the two constraint sets reduces the dimension of the product spaces. We refer to this technique as the constraint reduction reformulation and use it to obtain constraint-reduced variants of well-known projection algorithms such as the Douglas–Rachford algorithm and the method of alternating projections, among others. We prove global convergence of constraint-reduced algorithms in the presence of convexity and local convergence in a nonconvex setting. In order to analyze convergence of the constraint-reduced Douglas–Rachford method, we generalize a classical result which guarantees that the composition of two projectors onto subspaces is a projector onto their intersection. Finally, we apply the constraint-reduced versions of Douglas–Rachford and alternating projections to solve the wavelet feasibility problems and then compare their performance with their usual product variants. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
Gateaux differentiability revisited
- Authors: Abbasi, Malek , Kruger, Alexander , Théra, Michel
- Date: 2021
- Type: Text , Journal article
- Relation: Applied Mathematics and Optimization Vol. 84, no. 3 (2021), p. 3499-3516
- Relation: http://purl.org/au-research/grants/arc/DP160100854
- Full Text:
- Reviewed:
- Description: We revisit some basic concepts and ideas of the classical differential calculus and convex analysis extending them to a broader frame. We reformulate and generalize the notion of Gateaux differentiability and propose new notions of generalized derivative and generalized subdifferential in an arbitrary topological vector space. Meaningful examples preserving the key properties of the original notion of derivative are provided. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.
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.
Lipschitz modulus of linear and convex inequality systems with the Hausdorff metric
- Authors: Beer, Gerald , Cánovas, M. J. , López, Marco , Parra, Juan
- Date: 2021
- Type: Text , Journal article
- Relation: Mathematical Programming Vol. 189, no. 1-2 (2021), p. 75-98. https://purl.org/au-research/grants/arc/DP180100602
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: This paper analyzes the Lipschitz behavior of the feasible set mapping associated with linear and convex inequality systems in Rn. To start with, we deal with the parameter space of linear (finite/semi-infinite) systems identified with the corresponding sets of coefficient vectors, which are assumed to be closed subsets of Rn+1. In this framework the size of perturbations is measured by means of the (extended) Hausdorff distance. A direct antecedent, extensively studied in the literature, comes from considering the parameter space of all linear systems with a fixed index set, T, where the Chebyshev (extended) distance is used to measure perturbations. In the present work we propose an appropriate indexation strategy which allows us to establish the equality of the Lipschitz moduli of the feasible set mappings in both parametric contexts, as well as to benefit from existing results in the Chebyshev setting for transferring them to the Hausdorff one. In a second stage, the possibility of perturbing directly the set of coefficient vectors of a linear system leads to new contributions on the Lipschitz behavior of convex systems via linearization techniques. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society. Correction: The article “Lipschitz modulus of linear and convex inequality systems with the Hausdorff metric”, written by Beer,G., Cánovas, M.J., López, M.A., Parra, J.was originally published Online First without Open Access. After publication in volume 189, issue 1–2, page 75–98 the author decided to opt for Open Choice and to make the article an Open Access publication. Therefore, the copyright of the article has been changed to © The Author(s) 2020 and the article is forthwith distributed under the terms of the Creative Commons Attribution 4.0 International License. https://doi.org/10.1007/s10107-021-01751-x
- Description: This paper analyzes the Lipschitz behavior of the feasible set mapping associated with linear and convex inequality systems in Rn. To start with, we deal with the parameter space of linear (finite/semi-infinite) systems identified with the corresponding sets of coefficient vectors, which are assumed to be closed subsets of Rn+1. In this framework the size of perturbations is measured by means of the (extended) Hausdorff distance. A direct antecedent, extensively studied in the literature, comes from considering the parameter space of all linear systems with a fixed index set, T, where the Chebyshev (extended) distance is used to measure perturbations. In the present work we propose an appropriate indexation strategy which allows us to establish the equality of the Lipschitz moduli of the feasible set mappings in both parametric contexts, as well as to benefit from existing results in the Chebyshev setting for transferring them to the Hausdorff one. In a second stage, the possibility of perturbing directly the set of coefficient vectors of a linear system leads to new contributions on the Lipschitz behavior of convex systems via linearization techniques. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
Logarithmically improved regularity criterion for the 3D Hall-MHD equations
- Authors: Gala, Sadek , Théra, Michel
- Date: 2021
- Type: Text , Journal article
- Relation: Computational and Applied Mathematics Vol. 40, no. 7 (2021), p.
- Full Text:
- Reviewed:
- Description: In this work, we study the blow-up criterion of the smooth solutions of three-dimensional incompressible Hall-magnetohydrohynamics equations (in short, Hall-MHD). We obtain a logarithmically improved regularity criterion of smooth solutions in terms of the B˙∞,∞0 norm. We improve the blow-up criterion for smooth solutions established in Ye (Appl Anal 96:2669–2683, 2016). © 2021, SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional.
Necessary and sufficient optimality conditions in DC semi-infinite programming
- Authors: Correa, Rafael , López, Marco , Pérez-Aros, Pedro
- Date: 2021
- Type: Text , Journal article
- Relation: SIAM Journal on Optimization Vol. 31, no. 1 (2021), p. 837-865
- Full Text:
- Reviewed:
- Description: This paper deals with particular families of DC optimization problems involving suprema of convex functions. We show that the specific structure of this type of function allows us to cover a variety of problems in nonconvex programming. Necessary and sufficient optimality conditions for these families of DC optimization problems are established, where some of these structural features are conveniently exploited. More precisely, we derive necessary and sufficient conditions for (global and local) optimality in DC semi-infinite programming and DC cone-constrained optimization, under natural constraint qualifications. Finally, a penalty approach to DC abstract programming problems is developed in the last section. © 2021 Society for Industrial and Applied Mathematics
On a semismooth* Newton method for solving generalized equations
- Authors: Gfrerer, Helmut , Outrata, Jiri
- Date: 2021
- Type: Text , Journal article
- Relation: SIAM Journal on Optimization Vol. 31, no. 1 (2021), p. 489-517
- Relation: https://doi.org/10.1137/19M1257408
- Full Text:
- Reviewed:
- Description: In the paper, a Newton-type method for the solution of generalized equations (GEs) is derived, where the linearization concerns both the single-valued and the multivalued part of the considered GE. The method is based on the new notion of semismoothness\ast, which, together with a suitable regularity condition, ensures the local superlinear convergence. An implementable version of the new method is derived for a class of GEs, frequently arising in optimization and equilibrium models. © 2021 Society for Industrial and Applied Mathematics
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
A pupil-positioning method based on the starburst model
- Authors: Yu, Pingping , Duan, Wenjie , Sun, Yi , Cao, Ning , Wang, Zhenzhou , Lu, Guojun
- Date: 2020
- Type: Text , Journal article
- Relation: Cmc-Computers Materials & Continua Vol. 64, no. 2 (2020), p. 1199-1217
- Full Text:
- Reviewed:
- Description: Human eye detection has become an area of interest in the field of computer vision with an extensive range of applications in human-computer interaction, disease diagnosis, and psychological and physiological studies. Gaze-tracking systems are an important research topic in the human-computer interaction field. As one of the core modules of the head-mounted gaze-tracking system, pupil positioning affects the accuracy and stability of the system. By tracking eye movements to better locate the center of the pupil, this paper proposes a method for pupil positioning based on the starburst model. The method uses vertical and horizontal coordinate integral projections in the rectangular region of the human eye for accurate positioning and applies a linear interpolation method that is based on a circular model to the reflections in the human eye. In this paper, we propose a method for detecting the feature points of the pupil edge based on the starburst model, which clusters feature points and uses the RANdom SAmple Consensus (RANSAC) algorithm to perform ellipse fitting of the pupil edge to accurately locate the pupil center. Our experimental results show that the algorithm has higher precision, higher efficiency and more robustness than other algorithms and excellent accuracy even when the image of the pupil is incomplete.
- Description: Science and Technology Support Plan Project of Hebei Province (grant numbers 17210803D and 19273703D Science and Technology Spark Project of the Hebei Seismological Bureau (grant number DZ20180402056) Education Department of Hebei Province (grant number QN2018095) Polytechnic College of Hebei University of Science and Technology
An existence result for quasi-equilibrium problems via Ekeland’s variational principle
- Authors: Cotrina, John , Théra, Michel , Zúñiga, Javier
- Date: 2020
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 187, no. 2 (2020), p. 336-355
- Full Text:
- Reviewed:
- Description: This paper deals with the existence of solutions to equilibrium and quasi-equilibrium problems without any convexity assumption. Coverage includes some equivalences to the Ekeland variational principle for bifunctions and basic facts about transfer lower continuity. An application is given to systems of quasi-equilibrium problems. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
- Description: Research of M. Théra is supported by the Australian Research Council (ARC) Grant DP160100854 and benefited from the support of the FMJH Program PGMO and from the support of EDF. http://purl.org/au-research/grants/arc/DP160100854
On computation of optimal strategies in oligopolistic markets respecting the cost of change
- Authors: Outrata, Jiri , Valdman, Jan
- Date: 2020
- Type: Text , Journal article
- Relation: Mathematical Methods of Operations Research Vol. 92, no. 3 (2020), p. 489-509
- Relation: http://purl.org/au-research/grants/arc/DP160100854
- Full Text:
- Reviewed:
- Description: The paper deals with a class of parameterized equilibrium problems, where the objectives of the players do possess nonsmooth terms. The respective Nash equilibria can be characterized via a parameter-dependent variational inequality of the second kind, whose Lipschitzian stability, under appropriate conditions, is established. This theory is then applied to evolution of an oligopolistic market in which the firms adapt their production strategies to changing input costs, while each change of the production is associated with some “costs of change”. We examine both the Cournot-Nash equilibria as well as the two-level case, when one firm decides to take over the role of the Leader (Stackelberg equilibrium). The impact of costs of change is illustrated by academic examples. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.
On the Aubin property of solution maps to parameterized variational systems with implicit constraints
- Authors: Gfrerer, Helmut , Outrata, Jiri
- Date: 2020
- Type: Text , Journal article
- Relation: Optimization Vol. 69, no. 7-8 (2020), p. 1681-1701
- Relation: http://purl.org/au-research/grants/arc/DP160100854
- Full Text:
- Reviewed:
- Description: In the paper, a new sufficient condition for the Aubin property to a class of parameterized variational systems is derived. In these systems, the constraints depend both on the parameter as well as on the decision variable itself and they include, e.g. parameter-dependent quasi-variational inequalities and implicit complementarity problems. The result is based on a general condition ensuring the Aubin property of implicitly defined multifunctions which employs the recently introduced notion of the directional limiting coderivative. Our final condition can be verified, however, without an explicit computation of these coderivatives. The procedure is illustrated by an example. © 2019, © 2019 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group.
- Description: The research of the first author was supported by the Austrian Science Fund (FWF) under grant P29190-N32. The research of the second author was supported by the Grant Agency of the Czech Republic, Project 17-04301S and the Australian Research Council, Project 10.13039/501100000923DP160100854.
Polytopes close to being simple
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 64, no. 1 (2020), p. 200-215
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: It is known that polytopes with at most two nonsimple vertices are reconstructible from their graphs, and that d-polytopes with at most d- 2 nonsimple vertices are reconstructible from their 2-skeletons. Here we close the gap between 2 and d- 2 , showing that certain polytopes with more than two nonsimple vertices are reconstructible from their graphs. In particular, we prove that reconstructibility from graphs also holds for d-polytopes with d+ k vertices and at most d- k+ 3 nonsimple vertices, provided k
Refining the partition for multifold conic optimization problems
- Authors: Ramirez, Hector , Roshchina, Vera
- Date: 2020
- Type: Text , Journal article
- Relation: Optimization Vol. 69, no. 11 (2020), p. 2489-2507
- Full Text:
- Reviewed:
- Description: In this paper, we give a unified treatment of two different definitions of complementarity partition of multifold conic programs introduced independently in Bonnans and Ramirez [Perturbation analysis of second-order cone programming problems, Math Program. 2005;104(2-30):205-227] for conic optimization problems, and in Pena and Roshchina [A complementarity partition theorem for multifold conic systems, Math Program. 2013;142(1-2):579-589] for homogeneous feasibility problems. We show that both can be treated within the same unified geometric framework and extend the latter notion to optimization problems. We also show that the two partitions do not coincide, and their intersection gives a seven-set index partition. Finally, we demonstrate that the partitions are preserved under the application of nonsingular linear transformations, and in particular, that a standard conversion of a second-order cone program into a semidefinite programming problem preserves the partitions.
- Description: This research was partially supported by ANID (Chile) under REDES project number 180032 and by the Australian Research Council grant DE150100240. The second author was supported by FONDECYT (Fondo de Fomento al Desarrollo Cientifico y Tecnologico) regular projects 1160204 and 1201982, and Basal Program CMM-AFB 170001 (Comision Nacional de Investigacion Cientifica y Tecnologica), all from ANID (Chile).
A counterexample to De Pierro's conjecture on the convergence of under-relaxed cyclic projections
- Authors: Cominetti, Roberto , Roshchina, Vera , Williamson, Andrew
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Vol. 68, no. 1 (2019), p. 3-12
- Full Text:
- Reviewed:
- Description: The convex feasibility problem consists in finding a point in the intersection of a finite family of closed convex sets. When the intersection is empty, a best compromise is to search for a point that minimizes the sum of the squared distances to the sets. In 2001, de Pierro conjectured that the limit cycles generated by the ε-under-relaxed cyclic projection method converge when ε ↓ 0 towards a least squares solution. While the conjecture has been confirmed under fairly general conditions, we show that it is false in general by constructing a system of three compact convex sets in R3 for which the ε-under-relaxed cycles do not converge. © 2018 Informa UK Limited, trading as Taylor & Francis Group.
Calmness of partially perturbed linear systems with an application to the central path
- Authors: Cánovas, Maria , Hall, Julian , López, Marco , Parra, Juan
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Vol. 68, no. 2-3 (2019), p. 465-483
- Full Text:
- Reviewed:
- Description: In this paper we develop point-based formulas for the calmness modulus of the feasible set mapping in the context of linear inequality systems with a fixed abstract constraint and (partially) perturbed linear constraints. The case of totally perturbed linear systems was previously analyzed in [Canovas MJ, Lopez MA, Parra J, et al. Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 2014;22:375-389, Section 5]. We point out that the presence of such an abstract constraint yields the current paper to appeal to a notable different methodology with respect to previous works on the calmness modulus in linear programming. The interest of this model comes from the fact that partially perturbed systems naturally appear in many applications. As an illustration, the paper includes an example related to the classical central path construction. In this example we consider a certain feasible set mapping whose calmness modulus provides a measure of the convergence of the central path. Finally, we underline the fact that the expression for the calmness modulus obtained in this paper is (conceptually) implementable as far as it only involves the nominal data.
Characterizations of nonsmooth robustly quasiconvex functions
- Authors: Bui, Hoa , Khanh, Pham , Tran, Thi
- Date: 2019
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 180, no. 3 (2019), p. 775-786
- Full Text:
- Reviewed:
- Description: Two criteria for the robust quasiconvexity of lower semicontinuous functions are established in terms of Fréchet subdifferentials in Asplund spaces. The first criterion extends to such spaces a result established by Barron et al. (Discrete Contin Dyn Syst Ser B 17:1693–1706, 2012). The second criterion is totally new even if it is applied to lower semicontinuous functions on finite-dimensional spaces. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
Convexity and closedness in stable robust duality
- Authors: Dinh, Nguyen , Goberna, Miguel , López, Marco , Volle, Michel
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 13, no. 2 (2019), p. 325-339
- Relation: http://purl.org/au-research/grants/arc/DP160100854
- Full Text:
- Reviewed:
- Description: The paper deals with optimization problems with uncertain constraints and linear perturbations of the objective function, which are associated with given families of perturbation functions whose dual variable depends on the uncertainty parameters. More in detail, the paper provides characterizations of stable strong robust duality and stable robust duality under convexity and closedness assumptions. The paper also reviews the classical Fenchel duality of the sum of two functions by considering a suitable family of perturbation functions.