Publications

These reports can be downloaded in either compressed dvi, compressed postscript or pdf format by clicking on the appropriate tag.

1) linear.pdf. (OK)

R.D.C. Monteiro, I. Adler, "An O ( n^3 L ) primal-dual interior point algorithm for linear programming". Revised version: "Interior path following primal-dual algorithms. Part I: Linear programming," Mathematical Programming 44 (1989) 27-41.

2) quad.pdf. (OK)

R.D.C. Monteiro, I. Adler, "An O ( n^3 L ) interior point algorithm for convex quadratic programming". Revised version: "Interior path following primal-dual algorithms. Part II: Convex quadratic programming," Mathematical Programming 44 (1989) 43-66.

3) nonli.

R.D.C. Monteiro, I. Adler, "An extension of Karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence," Mathematics of Operations Research 15 (1990) 408-422.

4) pd.dvi, pd.ps.

R.D.C. Monteiro, I. Adler and M.G.C. Resende, "A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension," Mathematics of Operations Research 15 (1990) 191-214.

5) waffine.pdf.

I. Adler and R.D.C. Monteiro, "Limiting behavior of the affine scaling continuous trajectories for linear programming problems," Mathematical Programming 50 (1991) 29-51. It also appeared in: J.C. Lagarias and M.J. Todd, eds. Contemporary Mathematics: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on "Mathematical Developments Arising from Linear Programming," (Providence, Rhode Island, 1990) pp. 189-211.

6) projective.ps.

R.D.C. Monteiro, "Convergence and boundary behavior of the projective scaling trajectories for linear programming," Mathematics of Operations Research 16 (1991) 842-858. It also appeared in: J.C. Lagarias and M.J. Todd, eds. Contemporary Mathematics: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on "Mathematical Developments Arising from Linear Programming," Providence, Rhode Island, 1990, pp 213-229.

7) sensi.

I. Adler and R.D.C. Monteiro, "A geometric view of parametric linear programming," Algorithmica 8 (1992) 161-176.

8) potential.

R.D.C. Monteiro, "On the continuous trajectories for a potential reduction algorithm for linear programming," Mathematics of Operations Research 17 (1992) 225-253.

9) convex.pdf. (OK)

R.D.C. Monteiro, "A globally convergent primal-dual interior point algorithm for convex programming," Mathematical Programming 64 (1994) 123-147.

10) primconv1.

R.D.C. Monteiro, "The global convergence of a class of primal potential reduction algorithms for convex programming," manuscript, SIE Dept., University of Arizona, Tucson, AZ 85721, 1991 (submitted to SIAM Journal on Optimization).

11) range.pdf. (OK)

R.D.C. Monteiro and S. Mehrotra, "A General Parametric Analysis Approach and Its Implication to Sensitivity Analysis in Interior Point Methods," Mathematical Programming 72 (1996) 65-82.

12) paper1.dvi, paper.ps.

R.D.C. Monteiro and S. Wright, "A globally and superlinearly convergent potential reduction interior point method for convex programming," SIE Working Paper 92-13, SIE Department, University of Arizona, Tucson, AZ 85721, 1992 (submitted to SIAM Journal on Optimization).

13) aff.dvi, aff.ps.

R.D.C. Monteiro, T. Tsuchiya and Y. Wang, "A simplified global convergence proof of the affine scaling algorithm," Annals of Operations Research 47 (1993) 443-482.

14) supaff.pdf. (OK)

T. Tsuchiya and R.D.C. Monteiro, "Superlinear convergence of the affine scaling algorithm," Mathematical Programming 75 (1996) 77-110.

15) lcp.dvi, lcp.ps.

R.D.C. Monteiro and T. Tsuchiya, "Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem," Mathematics of Operations Research 21 (1996) 793-814.

16) positive.dvi, positive.ps.

R.D.C. Monteiro, J.-S. Pang, and T. Wang, "A Positive Algorithm for the Nonlinear Complementarity Problem," SIAM Journal on Optimization 5 (1995) 129-148.

17) jne.dvi, jne.ps.

R.D.C. Monteiro and S. Wright: "Local convergence of interior-point algorithms for degenerate monotone LCPs," Computational Optimization and Applications 3 (1993) 131-155.

18) fas.pdf. (OK)

R.D.C. Monteiro and S. Wright: "Superlinear primal-dual affine scaling algorithms for LCP," Mathematical Programming 69 (1995) 311-333.

19) ias.dvi, ias.ps.

R.D.C. Monteiro and S. Wright: "A superlinear infeasible-interior-point affine scaling algorithm for LCP," SIAM Journal on Optimization 6 (1996) 1-18.

