Abstract.
This paper presents some examples of ill-behaved central paths in convex optimization. Some contain infinitely many fixed length central segments; others manifest oscillations with infinite variation. These central paths can be encountered even for infinitely differentiable data.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adler, I., Monteiro, R.D.C.: Limiting behavior of the affine scaling continuous trajectories for linear programming problems. Math. Program. 50, 29–51 (1991)
Auslender, A., Cominetti, R., Haddou, M.: Asymptotic analysis for penalty and barrier methods in convex and linear programming. Math. Oper. Res. 22, 43–62 (1997)
Bayer, D.A., Lagarias, J.C.: The nonlinear geometry of linear programming, Part I : Affine and projective scaling trajectories. Transactions Am. Math. Soc. 314, 499–526 (1989)
Byrd, R.H., Gilbert, J.C., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Math. Program. 89, 149–185 (2000)
Champion, T.: Asymptotic Convergence of Penalty Trajectories in Convex Programming with Multiple Solutions. Ph.D. thesis, Département de Mathématique, Université de Montpellier II, France, 2001
Chen, C., Mangasarian, O.L.: Smoothing methods for convex inequalities and linear complementary problems. Math. Program. 71, 1–112 (1995)
Chen, C., Mangasarian, O.L.: A class of smoothing functions for non-linear and mixed complementary problems. Comput. Optim. Appl. 5, 97–138 (1996)
Cominetti, R.: Nonlinear averages and convergence of penalty trajectories in convex programming. In: Michel Théra, R. T., (ed.), Ill-posed variational problems and regularization techniques, Springer Verlag, Berlin, vol. 477 of Lecture Notes in Economics and Mathematical System, 1999, pp. 65–78
Conn, A.R., Gould, N.I.M., Orban, D., Toint, P.L.: A primal-dual trust region algorithm for minimizing a non-convex function subject to general inequality and linear equality constraints. Tech. Rep. RAL-TR-1999-054, Computation Science and Engeneering Department, Atlas Centre, Rutherford Appleton Laboratory, Oxon, OX11 OQX, 1999
den Hertog, D.: Interior Point Approach to Linear, Quadratic and Convex Programming. Math. and its Applications 277, Kluwer Academic Publishers, Dordrecht, 1992
Dennis, J.E., Heinkenschloss, M., Vicente, L.N.: Trust-region interior-point SQP algorithms for a class of nonlinear programming problems. Tech. Rep. 94-45, Department of Comput. and Applied Math., Rice University, 1994
Fiacco, A.V., McCormick, G.P.: NonLinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley & Sons, New York, reprint: Volume 4 of SIAM Classics in Applied Math., SIAM Publications, Philadelphia, PA 19104–2688, USA, 1990, 1968
Fleming, W.H.: Functions of Several Variables. Addison-Wesley Publishing Company, United States, 1965
Forsgren, A., Gill, P.E.: Primal-dual interior methods for nonconvex nonlinear programming. SIAM J. Optim. 8, 1132–1152 (1998)
Gay, D.M., Overton, M.L., Wright, M.H.: A primal-dual interior method for nonconvex nonlinear programming. In: Y, Y., (ed.), Advances in Nonlinear Programming, Kluwer Academic Publishers, Dordretch, 1998, pp. 31–56
Gonzaga, C.C.: Path following methods for linear programming. SIAM Rev. 34, 167–227 (1992)
Hiriart-Urruty, J.-B., Lemarechal, C.: Convex Analysis and Minimization Algorithms I. Springer-Verlag, New York, 1993
Jansen, B.: Interior Point Techniques in Optimization. Applied Optimization 6, Kluwer Academic Publishers, Dordrecht, 1997
Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems. In: Lecture Notes in Computer Science, Springer Verlag, Berlin, Vol. 538, 1991
Kojima, M., Mizuno, S., Noma, T.: Limiting behavior of trajectories by a continuation method for monotone complementarity problems. Math. Oper. Res. 15, 662–675 (1990)
McLinden, L.: An analogue of Moreau’s proximation theorem, with application to the nonlinear complementarity problem. Pacific J. Math. 88, 101–161 (1980)
Megiddo, N.: Pathways to the optimal set in linear programming. In: Megiddo, N. (ed.), Progress in Mathematical Programming: Interior Point and Related Methods, Springer Verlag, New York, 1989, pp. 131–158, identical version in: Proceedings of the 6th Mathematical Programming Symposium of Japan, Nagoya, Japan, 1986, pp. 1–35
Monteiro, R.D.C., Tsuchiya, T.: Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem. Math. Oper. Res. 21, 793–814 (1996)
Monteiro, R.D.C., Zhou, F.: On the existence and convergence of the centra path for convex programming and some duality results. Comput. Optim. Appl. 10, 51–77 (1998)
Nesterov, Y.E., Nemirovskii, A.S.: Interior-Point Polynomial Algorithms in Convex Programming. Vol. 13 of SIAM Studies in Applied Math. 13. SIAM, Philadelphia, 1994
Rockafellar, R.T., Wets, R.: Variational Analysis. Springer, 1998
Roos, C., Terlaky, T., Vial, J.P.: Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley & Sons, Chichester, 1997
Terlaky, T., ed.: Interior Point Methods of Mathematical Programming. Kluwer Academic Press, 1996
Vanderbei, R.J., Shanno, D.F.: An interior-point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13, 231–252 (1999)
Vavasis, S.A., Ye, Y.: A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Program. 74, 79–120 (1996)
Whitney, H.: Functions differentiable on the boundaries of regions. Ann. Math. 35, 482–485 (1934)
Witzgall, C., Boggs, P.T., Domich, P.D.: On the convergence behavior of trajectories for linear programming. In: Lagarias, J. C., Todd, M. J., (eds.), Mathematical Developments Arising from Linear Programming, American Mathematical Society, Providence, Rhode Island, USA, vol. 114 of Contemporary Math., 1990, pp. 161–188
Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM Publication, Philadelphia, 1997
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (2000): 90C25, 90C51
Research partially supported by CAPES, Brazil.
Research partially supported by CAPES and CNPq, Brazil.
Rights and permissions
About this article
Cite this article
Charles Gilbert, J., Gonzaga, C. & Karas, E. Examples of ill-behaved central paths in convex optimization. Math. Program. 103, 63–94 (2005). https://doi.org/10.1007/s10107-003-0460-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0460-0