On Solving Large-Scale Finite Minimax Problems using Exponential Smoothing

Abstract

This paper focuses on finite minimax problems with many functions, and their solutions by means of exponential smoothing. We conduct run-time complexity and rate of convergence analysis of smoothing algorithms and compare them with those of SQP algorithms. We find that smoothing algorithms may have only sublinear rate of convergence, but as shown by our complexity results, their slow rate of convergence may be compensated by small computational work per iteration. We present two smoothing algorithms with active-set strategies that reduce the effect of ill-conditioning using novel precision-parameter adjustment schemes. Numerical results indicate that the proposed algorithms are competitive with other smoothing and SQP algorithms, and they are especially efficient for large-scale minimax problems with a significant number of functions e-active at stationary points.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2010
Accession Number
ADA518716

Entities

People

  • E. Y. Pee
  • J. O. Royset

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Continuity
  • Convergence
  • Eigenvalues
  • Equations
  • Iterations
  • Multiplication Factor
  • Operations Research
  • Precision
  • Procedures (Computers)
  • Quadratic Programming
  • Sequences
  • Standards
  • Stationary
  • Test And Evaluation
  • Two Dimensional

Readers

  • Approximation Theory.
  • Operations Research