A weighted Mirror Descent algorithm for nonsmooth convex optimization problem

File Description SizeFormat 
art%3A10.1007%2Fs10957-016-0963-5.pdfPublished version513.87 kBAdobe PDFDownload
Title: A weighted Mirror Descent algorithm for nonsmooth convex optimization problem
Author(s): Parpas, P
Rustem
Duy V.N. Luong
Rueckert
Item Type: Journal Article
Abstract: Large scale nonsmooth convex optimization is a common problem for a range of computational areas including machine learning and computer vision. Problems in these areas contain special domain structures and characteristics. Special treatment of such problem domains, exploiting their structures, can significantly reduce the computational burden. In this paper, we consider a Mirror Descent method with a special choice of distance function for solving nonsmooth optimization problems over a Cartesian product of convex sets. We propose to use a nonlinear weighted distance in the projection step. The convergence analysis identifies optimal weighting parame ters that, eventually, lead to the optimally weighted step-size strategy for every projection on a corresponding convex set. We show that the optimality bound of the Mirror Descent algorithm using the weighted distance is either an improvement to, or in the worst-case as good as, the optimality bound of the Mirror Descent using unweighted distances. We demonstrate the efficiency of the algorithm by solving the Markov Random Fields (MRF) optimization problem. In order to exploit the domain of the MRF problem, we use a weighted logentropy distance and a weighted Euclidean distance. Promising experimental results demonstrate the effectiveness of the proposed method.
Publication Date: 14-Jun-2016
Date of Acceptance: 31-May-2016
URI: http://hdl.handle.net/10044/1/33370
DOI: https://dx.doi.org/10.1007/s10957-016-0963-5
ISSN: 1573-2878
Publisher: Springer Verlag (Germany)
Start Page: 900
End Page: 915
Journal / Book Title: Journal of Optimization Theory and Applications
Volume: 170
Issue: 3
Sponsor/Funder: Commission of the European Communities
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Funder's Grant Number: FP7 - 321698
EP/K040723/1
EP/M028240/1
Copyright Statement: © The Author(s) 2016. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Keywords: Operations Research
0102 Applied Mathematics
0103 Numerical And Computational Mathematics
0906 Electrical And Electronic Engineering
Publication Status: Published
Appears in Collections:Faculty of Engineering
Computing



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

Creative Commons