Back to search

Clemson University

Convex Hulls, Relaxations, and Approximations of General Monomials and Multilinear Functions

Abstract

dc:description.abstract

Motivated by a variety of problems in global optimization and integer programming that involve multilinear expressions of discrete or continuous variables, this research derives approxima-tions of multilinear functions, and studies the accuracy of these approximations through worst-case error-analyses: • The derivation of the convex hull representations of large families of symmetric multilinear polynomials (SMPs) that are defined over box constraints through geometrical exploitation of the polytope symmetry and specially designed facet generation method; and • The identification of the set of all points at which a nonnegative multilinear polynomial on a box vanishes, which applies to the identification of the set of all points which satisfy any facet at equality. • The worst-case error analysis associated with linearizations of monomial expressions in boun-ded discrete and/or continuous variables: for certain families of variable-bound structures, the worst-case errors associated with convex hull forms are studied, along with the identification of all points which produce these errors. • The worst-case error analysis associated with replacing the multilinear monomial term with a “best” approximating linear function, in contrast to the previous item on “convex hull linearization:” using the results of the first item, explicit convex hull forms are exploited to identify the “best” linear functions.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Xu, Yibo
Contributors dc:contributor
  • Dr. Warren Adams, Committee Chair
  • Dr. Xuhong Gao
  • Dr. Matthew Saltzman
  • Dr. Cole Smith

Subjects

dc:subject × 5

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/2094

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Xu, Yibo. Convex Hulls, Relaxations, and Approximations of General Monomials and Multilinear Functions. Dissertation thesis, https://open.clemson.edu/all_dissertations/2094