October  2019, 15(4): 1795-1807. doi: 10.3934/jimo.2018123

Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints

School of Science, Nanjing University of Posts and Telecommunications, Nanjing, Jiangsu 210023, China

* Corresponding author: Xiaona Fan

Received  July 2017 Revised  May 2018 Published  August 2018

In this paper, we utilize a new homotopy method to solve generalized Nash equilibrium problem with equality and inequality constraints on unbounded sets. Based on the existing homotopy method, we establish a new homotopy equation by introducing a suitable perturbation on the equality constraint, the existence and the global convergence of homotopy path under certain assumptions have also been proved. In the proposed method, the initial point only needs to satisfy the inequality constraints. Compared with the existing homotopy method, this method expands the scope of the initial points and provides the convenience for solving generalized Nash equilibrium problem. The numerical results illustrate the effectiveness of this method.

Citation: Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
References:
[1]

E. L. Allgower and K. Georg, Numerical Continuation Method: An Introduction, Springer-Vergal, Berlin, New York, 1990. doi: 10.1007/978-3-642-61257-2.  Google Scholar

[2]

D. AusselR. Correa and M. Marechal, Gap functions for quasivariational inequalities and generalized Nash equilibrium problems, J. Optim. Theory Appl., 151 (2011), 474-488.  doi: 10.1007/s10957-011-9898-z.  Google Scholar

[3]

H. Dietrich, A smooth dual gap function solution to a class of quasivariational inequalities, J. Math. Anal. Appl., 235 (1999), 380-393.  doi: 10.1006/jmaa.1999.6405.  Google Scholar

[4]

A. DrevesF. FacchineiA. Fischer and M. Herrich, A new error bound result for Generalized Nash Equilibrium Problems and its algorithmic application, Comput. Optim. Appl., 59 (2014), 63-84.  doi: 10.1007/s10589-013-9586-z.  Google Scholar

[5]

A. DrevesF. FacchineiC. Kanzow and S. Sagratella, On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., 21 (2011), 1082-1108.  doi: 10.1137/100817000.  Google Scholar

[6]

F. FachhineiA. Fischer and M. Herrich, A family of Newton methods for nonsmooth constrained systems with nonisolated solutions, Math. Methods Oper. Res., 77 (2013), 433-443.  doi: 10.1007/s00186-012-0419-0.  Google Scholar

[7]

F. FacchineiA. Fischer and M. Herrich, An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions, Math. Program., 146 (2014), 1-36.  doi: 10.1007/s10107-013-0676-6.  Google Scholar

[8]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, Annals of Operations Research, 175 (2010), 177-211.  doi: 10.1007/s10479-009-0653-x.  Google Scholar

[9]

F. FacchineiC. Kanzow and S. K. Sagratella, The semismooth Newton method for the solution of quasi-variational inequalities, Computational Optimization and Applications, 62 (2015), 85-109.  doi: 10.1007/s10589-014-9686-4.  Google Scholar

[10]

F. Facchinei and J.-S. Pang, Nash equilibria: The variational approach, in Convex Optimization in Signal Processing and Communications, D. P. Palomar and Y. C. Eldar, eds., Cambridge University Press, Cambridge, (2010), 443–493.  Google Scholar

[11]

M. Fukushima, A class of gap functions for quasi-variational inequality problems, J. Ind. Manag. Optim., 3 (2007), 165-171.  doi: 10.3934/jimo.2007.3.165.  Google Scholar

[12]

N. HarmsT. Hoheisel and C. Kanzow, On a smooth dual gap function for a class of quasi-variational inequalities, J. Optim. Theory Appl., 163 (2014), 413-438.  doi: 10.1007/s10957-014-0536-4.  Google Scholar

[13]

N. HarmsC. Kanzow and O. Stein, Smoothness properties of a regularized gap function for quasivariational inequalities, Optim. Methods Softw., 29 (2014), 720-750.  doi: 10.1080/10556788.2013.841694.  Google Scholar