20) gncp.dvi, gncp.ps.

R.D.C. Monteiro and J.-S. Pang: "Properties of an interior-point mapping for mixed complementarity problems," Mathematics of Operations Research 21 (1996) 629-654.

21) nle.ps, nle.pdf. (OK)

T. Wang, R.D.C. Monteiro and J.--S. Pang, "An interior point potential reduction method for constrained equations," Mathematical Programming 74 (1996) 159-195.

22) cp.pdf.

R.D.C. Monteiro and F. Zhou, "On the Existence and Convergence of the Central Path for Convex Programming and Some Duality Results," Computational Optimization and Applications 10 (1998) 51-77.

23) pdeg.dvi, pdeg.ps.

Y. Wang and R.D.C. Monteiro, "Nondegeneracy of polyhedra and linear programs," Computational Optimization and Applications 7 (1997) 221-237.

24) quadaff.dvi, quadaff.ps, quadaff.pdf. (OK)

R.D.C. Monteiro and T. Tsuchiya: "Global convergence of the affine scaling algorithm for convex quadratic programming," SIAM Journal on Optimization 8 (1998) 26-58.

25) supconv.dvi, supconv.ps.

R.D.C. Monteiro and F. Zhou: " On Superlinear Convergence of Infeasible-Interior-Point Algorithms for Linearly Constrained Convex Programs," Computational Optimization and Applications 8 (1997) 245-262.

26) trust.pdf. (OK)

R.D.C. Monteiro and Y. Wang: " Trust Region Affine Scaling Algorithms for Linearly Constrained Convex and Concave Programs," Mathematical Programming 80 (1998) 283-313.

27) sdp.dvi, sdp.ps, sdp.pdf. (OK)

R.D.C. Monteiro: " Primal-Dual Path-Following Algorithms for Semidefinite Programming," SIAM Journal on Optimization 7 (1997) 663-678.

28) gsncp.dvi, gsncp.ps.

R.D.C. Monteiro and Jong-Shi Pang: " On Two Interior-Point Mappings for Nonlinear Semidefinite Complementarity Problems," Mathematics of Operations Research 23 (1998) 39-60.

29) zhang.pdf. (OK)

R.D.C. Monteiro and Y. Zhang: " A Unified Analysis for a Class of Path-Following Primal-Dual Interior-Point Algorithms for Semidefinite Programming," Mathematical Programming 81 (1998) 281-299.

30) note.pdf. (OK)

R.D.C. Monteiro and P. Zanjacomo: " A Note on the Existence of the Alizadeh-Haeberly-Overton Direction for Semidefinite Programming," Mathematical Programming 78 (1997) 393-396.

31) aho.dvi, aho.ps, aho.pdf. (OK)

R.D.C. Monteiro: "Polynomial Convergence of Primal-Dual Algorithms for Semidefinite Programming Based on Monteiro and Zhang Family of Directions," SIAM Journal on Optimization 8 (1998) 797-812.

32) ksh.ps, ksh.pdf. (OK)

R.D.C. Monteiro and T. Tsuchiya: " Polynomiality of Primal-Dual Algorithms for Semidefinite Linear Complementarity Problem Based on the Kojima-Shindoh-Hara Family of Directions," Mathematical Programming, 84 (1999) 39-53.

33) mtfam.ps, mtfam.pdf. (OK)

R.D.C. Monteiro and T. Tsuchiya: "Polynomial Convergence of a New Family of Primal-Dual Algorithms for Semidefinite Programming," SIAM Journal on Optimization 9 (1999) 551-577.

34) nlesdp.pdf. (OK)

R.D.C. Monteiro and J.-S. Pang: "A Potential Reduction Newton Method for Constrained Equations," SIAM Journal on Optimization 9 (1999) 729-754.

35) dir5.dvi, dir5.ps.

R.D.C. Monteiro and P. Zanjacomo: "Implementation of Primal-Dual Methods for Semidefinite Programming Based on Monteiro and Tsuchiya Newton Directions and their Variants," Optimization Methods and Software 11/12 (1999) 91-140.

36) iusem.dvi, iusem.ps.

A. Iusem and R.D.C. Monteiro: "On Dual Convergence of the Generalized Proximal Point Method with Bregman Distances," Mathematics of Operations Research 25 (2000) 606-624.

37) maps.dvi, maps.ps.

R.D.C. Monteiro and P. Zanjacomo: "General Interior-Point Maps and Existence of Weighted Paths for Nonlinear Semidefinite Complementarity Problems," Mathematics of Operations Research 25 (2000) 381-399.

