liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On Efficiently Combining Limited Memory and Trust-Region Techniques
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0003-1836-4200
Samsung Advanced Institute of Technology, China Lab, Beijing, China.
State Key Laboratory of Scientic and Engineering Computing, Institute of Computational.
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2013 (English)Report (Other academic)
Abstract [en]

Limited memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited memory methods are usually combined with a line search. We show how to efficiently combine limited memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead compared with the cost of computing the quasi-Newton direction in line-search limited memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2013. , 33 p.
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2013:13
Keyword [en]
Unconstrained Optimization; Large-scale Problems; Limited Memory Methods;
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-102005ISRN: LiTH-MAT-R--2013/13--SEOAI: oai:DiVA.org:liu-102005DiVA: diva2:667359
Available from: 2013-11-26 Created: 2013-11-26 Last updated: 2016-01-12Bibliographically approved
In thesis
1. Large-Scale Optimization Methods with Application to Design of Filter Networks
Open this publication in new window or tab >>Large-Scale Optimization Methods with Application to Design of Filter Networks
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Nowadays, large-scale optimization problems are among those most challenging. Any progress in developing methods for large-scale optimization results in solving important applied problems more effectively. Limited memory methods and trust-region methods represent two ecient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited memory methods are usually combined with a line search. We develop new limited memory trust-region algorithms for large-scale unconstrained optimization. They are competitive with the traditional limited memory line-search algorithms.

In this thesis, we consider applied optimization problems originating from the design of lter networks. Filter networks represent an ecient tool in medical image processing. It is based on replacing a set of dense multidimensional lters by a network of smaller sparse lters called sub-filters. This allows for improving image processing time, while maintaining image quality and the robustness of image processing.

Design of lter networks is a nontrivial procedure that involves three steps: 1) choosing the network structure, 2) choosing the sparsity pattern of each sub-filter and 3) optimizing the nonzero coecient values. So far, steps 1 and 2 were mainly based on the individual expertise of network designers and their intuition. Given a sparsity pattern, the choice of the coecients at stage 3 is related to solving a weighted nonlinear least-squares problem. Even in the case of sequentially connected lters, the resulting problem is of a multilinear least-squares (MLLS) type, which is a non-convex large-scale optimization problem. This is a very dicult global optimization problem that may have a large number of local minima, and each of them is singular and non-isolated. It is characterized by a large number of decision variables, especially for 3D and 4D lters.

We develop an effective global optimization approach to solving the MLLS problem that reduces signicantly the computational time. Furthermore, we  develop efficient methods for optimizing sparsity of individual sub-filters  in lter networks of a more general structure. This approach offers practitioners a means of nding a proper trade-o between the image processing quality and time. It allows also for improving the network structure, which makes automated some stages of designing lter networks.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2014. 52 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1561
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-103646 (URN)10.3384/diss.diva-103646 (DOI)978-91-7519-456-1 (ISBN)
Public defence
2014-02-26, Nobel (BL32), B-huset, Campus Valla, Linköping University, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2014-02-03 Created: 2014-01-21 Last updated: 2015-06-02Bibliographically approved

Open Access in DiVA

On Efficiently Combining Limited Memory and Trust-Region Techniques(367 kB)180 downloads
File information
File name FULLTEXT03.pdfFile size 367 kBChecksum SHA-512
7ba053a301f8e99883de2254ca6b074900f79f139a5fc00574cf70a4135d15663f2b0cd88a0a37e62655678d2cb60e3a766d6151d83a778a2be11c38643d42e5
Type fulltextMimetype application/pdf

Authority records BETA

Burdakov, OlegZikrin, Spartak

Search in DiVA

By author/editor
Burdakov, OlegZikrin, Spartak
By organisation
Optimization The Institute of Technology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 993 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 1319 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf