A Polynomial-Time Affine-Scaling Method for Semidefinite and Hyperbolic Programming

We develop a natural variant of Dikin’s affine-scaling method, first for semidefinite programming and then for hyperbolic programming in general. We match the best complexity bounds known for interior-point methods. All previous polynomial-time affine-scaling algorithms have been for conic optimization problems in which the underlying cone is symmetric. Hyperbolicity cones, however, need not be symmetric. … Read more

Constraint Reduction with Exact Penalization for Model-Predictive Rotorcraft Control

Model Predictive Control (also known as Receding Horizon Control (RHC)) has been highly successful in process control applications. Its use for aerospace applications has been hindered by its high computational requirements. In the present paper, we propose using enhanced primal-dual interior-point optimization techniques in the convex-quadratic-program-based RHC control of a rotorcraft. Our enhancements include a … Read more

On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds

We introduce an inexact Gauss-Newton trust-region method for solving bound-constrained nonlinear least-squares problems where, at each iteration, a trust-region subproblem is approximately solved by the Conjugate Gradient method. Provided a suitable control on the accuracy to which we attempt to solve the subproblems, we prove that the method has global and asymptotic fast convergence properties. … Read more

On affine scaling inexact dogleg methods for bound-constrained nonlinear systems

A class of trust-region methods for large scale bound-constrained systems of nonlinear equations is presented. The methods in this class follow the so called affine-scaling approach and can efficiently handle large scale problems. At each iteration, a suitably scaled region around the current approximate solution is defined and, within such a region, the norm of … Read more

On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP

A new class of infeasible interior point methods for solving sufficient linear complementarity problems requiring one matrix factorization and $m$ backsolves at each iteration is proposed and analyzed. The algorithms from this class use a large $(\caln_\infty^-$) neighborhood of an infeasible central path associated with the complementarity problem and an initial positive, but not necessarily … Read more

Primal-dual affine scaling interior point methods for linear complementarity problems

A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both … Read more

A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more

Constraint Reduction for Linear Programs with Many Inequality Constraints

Consider solving a linear program in standard form, where the constraint matrix $A$ is $m \times n$, with $n \gg m \gg 1$. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is $O(m^2n)$. We propose to reduce … Read more

A primal affine-scaling algorithm for constrained convex programs

The affine-scaling algorithm was initially developed for linear programming problems. Its extension to problems with a nonlinear objective performs at each iteration a scaling followed by a line search along the steepest descent direction. In this paper we prove that any accumulation point generated by this algorithm when applied to a convex function is an … Read more