nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

7. Local Search for Nonsmooth DC Optimization with DC Equality and Inequality Constraints

Erschienen in: Numerical Nonsmooth Optimization

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The chapter addresses the nonsmooth optimization problem with the objective function and equality and inequality constraints given by DC functions. First, the original problem is reduced to a problem without constraints by the exact penalization theory, so that the reduced (penalized) problem is also a DC minimization problem. Then, we develop a local search (LS) scheme which is based, first, on the linearization of the basic nonconvexity of the penalized problem and, second, on consecutive solutions of linearized (convex) problems. Convergence properties of the LS scheme are also investigated, which, in particular, yield that the sequence produced by LSM converges to a solution of the problem linearized at the limit point just. Moreover, the cluster point of the sequence is the KKT point for the original problem with the Lagrange multipliers provided by an auxiliary linearized problem. Finally, on the base of the developed theory several new stopping criteria are elaborated, which allow to transform the local search scheme into a local search algorithm.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Gradient Sampling Methods for Nonsmooth Optimization

Nächstes Kapitel Bundle Methods for Nonsmooth DC Optimization

Benson, H., Sen, A., Shanno, D., Vanderbei, R.: Interior-point algorithms, penalty methods and equilibrium problems. Comput. Optim. Appl. 34(2), 155–182 (2006)CrossRefMathSciNetMATH

Bonnans, J.F., Gilbert, J., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization. Theoretical and Practical Aspects. Springer, Berlin (2006)

Burke, J.: An exact penalization viewpoint of constrained optimization. SIAM J. Control Optim. 29(4), 968–998 (1991)CrossRefMathSciNetMATH

Byrd, R., Marazzi, M., Nocedal, J.: On the convergence of Newton iterations to non-stationary points. Math. Program. 99(1), 127–148 (2004)CrossRefMathSciNetMATH

Byrd, R., Nocedal, J., Waltz, R.: Steering exact penalty methods for nonlinear programming. Optim. Methods Softw. 23(2), 197–213 (2008)CrossRefMathSciNetMATH

Byrd, R., Lopez-Calva, G., Nocedal, J.: A line search exact penalty method using steering rules. Math. Program. 133(1), 39–73 (2012)CrossRefMathSciNetMATH

Clarke, F.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)MATH

Demyanov, V.: Extremum’s conditions and variational calculus. High School Edition, Moscow (2005). (in Russian)

Demyanov, V., Vasiliev, L.: Nondifferentiable Optimization. Translation Series in Mathematics and Engineering. Springer, New York (1985)

10.

Demyanov, V., Rubinov, A.: Constructive Nonsmooth Analysis. Peter Lang, Frankfurt (1995)MATH

11.

Di Pillo, G., Grippo, L.: Exact penalty functions in constrained optimization. SIAM J. Control Optim. 27, 1333–1360 (1989)CrossRefMathSciNetMATH

12.

Di Pillo, G., Lucidi, S., Rinaldi, F.: An approach to constrained global optimization based on exact penalty functions. J. Global Optim. 54, 251–260 (2012)CrossRefMathSciNetMATH

13.

Di Pillo, G., Lucidi, S., Rinaldi, F.: A derivative-free algorithm for constrained global optimization based on exact penalty functions. J. Optim. Theory Appl. 164, 862–882 (2015)CrossRefMathSciNetMATH

14.

Dür, M., Hiriart-Urruty, J.B.: Testing copositivity with the help of difference-of-convex optimization. Math. Program. 140(Ser. B), 31–43 (2013)

15.

Eremin, I.: The penalty method in convex programming. Soviet Math. Dokl. 8, 459–462 (1966)MATH

16.

Floudas, C.: Deterministic Global Optimization: Theory, Methods and Application. Kluwer, Dordrecht (1999)

17.

Floudas, C., Pardalos, P. (eds.): Frontiers in Global Optimization. Springer, Dordrecht (2004)MATH

18.

Gaudioso, M., Gruzdeva, T., Strekalovsky, A.: On numerical solving the spherical separability problem. J. Global Optim. 66, 21–34 (2016)CrossRefMathSciNetMATH

19.

Gruzdeva, T., Strekalovsky, A.: Local search in problems with nonconvex constraints. Comput. Math. Math. Phys. 47(3), 381–396 (2007)CrossRefMathSciNetMATH

20.

Gruzdeva, T., Strekalovsky, A.: Clique problems and nonconvex optimization. Nauka, Novosibirsk (2014). (in Russian)

21.

Gruzdeva, T., Strekalovsky, A.: On solving the sum-of-ratios problem. Appl. Math. Comput. 318, 260–269 (2018)MathSciNetMATH

22.

Han, S., Mangasarian, O.: Exact penalty functions in nonlinear programming. Math. Program. 17(3), 251–269 (1979)CrossRefMathSciNetMATH

23.

Hiriart-Urruty, J.B.: Generalized differentiability, duality and optimization for problems dealing with difference of convex functions. In: Ponstein, J. (ed.) Convexity and Duality in Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 256, pp. 37–70. Springer, Berlin (1985)CrossRef

24.

Hiriart-Urruty, J.B.: Optimisation et Analyse Convexe. Presses Universitaires de France, Paris (1998). (in French)MATH

25.

Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993)CrossRefMATH

26.

Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin (1996)CrossRefMATH

27.

Kruger, A.: Error bounds and metric subregularity. Optimization 64(1), 49–79 (2015)CrossRefMathSciNetMATH

28.

Kruger, A.: Nonlinear metric subregularity. J. Optim. Theory Appl. 171(3), 820–855 (2016)CrossRefMathSciNetMATH