[14]

A. von Heusinger and C. Kanzow, Relaxation methods for generalized nash equilibrium problems with inexact line search, Journal of Optimization Theory and Applications, 143 (2009), 159-183.  doi: 10.1007/s10957-009-9553-0.  Google Scholar

[15]

J. B. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications, Environmental Modeling & Assessment, 5 (2000), 63-73.   Google Scholar

[16]

K. Kubota and M. Fukushima, Gap function approach to the generalized Nash equilibrium problem, J. Optim. Theory Appl., 144 (2010), 511-531.  doi: 10.1007/s10957-009-9614-4.  Google Scholar

[17]

M. M. Makela and P. Neittaanmaki, Nonsmooth Optimization, World Scientific, Singapore, 1992. doi: 10.1142/1493.  Google Scholar

[18]

R. B. Myerson, Nash equilibrium and the history of economic theory, Journal of Economic Literature, 37 (1999), 1067-1082.   Google Scholar

[19]

G. L. Naber, Topological methods in Euclidean spaces, Cambridge University Press, 1980.  Google Scholar

[20]

K. Taji, On gap functions for quasi-variational inequalities, Abstract Appl. Anal., 2008 (2008), Art. ID 531361, 7 pp. doi: 10.1155/2008/531361.  Google Scholar

[21]

Q. XuX. Dai and B. Yu, Solving generalized Nash equilibrium problem with equality and inequality constraints, Optimization Methods & Software, 24 (2009), 327-337.  doi: 10.1080/10556780802578884.  Google Scholar

show all references

References:
[1]

E. L. Allgower and K. Georg, Numerical Continuation Method: An Introduction, Springer-Vergal, Berlin, New York, 1990. doi: 10.1007/978-3-642-61257-2.  Google Scholar

[2]

D. AusselR. Correa and M. Marechal, Gap functions for quasivariational inequalities and generalized Nash equilibrium problems, J. Optim. Theory Appl., 151 (2011), 474-488.  doi: 10.1007/s10957-011-9898-z.  Google Scholar

[3]

H. Dietrich, A smooth dual gap function solution to a class of quasivariational inequalities, J. Math. Anal. Appl., 235 (1999), 380-393.  doi: 10.1006/jmaa.1999.6405.  Google Scholar

[4]

A. DrevesF. FacchineiA. Fischer and M. Herrich, A new error bound result for Generalized Nash Equilibrium Problems and its algorithmic application, Comput. Optim. Appl., 59 (2014), 63-84.  doi: 10.1007/s10589-013-9586-z.  Google Scholar

[5]

A. DrevesF. FacchineiC. Kanzow and S. Sagratella, On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., 21 (2011), 1082-1108.  doi: 10.1137/100817000.  Google Scholar

[6]

F. FachhineiA. Fischer and M. Herrich, A family of Newton methods for nonsmooth constrained systems with nonisolated solutions, Math. Methods Oper. Res., 77 (2013), 433-443.  doi: 10.1007/s00186-012-0419-0.  Google Scholar

[7]

F. FacchineiA. Fischer and M. Herrich, An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions, Math. Program., 146 (2014), 1-36.  doi: 10.1007/s10107-013-0676-6.  Google Scholar

[8]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, Annals of Operations Research, 175 (2010), 177-211.  doi: 10.1007/s10479-009-0653-x.  Google Scholar

[9]

F. FacchineiC. Kanzow and S. K. Sagratella, The semismooth Newton method for the solution of quasi-variational inequalities, Computational Optimization and Applications, 62 (2015), 85-109.  doi: 10.1007/s10589-014-9686-4.  Google Scholar

[10]

F. Facchinei and J.-S. Pang, Nash equilibria: The variational approach, in Convex Optimization in Signal Processing and Communications, D. P. Palomar and Y. C. Eldar, eds., Cambridge University Press, Cambridge, (2010), 443–493.  Google Scholar

[11]

