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
Numerical Algorithms
Published in: Numerical Algorithms 4/2021

11-06-2020 | Original Paper

Nonmonotone inexact restoration approach for minimization with orthogonality constraints

Authors: Juliano B. Francisco, Douglas S. Gonçalves, Fermín S. V. Bazán, Lila L. T. Paredes

Published in: Numerical Algorithms | Issue 4/2021

Log in

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

search-config
loading …

Abstract

Minimizing a differentiable function restricted to the set of matrices with orthonormal columns finds applications in several fields of science and engineering. In this paper, we propose to solve this problem through a nonmonotone variation of the inexact restoration method consisting of two phases: restoration phase, aimed to improve feasibility, and minimization phase, aimed to decrease the function value in the tangent set of the constraints. For this, we give a suitable characterization of the tangent set of the orthogonality constraints, allowing us to (i) deal with the minimization phase efficiently and (ii) employ the Cayley transform to bring a point in the tangent set back to feasibility, leading to a SVD-free restoration phase. Based on previous global convergence results for the nonmonotone inexact restoration algorithm, it follows that any limit point of the sequence generated by the new algorithm is stationary. Moreover, numerical experiments on three different classes of the problem indicate that the proposed method is reliable and competitive with other recently developed methods.
previous article Analysis of optimal superconvergence of the local discontinuous Galerkin method for nonlinear fourth-order boundary value problems
next article Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

Dont have a licence yet? Then find out more about our products and how to get one 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

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+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
Appendix
Available only for authorised users
Footnotes
Literature
1.
Abrudan, T., Eriksson, J., Koivunen, V.: Steepest descent algorithms for optimization under unitary matrix constraint. IEEE Trans. Signal Process. 56(3), 1134–1147 (2008)MathSciNetCrossRef
2.
Absil, P.-A., Baker, C.G., Gallivan, K.A.: Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7(3), 303–330 (2007)MathSciNetCrossRef
3.
Absil, P.A., Mahony, R., Sepulchre, R.: Optimization algorithms on matrix manifolds. Princeton University Press, Princeton (2008)
4.
5.
Arouxét, B., Echebest, N.E., Pilotta, E.A.: Inexact Restoration method for nonlinear optimization without derivatives. J. Comput. Appl. Math. 290(15), 26–43 (2015)MathSciNetCrossRef
6.
7.
Birgin, E.G., Bueno, L.F., Martínez, J.M.: Assessing the reability of general-purpose inexact restoration methods. J. Comput. Appl. Math. 282, 1–16 (2015)MathSciNetCrossRef
8.
Birgin, E.G., Martínez, J.M., Raydan, Marcos: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10(4), 1196–1211 (2000)MathSciNetCrossRef
9.
Birgin, E.G., Martínez, J.M.: Local convergence of an inexact-restoration method and numerical experiments. J. Optim. Theory Appl. 127(2), 229–247 (2005)MathSciNetCrossRef
10.
Bueno, L.F., Martínez, J.M.: On the complexity of an inexact restoration method for constrained optimization. SIAM J. Optim. 30(1), 80–101 (2020)MathSciNetCrossRef
11.
Boumal, N., Mishra, B., Absil, P.-A., Sepulchre, R.: MAnopt, a Matlab Toolbox for optimization on manifolds. J. Mach. Learn. Res. 15, 1455–1459 (2014)MATH
12.
Bueno, L.F., Friedlander, A., Martínez, J.M., Sobral, F.N.C.: Inexact restoration method for derivative-free optimization with smooth constraints. SIAM J. Optim. 23(2), 1189–1213 (2013)MathSciNetCrossRef
13.
Bueno, L.F., Haeser, G., Martínez, J.M.: A flexible inexact-restoration method for constrained optimization. J. Optim. Theory Appl. 165, 188–208 (2015)MathSciNetCrossRef
14.
Cancès, E., Chakir, R., Maday, Y.: Numerical analysis of nonlinear eigenvalue problems. J. Sci. Comput. 45, 90–117 (2010)MathSciNetCrossRef
15.
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)MathSciNetCrossRef
16.
Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2), 303–353 (1998)MathSciNetCrossRef
17.
18.
Francisco, J.B., Viloche Bazán, F.S.: Nonmonotone algorithm for minimization on closed sets with application to minimization on Stiefel manifolds. J. Comp. and Appl. Math. 236(10), 2717–2727 (2012)MathSciNetCrossRef
19.
Francisco, J.B., Bazán, F.S.V., Weber Mendonça, M.: Non-monotone algorithm for minimization on arbitrary domains with applications to large-scale orthogonal Procrustes problem, Appl. Num. Math. 112, 51–64 (2017)CrossRef
20.
Francisco, J.B., Martínez, J.M., Martínez, L., Pisnitchenko, F.: Inexact restoration method for minimization problems arising in electronic structure calculations. Comput. Optim. Appl. 50, 555–590 (2011)MathSciNetCrossRef
21.
Fischer, A., Friedlander, A.: A new line search inexact restoration approach for nonlinear programming. Comput. Optim. Appl. 46, 333–346 (2010)MathSciNetCrossRef
22.
Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th ed. The Johns Hopkins University Press (2013)
23.
Helgaker, T., JøRgensen, J., Olsen, J.: Electronic - Structure theory. Wiley, New York (2000)
24.
Janin, R.: Directional derivative of the marginal function in non linear programming. In: Sensitivity, Stability and Parametric Analysis, Math. Program. Stud., pp. 110–126. Springer, Berlin (1984)
25.
Jiang, B., Dai, Y.H.: A framework of constraint preserving update schemes for optimization on Stiefel manifold. Math. Program., Ser. A 153(2), 535–575 (2015)MathSciNetCrossRef
26.
Journée, M., Nesterov, Y., Richtárik, P., Sepulchre, R.: Generalized power method for sparse principal component analysis. J. Mach. Learn. Res. 11, 517–553 (2010)MathSciNetMATH
27.
Manton, J.H.: Optimization algorithms exploiting unitary constraints. IEEE Trans. Signal Process. 50(3), 635–650 (2002)MathSciNetCrossRef
28.
Martínez, J.M., Pilotta, E.A.: Inexact restoration algorithm for constrained optimization. J. Optim. Theory App. 104(1), 135–163 (2000)MathSciNetCrossRef
29.
Martínez, J.M., Svaiter, B.F.: A practical optimality condition without constraint qualifications for nonlinear programming. J. Optimiz. Theory App. 118 (1), 117–133 (2003)MathSciNetCrossRef
30.
Nishimori, Y., Akaho, S.: Learning algorithms utilizing quasi-geodesic flows on the Stiefel manifold. Neurocomputing 67, 106–135 (2005)CrossRef
31.
Shariff, M.: A constrained conjugate gradient method and the solution of linear equations. Comp. Mathem. Appl. 30(11), 25–37 (1995)MathSciNetCrossRef
32.
Karas, E. W., Pilotta, E., Ribeiro, A.: Numerical comparison of merit function with filter criterion in inexact restoration algorithms using hard-spheres problems. Comput. Optim. Appl. 44, 427–441 (2009)MathSciNetCrossRef
33.
Kaya, C.Y.: Inexact restoration for Runge–Kutta discretization of optimal control problems. SIAM J. Numer. Anal. 48(4), 1492–1517 (2010)MathSciNetCrossRef
34.
Kohn, W.: Nobel lecture: electronic structure of matter–wave functions and density functionals. Rev. Modern Phys. 71(5), 1253–1266 (1999)CrossRef
35.
Krejić, N., Martínez, J.M.: Inexact restoration approach for minimization with inexact evaluation of the objective function. Mathematics of Computation 85, 1775–1791 (2016)MathSciNetCrossRef
36.
Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. Ser. A, 142, 397–434 (2013)
37.
Zhang, H., Hager, W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optimiz. 14(4), 1043–1056 (2004)MathSciNetCrossRef
38.
Zhao, Z., Bai, Z.-J., Jin, X.-Q.: A Riemannian Newton algorithm for nonlinear eigenvalue problems. SIAM J. Matrix Anal. Appl. 36(2), 752–774 (2015)MathSciNetCrossRef
39.
Zhu, X.: A feasible filter method for the nearest low-rank correlation matrix problem. Numer. Algorithm. 69, 763–784 (2015)MathSciNetCrossRef
Metadata
Title
Nonmonotone inexact restoration approach for minimization with orthogonality constraints
Authors
Juliano B. Francisco
Douglas S. Gonçalves
Fermín S. V. Bazán
Lila L. T. Paredes
Publication date
11-06-2020
Publisher
Springer US
Published in
Numerical Algorithms / Issue 4/2021
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-020-00948-z

Other articles of this Issue 4/2021

Numerical Algorithms 4/2021 Go to the issue

Original Paper

Halpern-type iterative process for solving split common fixed point and monotone variational inclusion problem between Banach spaces

Original Paper

On equivalence of three-parameter iterative methods for singular symmetric saddle-point problem

Original Paper

Accurate sampling formula for approximating the partial derivatives of bivariate analytic functions

Original Paper

A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems

Original Paper

Unconditional optimal error estimates of linearized backward Euler Galerkin FEMs for nonlinear Schrödinger-Helmholtz equations

Original Paper

A two-grid method for discontinuous Galerkin approximations to nonlinear Sobolev equations

Premium Partner

    Image Credits