29.

Le Thi, H.A.: D.C. programming for solving a class of global optimization problems via reformulation by exact penalty. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) Global Optimization and Constraint Satisfaction. Lecture Notes in Computer Science, vol. 2861, pp. 87–101. Springer, Berlin (2003)CrossRef

30.

Le Thi, H.A., Pham Dinh, T.: Solving a class of linearly constrained indefinite quadratic problems by DCA algorithm. J. Global Optim. 11, 253–285 (1997)CrossRefMathSciNetMATH

31.

Le Thi, H.A., Pham Dinh, T.: The DC programming and DCA revisited with DC model of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)CrossRefMathSciNetMATH

32.

Le Thi, H.A., Pham Dinh, T.: DC programming in communication systems: challenging problems and methods. Vietnam J. Comput. Sci. 1(1), 15–28 (2014)CrossRef

33.

Le Thi, H.A., Pham Dinh, T., Van Ngai, H.: Exact penalty and error bounds in DC programming. J. Global Optim. 52(3), 509–535 (2012)CrossRefMathSciNetMATH

34.

Le Thi, H.A., Ngai Huynh, V., Pham Dinh, T.: DC programming and DCA for general DC programs. In: Advanced Computational Methods for Knowledge Engineering, pp. 15–35. Springer, New York (2014)

35.

Mascarenhas, W.: The BFGS methods with exact line search fails for nonconvex objective functions. Math. Program. 99(1, Ser. A), 49–61 (2004)

36.

Mascarenhas, W.: On the divergence of line search methods. Comput. Appl. Math. 26(1), 129–169 (2007)MathSciNetMATH

37.

Mascarenhas, W.: Newton’s iterates can converge to non-stationary points. Math. Program. 112(2), 327–334 (2008)CrossRefMathSciNetMATH

38.

Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2006)MATH

39.

Pang, J.S.: Three modelling paradigms in mathematical programming. Math. Program. 125(2, Ser. B), 297–323 (2010)

40.

Pang, J.S., Razaviyan, M., Alvarado, A.: Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res. 42(1), 95–118 (2016)CrossRefMathSciNet

41.

Robinson, S.: Stability theory for systems of inequalities, Part II: differentiable nonlinear systems. SIAM J. Numer. Anal. 13(4), 497–513 (1976)MATH

42.

Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton (1970)CrossRefMATH

43.

Rockafellar, R.: Lagrange multipliers and optimality. SIAM Rev. 35(2), 183–238 (1993)CrossRefMathSciNetMATH

44.

Rockafellar, R., Wets, R.B.: Variational Analysis. Springer, New York (1998)CrossRefMATH

45.

Strekalovsky, A.: Elements of Nonconvex Optimization. Nauka, Novosibirsk (2003). (in Russian)

46.

Strekalovsky, A.: On solving optimization problems with hidden nonconvex structures. In: Rassias, T., Floudas, C., Butenko, S (eds.) Optimization in Science and Engineering, pp. 465–502. Springer, New York (2014)CrossRefMATH

47.

Strekalovsky, A.: On local search in D.C. optimization problems. Appl. Math. Comput. 255, 73–83 (2015)

48.

Strekalovsky, A.: Global optimality conditions in nonconvex optimization. J. Optim. Theory Appl. 173(3), 770–792 (2017)CrossRefMathSciNetMATH

49.

Strekalovsky, A.: Global optimality conditions and exact penalization. Optim. Lett. 13(3), 597–615 (2019). https://doi.org/0.1007/s11590-017-1214-x CrossRefMathSciNetMATH

50.

Strekalovsky, A., Minarchenko, I.: A local search method for optimization problem with d.c. inequality constraints. Appl. Math. Model. 58, 229–244 (2018)

51.

Strekalovsky, A., Orlov, A.: Bimatrix Games and Bilinear Programming. FIZMATLIT, Moskow (2007). (in Russian)

52.

Strekalovsky, A., Orlov, A., Malyshev, A.: On computational search for optimistic solutions in bilevel problems. J. Global Optim. 48(1), 159–172 (2010)CrossRefMathSciNetMATH

53.

Toland, J.: Duality in nonconvex optimization. J. Math. Anal. Appl. 66, 399–415 (1978)CrossRefMathSciNetMATH

54.

Toland, J.: A duality principle for nonconvex optimization and the calculus of variations. Arch. Ration. Mech. Anal. 71, 41–61 (1979)CrossRefMATH

55.

Toland, J.: On the stability of rotating heavy chains. J. Differ. Equ. 32, 15–31 (1979)CrossRefMathSciNetMATH

56.

Tuy, H.: D.C. optimization: Theory, methods and algorithms. In: Horst, R., Pardalos, P. (eds.) Handbook of Global optimization, pp. 149–216. Kluwer, Dordrecht (1995)CrossRefMATH

57.

Vasiliev, F.: Optimization Methods. Factorial Press, Moscow (2002). (in Russian)

58.

Zangwill, W.: Non-linear programming via penalty functions. Manag. Sci. 13, 344–358 (1967)CrossRefMathSciNetMATH

59.

Zaslavski, A.: Exact penalty property in optimization with mixed constraints via variational analysis. SIAM J. Optim. 23(1), 170–187 (2013)CrossRefMathSciNetMATH

Titel: Local Search for Nonsmooth DC Optimization with DC Equality and Inequality Constraints
Buch: Numerical Nonsmooth Optimization
Print ISBN: 978-3-030-34909-7

Electronic ISBN: 978-3-030-34910-3

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-34910-3_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner