On Some Optimization Problems that Can Be Solved in O(n) Time

Yanqin Bai, Kees Roos*

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Abstract

We consider nine elementary problems in optimization. We simply explore the conditions for optimality as known from the duality theory for convex optimization. This yields a quite straightforward solution method for each of these problems. The main contribution of this paper is that we show that even in the harder cases the solution needs only O(n) time.

Original languageEnglish
Title of host publicationNumerical Analysis and Optimization, NAOV 2020
EditorsMehiddin Al-Baali, Anton Purnama, Lucio Grandinetti
Place of PublicationCham
PublisherSpringer
Pages81-108
Number of pages28
ISBN (Electronic)978-3-030-72040-7
ISBN (Print)978-3-030-72039-1
DOIs
Publication statusPublished - 2021
Event5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020 - Muscat, Oman
Duration: 6 Jan 20209 Jan 2020

Publication series

NameSpringer Proceedings in Mathematics and Statistics
Volume354
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

Conference

Conference5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020
Country/TerritoryOman
CityMuscat
Period6/01/209/01/20

Bibliographical note

Accepted author manuscript

Keywords

  • Linear time methods
  • Optimality conditions
  • Optimization problems

Fingerprint

Dive into the research topics of 'On Some Optimization Problems that Can Be Solved in O(n) Time'. Together they form a unique fingerprint.

Cite this