Solving nonconvex nonlinear programs with reverse convex constraints by sequential linear programming

• Author: Pawel Kalczynski,Zvi Drezner
• Date: 01 May 2020
• Published date: 01 May 2020
• DOI: http://doi.org/10.1111/itor.12736

Intl. Trans. in Op. Res. 27 (2020) 1320–1342

DOI: 10.1111/itor.12736

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Solving nonconvex nonlinear programs with reverse convex

constraints by sequential linear programming

Zvi Drezner and Pawel Kalczynski

Steven G. Mihaylo Collegeof Business and Economics, California State University-Fullerton, Fullerton, CA 92834, USA

E-mail: zdrezner@fullerton.edu [Drezner];pkalczynski@fullerton.edu [Kalczynski]

Received 20 February2019; received in revised form 27 August 2019; accepted 27 September 2019

Abstract

The sequential linear programming(SLP) method for solving nonlinear problems was introduced in the 1960s.

Many papers that attempted to use SLP reported poor performance and convergence issues. We found that

nonlinear programs with reverse convex constraints, which are the most difficult nonlinear programs with

many local optima, are solved (heuristically) very well by SLP. We proved that for this type of problems,

the solutions to the sequence of the linear programming problems converge to a local optimum. Since the

final solution depends on the starting solution, we propose to apply SLP in a multistart approach starting

from randomly generated solutions. This multistart SLP is very easy to implement. We recommend that the

research community reconsiders the application of SLP for this type of problems.

Keywords:nonconvex optimization; heuristic procedures; sequential linear programs

1. Introduction

The concept of “sequential linear programming” (SLP) was introducedas early as the 1960s (Cour-

tillot, 1962). Consider a typical nonlinear optimization problem:

max{g(X)},

subject to: (1)

fi(X)≥bifor i=1,...m,

where Xis a vector of nvariable s and mis the number of constraints.

The SLP algorithm starts with a feasible solution X. A possibly better solution is found by

solving a linear programming problem. We replace each function by its tangent surface at the point

X, defining the linear functions (tangent planes)

gL(X)=g(X)+∇g(X)(X−X);fL

i(X)=fi(X)+∇fi(X)(X−X)

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

Z. Drezner and P. Kalczynski / Intl. Trans.in Op. Res. 27 (2020) 1320–1342 1321

Convex Outside Convex

Fig. 1. Convex and outside convexconstraints.

and solve the linear program:

maxgL(X),

subject to: (2)

fL

i(X)≥bifor i=1,...m.

If there are additional linear constraints in the original formulation, such constraints can be added

to the linear program (2). The solution serves as the ¯

Xfor the next iteration until convergence.

Most attempts to utilize SLP report convergence issues necessitating the ad hoc establishment

of moving limits and were not that efficient (Bhaviktti and Ramakrishnan, 1980; John et al., 1987;

Chen, 1993). For example, Chen (1993) proposed six methods for establishing moving limits, which

complicates the procedure significantly.These methods were tested on relatively small problems and

some even failed to convergein some instances. However, we observed that when the constraints are

outside convex regions, the simple linear programming solution is feasible to the original problem

and therefore, must converge to a local optimum. No additional modifications/complications are

necessary in this case.

Consider the illustration in Fig. 1. The objective is to maximize x, that is, finding the right-

most feasible point. On the left are three convex constraints forming a convex triangle-like shape.

The three tangent lines form a “big” triangle, in which most of it is infeasible. The linear pro-

gramming solution is on the right vertex of the triangle, which is infeasible quite far from the

optimum. Therefore, researches who attempted to use SLP for convex problems had to design

“moving limits” to stop the solution of the linear programming from moving all the way to its

optimum. On the other hand, on the right of the figure the constraints are outside convex areas.

The triangle-like nonconvex feasible area leads to a linear programming in a triangle, which is all

feasible and the solution to the linear programming (a vertex of the triangle) is very close to the

optimum.

Using such an SLP approach for convex problems does not work well because a feasible solution

to the linear program may not be feasible for the original nonlinear program. If a constraint is

convex, then the tangent to the convex region is outside the region and usually the “distance” from

the feasible region increases as we move further away from the point on the periphery at which the

tangent is generated. For example, if the constraint restricts the solution to be inside a circle, the

tangent line to a point on the periphery of that circle is outside the circle and thus infeasible. If a

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies