Efficient method for finding globally optimal solution of problem with weighted Lp norm and L2 norm objective function

• Published in: IET signal processing 2016-06, Vol.10 (4), p.366-375
• Main Authors: Li, Ya, Xie, Langxiong, Ling, Bingo Wing-Kuen, Cao, Jiangzhong, Dai, Qingyun
• Format: Article
• Language: English
• Subjects: concave programming; image reconstruction; iterative method; iterative methods; L1 norm N independent one‐dimensional optimisation problem sequence; L2 norm SSF iterative shrinkage algorithm; non‐convex optimisation problems; N‐dimensional optimisation problem; separable surrogate functional iterative shrinkage algorithm; weighted L2 norm objective function; weighted Lp norm objective function
• ISSN: 1751-9675; 1751-9683; 1751-9683
• DOI: 10.1049/iet-spr.2014.0240

This study proposes an iterative method to approximate an N-dimensional optimisation problem with a weighted Lp and L2 norm objective function by a sequence of N independent one-dimensional optimisation problems. Inspired by the existing weighted L1 and L2 norm separable surrogate functional (SSF) iterative shrinkage algorithm, there are N independent one-dimensional optimisation problems with weighted Lp and L2 norm objective functions. However, these optimisation problems are non-convex. Hence, they may have more than one locally optimal solutions and it is very difficult to find their globally optimal solutions. This paper proposes to partition the feasible set of each approximated problem into various regions such that the sign of the convexity of the objective function in each region remains unchanged. Here, there is no more than one stationary point in each region. By finding the stationary point in each region, the globally optimal solution of each approximated optimisation problem can be found. Besides, this study also shows that the sequence of the globally optimal solutions of the approximated problems converge to the globally optimal solution of the original optimisation problem. Computer numerical simulation results show that the proposed method outperforms the existing weighted L1 and L2 norm SSF iterative shrinkage algorithm.