Applications of Semidefinite Programming
公开可下载的内容
open in viewerSemidefinite programming is a type of convex optimization that aims to optimize a linear function, the trace of the product of a matrix and the variable matrix X, while subject to nonlinear constraints. In a semidefinite program (SDP), the decision matrix X is required to be positive semidefinite.\n\nWe examine an interior point method for solving SDPs and explore its application to the Quadratic Assignment Problem (QAP), an NP-hard problem used to assign n facilities to n locations, minimizing the quadratic objective function of the product of distances between locations and flow between facilities.\n\nUsing a relaxation of the QAP formulation into an SDP, we solve QAP relaxations using the NEOS solver, a web service for numerical optimization, with the interior point method described above.
- This report represents the work of one or more WPI undergraduate students submitted to the faculty as evidence of completion of a degree requirement. WPI routinely publishes these reports on its website without editorial or peer review.
- Creator
- Publisher
- Identifier
- E-project-042419-000617
- Advisor
- Year
- 2019
- Date created
- 2019-04-24
- Resource type
- Major
- Rights statement
关系
- 属于 Collection:
项目
Permanent link to this page: https://digital.wpi.edu/show/c821gn10v