SIAM Journal on Optimization · 1998 · 569 citations · 20 references
Natural SciencesComputer ScienceAlgorithmsOptimizationScientific ComputingConvex AnalysisConvex OptimizationGlobal OptimizationIterative SolversNonlinear ProgrammingOptimization TheoryConvex FunctionsDuality TheoremEigenvaluesNonconvex OptimizationOptimality Conditions
Difference‑convex (d.c.) optimization, including its duality theory and optimality conditions, forms the theoretical backdrop of this work. The study proposes the DCA algorithm for solving the trust‑region subproblem. The DCA iteratively solves the trust‑region subproblem using only matrix‑vector products, with optimality verified by an implicitly restarted Lanczos method and a restart strategy for nonglobal solutions. In nonconvex instances, the DCA converges to the global optimum within at most 2m+2 restarts (m = number of negative eigenvalues) and outperforms standard methods in robustness and efficiency, particularly for large‑scale problems.
This paper is devoted to difference of convex functions (d.c.) optimization: d.c. duality, local and global optimality conditions in d.c. programming, the d.c. algorithm (DCA), and its application to solving the trust-region problem. The DCA is an iterative method that is quite different from well-known related algorithms. Thanks to the particular structure of the trust-region problem, the DCA is very simple (requiring only matrix-vector products) and, in practice, converges to the global solution. The inexpensive implicitly restarted Lanczos method of Sorensen is used to check the optimality of solutions provided by the DCA. When a nonglobal solution is found, a simple numerical procedure is introduced both to find a feasible point having a smaller objective value and to restart the DCA at this point. It is shown that in the nonconvex case, the DCA converges to the global solution of the trust-region problem, using only matrix-vector products and requiring at most 2m+2 restarts, where m is the number of distinct negative eigenvalues of the coefficient matrix that defines the problem. Numerical simulations establish the robustness and efficiency of the DCA compared to standard related methods, especially for large-scale problems.
20
Practical methods of optimization
Mathematics and Computers in Simulation · 1988 · 5.9K citations
Choice Reviews Online · 1989 · 1.8K citations
Jorge J. Morè, D. C. Sorensen · SIAM Journal on Scientific and Statistical Computing · 1983 · 1.4K citations · Full text