Interior-point methods for nonconvex nonlinear programming: Jamming and numerical testing

The paper considers an example of Wächter and Biegler which is shown to converge to a nonstationary point for the standard primal–dual interior-point method for nonlinear programming. The reason for this failure is analyzed and a heuristic resolution is discussed. The paper then characterizes the performance of LOQO, a line-search interior-point code, on a large test set of nonlinear programming problems. Specific types of problems which can cause LOQO to fail are identified.Research of the first and third authors supported by NSF grant DMS-9870317, ONR grant N00014-98-1-0036.Research of the second author supported by NSF grant DMS-9805495.     

A constraint shifting homotopy method for general non-linear programming

In this article, a constraint shifting homotopy method (CSHM) is proposed for solving non-linear programming with both equality and inequality constraints. A new homotopy is constructed, and existence and global convergence of a homotopy path determined by it are proven. All problems that can be solved by the combined homotopy interior point method (CHIPM) can also be solved by the proposed method. In contrast to the combined homotopy infeasible interior point method (CHIIPM), it needs a weaker regularity condition. And the starting point in the proposed method is not necessarily a feasible point or an interior point, so it is more convenient to be implemented than CHIPM and CHIIPM. Numerical results show that the proposed algorithm is feasible and effective.     

Global convergence analysis of the aggregate constraint homotopy method for nonlinear programming problems with both inequality and equality constraints

In this paper, we construct appropriate aggregate mappings and a new aggregate constraint homotopy (ACH) equation by converting equality constraints to inequality constraints and introducing two variable parameters. Then, we propose an ACH method for nonlinear programming problems with inequality and equality constraints. Under suitable conditions, we obtain the global convergence of this ACH method, which makes us prove the existence of a bounded smooth path that connects a given point to a Karush–Kuhn–Tucker point of nonlinear programming problems. The numerical tracking of this path can lead to an implementable globally convergent algorithm. A numerical procedure is given to implement the proposed ACH method, and the computational results are reported.     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.     

An accelerated multiplier method for nonlinear programming

This paper describes an accelerated multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems. The unconstrained problems are solved using a rank-one recursive algorithm described in an earlier paper. Multiplier estimates are obtained by minimizing the error in the Kuhn-Tucker conditions using a quadratic programming algorithm. The convergence of the sequence of unconstrained problems is accelerated by using a Newton-Raphson extrapolation process. The numerical effectiveness of the algorithm is demonstrated on a relatively large set of test problems.This work was supported by the US Air Force under Contract No. F04701-74-C-0075.     

Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods

The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance. Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000     

A second-order method for the general nonlinear programming problem

This paper presents a multiplier-type method for nonlinear programming problems with both equality and inequality constraints. Slack variables are used for the inequalities. The penalty coefficient is adjusted automatically, and the method converges quadratically to points satisfying second-order conditions.The work of the first author was supported by NSF RANN and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by the National Science Foundation Grant No. ENG73-08214A01 and US Army Research Office Durham Contract No. DAHC04-73-C-0025.     

A filter method for nonlinear semidefinite programming with global convergence

In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective.     

An adaptation of homotopy analysis method for reliable treatment of strongly nonlinear problems: construction of homotopy polynomials

In this paper, a new adaption of homotopy analysis method is presented to handle nonlinear problems. The proposed approach is capable of reducing the size of calculations and easily overcome the difficulty arising in calculating complicated integrals. Furthermore, the homotopy polynomials that decompose the nonlinear term of the problem as a series of polynomials are introduced. Then, an algorithm of calculating such polynomials, which makes the solution procedure more straightforward and more effective, is constructed. Numerical examples are examined to highlight the significant features of the developed techniques. The algorithms described in this paper are expected to be further employed to solve nonlinear problems in mathematical physics. Copyright © 2014 John Wiley & Sons, Ltd.     

Exact solutions for nonlinear Burgers' equation by homotopy perturbation method

