Date

2019

Document Type

Dissertation

Degree

Doctor of Philosophy

Department

Industrial Engineering

First Adviser

Zuluaga, Luis F.

Abstract

This thesis focuses on solution techniques for non-convex optimization problems. The first part of the dissertation presents a generalization of the completely positive reformulation of quadratically constrained quadratic programs (QCQPs) to polynomial optimization problems. We show that by explicitly handling the linear constraints in the formulation of the POP, one obtains a refinement of the condition introduced in Bai's (2015) Thoerem on QCQPs, where the refined theorem only requires nonnegativity of polynomial constraints over the feasible set of the linear constraints. The second part of the thesis is concerned with globally solving non-convex quadratic programs (QPs) using integer programming techniques. More specifically, we reformulate non-convex QP as a mixed-integer linear problem (MILP) by incorporating the KKT condition of the QP to obtain a linear complementary problem, then use binary variables and big-M constraints to model the complementary constraints. We show how to impose bounds on the dual variables without eliminating all the (globally) optimal primal solutions; using some fundamental results on the solution of perturbed linear systems. The solution approach is implemented and labeled as quadprogIP, where computational results are presented in comparison with quadprogBB, BARON and CPLEX. The third part of the thesis involves the formulation and solution approach of a problem that arises from an on-demand aviation transportation network. A multi-commodity network flows (MCNF) model with side constraints is proposed to analyze and improve the efficiency of the on-demand aviation network, where the electric vertical-takeoff-and-landing (eVTOLs) transportation vehicles and passengers can be viewed as commodities, and routing them is equivalent to finding the optimal flow of each commodity through the network. The side constraints capture the decisions involved in the limited battery capacity for each eVTOL. We propose two heuristics that are efficient in generating integer feasible solutions that are feasible to the exponential number of battery side constraints. The last part of the thesis discusses a solution approach for copositive programs using linear semi-infinite optimization techniques. A copositive program can be reformulated as a linear semi-infinite program, which can be solved using the cutting plane approach, where each cutting plane is generated by solving a standard quadratic subproblem. Numerical results on QP-reformulated copositive programs are presented in comparison to the approximation hierarchy approach in Bundfuss (2009) and Yildirim (2012).

Share

COinS