Optimization Online


Set Intersection Theorems and Existence of Optimal Solutions

Dimitri Bertsekas (dimitrib***at***mit.edu)
Paul Tseng (tseng***at***math.washington.edu)

Abstract: The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We introduce the new notion of an asymptotic direction of a sequence of closed sets, and the associated notions of retractive, horizon, and critical directions, and we provide several conditions that guarantee the nonemptiness of the corresponding intersection. We show how these conditions can be used to obtain simple proofs of some known results on existence of optimal solutions, and to derive some new results, including an extension of the Frank-Wolfe Theorem for (nonconvex) quadratic programming.

Keywords: Existence of solutions, recession directions, Frank-Wolfe Theorem, quadratic programming

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Lab. for Information and Decision Systems Report 2628, Mass. Institute of Technology, Cambridge, MA, 02139

Download: [PDF]

Entry Submitted: 12/30/2004
Entry Accepted: 12/30/2004
Entry Last Modified: 12/30/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society