Regularized Step Directions in Conjugate Gradient Minimization for Machine Learning

Conjugate gradient minimization methods (CGM) and their accelerated variants are widely used in machine learning applications. We focus on the use of cubic regularization to improve the CGM direction independent of the steplength (learning rate) computation. Using Shanno’s reformulation of CGM as a memoryless BFGS method, we derive new formulas for the regularized step direction, … Read more

A Mixed Integer Nonlinear Programming Framework for Fixed Path Coordination of Multiple Underwater Vehicles under Acoustic Communication Constraints

Mixed Integer Nonlinear Programming (MINLP) techniques are increasingly used to address challenging problems in robotics, especially Multi-Vehicle Motion Planning (MVMP). The main contribution of this paper is a discrete time-distributed Receding Horizon Mixed Integer Nonlinear Programming (RH-MINLP) formulation of the underwater multi-vehicle path coordination problem with constraints on kinematics, dynamics, collision avoidance, and acoustic communication … Read more

Interior-Point Methods for Nonconvex Nonlinear Programming: Primal-Dual Methods and Cubic Regularization

In this paper, we present a primal-dual interior-point method for solving nonlinear programming problems. It employs a Levenberg-Marquardt (LM) perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the LM perturbation is equivalent to replacing the Newton step by a … Read more

Interior-Point Methods for Nonconvex Nonlinear Programming: Cubic Regularization

In this paper, we present a barrier method for solving nonlinear programming problems. It employs a Levenberg-Marquardt perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the Levenberg-Marquardt perturbation is equivalent to replacing the Newton step by a cubic regularization … Read more

Convergence Analysis of an Interior-Point Method for Nonconvex Nonlinear Programming

In this paper, we present global and local convergence results for an interior-point method for nonlinear programming. The algorithm uses an $\ell_1$ penalty approach to relax all constraints, to provide regularization, and to bound the Lagrange multipliers. The penalty problems are solved using a simplified version of Chen and Goldfarb’s strictly feasible interior-point method [6]. … Read more

Interior-Point Methods for Nonconvex Nonlinear Programming: Regularization and Warmstarts

In this paper, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the LOQO algorithm and provide extensive … Read more

An Exact Primal-Dual Penalty Method Approach to Warmstarting Interior-Point Methods for Linear Programming

One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal-dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set … Read more

Interior-Point Algorithms, Penalty Methods and Equilibrium Problems

In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPEC’s)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties, present an example … Read more

Interior-Point Methods for Nonconvex Nonlinear Programming: Complementarity Constraints

In this paper, we present the formulation and solution of optimization problems with complementarity constraints using an interior-point method for nonconvex nonlinear programming. We identify possible difficulties that could arise, such as unbounded faces of dual variables, linear dependence of constraint gradients and initialization issues. We suggest remedies. We include encouraging numerical results on the … Read more

A Comparative Study of Large-Scale Nonlinear Optimization Algorithms

In recent years, much work has been done on implementing a variety of algorithms in nonlinear programming software. In this paper, we analyze the performance of several state-of-the-art optimization codes on large-scale nonlinear optimization problems. Extensive numerical results are presented on different classes of problems, and features of each code that make it efficient or … Read more