Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Algorithmic Issues in Energy-Efficient Computation Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Extended Separating Plane Algorithm and NSO-Solutions of PageRank Problem

Author : Evgeniya Vorontsova

Published in: Discrete Optimization and Operations Research

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The separating plane method with additional clippings and stockpiling (SPACLIP-S) for nonsmooth optimization is proposed in this paper. Both the theoretical and experimental investigations of the method showed that this method is efficient and widely applicable to nonsmooth optimization problems with convex objective functions. Computational experiments demonstrated a rather high performance of SPACLIP-S when applied to the Web page ranking problem. Web page ranking approach is widely used by search engines such as Google and Yandex to order Web pages. Page ranking problem is one of the most important problems in information retrivial due to wide range of applications. In this paper an iterative regularization method with a new penalty function for solving PageRank problem is also presented. Finally, experimental results of comparison of SPACLIP-S and other algorithms for solving test PageRank problems are provided.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Robust Leaky-LMS Algorithm for Sparse System Identification
next chapter Location, Pricing and the Problem of Apollonius
Literature
1.
Shary, S.P.: Maximum consistency method for data fitting under interval uncertainty. J. Glob. Optim. 63, 1–16 (2015)MathSciNetCrossRef
2.
Shor, N.Z.: Minimization Methods for Non-differentiable Functions. Springer Science & Business Media, Berlin (2012)
3.
Jung, M., Kang, M.: Efficient nonsmooth nonconvex optimization for image restoration and segmentation. J. Sci. Comput. 62(2), 336–370 (2015)MathSciNetCrossRefMATH
4.
Clarke, F.N., Ledyaev, Y.S., Stern, R.J., Wolenski, P.R.: Nonsmooth Analysis and Control Theory. Springer, Heidelberg (1998)MATH
5.
Powell, M.J.D.: A View of Algorithms for Optimization without Derivatives. DAMTp. 2007/NA03. Technical Report, Cambridge University (2007)
6.
7.
Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific Publishing Co., Singapore (1992)
8.
9.
Haarala, N., Miettinen, K., Mäkelä, M.M.: Globally convergent limited memory bundle method for large-scale nonsmooth optimization. Math. Program. 109, 181–205 (2007)MathSciNetCrossRefMATH
10.
11.
Bagirov, A., Karmitsa, N., Mäkelä, M.M.: Introduction to Nonsmooth Optimization: Theory, Practice and Software. Springer, Heidelberg (2014)CrossRefMATH
12.
Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods. Fundamental Principles of Mathematical Sciences. Springer, Berlin (1993)MATH
13.
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley-Interscience, New York (1983)MATH
14.
Shor, N.Z.: Minimization Methods for Non-differentiable Functions. Springer, New York (1985)CrossRefMATH
15.
Polyak, B.T.: Minimization of nonsmooth functionals. Comp. Math. Math. Phys. 9, 509–521 (1969)MathSciNet
16.
Nurminski, E.A.: Envelope stepsize control for iterative algorithms based on Fejer processes with attractants. Optimiz. Meth. Softw. 25, 97–108 (2010)MathSciNetCrossRefMATH
17.
18.
de Oliveira, W., Sagastizábal, C.: Level bundle methods for oracles with on-demand accuracy. Optim. methods Softw. 29(6), 1180–1209 (2014)MathSciNetCrossRefMATH
19.
de Oliveira, W., Sagastizábal, C.: Bundle methods in the XXIst century: a Birds’-eye view. Pesquisa Operacional 34(3), 647–670 (2014)CrossRef
20.
de Oliveira, W., Sagastizábal, C., Lemaréchal, C.: Convex proximal bundle methods in depth: a unified analysis for inexact oracles. Math. Program. 148, 241–277 (2014)MathSciNetCrossRefMATH
21.
Nurminski, E.A.: Separating plane algorithms for convex optimization. Math. Program. 76, 373–391 (1997)MathSciNetMATH
22.
Nurminski, E.A.: Separating plane method with bounded memory for the solution of convex nonsmooth optimization problems. Comput. Meth. Program. 7, 133–137 (2006)
23.
Vorontsova, E.A.: A projective separating plane method with additional clipping for non-smooth optimization. WSEAS Trans. Math. 13, 115–121 (2014)
24.
Vorontsova, E.A., Nurminski, E.A.: Synthesis of cutting and separating planes in a nonsmooth optimization method. Cybern. Syst. Anal. 51(4), 619–631 (2015)MathSciNetCrossRefMATH
25.
Nurminski, E.: Multiple cuts in separating plane algorithms. In: Kochetov, Y., et al (eds.) DOOR 2016. LNCS, vol. 9869, pp. 430–440. Springer, Switzerland (2016)
26.
27.
28.
Vorontsova, E.A.: Modified fast line-search algorithm for non-smooth optimization. Inf. Sci. Control Syst. 2, 39–48 (2012). (in Russian)
29.
Nurminskii, E.A.: Convergence of the suitable affine subspace method for finding the least distance to a simplex. Comp. Math. Math. Physics. 45(11), 1915–1922 (2005)MathSciNet
30.
31.
Page, L., Brin, S., Motwani, R., Winograd, T.: The Pagerank Citation Ranking: Bringing Order to the Web. Technical Report, Computer Science Department, Stanford University (1998)
32.
33.
Bogolubsky, L., Dvurechensky, P., Gasnikov, A., Gusev, G., Nesterov, Y., Raigorodskii, A., Tikhonov, A., Zhukovskii, M.: Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods (2016). arXiv:​1603.​00717
34.
Teo, C.H., Vishwanathan, S.V.N., Smola, A.J., Le, Q.V.: Bundle methods for regularized risk minimization. J. Mach. Learn. Res. 11, 311–365 (2010)MathSciNetMATH
35.
Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst. 30, 107–117 (1998)CrossRef
36.
Langville, A.N., Meyer, C.D.: Googles PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, Princeton (2011)MATH
37.
38.
39.
Polyak, B.T., Timonina, A.V.: PageRank: new regularizations and simulation models. In: Proceedings of 18th IFAC World Congress, pp. 11202–11207. Milano, Italy (2011)
40.
Polyak, B.T., Tremba, A.A.: Regularization-based solution of the PageRank problem for large matrices. Autom. Remote Control 73(11), 1877–1894 (2012)MathSciNetCrossRefMATH
41.
Gasnikov, A.V., Dmitriev, D.Y.: On efficient randomized algorithms for finding the PageRank vector. Comp. Math. Math. Phys. 55(3), 349–365 (2015)MathSciNetCrossRefMATH
42.
Nesterov, Y., Nemirovski, A.: Finding the stationary states of Markov chains by iterative methods. Appl. Math. Comput. 255, 58–65 (2015)MathSciNetMATH
43.
44.
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006)MATH
45.
Anikin, A., Gasnikov, A., Gornov, A., Kamzolov, D., Maximov, Y., Nesterov, Y.: Effective Numerical Methods for Huge-Scale Linear Systems with Double-Sparsity and Applications to PageRank (2016). arXiv:​1508.​07607v3
Metadata
Title
Extended Separating Plane Algorithm and NSO-Solutions of PageRank Problem
Author
Evgeniya Vorontsova
Copyright Year
2016
Book
Discrete Optimization and Operations Research

Print ISBN: 978-3-319-44913-5

Electronic ISBN: 978-3-319-44914-2

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-44914-2_43

Premium Partner

    Image Credits