38) ahoice.dvi, ahoice.ps, ahoice.pdf. (OK)

R.D.C. Monteiro and T. Tsuchiya: "Polynomial Convergence of Primal-Dual Algorithms for the Second-Order Cone Program Based on the MZ-Family of Directions," Mathematical Programming 88 (2000) 61-83.

39) maxcut.dvi, maxcut.ps, maxcut.pdf.

S. Burer and R.D.C. Monteiro: "A Projected Gradient Algorithm for Solving the Maxcut SDP Relaxation," Optimization Methods and Software 15 (2001) 175-200.

40) unify.dvi, unify.ps, unify.pdf.

S. Burer and R.D.C. Monteiro: "A General Framework for Establishing Polynomial Convergence of Long-Step Methods for Semidefinite Programming", Optimization Methods and Software 18 (2003) 1-38.

41) transf.dvi, transf.ps.

S. Burer, R.D.C. Monteiro and Y. Zhang: "Solving Semidefinite Programs via Nonlinear Programming. Part I: Transformations and Derivatives", working paper, School of ISyE, Georgia Tech, USA, September 1999 (submitted to Mathematical Programming).

42) nlint.dvi, nlint.ps.

S. Burer, R.D.C. Monteiro and Y. Zhang: "Solving Semidefinite Programs via Nonlinear Programming. Part II: Interior Point Methods for a Subclass of SDPs", working paper, School of ISyE, Georgia Tech, USA, October 1999 (submitted to Mathematical Programming).

42a) transf.dvi, transf.ps, transf.pdf. (OK) (This is a revised version of the papers 41 and 42 which have been merged to form the present paper.)

S. Burer, R.D.C. Monteiro and Y. Zhang: "Solving a class of semidefinite programs via nonlinear programming", Mathematical Programming, 93 (2002) 97-122.

43) gnlint.dvi, gnlint.ps, gnlint.pdf.

S. Burer, R.D.C. Monteiro and Y. Zhang: "Interior-Point Algorithms for Semidefinite Programming Based on A Nonlinear Programming Formulation", Computational Optimization and Applications 22 (2002) 49-79.

44) r2mcut.dvi, r2mcut.ps, r2mcut.pdf. (OK)

S. Burer, R.D.C. Monteiro and Y. Zhang: "Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs", SIAM Journal on Optimization 12 (2002) 503-521.

45) stabset.ps, stable.pdf. (OK)

S. Burer, R.D.C. Monteiro and Y. Zhang: "Maximum stable set formulations and heuristics based on continuous optimization", Mathematical Programming 94 (2002) 137-166.

46) lowrank.ps, lowrank.pdf. (OK)

S. Burer and R.D.C. Monteiro: "A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization", Mathematical Programming, Series B 95 (2003) 329-357.

47) layered.pdf. (OK)

R.D.C. Monteiro and T. Tsuchiya: "A variant of the Vavasis-Ye layered-step interior-point algorithm for linear programming", SIAM Journal on Optimization 13 (2003) 1054-1079.

48) dualimpl.ps, dualimpl.pdf. (OK)

S. Burer, R.D.C. Monteiro and Y. Zhang: "A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs", Mathematical Programming, Series B 95 (2003) 359-379.

49) layaff.ps, layaff.pdf. (OK)

R.D.C. Monteiro and T. Tsuchiya: "A new iteration-complexity bound for the MTY predictor-corrector algorithm", SIAM Journal on Optimization 15 (2004) 319-347.

50) sdptut.pdf. (OK)

R.D.C. Monteiro: "First- and second-order methods for semidefinite programming", Mathematical Programming, Series B 97 (2003) 209-244.

51) precond.ps, precond.pdf. (OK)

R.D.C. Monteiro, J.W. O'Neal and T. Tsuchiya: "Uniform boundedness of a preconditioned normal matrix used in interior point methods", SIAM Journal on Optimization 15 (2004) 96-100.

52) wpath.ps. wpath.pdf. (OK)

Z. Lu and R.D.C. Monteiro: "Error bounds and limiting behavior of weighted paths associated with the SDP map $X^{1/2}SX^{1/2}$", SIAM Journal on Optimization 15 (2004) 348-374.

53) centralpath.pdf. (OK)

J.X. da Cruz Neto, O. P. Ferreira and R.D.C. Monteiro: "Asymptotic behavior of the central path for a special class of degenerate SDP problems", Mathematical Programming 103 (2005) 487-514.

54) limaho.pdf. (OK)

Z. Lu and R.D.C. Monteiro: "Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming", Optimization Methods and Software 22 (2007) 849-870.

