Minimizing Sequences in a Constrained DC Optimization Problem

A. S. Strekalovskii

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 185-209

Résumé

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 the penalized problem with a fixed penalty parameter is proposed and the convergence of the method is proved. A well-known local search method and its properties are used for developing a new global search scheme based on global optimality conditions with a 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.

Détail

Keywords: DC function, exact penalty, linearized problem, minimizing sequence, global optimality conditions, local search, global search, critical vector, resolving approximation.

Bibliographie

[1] Vasilev F.P., Metody optimizatsii, v 2-kh kn., MTsNMO, M., 2011, 620 pp.; 433 с.

[2] Vasin V.V., Eremin I.I., Operatory i iteratsionnye protsessy feierovskogo tipa: teoriya i prilozheniya, Izd-vo “Institut kompyuternykh issledovanii”, M., 2005, 199 pp. | MR

[3] Demyanov V.F., Usloviya ekstremuma i variatsionnoe ischislenie, Vysshaya shkola, M., 2005, 336 pp.

[4] Evtushenko Yu.G., Metody resheniya ekstremalnykh zadach i ikh primenenie v sistemakh optimizatsii, Nauka, M., 1982, 432 pp. | MR

[5] Eremin I.I., “Metod “shtrafov” v vypuklom programmirovanii”, Dokl. AN, 173:4 (1967), 748–751 | Zbl

[6] Eremin I.I., “O metode shtrafov v vypuklom programmirovanii”, Kibernetika, 1967, no. 4, 63–67 | Zbl

[7] Eremin I.I., Astafev N.N., Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya, Fizmatlit, M., 1976, 192 pp.

[8] Eremin I.I., Mazurov V.D., Nestatsionarnye protsessy matematicheskogo programmirovaniya, Nauka, M., 1979, 288 pp.

[9] Eremin I.I., Protivorechivye modeli optimalnogo planirovaniya, Nauka, M., 1988, 160 pp. | MR

[10] Zhadan V.G., Metody optimizatsii, ch. I, II, MFTI, M., 2015, 270 pp.; 320 с.

[11] Konnov I.V., Nelineinaya optimizatsiya i variatsionnye neravenstva, Izd-vo Kazan. un-ta, Kazan, 2013, 508 pp.

[12] Strekalovskii A.S., Elementy nevypukloi optimizatsii, Nauka, Novosibirsk, 2003, 356 pp.

[13] Strekalovskii A.S., Orlov A.V., Bimatrichnye igry i bilineinoe programmirovanie, Fizmatlit, M., 2007, 224 pp.

[14] Strekalovskii A.S., Orlov A.V., Lineinye i kvadratichno-lineinye zadachi dvukhurovnevoi optimizatsii, Izd-vo SO RAN, Novosibirsk, 2019, 262 pp.

[15] Strekalovskii A.S., “Novye usloviya globalnoi optimalnosti v zadache s d.c. ogranicheniyami”, Tr. In-ta matematiki i mekhaniki UrO RAN, 25:1 (2019), 245–261 | DOI | MR

[16] Strekalovskii A.S., “Elementy globalnogo poiska v obschei zadache d.c. optimizatsii”, Itogi nauki i tekhniki. Sovremennaya matematika i ee prilozheniya. Temat. obzory, 196 (2021), 114–127 | DOI

[17] Sukharev A.G., Timokhov A.V., Fedorov V.V., Kurs metodov optimizatsii, uch. posobie, 2-e izd., Fizmatlit, M., 2011, 384 pp. | MR

[18] Bonnans J.-F., Gilbert J.C., Lemaréchal C., Sagastizábal C.A., Numerical optimization: Theoretical and practical aspects, Springer-Verlag, Berlin; Heidelberg, 2006, 494 pp. | MR | Zbl

[19] Burke J., “An exact penalization viewpoint of constrained optimization”, SIAM J. Control Optim., 29:4 (1991), 968–998 | DOI | MR | Zbl

[20] Byrd R., Lopez-Calva G., Nocedal J., “A line search exact penalty method using steering rules”, Math. Progr. Ser. A, 133:1–2 (2012), 39–73 | DOI | MR | Zbl

[21] Di Pillo G., Lucidi S., Rinaldi F., “An approach to constrained global optimization based on exact penalty functions”, J. Global Optim., 54:2 (2012), 251–260 | DOI | MR | Zbl

[22] Dur M., Hiriart-Urruty J.B., “Testing copositivity with the help of difference-of-convex optimization”, Math. Program. Ser. B, 140:1 (2013), 31–43 | DOI | MR | Zbl

[23] Frontiers in global optimization, eds. Floudas C.A., Pardalos P.M., Kluwer Acad. Publ., Dordrecht, 2004, 604 pp. | MR | Zbl

[24] Fiacco A.V., McCormick G.P., Nonlinear programming: Sequential unconstrained minimization techniques, John Wiley, NY, 1968, 210 pp. | MR | Zbl

[25] Gaudioso M., Gruzdeva T.V., Strekalovsky A.S., “On numerical solving the spherical separability problem”, J. Global Optim., 66:1 (2016), 21–34 | DOI | MR | Zbl

[26] Hiriart-Urruty J.-B., “Generalized differentiability, duality and optimization for problems dealing with difference of convex functions”, Convexity and Duality in Optimization, Lecture Notes in Economics and Math. Systems, 256, ed. J. Ponstein, Springer-Verlag, Berlin, 1985, 37–69 | DOI | MR

[27] Hiriart-Urruty J.-B., Lemaréchal C., Convex analysis and minimization algorithms, Springer-Verlag, Berlin, 1993, 418 pp. | MR

[28] Horst R., Tuy H., Global optimization. Deterministic approaches, Springer-Verlag, Berlin, 1993, 730 pp. | MR

[29] Kruger A., “Error bounds and metric subregularity”, Optimization, 64:1 (2015), 49–79 | DOI | MR | Zbl

[30] Le Thi H.A., Pham Dinh T., Van Ngai H., “Exact penalty and error bounds in DC programming ”, J. Global Optim., 52:3 (2012), 509–535 | DOI | MR | Zbl

[31] Le Thi H.A., Huynh V.N., Dinh T.P., “DC Programming and DCA for general DC programs”, Advanced computational methods for knowledge engineering, Advances in Intelligent Systems and Computing, 282, eds. van T. Do, H. Thi, N. Nguyen, Springer, Cham, 2014, 15–35 | DOI | MR | Zbl

[32] Mascarenhas W., “The BFGS methods with exact line search fails for nonconvex objective functions”, Math. Program. Ser. A, 99:1 (2004), 49–61 | DOI | MR | Zbl

[33] Mascarenhas W., “On the divergence of line search methods”, Comput. Appl. Math., 26:1 (2007), 129–169 | DOI | MR | Zbl

[34] Mascarenhas W., “Newton's iterates can converge to non-stationary points”, Math. Program., 112:2 (2008), 327–334 | DOI | MR | Zbl

[35] Nocedal J., Wright S.J., Numerical optimization, Springer, NY, 2006, 634 pp. | MR | Zbl

[36] Pang J.S., “Three modelling paradigms in mathematical programming”, Math. Program. Ser. B, 125:2 (2010), 297–323 | DOI | MR | Zbl

[37] Pang J.S., Razaviyan M., Alvarado A., “Computing B-stationary points of nonsmooth DC programs”, Math. Oper. Res., 42:1 (2016), 95–118 | DOI | MR

[38] Rockafellar R.T., Convex Analysis, Princeton Univ. Press, Princeton, 1970, 472 pp. | MR | Zbl

[39] Strekalovsky A.S., “On solving optimization problems with hidden nonconvex structures”, Optimization in science and engineering, eds. T.M. Rassias, C.A. Floudas, S. Butenko, Springer, NY, 2014, 465–502 | DOI | MR | Zbl

[40] Strekalovsky A.S., “On local search in d.c. optimization problems”, Appl. Math. Comput., 255 (2015), 73–83 | DOI | MR | Zbl

[41] Strekalovsky A.S., “Local search for nonsmooth DC optimization with DC equality and inequality”, Constraints Numerical Nonsmooth Optimization: State of the Art Algorithms, eds. A.M. Bagirov, M. Gaudioso, N. Karmitsa, M.M. Makela, S. Taheri, Springer Internat. Publ., NY, 2020, 229–261 | DOI | MR

[42] Strekalovsky A.S., Minarchenko I.M., “A local search method for optimization problem with d.c. inequality constraints”, Appl. Math. Model., 58 (2018), 229–244 | DOI | MR | Zbl

[43] Strekalovsky A.S., “Global optimality conditions in nonconvex optimization”, J. Optim. Theory Appl., 173:3 (2017), 770–792 | DOI | MR | Zbl

[44] Strekalovsky A.S., “Global optimality conditions and exact penalization”, Optim. Letters, 13:3 (2019), 597–615 | DOI | MR | Zbl

[45] Strekalovsky A.S., “On global optimality conditions for D.C. minimization problems with D.C. constraints”, J. Appl. Numer. Optim., 3:1 (2021), 175–196 | DOI | MR

[46] Strekalovsky A.S., Yanulevich M.V., “On global search in nonconvex optimal control problems”, J. Global Optim., 65:1 (2016), 119–135 | DOI | MR | Zbl

[47] Tuy H., “D.C. Optimization: Theory, methods and algorithms”, Handbook of Global Optimization, eds. R. Horst and P. M. Pardalos, Kluwer Acad. Publ., Dordrecht, 1995, 149–216 | DOI | MR | Zbl

[48] Zangwill W., “Non-linear programming via penalty functions”, Management Science. Ser. A, 13:5 (1967), 344–358 | DOI | MR | Zbl

[49] Zangwill W., Nonlinear programming: a unified approach, Prentice-Hall, Englewood Cliffs, 1969, 356 pp. | MR | Zbl

[50] Zaslavski A.J., “Exact penalty property in optimization with mixed constraints via variational analysis”, SIAM J. Optim., 23:1 (2013), 170–187 | DOI | MR | Zbl