Abstract
Nonconvex optimization problems with an inequality constraint given by the difference of two convex functions (by a d.c. function) are considered. Two methods for finding local solutions to this problem are proposed that combine the solution of partially linearized problems and descent to a level surface of the d.c. function. The convergence of the methods is analyzed, and stopping criterions are proposed. The methods are compared by testing them in a numerical experiment.
Similar content being viewed by others
References
F. P. Vasil’ev, Optimization Methods (Faktodrial Press, Moscow, 2002) [in Russian].
B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983; Optimization Software, New York, 1987).
I. I. Eremin, Theory of Linear Optimization (Inst. Mat. Mekh. Ural Otd. Ross. Akad. Nauk, Yekaterinburg, 1998) [in Russian].
Handbook of Global Optimization, Ed. by R. Horst and P. Pardalos (Kluwer Academic, Dordrecht, 1995).
R. Horst and H. Tuy, Global Optimization (Deterministic Approaches) (Springer-Verlag, Berlin, 1993).
A. S. Strekalovsky, Elements of Nonconvex Optimization (Nauka, Novosibirsk, 2003) [in Russian].
A. S. Strekalovsky, “Extremal Problems with d.c.-Constraints,” Zh. Vychisl. Mat. Mat. Fiz. 41, 1833–1843 (2001) [Comput. Math. Math. Phys. 41, 1742–1751 (2001)].
A. S. Strekalovsky, “On the Minimization of the Difference of Convex Functions on a Feasible Set,” Zh. Vychisl. Mat. Mat. Fiz. 43, 399–409 (2003) [Comput. Math. Math. Phys. 43, 380–390 (2003)].
A. S. Strekalovsky, “Minimizing Sequences in Problems with d.c. Constraints,” Zh. Vychisl. Mat. Fiz. 45, 435–447 (2005) [Comput. Math. Math. Phys. 45, 418–429 (2005)].
A. S. Strekalovsky and T. V. Yakovleva, “On Local and Global Search in Nonconvex Optimization Problems,” Avtom. Telemekh., No. 3, 23–34 (2004).
A. S. Strekalovsky and T. V. Yakovleva, “Modification Rosen’s Method in an Inverse Convex Problem,” Izv. Vyssh. Uchebn. Zaved. Mat., No. 12, 70–75 (2005).
V. I. Zabotin and Yu. A. Chernyaev, “A Generalization of the Gradient Projection Method to Extremum Value Problems with Preconvex Constraints,” Zh. Vychisl. Mat. Mat. Fiz. 41, 367–373 (2001) [Comput. Math. Math. Phys. 41, 340–346 (2001)].
J. B. Rosen, “Iterative Solution of Nonlinear Optimal Control Problems,” J. SIAM Control 4(1), 223–244 (1966).
R. R. Meyer, “The Validity of a Family of Optimization Methods,” J. SIAM Control 8(1), 41–54 (1970).
T. S. Motzkin and E. G. Straus, “Maxima for Graphs and a New Proof of a Theorem of Turan,” Canad. J. Math. 17, 533–540 (1965).
Author information
Authors and Affiliations
Additional information
Original Russian Text © T.V. Gruzdeva, A.S. Strekalovsky, 2007, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2007, Vol. 47, No. 3, pp. 397–413.
Rights and permissions
About this article
Cite this article
Gruzdeva, T.V., Strekalovsky, A.S. Local search in problems with nonconvex constraints. Comput. Math. and Math. Phys. 47, 381–396 (2007). https://doi.org/10.1134/S0965542507030049
Received:
Issue Date:
DOI: https://doi.org/10.1134/S0965542507030049