Piecewise linear approximation for nonlinear programming problems

Date

2016-07-26

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

This research primarily focuses on mathematical optimization (or mathematical programming) problems. In particular, we study optimization problems which have a nonlinear separable objective function with multiple variables. We present an algorithm which uses piecewise linear functions to approximate the nonlinear objective function. The algorithm is different from other piecewise linear approximation techniques in that we begin with a coarse piecewise linear function consisting of only one line segment per variable, and use this coarse approximation to relax the original problem to a linear programming problem (LP). The LP is then solved using an optimization software package, and the resulting optimal solution is used to determine additional breakpoints for new piecewise linear function approximations in the next iteration. In this way, the piecewise linear approximations are coarse in the beginning, but they are refined after each iteration using the optimal solution to the LP relaxation in the previous step. The point is to choose breakpoints for piecewise linear approximations intelligently rather than simply choosing a large number of uniform breakpoints at the beginning.

Results are presented for randomly generated problems of six different sizes. The results are promising in that the algorithm is very fast, while retaining some level of accuracy.

Description

Keywords

Piecewise linear, Nonlinear programming

Citation