Tracing parametrized optima for inequality constrained nonlinear minimization problems

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Tech


A general algorithm for tracing the path of optima of inequality constrained optimization problems as a function of a parameter was developed in this research. The algorithm is an active set algorithm using a homotopy method to trace the path. A new feature of the algorithm is a capability of handling the transition points between segments in a routine way. The algorithm locates the transition points, and finds an active set for the next segment by considering all possible sets of active constraints. The nonoptimal sets are eliminated on the basis of the Lagrange multipliers and the derivatives of the optimal solutions with respect to the parameter.

The algorithm was implemented for three different problems. The first application, a spring-mass problem, was used to illustrate various kinds of transition events between segments. The second application, a well known ten-bar truss structural optimization problem, was used to validate the algorithm, since the numerical results for this problem have been obtained by other methods. The third application, bi-objective control-structure optimization, had an important engineering application. The numerical results obtained in this application could be used in the design process — they allowed selection of the best designs and provided some insight into behavior of the structure.

The sufficient conditions for persistence of the minima were given using the results of the stability theory, and the connection was shown between these results and classical optimization theory. For the standard nonlinear programming problem these conditions are equivalent to the Mangasarian-Fromovitz criterion and the standard second order sufficient optimality condition.

A method for computational verification of the conditions for persistence of the minima was proposed. By using Motzkin’s Transposition Theorem, the Mangasarian-Fromovitz criterion can be reduced to the problem of finding a feasible point for a linear optimization problem. In this form it can be easily solved by Phase I of the simplex method. It was shown that the linear programming problem can be transformed to the form of general nonlinear problem in such a way that the regularity of the constraints is preserved. Therefore for linear problems necessary and sufficient condition for solvability of the perturbed system can be verified computationally.

The results of bifurcation theory were used to characterize the possible points of discontinuity of the path. The necessary conditions for discontinuity of the path of optima can be checked by the developed algorithm with no extra work. The results of bifurcation theory were also used to describe the possible singularities of the path of optima and the behavior of the path near singular points.