The aim of this article is to construct a new efficient recurrent relation to solve nonlinear Burgers' equation. The homotopy perturbation method is used to solve this equation. Because Burgers' equation arises in many applications, it is worth trying new solution methods. Comparison of the results with those of Adomian's decomposition method leads to significant consequences. Four standard problems are used to illustrate the method. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

A combined penalty function and gradient projection method for nonlinear programming

A new programming algorithm for nonlinear constrained optimization problems is proposed. The method is based on the penalty function approach and thereby circumyents the necessity to maintain feasibility at each iteration, but it also behaves much like the gradient projection method. Although only first-order information is used, the algorithm converges asymptotically at a rate which is independent of the magnitude of the penalty term; hence, unlike the simple gradient method, the asymptotic rate of the proposed method is not affected by the ill-conditioning associated with the introduction of the penalty term. It is shown that the asymptotic rate of convergence of the proposed method is identical with that of the gradient projection method.Dedicated to Professor M. R. HestenesThis research was supported by the National Science Foundation, Grant No. GK-16125.     

A discrete dynamic convexized method for nonlinear integer programming

In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust.     

A homotopy method for nonlinear semidefinite programming

In this paper, for solving the nonlinear semidefinite programming problem, a homotopy is constructed by using the parameterized matrix inequality constraint. Existence of a smooth path determined by the homotopy equation, which starts from almost everywhere and converges to a Karush–Kuhn–Tucker point, is proven under mild conditions. A predictor-corrector algorithm is given for numerically tracing the smooth path. Numerical tests with nonlinear semidefinite programming formulations of several control design problems with the data contained in COMPl _e ib are done. Numerical results show that the proposed algorithm is feasible and applicable.     

A one-step smoothing Newton method for second-order cone programming

A new smoothing function for the second-order cone programming is given by smoothing the symmetric perturbed Fischer–Burmeister function. Based on this new function, a one-step smoothing Newton method is presented for solving the second-order cone programming. The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. This algorithm does not have restrictions regarding its starting point and is Q-quadratically convergent. Numerical results suggest the effectiveness of our algorithm.     

A homotopy interior point method for semi-infinite programming problems

This paper presents a homotopy interior point method for solving a semi-infinite programming (SIP) problem. For algorithmic purpose, based on bilevel strategy, first we illustrate appropriate necessary conditions for a solution in the framework of standard nonlinear programming (NLP), which can be solved by homotopy method. Under suitable assumptions, we can prove that the method determines a smooth interior path from a given interior point to a point w ^*, at which the necessary conditions are satisfied. Numerical tracing this path gives a globally convergent algorithm for the SIP. Lastly, several preliminary computational results illustrating the method are given.     

Solving nonconvex nonlinear programming problems via a new aggregate constraint homotopy method

In this paper, by introducing C² mappings ξ_i(x,z_i),i=1,…,m and using the idea of the aggregate function method, a new aggregate constraint homotopy method is proposed to solve the Karush-Kuhn-Tucker (KKT) point of nonconvex nonlinear programming problems. Compared with the previous results, the choice scope of initial points is greatly enlarged, so use of the new aggregate constraint homotopy method may improve the computational efficiency of reduced predictor-corrector algorithms.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

A new technique of using homotopy analysis method for solving high‐order nonlinear differential equations

In this paper, a new technique of homotopy analysis method (HAM) is proposed for solving high‐order nonlinear initial value problems. This method improves the convergence of the series solution, eliminates the unneeded terms and reduces time consuming in the standard homotopy analysis method (HAM) by transform the nth‐order nonlinear differential equation to a system of n first‐order equations. Second‐ and third‐ order problems are solved as illustration examples of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.     

A globally convergent method for nonlinear programming

Recently developed Newton and quasi-Newton methods for nonlinear programming possess only local convergence properties. Adopting the concept of the damped Newton method in unconstrained optimization, we propose a stepsize procedure to maintain the monotone decrease of an exact penalty function. In so doing, the convergence of the method is globalized.This research was supported in part by the National Science Foundation under Grant No. ENG-75-10486.