Brown Bag Seminar - March 29, 2005
Speaker: Fabio Tardella
Affiliation: Department of Mathematics for Economics Finance and Insurance, University of Rome "La Sapienza"
Title: An extension of the fundamental theorems of Linear and Quadratic Programming and applications
Time: 12:00 - 1:00 PM
Location: RUTCOR Building - Lounge, Rutgers University, Busch
Campus, Piscataway, NJ
Abstract:
We describe a common extension of the fundamental theorem of Linear
Programming on the existence of a global minimum in a vertex for lower
bounded linear programs, and of the Frank-Wolfe (fundamental) theorem on
the existence of the minimum of a lower bounded quadratic programming
problem.
We then show that several known and new results providing continuous
formulations for discrete optimization problems can be easily derived and
generalized with our result. These include the Quadratic Programming
formulation of the maximum clique problem by Motzkin and Straus and its
weighted extension by Gibbons et al., the equivalence between the
minimization of a multilinear function on the continuous and discrete unit
hypercube by Rosenberg, and a recent continuous polynomial formulation of
the maximum independent set problem by Abello et al.
Furthermore, we use our extension of the fundamental theorem of Linear
Programming to obtain combinatorial formulations and polynomiality results
for some nonlinear problems with simple polyhedral constraints, like
nonconvex (standard) quadratic programming.
Back to Seminars Page.
Back to RUTCOR homepage.
| 