M. Fukushima, A class of gap functions for quasi-variational inequality problems, J. Ind. Manag. Optim., 3 (2007), 165-171.  doi: 10.3934/jimo.2007.3.165.  Google Scholar

[12]

N. HarmsT. Hoheisel and C. Kanzow, On a smooth dual gap function for a class of quasi-variational inequalities, J. Optim. Theory Appl., 163 (2014), 413-438.  doi: 10.1007/s10957-014-0536-4.  Google Scholar

[13]

N. HarmsC. Kanzow and O. Stein, Smoothness properties of a regularized gap function for quasivariational inequalities, Optim. Methods Softw., 29 (2014), 720-750.  doi: 10.1080/10556788.2013.841694.  Google Scholar

[14]

A. von Heusinger and C. Kanzow, Relaxation methods for generalized nash equilibrium problems with inexact line search, Journal of Optimization Theory and Applications, 143 (2009), 159-183.  doi: 10.1007/s10957-009-9553-0.  Google Scholar

[15]

J. B. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications, Environmental Modeling & Assessment, 5 (2000), 63-73.   Google Scholar

[16]

K. Kubota and M. Fukushima, Gap function approach to the generalized Nash equilibrium problem, J. Optim. Theory Appl., 144 (2010), 511-531.  doi: 10.1007/s10957-009-9614-4.  Google Scholar

[17]

M. M. Makela and P. Neittaanmaki, Nonsmooth Optimization, World Scientific, Singapore, 1992. doi: 10.1142/1493.  Google Scholar

[18]

R. B. Myerson, Nash equilibrium and the history of economic theory, Journal of Economic Literature, 37 (1999), 1067-1082.   Google Scholar

[19]

G. L. Naber, Topological methods in Euclidean spaces, Cambridge University Press, 1980.  Google Scholar

[20]

K. Taji, On gap functions for quasi-variational inequalities, Abstract Appl. Anal., 2008 (2008), Art. ID 531361, 7 pp. doi: 10.1155/2008/531361.  Google Scholar

[21]

Q. XuX. Dai and B. Yu, Solving generalized Nash equilibrium problem with equality and inequality constraints, Optimization Methods & Software, 24 (2009), 327-337.  doi: 10.1080/10556780802578884.  Google Scholar

Table 1.  The numerical results of Example 3.1
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.8, 0.2, 0.5, 0.5)^T$ A1 0.049842 19 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6755\times 10^{-7}$
A2 0.068653 23 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $4.8879\times 10^{-7}$
$(0.6, 0.4, 0.5, 0.5)^T$ A1 0.032000 11 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.2632\times 10^{-7}$
A2 0.047000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $8.5698\times 10^{-7}$
$(0.3, 0.4, 0.6, 0.5)^T$ A1 0.015000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.3661\times 10^{-7}$
$(0.3, 0.4, 0.5, 0.4)^T$ A1 0.016000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $ 5.6057\times 10^{-7}$
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.8, 0.2, 0.5, 0.5)^T$ A1 0.049842 19 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6755\times 10^{-7}$
A2 0.068653 23 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $4.8879\times 10^{-7}$
$(0.6, 0.4, 0.5, 0.5)^T$ A1 0.032000 11 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.2632\times 10^{-7}$
A2 0.047000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $8.5698\times 10^{-7}$
$(0.3, 0.4, 0.6, 0.5)^T$ A1 0.015000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.3661\times 10^{-7}$
$(0.3, 0.4, 0.5, 0.4)^T$ A1 0.016000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $ 5.6057\times 10^{-7}$
Table 2.  The numerical results of Example 3.2
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.7, 0.3, 0.3, 0.7)^T$ A1 0.017811 20 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.5142\times 10^{-7}$
A2 0.052286 23 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.2044\times 10^{-7}$
$(0.7, 0.3, 0.5, 0.5)^T$ A1 0.016000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.7536\times 10^{-7}$
A2 0.032000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.0169\times 10^{-7}$
$(0.6, 0.3, 0.6, 0.5)^T$ A1 0.016000 10 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $2.0758\times 10^{-7}$
$(0.6, 0.5, 0.6, 0.5)^T$ A1 0.015000 9 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $ 8.4904\times 10^{-7}$
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.7, 0.3, 0.3, 0.7)^T$ A1 0.017811 20 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.5142\times 10^{-7}$
A2 0.052286 23 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.2044\times 10^{-7}$
$(0.7, 0.3, 0.5, 0.5)^T$ A1 0.016000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.7536\times 10^{-7}$
A2 0.032000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.0169\times 10^{-7}$
$(0.6, 0.3, 0.6, 0.5)^T$ A1 0.016000 10 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $2.0758\times 10^{-7}$
$(0.6, 0.5, 0.6, 0.5)^T$ A1 0.015000 9 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $ 8.4904\times 10^{-7}$
Table 3.  The numerical results of Example 3.3
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.8, 0.2, 0.2, 0.8)^T$ A1 0.060919 27 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $2.9945\times 10^{-7}$
A2 0.102540 102 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.3449\times 10^{-7}$
$(0.9, 0.1, 0.1, 0.9)^T$ A1 0.036579 33 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $4.5683\times 10^{-7}$
A2 0.097798 128 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.6001\times 10^{-7}$
$(0.3, 0.8, 0.4, 0.5)^T$ A1 0.050146 18 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $8.8414\times 10^{-7}$
$(0.2, 0.6, 0.3, 0.4)^T$ A1 0.032000 22 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $ 1.6179\times 10^{-7}$
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.8, 0.2, 0.2, 0.8)^T$ A1 0.060919 27 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $2.9945\times 10^{-7}$
A2 0.102540 102 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.3449\times 10^{-7}$
$(0.9, 0.1, 0.1, 0.9)^T$ A1 0.036579 33 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $4.5683\times 10^{-7}$
A2 0.097798 128 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.6001\times 10^{-7}$
$(0.3, 0.8, 0.4, 0.5)^T$ A1 0.050146 18 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $8.8414\times 10^{-7}$
$(0.2, 0.6, 0.3, 0.4)^T$ A1 0.032000 22 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $ 1.6179\times 10^{-7}$
Table 4.  The numerical results of Example 3.4
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.8, 0.2, 0.2, 0.8)^T$ A1 0.090294 34 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.9066\times 10^{-7}$
A2 0.170305 79 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $8.9245\times 10^{-7}$
$(0.7, 0.3, 0.3, 0.7)^T$ A1 0.074322 31 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.4454\times 10^{-7}$
A2 0.096164 64 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $6.9529\times 10^{-7}$
$(0.3, 0.8, 0.4, 0.7)^T$ A1 0.071024 32 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $7.7431\times 10^{-7}$
$(0.4, 0.5, 0.4, 0.5)^T$ A1 0.031000 17 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $ 1.3352\times 10^{-7}$
$x_0$ method CPU IT $x^*$ $\mu^*$
$(0.8, 0.2, 0.2, 0.8)^T$ A1 0.090294 34 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.9066\times 10^{-7}$
A2 0.170305 79 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $8.9245\times 10^{-7}$
$(0.7, 0.3, 0.3, 0.7)^T$ A1 0.074322 31 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.4454\times 10^{-7}$
A2 0.096164 64 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $6.9529\times 10^{-7}$
$(0.3, 0.8, 0.4, 0.7)^T$ A1 0.071024 32 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $7.7431\times 10^{-7}$
$(0.4, 0.5, 0.4, 0.5)^T$ A1 0.031000 17 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $ 1.3352\times 10^{-7}$
[1]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[2]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171

[3]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345

[4]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[5]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[6]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[7]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[8]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[9]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[10]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[11]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[12]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345

[13]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346

[14]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[15]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[16]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[17]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[18]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[19]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[20]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (171)
  • HTML views (1126)
  • Cited by (0)

Other articles
by authors

[Back to Top]