A smooth nonconvex optimization problem is considered, where the equality and inequality constraints and the objective function are given by DC functions. First, the original problem is reduced to an unconstrained problem with the help of I.I. Eremin's exact penalty theory, and the objective function of the penalized problem also turns out to be a DC function. Necessary and sufficient conditions for minimizing sequences of the penalized problem are proved. On this basis, a "theoretical method" for constructing a minimizing sequence in a penalized problem with a fixed penalty parameter is proposed and the convergence of the method is proved. The well-known local search method and its properties are used for developing a new global search scheme based on global optimality conditions with varying penalty parameter. The sequence constructed using the global search scheme turns out to be minimizing in the "limit" penalized problem, and each of its terms $z^{k+1}$ turns out to be an approximately critical vector for the local search method and an approximate solution of the current penalized problem $(\mathcal{P}_k)\triangleq (\mathcal{P}_{\sigma_k})$. Finally, under an additional condition of "approximate feasibility", the constructed sequence turns out to be minimizing for the original problem with DC constraints.
Keywords: DC function, exact penalty, linearized problem, minimizing sequence, global optimality conditions, local search, global search, critical vector, resolving approximation
Received April 28, 2023
Revised June 1, 2023
Accepted June 5, 2023
Funding Agency: The research was funded by the Ministry of Science and Higher Education of the Russian Federation within the project “Theoretical foundations, methods, and high-performance algorithms for continuous and discrete optimization to support interdisciplinary research” (no. of state registration 121041300065-9, project code FWEW-2021-0003).
Aleksandr Sergeevich Strekalovsky, Dr. Phys.-Math. Sci., Prof., Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: strekal@icc.ru
REFERENCES
1. Vasil’ev F.P. Metody optimizatsii [Optimization methods]. Moscow: Moscow Centre of Continuous Math. Education Publ., 2011. Vol. 1: 620 p., ISBN: 978-5-94057-707-2; Vol. 2: 433 p., ISBN: 978-5-94057-708-9.
2. Vasin V.V., Eremin I.I. Operators and iterative processes of Fejér type. Theory and Applications. Berlin, NY, Walter de Gruyter, 2009, 155 p. ISBN: 3110218186. Original Russian text was published in Vasin V.V., Eremin I.I., Operatory i iteratsionnye protsessy feierovskogo tipa, Izhevsk, Regular and Chaotic Dynamics Publ., 2005, 200 p. ISBN: 5-93972-427-2.
3. Dem’yanov V.F. Usloviya ekstremuma i variatsionnoe ischislenie [Extremum conditions and calculus of variations]. Moscow, Vysshaya Shkola Publ., 2005, 336 p. ISBN: 5-06-004751-2.
4. Evtushenko Yu.G. Numerical optimization techniques. NY, Springer-Verlag, 1985, 562 p. ISBN: 978-1-4612-9530-3. Original Russian text published in Evtushenko Yu. G., Metody resheniya ekstremal’nykh zadach i ikh primenenie v sistemakh optimizatsii, Moscow, Nauka Publ., 1982, 432 p.
5. Eremin I.I. The “penalty” method in convex programming. Soviet Math. Dokl., 1967, vol. 8, p. 459–462.
6. Eremin I.I. The penalty method in convex programming. Cybernetics, 1967, vol. 3, no. 4, pp. 53–56. doi: 10.1007/bf01071708
7. Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya [Introduction to the theory of linear and convex programming]. Moscow, Nauka Publ., 1976, 192 p.
8. Eremin I.I., Mazurov V.D. Nestatsionarnye protsessy matematicheskogo programmirovaniya [Nonstationary processes of mathematical programming]. Moscow, Nauka Publ., 1979, 288 p.
9. Eremin I.I. Protivorechivye modeli optimal’nogo planirovaniya [Contradictory models of optimal planning]. Moscow, Nauka Publ., 1988, 160 p. ISBN: 5-02-013773-1.
10. Zhadan V.G. Metody optimizatsii [Optimization methods], part I, part II. Moscow, Moscow Phys. Tech. Inst. Publ., 2015, I: 270 p., II: 320 p. ISBN: 978-5-7417-0516-2.
11. Konnov I.V. Nelineinaya optimizatsiya i variatsionnye neravenstva [Nonlinear optimization and variational inequalities]. Kazan, Kazan Univ. Publ., 2013, 508 p. ISBN 978-5-00019-059-3.
12. Strekalovskii A.S. Elementy nevypukloi optimizatsii [Elements of non-convex optimization]. Novosibirsk, Nauka Publ., 2003, 356 p. ISBN 5-02-032064-1.
13. Strekalovskii A.S., Orlov A.V. Bimatrichnye igry i bilineinoe programmirovanie [Bimatrix games and bilinear programming], Moscow, Fizmatlit Publ., 2007. ISBN 978-5-9221-0853-9.
14. Strekalovskii A.S., Orlov A.V. Lineinye i kvadratichno-lineinye zadachi dvukhurovnevoi optimizatsii [Linear and quadratic linear problems of two-level optimization], Novosibirsk, Syberian Branch of Russian Akad. Sci., 2019. ISBN: 978-5-6042856-2-6.
15. Strekalovskii A.S. New global optimality conditions in a problem with d.c. constraints. Trudy Inst. Math. Mekh. UrO RAN, 2019, vol. 25, no. 1, pp. 245–261 (in Russian). doi: 10.21538/0134-4889-2019-25-1-245-261
16. Strekalovsky A.S. Elements of global search in the general d.c. optimization problem. Itogi Nauki i Tekhniki. Ser. Sovremennaya Matematika i ee Prilozheniya. Tematicheskie Obzory, 2021, vol. 196, pp. 114–127 (in Russian). doi: 10.36535/0233-6723-2021-196-114-127
17. Sukharev A.G., Timokhov A.V., Fedorov V.V. Kurs metodov optimizatsii : uchebnoe posobie [Course of optimization methods : a tutorial], Moscow, Fizmatlit Publ., 2011, 384 p. ISBN: 978-5-9221-0559-0.
18. Bonnans J.-F., Gilbert J.C., Lemaréchal C., Sagastizábal C.A. Numerical optimization: theoretical and practical aspects, Berlin, Heidelberg, Springer-Verlag, 2006, 494 p. ISBN: 3-540-35445-X.
19. Burke J. An exact penalization viewpoint of constrained optimization. SIAM J. Control Optim., 1991, vol. 29, no. 4, pp. 968–998. doi: 10.1137/0329054
20. Byrd R., Lopez-Calva G., Nocedal J. A line search exact penalty method using steering rules. Math. Progr., Ser. A, 2012, vol. 133, no. 1–2, pp. 39–73. doi: 10.1007/s10107-010-0408-0
21. Di Pillo G., Lucidi S., Rinaldi F. An approach to constrained global optimization based on exact penalty functions. J. Global Optim., 2012, vol. 54, no. 2, pp. 251–260. doi: 10.1007/s10898-010-9582-0
22. Dur M., Hiriart-Urruty J.B. Testing copositivity with the help of difference-of-convex optimization. Math. Progr., Ser. B, 2013, vol. 140, no. 1, pp. 31–43. doi: 10.1007/s10107-012-0625-9
23. Floudas C.A., Pardalos P. M. (eds.): Frontiers in global optimization. Dordrecht, Kluwer Acad. Publ., 2004, 604 p. ISBN: 978-1402076992.
24. Fiacco A.V., McCormick G.P. Nonlinear programming: Sequential unconstrained minimization techniques. NY, John Wiley, 1968, 210 p. doi: 10.1137/1.9781611971316. Translated to Russian under the title Nelineinoe programmirovanie. Metody posledovatel’noi bezuslovnoi minimizatsii, Moscow, Mir Publ., 1972.
25. Gaudioso M., Gruzdeva T.V., Strekalovsky A.S. On numerical solving the spherical separability problem. J. Global Optim., 2016, vol. 66, no. 1, pp. 21–34. doi: 10.1007/s10898-015-0319-y
26. Hiriart-Urruty J.-B. Generalized differentiability, duality and optimization for problems dealing with differences of convex functions. In: Convexity and Duality in Optimization, ed. J. Ponstein, Ser. Lecture Notes in Economics and Math. Systems, vol. 256, Berlin, Springer-Verlag, 1985, pp. 37–69. doi: 10.1007/978-3-642-45610-7_3
27. Hiriart-Urruty J.-B., Lemaréchal C. Convex analysis and minimization algorithms. Berlin: Springer-Verlag, 1993. Part I, 418 p. doi: 10.1007/978-3-662-02796-7. Part II, 348 p. doi: 10.1007/978-3-662-06409-2.
28. Horst R., Tuy H. Global Optimization. Deterministic Approaches. Berlin, Springer-Verlag, 1993, 730 p. ISBN: 9780387560946.
29. Kruger A. Error bounds and metric subregularity. Optimization, 2015, vol. 64, no. 1, pp. 49–79. doi: 10.1080/02331934.2014.938074
30. Le Thi H.A., Pham Dinh T., Van Ngai H. Exact penalty and error bounds in DC programming. J. Global Optim., 2012, vol. 52, no. 3, pp. 509–535. doi: 10.1007/s10898-011-9765-3
31. Thi H.A., Huynh V.N., Dinh T.P. DC programming and DCA for general DC programs. In: Advanced computational methods for knowledge engineering / eds. van T. Do, H. Thi, Nguyen, Ser. Advances in intelligent systems and computing, Cham, Springer, 2014, vol. 282, pp. 15–35. doi: 10.1007/978-3-319-06569-4_2
32. Mascarenhas W. The BFGS methods with exact line search fails for nonconvex objective functions. Math. Program., Ser. A, 2004, vol. 99, no. 1, pp. 49–61. doi: 10.1007/s10107-003-0421-7
33. Mascarenhas W. On the divergence of line search methods. Comput. Appl. Math., 2007, vol. 26, no. 1, pp. 129–169. doi: 10.1590/S0101-82052007000100006
34. Mascarenhas W. Newton’s iterates can converge to non-stationary points. Math. Program., 2008, vol. 112, no. 2, pp. 327–334. doi: 10.1007/s10107-006-0019-y
35. Nocedal J., Wright S.J. Numerical Optimization. NY, Springer, 2006, 634 p. doi: 10.1007/978-0-387-40065-5
36. Pang J.S. Three modelling paradigms in mathematical programming. Math. Program., Ser. B, 2010, vol. 125, no. 2, pp. 297–323. doi: 10.1007/s10107-010-0395-1
37. Pang J.S., Razaviyayn M., Alvarado A. Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res., 2017, vol. 42, no. 1, pp. 95–118. doi: 10.1287/moor.2016.0795
38. Rockafellar R.T. Convex Analysis. Princeton, Princeton Univ. Press, 1970, 451 pp. ISBN: 9780691080697. Translated to Russian under the title Vypuklyi analiz, Moscow, Mir Publ., 1973, 471 pp.
39. Strekalovsky A.S. On solving optimization problems with hidden nonconvex structures. In: Optimization in science and engineering, eds. T.M. Rassias., C.A. Floudas, S. Butenko, NY, Springer, 2014, pp. 465–502. doi: 10.1007/978-1-4939-0808-0_23
40. Strekalovsky A.S. On local search in d.c. optimization problems. Appl. Math. Comput., 2015, vol. 255, pp. 73–83. doi: 10.1016/j.amc.2014.08.092
41. Strekalovsky A.S. Local search for nonsmooth DC optimization with DC equality and inequality constraints. In: Numerical nonsmooth optimization: state of the art algorithms, eds. A.M. Bagirov, M. Gaudioso, N. Karmitsa, M.M. Makela, S. Taheri. Cham, Springer, 2020, pp. 229–261. doi: 10.1007/978-3-030-34910-3_7
42. Strekalovsky A.S., Minarchenko I.M. A local search method for optimization problem with d.c. inequality constraints. Appl. Math. Model., 2018, vol. 58, pp. 229–244. doi: 10.1016/j.apm.2017.07.031
43. Strekalovsky A.S. Global optimality conditions in nonconvex optimization. J. Optim. Theory Appl., 2017, vol. 173, no. 3, pp. 770–792. doi: 10.1007/s10957-016-0998-7
44. Strekalovsky A.S. Global optimality conditions and exact penalization. Optim. Letters, 2019, vol. 13, no. 3, pp. 597–615. doi: 10.1007/s11590-017-1214-x
45. Strekalovsky A.S. On global optimality conditions for D.C. minimization problems with D.C. constraints. J. Appl. Numer. Optim., 2021, vol. 3, no. 1, pp. 175–196. doi: 10.23952/jano.3.2021.1.10
46. Strekalovsky A.S., Yanulevich M.V. On global search in nonconvex optimal control problems. J. Global Optim., 2016, vol. 65, no. 1, pp. 119–135. doi: 10.1007/s10898-015-0321-4
47. Tuy H. D.C. optimization: Theory, methods and algorithms. In: Handbook of global optimization, eds. R. Horst and P. M. Pardalos, Dordrecht, Kluwer Acad. Publ., 1995, pp. 149–216. doi: 10.1007/978-1-4615-2025-2_4
48. Zangwill W. Non-linear programming via penalty functions. Management Science, 1967, vol. 13, no. 5, ser. A, pp. 344–358. doi: 10.1287/mnsc.13.5.344
49. Zangwill W. Nonlinear programming: a unified approach. Englewood Cliffs, Prentice-Hall, 1969, 356 p. ISBN: 978-0136235798. Translated to Russian under the title Nelineinoe programmirovanie: edinyi podkhod, Moscow, Soviet Radio Publ., 1973.
50. Zaslavski A. J. Exact penalty property in optimization with mixed constraints via variational analysis. SIAM J. Optim., 2013, vol. 23, no. 1, pp. 170–187. doi: 10.1137/120870840
Cite this article as: A.S. Strekalovsky. Minimizing sequences in a constrained DC optimization problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 185–209; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S255–S278.
