List of Monteiro's PublicationsList of Monteiro's Publications
These reports can be downloaded in either compressed dvi or postscript form by clicking on the appropriate tag.
We describe a primal-dual interior point algorithm for linear programming problems which requires a total of $ O ( sqrt n L ) $ number of iterations, where $ size 11 L $ is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.
We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of $ O ( sqrt n L ) $ number of iterations, where $ L $ is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of $ O ( n^3 L ) $.
We describe a primal-dual interior point algorithm for a class of convex separable programming problems subject to linear constraints. Each iteration updates a penalty parameter and finds a Newton step associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem for that parameter. It is shown that the duality gap is reduced at each iteration by a factor of $ ( 1 - \delta / \sqrt{n} ) $, where $ \delta $ is positive and depends on some parameters associated with the objective function.
We describe an algorithm for linear and convex quadratic programming problems that uses power series approximation of the weighted barrier path that passes through the current iterate in order to find the next iterate. If $r \geq 1$ is the order of approximation used, we show that our algorithm has time complexity O$\left( n^{\frac{1}{2}(1+\frac{1}{r})}L^{(1+\frac{1}{r})} \right)$ iterations and O($n^3 + n^2 r$) arithmetic operations per iteration, where $n$ is the dimension of the problem and $L$ is the size of the input data. When $r=1$, we show that the algorithm can be interpreted as an affine scaling algorithm in the primal-dual setup.
We consider the continuous trajectories of the vector field induced by the primal affine scaling algorithm as applied to linear programming problems in standard form. By characterizing these trajectories as solutions of certain parametrized logarithmic barrier families of problems, we show that these trajectories tend to an optimal solution which in general depends on the starting point. By considering the trajectories that arise from the Lagrangian multipliers of the above mentioned logarithmic barrier families of problems, we show that the trajectories of the dual estimates associated with the affine scaling trajectories converge to the so called "centered" optimal solution of the dual problem. We also present results related to asymptotic direction of the affine scaling trajectories. We briefly discuss how to apply our results to linear programs formulated in formats different from the standard form. Finally, we extend the results to the primal-dual affine scaling algorithm.
We analyze the convergence and boundary behavior of the continuous trajectories of the vector field induced by the projective scaling algorithm as applied to (possibly degenerate) linear programming problems in Karmarkar's standard form. We show that a projective scaling trajectory tends to an optimal solution which in general depends on the starting point. When the optimal solution is unique, we show that all projective scaling trajectories approach the optimal solution through the same asymptotic direction. Our analysis is based on the affine scaling trajectories for the homogeneous standard form linear program that arises from the Karmarkar's standard form linear program by removing the unique nonhomogeneous constraint.
We present a new definition of optimality intervals for the parametric right hand side linear programming (parametric RHS LP) problem $ \phi ( \lambda ) = \min \{ c^T x | A x = b + \lambda \bar b , x >= 0 \} $. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function $ \phi ( \lambda ) $. As a consequence, the optimality intervals form a partition of the closed interval $ \{ \lambda ; \phi ( \lambda ) | < inf \}$. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of $ \phi ( \lambda ) $ is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.
For a possibly degenerate linear program $ \min_x \{c^T x ; A x = b , x >= 0 \} $ ($ A $ is an $ m \times n $ real matrix, $ b \in R^m$ and $ c \in R^n $), whose optimal value is $ 0 $, we study the limiting behavior of the trajectories of the family of vector fields $ \phi_q ( x ) \equiv - X P_AX [ X c - { c^T x } / q ] $, for all values of $ q >= n $, where $ X $ is the diagonal matrix associated with $ x $ and $ P_AX $ is the projection operator onto the null space of $ AX $. A polynomial algorithm based on the directions $ \phi_q ( x ) $ has been presented by Gonzaga [6] when $ q = n $ or $ q = n + \sqrt{n} $. We show that all trajectories of $ \phi_q ( x ) $ converge to the unique "center" of the optimal face of the given linear program. When this face consists of a unique vertex, it is shown that any trajectory of $ \phi_q ( x ) $ approaches this vertex along the same direction. When the optimal face consists of more than one point, we show that there is a threshold value $ tau > 0 $ such that: for $ q > tau $, "most" of the trajectories of $ \phi_q ( x ) $ converge to the "center" tangentially to the optimal face and that the direction of approach of a trajectory of $ \phi_q ( x ) $ depends on the initial condition; for $ q < tau $ ($ q = tau $), the trajectories of $ \phi_q ( x ) $ converge to the "center" along a unique direction (along several directions which depend on the initial condition) forming a positive angle with the optimal face.
In this paper, we study the global convergence of a large class of primal-dual interior point algorithms for solving the linearly constrained convex programming problem. The algorithms in this class decrease the value of a primal-dual potential function and hence belong to the class of so-called potential reduction algorithms. An inexact line search based on Armijo stepsize rule is used to compute the stepsize. The directions used by the algorithms are the same as the ones used in primal-dual path following and potential reduction algorithms and a very mild condition on the choice of the "centering parameter" is assumed. The algorithms always keep primal and dual feasibility and, in contrast to the polynomial potential reduction algorithms, they do not need to drive the value of the potential function towards $ - ^ inf $ in order to converge. One of the techniques used in the convergence analysis of these algorithms has its root in nonlinear unconstrained optimization theory.
In this paper, we study the global convergence of a class of interior point primal potential reduction algorithms for the linearly constrained convex programming problem. The directions used by our class of algorithms are sufficiently general so as to include as special case several directions that have been used in the literature in the context of LP problems. The stepsize is calculated by means of Armijo rule applied to the primal potential function. Our proof of convergence is based on the techniques introduced in Monteiro where a global convergence result for a class of primal-dual interior point algorithms is shown. The directions used by the algorithms described in Monteiro require the evaluation of the Hessian of the objective function at every iterate. In contrast, the directions of the algorithms described in this paper require no Hessian evaluation. The determination of the directions depend on a sequence of symmetric positive definite matrices which are required to satisfy a very mild condition. As a consequence of our result, it is possible to introduce techniques of Quasi-Newton updates if a second order algorithm is desired while having no need to compute the Hessian of the objective function.
In Adler and Monteiro \cite{AdMon1}, a parametric analysis approach is developed that is naturally related to the geometry of the linear program. This approach is based on the availability of primal and dual optimal solutions satisfying strong complementarity. In this paper, we develop an alternative geometric approach for parametric analysis which does not require the strong complementarity condition. This parametric analysis approach is used to develop range and marginal analysis techniques which are suitable for interior point methods. Two approaches are developed, namely the $LU$ factorization approach and the affine scaling approach. We also give an interpretation of the parametric simplex algorithm as being a special implementation of our general parametric analysis approach.
We consider an interior point algorithm for convex programming in which the steps are generated by using a primal-dual affine scaling technique. A ``local" variant of the algorithm is shown to have superlinear convergence with q-order up to (but not including) 2. The technique is embedded in a potential reduction algorithm and the resulting method is shown to be globally and superlinearly convergent. An important feature of the convergence analysis is its use of a novel strict interiority condition, which generalizes the usual conical neighborhood of the central path.
This paper presents a simplified and self-contained global convergence proof for the affine scaling algorithm applied to degenerate linear programming problems. Convergence of the sequence of dual estimates to the center of the optimal dual face is also proven. In addition, we give a sharp rate of convergence result for the sequence of objective function values. All these results are proved with respect to the long step version of the affine scaling algorithm in which we move a fraction $\lambda$, where $\lambda \in (0,2/3]$, of the step to the boundary of the feasible region.
In this paper we show that a variant of the long-step affine scaling algorithm (with variable stepsizes) is two-step superlinearly convergent when applied to general linear programming (LP) problems. Superlinear convergence of the sequence of dual estimates is also established. For homogeneous LP problems having the origin as the unique optimal solution, we also show that $2/3$ is a sharp upper bound on the (fixed) stepsize that provably guarantees that the sequence of primal iterates converge to the optimal solution along a unique direction of approach. Since the point to which the sequence of dual estimates converge depend on the direction of approach of the sequence of primal iterates, this result gives a plausible (but not accurate) theoretical explanation for the reason $2/3$ is a sharp upper bound on the (fixed) stepsize that guarantees the convergence of the dual estimates.
Given a certain monotone horizontal linear complementarity problem (LCP), we can naturally construct a family of systems of nonlinear equations parametrized by a parameter $t \in (0,1]$ with the property that, as $t$ tends to $0$, the corresponding system ``converges'' to the horizontal LCP. The limiting behavior of the trajectory of solutions of these systems has been analyzed by Kojima et al.\ \cite{KoMiNo90-1} in the context of the regular monotone LCP. Under reasonable conditions, they have shown that each system of the family has a unique solution and that, as $t$ tends to $0$, these solutions converge to a specific solution of the LCP. Their result is easily generalized to the context of the monotone horizontal LCP using a recent result of Sznajder and Gowda \cite{SznGow} which states that any monotone horizontal LCP can be reduced to a regular monotone LCP by relabeling some pairs of complementary variables $(x_i,y_i)$ as $(y_i,x_i)$. The main purpose of this paper is to study the asymptotic behavior of the derivative of the trajectory of solutions and therefore obtain information on the way the trajectory approaches the solution set of the horizontal LCP. We show that the behavior depends on two cases: whether the problem has a solution satisfying strict complementarity or not. In both cases, the trajectory of solutions converges to the solution set along a unique and well-characterized direction. If the horizontal LCP has a solution satisfying strict complementarity then the direction forms a definite angle with any face of the feasible region which contains the limit point; otherwise, the direction is tangent to some face of the feasible region. We also show an interesting connection between the affine scaling continuous trajectories for a certain linear program and the trajectories of solutions associated with the horizontal LCP which expresses the optimality conditions for the linear program.
In this paper, we describe and establish the convergence of a new iterative method for solving the (nonmonotone) nonlinear complementarity problem (NCP). The method utilizes ideas from two distinct approaches for solving this problem and combine them into one unified framework. One of these is the infeasible-interior-point approach which computes an approximate solution to the NCP by staying in the interior of the nonnegative orthant; the other approach is typified by the NE/SQP method which is based on a generalized Gauss-Newton scheme applied to a constrained nonsmooth-equations formulation of the complementarity problem. The new method, which we call a {\sl positive algorithm} for the NCP, generates a sequence of positive vectors by solving a sequence of linear equations (as in a typical interior-point method) whose solutions (if nonzero) provide descent directions for a certain merit function that is derived from the NE/SQP iteration function modified for use in an interior-point context.
Most asymptotic convergence analysis of interior-point algorithms for monotone linear complementarity problems assumes that the problem is nondegenerate, that is, the solution set contains a strictly complementary solution. We investigate the behavior of these algorithms when this assumption is removed.
We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.
We present an infeasible-interior-point algorithm for monotone linear complementarity problems in which the search directions are affine scaling directions and the step lengths are obtained from simple formulae that ensure both global and superlinear convergence. By choosing the value of a parameter in appropriate ways, polynomial complexity and convergence with Q-order up to (but not including) two can be achieved. The only assumption made to obtain the superlinear convergence is the existence of a solution satisfying strict complementarity.
Using a unified theory of local homeomorphic maps, we establish some basic properties of a fundamental mapping associated with the family of path-following interior-point methods for solving a mixed nonlinear complementarity problem.
We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs, linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm for solving several classes of convex programs.
This paper gives several equivalent conditions which guarantee the existence of the weighted central paths for a given convex programming problem satisfying some mild conditions. When the objective and constraint functions of the problem are analytic, we also characterize the limiting behavior of these paths as they approach the set of optimal solutions. A duality relationship between a certain pair of logarithmic barrier problems is also discussed.
This paper deals with nondegeneracy of polyhedra and linear programming (LP) problems. We allow for the possibility that the polyhedra and the feasible polyhedra of the LP problems under consideration be non-pointed. (A polyhedron is pointed if it has a vertex.) \ With respect to a given polyhedron, we consider two notions of nondegeneracy and then provide several equivalent characterizations for each of them. With respect to LP problems, we study the notion of {\em constant cost} nondegeneracy first introduced by Tsuchiya \cite{Tsu92-1} under a different name, namely dual nondegeneracy. (We do not follow this terminology since the term dual nondegeneracy is already used to refer to a related but different type of nondegeneracy.) We show two main results about constant cost nondegeneracy of an LP problem. The first one shows that constant cost nondegeneracy of an LP problem is equivalent to the condition that the union of all minimal faces of the feasible polyhedron be equal to the set of feasible points satisfying a certain generalized strict complementarity condition. When the feasible polyhedron is nondegenerate, the second result shows that constant cost nondegeneracy of an LP is equivalent to the condition that the set of feasible points satisfying the generalized complementarity condition be equal to the set of feasible points satisfying the same complementarity condition strictly. For the purpose of giving a preview of the paper, the above results specialized to the context of polyhedra and LP problems in standard form are described in the introduction.
In this paper we give a global convergence proof of the second order affine scaling algorithm for convex quadratic programming problems, where the next iterate is the point which minimizes the objective function over the intersection of the feasible region with the ellipsoid centered at the current point and whose radius is a fixed fraction $\beta \in (0,1]$ of the radius of the largest ``scaled'' ellipsoid inscribed in the nonnegative orthant. The analysis is based on the local Karmarkar potential function introduced by Tsuchiya. For any $\beta \in (0, 2/3]$ and without assuming any nondegeneracy assumption on the problem, it is shown that the sequences of primal iterates and dual estimates converge to optimal solutions of the quadratic program and its dual, respectively.
This note derives bounds on the length of the primal-dual affine scaling directions associated with a linearly constrained convex program satisfying the following conditions: 1) the problem has a solution satisfying strict complementarity, 2) the Hessian of the objective function satisfies a certain invariance property. The derived bounds can be used to establish the superlinear convergence of the algorithm presented in Wright and Ralph \cite{WrRa92} for solving the optimality conditions associated with a linearly constrained convex program satisfying the above conditions.
We study a trust region affine scaling algorithm for solving the linearly constrained convex or concave programming problem. Under primal nondegeneracy assumption, we prove that every accumulation point of the sequence generated by the algorithm satisfies the first order necessary condition for optimality of the problem. For a special class of convex or concave functions satisfying a certain invariance condition on their Hessians, it is shown that the sequences of iterates and objective function values generated by the algorithm converge $R$-linearly and $Q$-linearly, respectively. Moreover, under primal nondegeneracy and for this class of objective functions, it is shown that the limit point of the sequence of iterates satisfies the first and second order necessary conditions for optimality of the problem.
This paper deals with a class of primal-dual interior-point algorithms for semidefinite programming (SDP) which was recently introduced by Kojima, Shindoh and Hara \cite{KoShHa94-1}. These authors proposed a family of primal-dual search directions that generalizes the one used in algorithms for linear programming based on the scaling matrix $X^{1/2}S^{-1/2}$. They study three primal-dual algorithms based on this family of search directions: a short-step path following method, a feasible potential-reduction method and an infeasible potential-reduction method. However, they were not able to provide an algorithm which generalizes the long-step path-following algorithm introduced by Kojima, Mizuno and Yoshise \cite{KojMY89-1}. In this paper, we characterize two search directions within their family as being (unique) solutions of systems of linear equations in symmetric variables. Based on this characterization, we present: 1) a simplified polynomial convergence proof for their short-step path following algorithm and, 2) for the first time, a polynomially convergent long-step path following algorithm for SDP which requires an extra $\sqrt{n}$ factor in its iteration-complexity order as compared to its linear programming counterpart, where $n$ is the number of rows (or columns) of the matrices involved.
Extending our previous work \cite{monpang-2}, this paper studies properties of two fundamental mappings associated with the family of interior-point methods for solving monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. The first of these maps lead to a family of new continuous trajectories which include the central trajectory as a special case. The trajectories of this family completely ``fill up'' the set of interior feasible points of the problem in the same way as the weighted central paths ``fill up'' the interior feasible region of a linear program. Unlike the approach based on the theory of maximal monotone maps taken by Shida, Shindoh \cite{shida-shindoh} and Shida, Shindoh, and Kojima \cite{shida-shindoh-kojima-1}, our approach is based on the theory of local homeomorphic maps in nonlinear analysis.
We present a unified analysis for a class of long-step primal-dual path-following algorithms for semidefinite programming whose search directions are obtained through linearization of the symmetrized equation of the central path $H_P(XS) \equiv [PXSP^{-1} + (PXSP^{-1})^T]/2 = \mu I$, introduced by Zhang. At an iterate $(X,S)$, our permissible class of scaling matrices $P$ consists of all nonsingular matrices $P$ such that $PXSP^{-1}$ is symmetric. This class of matrices includes the three well-known choices, namely: $P=S^{1/2}$ and $P=X^{-1/2}$ proposed by Monteiro, and the matrix $P$ corresponding to the Nesterov-Todd direction. We show that within the class of algorithms studied in this paper, the method based on the Nesterov-Todd direction has the lowest possible iteration-complexity bound that can provably be derived from our analysis. More specifically, its iteration-complexity bound is of the same order as that of the corresponding long-step primal-dual path-following algorithm for linear programming introduced by Kojima, Mizuno and Yoshise.
This note establishes a new sufficient condition for the existence and uniqueness of the Alizadeh-Haeberly-Overton direction for semidefinite programming.
This paper establishes the polynomial convergence of the class of primal-dual feasible interior-point algorithms for semidefinite programming (SDP) based on Monteiro and Zhang family of search directions. In contrast to Monteiro and Zhang's work, no condition is imposed on the scaling matrix that determines the search direction. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al.\ and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al.\, carry over to the context of SDP. Since Monteiro and Zhang family of directions includes the Alizadeh, Haeberly and Overton direction, we establish for the first time the polynomial convergence of algorithms based on this search direction.
Kojima, Shindoh and Hara proposed a family of search directions for semidefinite linear complementarity problem (SDLCP) and established polynomial convergence of a feasible short-step path-following algorithm based on a particular direction of their family. The question of whether polynomiality could be established for any direction of their family thus remained an open problem. This paper answers this question in the affirmative by establishing the polynomiality of primal-dual interior-point algorithms for SDLCP based on any direction of the Kojima, Shindoh and Hara family of search directions. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al.\ and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SDLCP.
This paper establishes the polynomial convergence of a new class of (feasible) primal-dual interior-point path following algorithms for semidefinite programming (SDP) whose search directions are obtained by applying Newton method to the symmetric central path equation $$(P^T X P)^{1/2}(P^{-1} S P^{-T}) ( P^T X P)^{1/2} - \mu I =0,$$ where $P$ is a nonsingular matrix. Specifically, we show that the short-step path following algorithm based on the Frobenius norm neighborhood and the semilong-step path following algorithm based on the operator 2-norm neighborhood have $O(\sqrt{n}L)$ and $O(nL)$ iteration-complexity bounds, respectively. When $P=I$, this yields the first polynomially convergent semilong-step algorithm based on a pure Newton direction. Restricting the scaling matrix $P$ at each iteration to a certain subset of nonsingular matrices, we are able to establish an $O(n^{3/2}L)$ iteration-complexity for the long-step path following method. The resulting subclass of search directions contains both the Nesterov-Todd direction and the Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro direction.
Extending our previous work \cite{TaMoPa96-1}, this paper presents a general potential reduction Newton method for solving a constrained system of nonlinear equations. A main convergence result for the method is established. Specializations of the method to a convex semidefinite program and a monotone complementarity problem in symmetric matrices are discussed. Strong convergence results are established in these specializations.
Monteiro and Tsuchiya \cite{MoTs96-2} have proposed two primal-dual Newton directions for semidefinite programming, referred to as the MT directions, and established polynomial convergence of path following methods based on them. This paper reports some computational results on the performance of interior-point predictor-corrector methods based on the MT directions and a variant of these directions, called the S-Ch-MT direction. We discuss how to compute these directions efficiently and derive their corresponding computational complexities. A main feature of our analysis is that computational formulae for these directions are derived from a unified point of view which entirely avoids the use of Kronecker product. Using this unified approach, we also show that the Alizadeh-Haeberly-Overton (AHO) direction can be computed substantially faster than previously reported in the literature. Our computational results are quite promising. We have observed that the method based on one of the MT directions is as robust as the one based on the AHO direction and that the method based on the S-Ch-MT direction is faster (in terms of flops required to reduce the duality gap below $10^{-6}$) than methods based on the MT directions, the Nesterov-Todd direction, the AHO direction and the HRVW/KSH/M direction.
The use of generalized distances (e.g.\ Bregman distances), instead of the Euclidean one, in the proximal point method for convex optimization, allows for elimination of the inequality constraints from the subproblems. In this paper we consider the proximal point method with Bregman distances applied to linearly constrained convex optimization problems, and study the behavior of the dual sequence obtained from the optimal multipliers of the linear constraints of each subproblem. Under rather general assumptions, which cover most Bregman distances of interest, we obtain an ergodic convergence result, namely that a sequence of weighted averages of the dual sequence converges to the centroid of the dual optimal set. As an intermediate result, we prove under the same assumptions that the dual central path generated by a large class of barriers, including the generalized Bregman distances, converges to the same point.
Extending the previous work of Monteiro and Pang (1996b), this paper studies properties of fundamental maps that can be used to describe the central path of the monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. Instead of focusing our attention on a specific map as was done in the approach of Monteiro and Pang (1996b), this paper considers a general form of a fundamental map and introduces conditions on the map that allow us to extend the main results of Monteiro and Pang (1996b) to this general map. Each fundamental map leads to a family of ``weighted'' continuous trajectories which include the central trajectory as a special case. Hence, for complementarity problems over the cone of symmetric positive semidefinite matrices, the notion of weighted central path depends on the fundamental map used to represent the central path.
Take me back...