litlas
Log inCreate account

A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem

Authors: Pham Dinh Tao, Hoai An Le Thi - SIAM Journal on Optimization 1998 cited by 569

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.

On the Stationary Valuesof a Second-Degree…On the Stationary Values of a Second-Degree Polynomial on the Unit SphereComputing OptimalLocally Constrained…Computing Optimal Locally Constrained StepsNewton’s Method with aModel Trust Region…Newton’s Method with a Model Trust Region ModificationComputing a Trust RegionStepComputing a Trust Region StepConvergence of asubgradient method for…Convergence of a subgradient method for computing the bound norm of matricesGlobal Optimization:Deterministic ApproachesGlobal Optimization: Deterministic ApproachesLocal Minimizers ofQuadratic Functions on…Local Minimizers of Quadratic Functions on Euclidean Balls and SpheresSolving a Class ofLinearly Constrained…Solving a Class of Linearly Constrained Indefinite Quadratic Problems by D.C. AlgorithmsMinimization of aLarge-Scale Quadratic…Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical ConstraintOn Some Properties ofQuadratic Programs with…On Some Properties of Quadratic Programs with a Convex Quadratic ConstraintThe Symmetric EigenvalueProblemThe Symmetric Eigenvalue ProblemA New Matrix-FreeAlgorithm for the…A New Matrix-Free Algorithm for the Large-Scale Trust-Region SubproblemA Branch and BoundMethod via d.c…A Branch and Bound Method via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic ProblemsA continuous approch forglobally solving…A continuous approch for globally solving linearly constrained quadraticA new efficientalgorithm based on DC…A new efficient algorithm based on DC programming and DCA for clusteringA DC programmingapproach for feature…A DC programming approach for feature selection in support vector machines learningLearning sparseclassifiers with…Learning sparse classifiers with difference of convex functions algorithmsNew and efficient DCAbased algorithms for…New and efficient DCA based algorithms for minimum sum-of-squares clusteringBlock Clustering Basedon Difference of Convex…Block Clustering Based on Difference of Convex Functions (DC) Programming and DC AlgorithmsFeature selection forlinear SVMs under…Feature selection for linear SVMs under uncertain data: Robust optimization based on difference of convex functions algorithmsDC approximationapproaches for sparse…DC approximation approaches for sparse optimizationDC programming and DCAfor sparse optimal…DC programming and DCA for sparse optimal scoring problemSolving the Trust-RegionSubproblem By a…Solving the Trust-Region Subproblem By a Generalized Eigenvalue ProblemDC programming and DCA:thirty years of…DC programming and DCA: thirty years of developmentsA D.C. OptimizationAlgorithm for Solving…A D.C. Optimization Algorithm for Solving the Trust-Region SubproblemEarlier referencesFocus paperCiting papersOlderNewer

Click a node to pin it, click the empty canvas to go back to this paper, or hover to preview. Open a node’s page from its title.