HomeHome

Cutting Planes for Convex Objective Nonconvex Optimization

Alexander Michalka

Title:
Cutting Planes for Convex Objective Nonconvex Optimization
Author(s):
Michalka, Alexander
Thesis Advisor(s):
Bienstock, Daniel
Date:
Type:
Theses
Degree:
Ph.D., Columbia University
Department(s):
Industrial Engineering and Operations Research
Persistent URL:
Abstract:
This thesis studies methods for tightening relaxations of optimization problems with convex objective values over a nonconvex domain. A class of linear inequalities obtained by lifting easily obtained valid inequalities is introduced, and it is shown that this class of inequalities is sufficient to describe the epigraph of a convex and differentiable function over a general domain. In the special case where the objective is a positive definite quadratic function, polynomial time separation procedures using the new class of lifted inequalities are developed for the cases when the domain is the complement of the interior of a polyhedron, a union of polyhedra, or the complement of the interior of an ellipsoid. Extensions for positive semidefinite and indefinite quadratic objectives are also studied. Applications and computational considerations are discussed, and the results from a series of numerical experiments are presented.
Subject(s):
Industrial engineering
Item views
919
Metadata:
text | xml
Suggested Citation:
Alexander Michalka, , Cutting Planes for Convex Objective Nonconvex Optimization, Columbia University Academic Commons, .

Columbia University Libraries | Policies | FAQ