The trust region subproblem and semidefinite programming.

*(English)*Zbl 1070.65041Authors’ summary: The trust region (TR) subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g., function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in TR algorithms for function minimization. Trust region algorithms are popular for their strong convergence properties. However, a drawback has been the inability to exploit sparsity as well as the difficulty in dealing with the so-called hard case. These concerns have been addressed by recent advances in the theory and algorithmic development. In particular, this has allowed Lanczos techniques to replace Cholesky factorizations.

This article provides an in depth study of TRS and its properties as well as a survey of recent advances. We emphasize large scale problems and robustness. This is done using semidefinite programming (SDP) and the modem primal-dual approaches as a unifying framework. The SDP framework arises naturally and solves TRS efficiently. In addition, it shows that TRS is always a well-posed problem, i.e., the optimal value and an optimum can be calculated to a given tolerance. We provide both theoretical and empirical evidence to illustrate the strength of the SDP and duality approach. In particular, this includes new insights and techniques for handling the hard case, as well as numerical results on large test problems.

This article provides an in depth study of TRS and its properties as well as a survey of recent advances. We emphasize large scale problems and robustness. This is done using semidefinite programming (SDP) and the modem primal-dual approaches as a unifying framework. The SDP framework arises naturally and solves TRS efficiently. In addition, it shows that TRS is always a well-posed problem, i.e., the optimal value and an optimum can be calculated to a given tolerance. We provide both theoretical and empirical evidence to illustrate the strength of the SDP and duality approach. In particular, this includes new insights and techniques for handling the hard case, as well as numerical results on large test problems.

Reviewer: Klaus Schittkowski (Bayreuth)

##### MSC:

65K05 | Numerical mathematical programming methods |

90C22 | Semidefinite programming |

90C20 | Quadratic programming |

90C30 | Nonlinear programming |

90C06 | Large-scale problems in mathematical programming |

90C55 | Methods of successive quadratic programming type |

##### Keywords:

trust region method; semidefinite programming; quadratic programming; convergence; large scale problems; robustness; numerical results
PDF
BibTeX
XML
Cite

\textit{C. Fortin} and \textit{H. Wolkowicz}, Optim. Methods Softw. 19, No. 1, 41--67 (2004; Zbl 1070.65041)

Full Text:
DOI

##### References:

[1] | Fortin C. Wolkowicz H. (2002) A survey of the trust region subproblem within a semidefinite framework Technical Report CORR 2002-22 University of Waterloo, Waterloo, Canada,URL:orion.math.uwaterloo.ca:80/hwolkowi/henry/reports/ABSTRACTS.html#surveytrs |

[2] | DOI: 10.1137/1.9780898719857 · Zbl 0958.65071 |

[3] | Tikhonov A.N., Solutions of Ill-Posed Problems (1977) · Zbl 0354.65028 |

[4] | DOI: 10.2307/1267351 · Zbl 0202.17205 |

[5] | Fletcher R., Practical Methods of Optimization (1987) · Zbl 0905.65002 |

[6] | DOI: 10.1007/b98874 · Zbl 0930.65067 |

[7] | DOI: 10.1137/S1052623497327854 · Zbl 1020.65019 |

[8] | DOI: 10.1137/0801023 · Zbl 0756.65091 |

[9] | Björck Å., Numerical Methods for Least Squares Problems (1996) · Zbl 0847.65023 |

[10] | DOI: 10.1137/0904038 · Zbl 0551.65042 |

[11] | Rendl F., Mathematical Programming Series B 77 pp 273– (1997) |

[12] | DOI: 10.1137/S1052623497322735 · Zbl 1047.90510 |

[13] | DOI: 10.1137/0902016 · Zbl 0467.65027 |

[14] | DOI: 10.1137/S1052623494274374 · Zbl 0878.65044 |

[15] | DOI: 10.1016/S0167-6377(96)00036-3 · Zbl 0876.90071 |

[16] | Hager W.W. 2000 Minimizing a quadratic over a sphere Technical report University of Florida Gainsville FA |

[17] | DOI: 10.1006/jcom.1994.1014 · Zbl 0844.65045 |

[18] | DOI: 10.1137/0902016 · Zbl 0467.65027 |

[19] | DOI: 10.1137/0719026 · Zbl 0483.65039 |

[20] | Demmel J.W., Applied Numerical Linear Algebra (1997) · Zbl 0879.65017 |

[21] | DOI: 10.1007/BF02592331 · Zbl 0851.90087 |

[22] | Gol’stein E.G., Theory of Convex Programming (1972) |

[23] | Fiacco A.V., Introduction to Sensitivity and Stability Analysis in Nonlinear Programming. Mathematics in Science and Engineering 165 (1983) · Zbl 0543.90075 |

[24] | DOI: 10.1137/0805016 · Zbl 0846.49017 |

[25] | DOI: 10.1007/BF02162161 · Zbl 0161.36203 |

[26] | DOI: 10.1007/BF02169154 · Zbl 1248.65020 |

[27] | Reinsch M.D. 1973 An algorithm for minimization using exact second derivatives Technical Report 515 Harwell Laboratory Harwell Oxfordshire England |

[28] | DOI: 10.1137/0113073 · Zbl 0168.03005 |

[29] | DOI: 10.1137/0720042 · Zbl 0518.65042 |

[30] | Toint P.L., Sparse Matrices and Their Uses pp 57– (1981) |

[31] | DOI: 10.1007/978-1-4615-4381-7 |

[32] | Vanderbei R.J., Linear Programming: Foundations and Extensions (1998) |

[33] | Wright S., Primal-Dual Interior-Point Methods (1996) · Zbl 0863.65031 |

[34] | Helmberg C., SIAM J. Optimiz. 10 pp 673– · Zbl 0960.65074 |

[35] | DOI: 10.1137/S1052623497328008 · Zbl 0997.90059 |

[36] | Horn R.A., Matrix Analysis (1987) |

[37] | DOI: 10.1023/A:1013768901780 · Zbl 1087.90058 |

[38] | Fortin C., A survey of the trust region subproblem within a semidefinite framework (2000) |

[39] | DOI: 10.1007/BF02592055 · Zbl 0523.90078 |

[40] | Bouriacha. A. Private communication |

[41] | DOI: 10.1137/0325023 · Zbl 0624.90083 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.