Academic Commons

Theses Doctoral

Cutting Planes for Convex Objective Nonconvex Optimization

Michalka, Alexander

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.


  • thumnail for Michalka_columbia_0054D_11603.pdf Michalka_columbia_0054D_11603.pdf binary/octet-stream 889 KB Download File

More About This Work

Academic Units
Industrial Engineering and Operations Research
Thesis Advisors
Bienstock, Daniel
Ph.D., Columbia University
Published Here
October 17, 2013