Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/67227
Title: Second-order methods for nonconvex optimization : theory and complexity analysis
Authors: Wang, Hong
Advisors: Chen, Xiaojun (AMA)
Keywords: Mathematical optimization.
Issue Date: 2016
Publisher: The Hong Kong Polytechnic University
Abstract: We consider the second-order methods for solving two classes of nonconvex minimization problem arising from diverse applications of optimization. By second-order methods, we refer to those methods involving second-order information of the objective function. The first class of nonconvex problem is the so-called Affine Rank Minimization Problem (ARMP), whose aim is to minimize the rank of a matrix over a given affine set. The other one is the Partially Separable Minimization Problem (PSMP), which is to minimize the objective function with a partially separable structure over a given convex set. This thesis hence can be sharply divided into two distinct parts. In the first part, we focus on exploring the ARMP utilizing the matrix factorization reformulation. Under some particular situations, we show that the corresponding factorization models are of the property that all second-order stationary points are global minimizers. By presuming such property holds, we propose an algorithm framework which outputs the global solution of the ARMP after solving a series of its factorization models with different ranks to the second-order necessary optimality. Finally, we put forward a conjecture that the reduction between the global minima of the low-rank approximation with consecutive ranks is monotonically decreasing with the increase of the rank. If this conjecture holds, we can accelerate the estimation of the optimal rank by an adaptive technique, and hence significantly increase the efficiency of the overall performance of our framework in solving ARMP. In the second part of this thesis, we mainly study the PSMP over a convex constraint. We first propose an adaptive regularization algorithm for solving PSMP, in which the expense of using high-order models is mitigated by the use of the partially separable structure. We then show that the algorithm using an order p model needs at most O(ε -p+1/p) evaluations of the objective function and its derivatives to arrive at an ε-approximate first-order stationary point. The complexity in terms of c is unaffected by the use of structure. An extension of the main idea is also presented for the case where the objective function might be non-Lipschitz continuous. We apply the algorithm with an adaptive cubic regularization term to solving the problem of data fitting involving the q-quasi norm for q ε(0, 1) and it turns out that even for non-Lipschitz case, the complexity bound O(ε -3/2) can be retained.
Description: PolyU Library Call No.: [THS] LG51 .H577P AMA 2016 WangH
xv, 139 pages :illustrations
URI: http://hdl.handle.net/10397/67227
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b29350530_link.htmFor PolyU Users208 BHTMLView/Open
b29350530_ira.pdfFor All Users (Non-printable)2.05 MBAdobe PDFView/Open
Show full item record

Page view(s)

31
Last Week
2
Last month
Checked on Aug 20, 2017

Download(s)

5
Checked on Aug 20, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.