Solving Nonlinear Programs Without Using Analytic Derivatives

A new algorithm for the minimization of a nonlinear function subject to linear inequality constraints is presented. It is an extension of Mifflin's local variations-approximate Newton nonderivative method for unconstrained minimization. At each iteration, the algorithm approximates first and second partial derivatives by differencing function values at feasible points along directions that are determined from a factorization of the currently active constraint matrix. Accumulation points of the algorithm satisfy the Karush-Kuhn-Tucker first order necessary optimality conditions if the objective function is continuously differentiable and appropriately bounded. Under stronger assumptions, every accumulation point of the algorithm also satisfies second-order-necessary optimality conditions. The rate of convergence of the algorithm is super-linear when the function is twice continuously differentiable and there is a unique accumulation point satisfying second order sufficiency conditions. A computer code for the algorithm is described and computational results on a substantial set of test problems included.