Return to search
## Convex relaxations for cubic polynomial problems

This dissertation addresses optimization of cubic polynomial problems. Heuristics for finding good quality feasible solutions and for improving on existing feasible solutions for a complex industrial problem, involving cubic and pooling constraints among other complicating constraints, have been developed. The heuristics for finding feasible solutions are developed based on linear approximations to the original problem that enforce a subset of the original problem constraints while it tries to provide good approximations for the remaining constraints, obtaining in this way nearly feasible solutions. The

performance of these heuristics has been tested by using industrial case studies that are

of appropriate size, scale and structure. Furthermore, the quality of the solutions can

be quantified by comparing the obtained feasible solutions against upper bounds on the

value of the problem.

In order to obtain these upper bounds we have extended efficient existing techniques for bilinear problems for this class of cubic polynomial problems. Despite the efficiency of the upper bound techniques good upper bounds for the industrial case problem could not be computed efficiently within a reasonable time limit (one hour). We have applied the same techniques to subproblems with

the same structure but about one fifth of the size and in this case, on average, the gap

between the obtained solutions and the computed upper bounds is about 3%.

In the remaining part of the thesis we look at global optimization of cubic polynomial

problems with non-negative bounded variables via branch and bound. A theoretical study on

the properties of convex underestimators for non-linear terms which are quadratic in one

of the variables and linear on the other variable is presented. A new underestimator is

introduced for this class of terms.

The final part of the thesis describes the numerical testing of the previously mentioned

underestimators together with approximations obtained by considering lifted approximations

of the convex hull of the (x x y) terms.

Two sets of instances are generated for this test and the descriptions of the procedures to

generate the instances are detailed here. By analyzing the numerical results we can

conclude that our proposed underestimator has the best behavior in the family of instances

where the only non-linear terms present are of the form (x x y).

Problems originating from least squares are much harder to solve than the other class of

problems. In this class of problems the efficiency of linear programming solvers plays a

big role and on average the methods that use these solvers perform better than the

others.

Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/47563 |

Date | 12 February 2013 |

Creators | Inacio, Helder |

Publisher | Georgia Institute of Technology |

Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |

Detected Language | English |

Type | Dissertation |

Page generated in 0.0017 seconds