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.
An augmented subgradient method for minimizing nonsmooth DC functions
- Authors: Bagirov, Adil , Hoseini Monjezi, Najmeh , Taheri, Sona
- Date: 2021
- Type: Text , Journal article
- Relation: Computational Optimization and Applications Vol. 80, no. 2 (2021), p. 411-438
- Relation: http://purl.org/au-research/grants/arc/DP190100580
- Full Text: false
- Reviewed:
- Description: A method, called an augmented subgradient method, is developed to solve unconstrained nonsmooth difference of convex (DC) optimization problems. At each iteration of this method search directions are found by using several subgradients of the first DC component and one subgradient of the second DC component of the objective function. The developed method applies an Armijo-type line search procedure to find the next iteration point. It is proved that the sequence of points generated by the method converges to a critical point of the unconstrained DC optimization problem. The performance of the method is demonstrated using academic test problems with nonsmooth DC objective functions and its performance is compared with that of two general nonsmooth optimization solvers and five solvers specifically designed for unconstrained DC optimization. Computational results show that the developed method is efficient and robust for solving nonsmooth DC optimization problems. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, 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.
Generalised rational approximation and its application to improve deep learning classifiers
- Authors: Peiris, V , Sharon, Nir , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2021
- Type: Text , Journal article
- Relation: Applied Mathematics and Computation Vol. 389, no. (2021), p.
- Relation: https://purl.org/au-research/grants/arc/DP180100602
- Full Text: false
- Reviewed:
- Description: A rational approximation (that is, approximation by a ratio of two polynomials) is a flexible alternative to polynomial approximation. In particular, rational functions exhibit accurate estimations to nonsmooth and non-Lipschitz functions, where polynomial approximations are not efficient. We prove that the optimisation problems appearing in the best uniform rational approximation and its generalisation to a ratio of linear combinations of basis functions are quasiconvex even when the basis functions are not restricted to monomials. Then we show how this fact can be used in the development of computational methods. This paper presents a theoretical study of the arising optimisation problems and provides results of several numerical experiments. We apply our approximation as a preprocessing step to deep learning classifiers and demonstrate that the classification accuracy is significantly improved compared to the classification of the raw signals. © 2020
- Description: This research was supported by the Australian Research Council (ARC), Solving hard Chebyshev approximation problems through nonsmooth analysis (Discovery Project DP180100602 ). This research was partially sponsored by Tel Aviv-Swinburne Research Collaboration Grant (2019).
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.
Incremental DC optimization algorithm for large-scale clusterwise linear regression
- Authors: Bagirov, Adil , Taheri, Sona , Cimen, Emre
- Date: 2021
- Type: Text , Journal article
- Relation: Journal of Computational and Applied Mathematics Vol. 389, no. (2021), p. 1-17
- Relation: https://purl.org/au-research/grants/arc/DP190100580
- Full Text: false
- Reviewed:
- Description: The objective function in the nonsmooth optimization model of the clusterwise linear regression (CLR) problem with the squared regression error is represented as a difference of two convex functions. Then using the difference of convex algorithm (DCA) approach the CLR problem is replaced by the sequence of smooth unconstrained optimization subproblems. A new algorithm based on the DCA and the incremental approach is designed to solve the CLR problem. We apply the Quasi-Newton method to solve the subproblems. The proposed algorithm is evaluated using several synthetic and real-world data sets for regression and compared with other algorithms for CLR. Results demonstrate that the DCA based algorithm is efficient for solving CLR problems with the large number of data points and in particular, outperforms other algorithms when the number of input variables is small. © 2020 Elsevier B.V.
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
Treatment of multiple input uncertainties using the scaled boundary finite element method
- Authors: Dsouza, Shaima , Varghese, Tittu , Ooi, Ean Tat , Natarajan, Sundararajan , Bordas, Stephane
- Date: 2021
- Type: Text , Journal article
- Relation: Applied Mathematical Modelling Vol. 99, no. (2021), p. 538-554
- Full Text: false
- Reviewed:
- Description: This paper presents a non-intrusive scaled boundary finite element method to consider multiple input uncertainties, viz., material and geometry. The types of geometric uncertainties considered include the shape and size of inclusions. The inclusions are implicitly defined, and a robust framework is presented to treat the interfaces, which does not require explicit generation of a conforming mesh or special enrichment techniques. A polynomial chaos expansion is used to represent the input and the output uncertainties. The efficiency and the accuracy of the proposed framework are elucidated in detail with a few problems by comparing the results with the conventional Monte Carlo method. A sensitivity analysis based on Sobol’ indices using the developed framework is presented to identify the critical input parameter that has a higher influence on the output response. © 2021 Elsevier Inc.
A note on primal-dual stability in infinite linear programming
- Authors: Goberna, Miguel , López, Marco , Ridolfi, Andrea , Vera de Serio, Virginia
- Date: 2020
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 14, no. 8 (2020), p. 2247-2263
- Full Text: false
- Reviewed:
- Description: In this note we analyze the simultaneous preservation of the consistency (and of the inconsistency) of linear programming problems posed in infinite dimensional Banach spaces, and their corresponding dual problems, under sufficiently small perturbations of the data. We consider seven different scenarios associated with the different possibilities of perturbations of the data (the objective functional, the constraint functionals, and the right hand-side function), i.e., which of them are known, and remain fixed, and which ones can be perturbed because of their uncertainty. The obtained results allow us to give sufficient and necessary conditions for the coincidence of the optimal values of both problems and for the stability of the duality gap under the same type of perturbations. There appear substantial differences with the finite dimensional case due to the distinct topological properties of cones in finite and infinite dimensional Banach spaces. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.
- Description: Funding details: Australian Research Council, ARC, DP180100602: http://purl.org/au-research/grants/arc/DP180100602
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
An incremental nonsmooth optimization algorithm for clustering using L1 and L∞ norms
- Authors: Ordin, Burak , Bagirov, Adil , Mohebi, Ehsam
- Date: 2020
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 16, no. 6 (2020), p. 2757-2779
- Relation: http://purl.org/au-research/grants/arc/DP190100580
- Full Text: false
- Reviewed:
- Description: An algorithm is developed for solving clustering problems with the similarity measure defined using the L1and L∞ norms. It is based on an incremental approach and applies nonsmooth optimization methods to find cluster centers. Computational results on 12 data sets are reported and the proposed algorithm is compared with the X-means algorithm. ©
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.