License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.41
URN: urn:nbn:de:0030-drops-68118
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6811/
Go to the corresponding LIPIcs Volume Portal

Kawase, Yasushi ; Makino, Kazuhisa

Surrogate Optimization for p-Norms

pdf-format:
LIPIcs-ISAAC-2016-41.pdf (0.5 MB)

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 q-norms, and the feasible region is a mu-dimensional space (i.e., a subspace of R^mu), a mu-intersection of matroids, or a mu-extendible system. We also show that this is the best possible bound. In addition, for mu-systems, we demonstrate that the ratio becomes mu^{1/p} when p < q and unbounded if p > q. Here, a mu-system 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 p-Norms}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{41:1--41:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6811},
  URN =		{urn:nbn:de:0030-drops-68118},
  doi =		{10.4230/LIPIcs.ISAAC.2016.41},
  annote =	{Keywords: surrogate optimization, matroid, extendible system, p-norm}
}

Keywords: surrogate optimization, matroid, extendible system, p-norm
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI