Kawase, Yasushi ;
Makino, Kazuhisa
Surrogate Optimization for pNorms
Abstract
In this paper, we study the effect of surrogate objective functions in optimization problems. We introduce surrogate ratio as a measure of such effect, where the surrogate ratio is the ratio between the optimal values of the original and surrogate objective functions.
We prove that the surrogate ratio is at most mu^{1/p  1/q} when the objective functions are p and qnorms, and the feasible region is a mudimensional space (i.e., a subspace of R^mu), a muintersection of matroids, or a muextendible system. We also show that this is the best possible bound. In addition, for musystems, we demonstrate that the ratio becomes mu^{1/p} when p < q and unbounded if p > q. Here, a musystem is an independence system such that for any subset of ground set the ratio of the cardinality of the largest to the smallest maximal independent subset of it is at most mu. We further extend our results to the surrogate ratios for approximate solutions.
BibTeX  Entry
@InProceedings{kawase_et_al:LIPIcs:2016:6811,
author = {Yasushi Kawase and Kazuhisa Makino},
title = {{Surrogate Optimization for pNorms}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {41:141:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6811},
URN = {urn:nbn:de:0030drops68118},
doi = {10.4230/LIPIcs.ISAAC.2016.41},
annote = {Keywords: surrogate optimization, matroid, extendible system, pnorm}
}
07.12.2016
Keywords: 

surrogate optimization, matroid, extendible system, pnorm 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

07.12.2016 