New global optimality conditions in a problem with d.c. constraints

A. S. Strekalovskii

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 1, pp. 245-261

Résumé

The paper addresses a nonconvex nonsmooth optimization problem with the cost function and equality and inequality constraints given by d.c. functions, i.e., functions representable as the difference of convex functions. The original problem is reduced to a problem without constraints with the help of exact penalization theory. Then the penalized problem is represented as a d.c. minimization problem without constraints, for which new mathematical tools are developed in the form of global optimality conditions (GOCs). The GOCs reduce the nonconvex problem in question to a family of linearized (convex) problems and are used to derive a nonsmooth form of the Karush-Kuhn-Tucker theorem for the original problem. In addition, the GOCs possess a constructive (algorithmic) property, which makes it possible to leave the local pits and stationary (critical) points of the original problem. The effectiveness of the GOCs is demonstrated with examples.

Détail

Keywords: d.c. function, exact penalty, linearized problem, global optimality conditions, Lagrange function, KKT-vector.
Mots-clés : Lagrange multipliers

Bibliographie

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

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

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

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

[5] Nocedal J., Wright S.J., Numerical optimization, Springer, N Y, 2006, 634 pp. | MR | Zbl

[6] 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

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

[8] Clarke F.H., Optimization and nonsmooth analysis, Wiley-Interscience, N Y, 1983, 308 pp. | MR | Zbl

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

[10] 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

[11] 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:3 (2015), 862–882 | DOI | MR | Zbl

[12] 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. eds. van T. Do, H. Thi, N. Nguyen, Springer, Cham, 2014, 15–35 | DOI | Zbl

[13] 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

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

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

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

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

[18] Rockafellar R.T., “Lagrange multipliers and optimality”, SIAM Review, 35:2 (1993), 183–238 | DOI | MR | Zbl

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

[20] 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 mathematical systems, 256, Springer-Verlag, Berlin, 1985, 37–69 | DOI | MR

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

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

[23] Byrd R., Marazzi M., Nocedal J., “On the convergence of Newton iterations to non-stationary points”, Math. Programming. Ser. A, 99:1 (2004), 127–148 | DOI | MR | Zbl

[24] Hiriart-Urruty J.-B., Optimisation et analyse convex, Presses Universitaires de France, Paris, 1998, 384 pp. | MR | Zbl

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

[26] Strekalovsky A.S., “Global optimality conditions for optimal control problems with functions of A.D. Alexandrov”, J. Optim. Theory Appl., 159:2 (2013), 297–321 | DOI | MR | Zbl

[27] Strekalovsky A.S., “Global optimality conditions and exact penalization”, Optim. Lett., 2017, 1–19 | DOI | MR

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

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

[30] Strekalovskii A.S., “O minimizatsii raznosti vypuklykh funktsii na dopustimom mnozhestve”, Zhurn. vychisl. matematiki i mat. fiziki, 43:3 (2003), 399–409 | MR | Zbl

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