Vol. 25, no. 1, 2019
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.
Keywords: d.c. function, exact penalty, linearized problem, global optimality conditions, Lagrange function, Lagrange multipliers, KKT-vector
Received December 15, 2018
Revised February 8, 2019
Accepted February 11, 2019
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
Cite this article as: A.S. Strekalovsky. New global optimality conditions in a problem with d.c. constraints, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 1, pp. 245-261.
REFERENCES
1. Eremin I. The penalty method in convex programming. Soviet Math. Dokl., 1966, vol. 8, pp. 459–462.
2. Zangwill W. Non-linear programming via penalty functions. Management Science, 1967, vol. 13, no. 5, pp. 344–358. doi: 10.1287/mnsc.13.5.344
3. Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu linejnogo i vypuklogo programmirovaniya [Introduction to the theory of linear and convex programming]. Moscow: Nauka Publ., 1976, 192 p.
4. Vasil’ev F.P. Metody optimizatsii [Optimization methods]. Moscow: MTsNMO Publ., 2011. Vol. 1: 620 p., ISBN: 978-5-94057-707-2 ; Vol. 2: 433 p., ISBN: 978-5-94057-708-9 .
5. Nocedal J., Wright S.J. Numerical optimization. N Y: Springer, 2006, 634 p. ISBN: 978-0-387-30303-1 .
6. Bonnans J.-F., Gilbert J.C., Lemar$\acute{\mathrm{e}}$chal C., Sagastiz$\acute{\mathrm{a}}$bal C.A. Numerical optimization: Theoretical and practical aspects. Berlin; Heidelberg: Springer-Verlag, 2006, 494 p. ISBN: 9783540354451 .
7. Hiriart-Urruty J.-B., Lemar$\acute{\mathrm{e}}$chal C. Convex analysis and minimization algorithms. Berlin: Springer-Verlag, 1993, 418 p. doi: 10.1007/978-3-662-02796-7
8. Clarke H. Optimization and nonsmooth analysis. N Y: Wiley, 1983, 308 p.
9. 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
10. 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
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., 2015, vol. 164, no. 3, pp. 862–882. doi: 10.1007/s10957-013-0487-1
12. Le Thi H.A., Huynh V.N., Dinh T.P. DC programming and DCA for general DC programs. In: van Do T., Thi H., Nguyen N. (eds) Advanced Computational Methods for Knowledge Engineering. Advances in Intelligent Systems and Computing. Cham: Springer, 2014, vol. 282, pp. 15–35. doi: 10.1007/978-3-319-06569-4_2
13. Zaslavski A.J. Exact Penalty Property in Optimization with Mixed Constraints via Variational Analysis. SIAM Journal on Optimization, 2013, vol. 23, no. 1, pp. 170–187. doi: 10.1137/120870840
14. Floudas C.A., Pardalos P.M.(eds.): Frontiers in global optimization. Dordrecht: Kluwer Acad. Publ., 2004, 604 p. ISBN: 1-4020-7699-1 .
15. Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin: Springer-Verlag, 1993, 730 p. ISBN: 3540560947 .
16. Tuy H. D.c. optimization: Theory, methods and algorithms. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization. Dordrecht: Kluwer Acad. Publ., 1995, ISBN: 0-7923-3120-6 , pp. 149–216.
17. Rockafellar R. Convex Analysis. Princeton: Princeton Univ. Press, 1970, 472 p. ISBN: 0691015864 .
18. Rockafellar R.T. Lagrange multipliers and optimality. SIAM Review, 1993, vol. 35, no. 2, pp. 183–238. doi: 10.1137/1035044
19. Demyanov V.F. Usloviya ekstremuma i variatsionnoe ischislenie [Extremum conditions and variational calculus]. Moscow: Vysshaya shkola Publ., 2005, 336 p.
20. 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. Berlin: Springer-Verlag, 1985, Ser. Lecture Notes in Economics and Mathematical Systems, vol. 256, pp. 37–69. doi: 10.1007/978-3-642-45610-7_3
21. Strekalovsky A.S. Elementy nevypukloi optimizatsii [Elements of nonconvex optimization]. Novosibirsk: Nauka Publ., 2003, 356 p. ISBN: 5-02-032064-1 .
22. Byrd R., Lopez-Calva G., Nocedal J. A line search exact penalty method using steering rules. Math. Programming, Ser. A, 2012, vol. 133, no. 1-2, pp. 39–73. doi: 10.1007/s10107-010-0408-0
23. Byrd R., Marazzi M., Nocedal J. On the convergence of Newton iterations to non-stationary points. Math. Programming, Ser. A, 2004, vol. 99, no. 1, pp. 127–148. doi: 10.1007/s10107-003-0376-8
24. Hiriart-Urruty J.-B. Optimisation et analyse convex. Paris: Presses Universitaires de France, 1998, 384 p. ISBN: 2-1304-8983-4 .
25. Strekalovsky A.S. On solving optimization problems with hidden nonconvex structures. In: Rassias T.M., Floudas C.A., Butenko S. (eds.) Optimization in Science and Engineering. N Y: Springer, 2014, pp. 465–502. doi: 10.1007/978-1-4939-0808-0_23
26. Strekalovsky A.S. Global optimality conditions for optimal control problems with functions of A.D. Alexandrov. J. Optim. Theory Appl., 2013, vol. 159, no. 2, pp. 297–321. doi: 10.1007/s10957-013-0355-z
27. Strekalovsky A.S. Global optimality conditions and exact penalization. Optim. Lett., 2017, pp. 1–19. doi: 10.1007/s11590-017-1214-x
28. 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
29. 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
30. Strekalovsky A.S. On the minimization of the difference of convex functions on a feasible set. Comput. Math. and Math. Physics, 2003, vol. 43, no. 3, pp. 380–390.
31. Strekalovsky A.S., Minarchenko I.M. A local search method for optimization problem with d.c. inequality constraints. Appl. Math. Modelling, 2018, vol. 58, pp. 229–244. doi: 10.1016/j.apm.2017.07.031
