Using eigenvalue techniques to obtain better bounds for convex

Event Details
  • Date/Time:
    • Tuesday November 3, 2009
      11:00 am - 12:00 pm
  • Location: Executive classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    $0.00
  • Extras:
Contact
Renato Monteiro
ISyE
Contact Renato Monteiro
404-894-2300
Summaries

Summary Sentence: Using eigenvalue techniques to obtain better bounds for convex

Full Summary: Using eigenvalue techniques to obtain better bounds for convex objective, non-convex optimization problems

TITLE: Using eigenvalue techniques to obtain better bounds for convex objective, non-convex optimization problems

SPEAKER: Dr. Daniel Bienstock

ABSTRACT:

Consider the problem of optimizing a convex function subject to nonconvex constraints; in particular, minimizing a positive-definite quadratic subject to nonconvex constraints. The approach favored by discrete optimizers would rely on solving some (hopefully strong) convex relaxation of the problem, and then resorting to branching and/or cutting. However, when the objective is convex, this approach will fail, because even if the relaxation consists of the convex hull of the feasible region, the optimum over the relaxation will typically be infeasible, and (typically) "far away" from the feasible region, yielding a very poor estimate (lower bound) on the value of the problem.

We describe a simple technique that relies on the so-called S-Lemma and on combinatorial estimates of the distance from a point to the feasible region, to obtain fast, strong bounds on the value of interesting cases of the situation described in the above paragraph.

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
convex, nonconvex
Status
  • Created By: Anita Race
  • Workflow Status: Draft
  • Created On: Feb 16, 2010 - 9:49am
  • Last Updated: Oct 7, 2016 - 9:50pm