A Variable-Complexity Norm Maximization Problem.

Abstract

The solution set to many important constrained optimization problems is a set that is bounded by planes. When such a set is bounded it is useful to find the size of a largest element in that set. In this work we show that this problem may be extremely easy or difficult depending on the measure of size (norm) employed. For one such measure the problem is relatively easy while for all other measures it is intractable. However the problem of merely finding an upper bound for the size of the largest element turns out to be a surprisingly simple problem that can be solved by a single linear program. Keywords include: Optimization, maximum norm, complexity theory, NP-complete.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1985
Accession Number
ADA153514

Entities

People

  • Olvi L. Mangasarian
  • T. H. Shiau

Organizations

  • University of Wisconsin–Madison

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computational Complexity
  • Contracts
  • Convex Programming
  • Evolutionary Algorithms
  • Linear Programming
  • Materials
  • Mathematical Programming
  • Mathematics
  • North Carolina
  • Operations Research
  • Optimization
  • Polynomials
  • United States
  • Wisconsin

Fields of Study

  • Mathematics

Readers

  • Operations Research