55) lr.pdf (OK)

S. Burer and R.D.C. Monteiro: "Local minima and convergence in low-rank semidefinite programming", Mathematical Programming 103 (2005) 427-444.

56) lprecond.dvi, lprecond.ps, lprecond.pdf.

R.D.C. Monteiro and J.W. O'Neal: "Convergence analysis of a long-step primal-dual infeasible interior-point LP algorithm based on iterative linear solvers", working paper, School of ISyE, Georgia Tech, USA, October 2003 (submitted to Mathematical Programming).

57) bregman.ps, bregman.pdf. (OK)

J.X. da Cruz Neto, O.P. Ferreira, A.N. Iusem and R.D.C. Monteiro: "Dual convergence of the proximal point method with Bregman distances for linear programming", Optimization Methods and Software 22 (2007) 339-360.

58) notekoj.ps, notekoj.pdf. (OK)

Z. Lu and R.D.C. Monteiro: "A note on the local convergence of a predictor-corrector interior-point algorithm for the semidefinite linear complementarity problem based on the {Alizadeh-Haeberly-Overton} search direction", SIAM Journal on Optimization 15 (2005) 1147--1154.

59) qpprecond.pdf. (OK)

Z. Lu, R.D.C. Monteiro and J.W. O'Neal: "An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming", SIAM Journal on Optimization 17 (2006) 287-310.

60) tr.pdf. (OK)

Z. Lu and R.D.C. Monteiro: "A modified nearly exact method for solving low-rank trust region subproblem", Mathematical Programming 109 (2007) 385-411.

61) cg.dvi, cg.ps, cg.pdf.

R.D.C. Monteiro, J.W. O'Neal and A. Nemirovski: "A new conjugate gradient algorithm incorporating adaptive ellipsoid preconditioning", working paper, School of ISyE, Georgia Tech, USA, October 2004 (submitted to SIAM Journal on Optimization).

62) pmirror.pdf. (OK)

Z. Lu, R.D.C. Monteiro and A. Nemirovski: "Large-scale semidefinite programming via saddle point mirror-prox algorithm", Mathematical Programming 109 (2007) 211-237.

63) gqpprecond.pdf. (OK)

Z. Lu, R.D.C. Monteiro and J. O'Neal: "An Iterative Solver-Based Long-Step Infeasible Primal-Dual Path-Following Algorithm for Convex QP Based on a Class of Preconditioners", Optimization Methods and Software 24 (2009) 123-143.

64) curv.pdf. (OK)

Z. R.D.C. Monteiro and T. Tsuchiya: "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", Mathematical Programming 115 (2008) 105-149.

65) multridge.pdf. (OK)

M. Yuan, A. Ekici, Z. Lu and R.D.C. Monteiro: "Dimension Reduction and Coefficient Estimation in the Multivariate Linear Regression", Journal of the Royal Statistical Society, Series B 69 (2007) 329-346.

66) pdfirst.pdf.

G. Lan, Z. Lu and R.D.C. Monteiro: "Primal-dual first-order methods with ${\cal O}(1/\epsilon)$ iteration-complexity for cone programming", working paper, School of ISyE, Georgia Tech, USA, December 2006 ( accepted in Mathematical Programming).

67) pctr.pdf. (OK)

G. Lan, R.D.C. Monteiro and T. Tsuchiya: "A polynomial predictor-corrector trust-region algorithm for linear programming", SIAM Journal on Optimization 19 (2009) 1918-1946.

68) dimreduct.dvi, dimreduct.ps, dimreduct.pdf.

Z. Lu, R.D.C. Monteiro and M. Yuan: "Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression", working paper, School of ISyE, Georgia Tech, USA, January 2008 (submitted to Mathematical Programming).

69) penalty.dvi, penalty.ps, penalty.pdf.

G. Lan and R.D.C. Monteiro: "Iteration-complexity of first-order penalty methods for convex programming", working paper, School of ISyE, Georgia Tech, USA, July 2008 (submitted to Mathematical Programming).

70) benar.dvi, benar.ps, benar.pdf.

R.D.C. Monteiro and B.F. Svaiter: "On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean", working paper, School of ISyE, Georgia Tech, USA, March 2009 (submitted to SIAM Journal on Optimization).

71) aug_lag.dvi, aug_lag.ps, aug_lag.pdf.

G. Lan and R.D.C. Monteiro: "Iteration-complexity of first-order augmented Lagrangian methods for convex programming", working paper, School of ISyE, Georgia Tech, USA, May 2009 (submitted to Mathematical Programming).