Feasible direction interior-point technique for nonlinear optimization. (English) Zbl 0911.90303
Summary: We propose a feasible direction approach for the minimization, by interior-point algorithms of a smooth function under smooth equality and inequality constraints. It consists of the iterative solution in the primal and dual variables of the Karush-Kuhn-Tucker first-order optimality conditions. At each iteration, a descent direction is defined by solving a linear system. In a second stage, the linear system is perturbed so as to deflect the descent direction and obtain a feasible descent direction. A line search is then performed to get a new interior point and ensure global convergence. Based on this approach, first-order, Newton, and quasi-Newton algorithms can be obtained. To introduce the method, we consider first the inequality constrained problem and present a globally convergent basic algorithm. Particular flrst-order and quasi-Newton versions of this algorithm are also stated. Then, equality constraints are included. This method, which is simple to code, does not require the solution of quadratic programs and it is neither a penalty method nor a barrier method. Several practical applications and numerical results show that our method is strong and efficient.
Keywords:
nonlinear constrained optimization; feasible direction approach; interior-point algorithms; smooth function; quasi-Newton algorithmsReferences:
| [1] | Herskovits, J., A Two-Stage Feasible Directions Algorithm for Nonlinear Constrained Optimization, Research Report 103, Inria, Le Chesnay, France, 1982. · Zbl 0623.90070 |
| [2] | Herskovits, J., Two-Stage Feasible Directions Algorithm for Nonlinear Constrained Optimization, Mathematical Programming, Vol. 36, pp. 19–38, 1986. · Zbl 0623.90070 · doi:10.1007/BF02591987 |
| [3] | Herskovits, J., A Two-Stage Feasible Directions Algorithm Including Variable Metric Techniques for Nonlinear Optimization, Research Report 118, Inria, Le Chesnay, France, 1982. |
| [4] | Panier, E. R., Tits, A. L., and Herskovits, J., A QP-Free, Globally Convergent, Locally Superlinearly Convergent Algorithm for Inequality Constrained Optimization, SIAM Journal of Control and Optimization, Vol. 26, pp. 788–810, 1988. · Zbl 0651.90072 · doi:10.1137/0326046 |
| [5] | Mayne, D. Q., and Polak, E., Feasible Directions Algorithms for Optimization Problems with Equality and Inequality Constraints, Mathematical Programming, Vol. 11, pp. 67–80, 1976. · Zbl 0351.90067 · doi:10.1007/BF01580371 |
| [6] | Panier, E. R., and Tits, A. L., A Superlinearly Convergent Algorithm for Constrained Optimization Problems, SIAM Journal on Control and Optimization, Vol. 25, pp. 934–950, 1987. · Zbl 0634.90054 · doi:10.1137/0325051 |
| [7] | Maratos, N., Exact Penalty Function Algorithms for Finite-Dimensional Optimization Problems, PhD Thesis, Imperial College of Science and Technology, London, England, 1978. |
| [8] | Powell, M. J. D., Variable Metric Methods for Constrained Optimization, Mathematical Programming: The State of the Art, Edited by A. Bachem, M. Grotschet, and B. Korte, Springer Verlag, Berlin, Germany, pp. 288–311, 1983. |
| [9] | Tits, L. A., and Zhou, J. L., A Simple, Quadratically Convergent Interior-Point Algorithm for Linear Programming and Convex Quadratic Programming, Large-Scale Optimization: State of the Art, Edited by W. W. Hager, D. W. Hearn, and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Holland, pp. 411–427, 1993. · Zbl 0811.90069 |
| [10] | Zouain, N. A., Herskovits, J., Borges, L. A., and Feijoo, R., An Iterative Algorithm for Limit Analysis with Nonlinear Yield Functions, International Journal on Solids and Structures, Vol. 30, pp. 1397–1417, 1993. · Zbl 0773.73032 · doi:10.1016/0020-7683(93)90220-2 |
| [11] | Auatt, S. S., Borges, L. A., and Herskovits, J., An Interior-Point Optimization Algorithm for Contact Problems in Linear Elasticity, Numerical Methods in Engineering ’96, Edited by J. A. Désidéri, P. Le Tallec, E. Oñate, J. Périaux, and E. Stein, John Wiley and Sons, New York, New York, pp. 855–861, 1996. |
| [12] | Leontiev, A., Herskovits, J., and Eboli, C., Optimization Theory Application to Slitted Plate Bending Problem, International Journal of Solids and Structures, Vol. 35, pp. 2679–2694, 1998. · Zbl 0918.73047 · doi:10.1016/S0020-7683(97)00173-X |
| [13] | Vautier, I., Salaun, M., and Herskovits, J., Application of an Interior-Point Algorithm to the Modeling of Unilateral Contact between Spot-Welded Shells, Proceedings of Structural Optimization ’93, Rio de Janeiro, Brazil, 1993; Edited by J. Herskovits, Vol. 2, pp. 293–300, 1993. |
| [14] | Dew, M. C., A Feasible Directions Method for Constrained Optimization Based on the Variable Metric Principle, Technical Report 155, Numerical Optimization Centre, Hatfield Polytechnic, Hatfield, Hertfordshire, England, 1985. |
| [15] | Herskovits, J., and Coelho, C. A. B., An Interior-Point Algorithm for Structural Optimization Problems, Computer-Aided Optimum Design of Structures: Recent Advances, Edited by C. A. Brevia and S. Hernandez, Computational Mechanics Publications, Springer Verlag, Berlin, Germany, pp. 231–239, 1989. |
| [16] | Santos, G., Feasible Directions Interior-Point Algorithms for Engineering Optimization, DSc Thesis, Mechanical Engineering Program, COPPE/Federal University of Rio de Janeiro, Rio de Janeiro, Brazil, 1996 (in Portuguese). |
| [17] | Baron, F. J., Duffa, G., Carrere, F., and Le Tallec, P., Optimisation de Forme en Aerodynamique, CHOCS, Revue Scientifique et Technique de la Direction des Applications Militaires due CEA, Paris, France, No. 12, pp. 47–56, 1994 (in French). |
| [18] | Bijan, M., and Pironneau, O., New Tools for Optimum Shape Design, CFD Review, Special Issue, 1995. · Zbl 0875.76494 |
| [19] | Baron, F. J., Constrained Shape Optimization of Coupled Problems with Electromagnetic Waves and Fluid Mechanics, PhD Thesis, University of Malaga, Malaga, Spain, 1994 (in Spanish). |
| [20] | Herskovits, J., Lapporte, E., Le Tallec, P., and Santos, G., A Quasi-Newton Interior-Point Algorithm Applied to Constrained Optimum Design in Computational Fluid Dynamics, European Journal of Finite Elements, Vol. 5, pp. 595–617, 1996. · Zbl 0924.76071 |
| [21] | Monteiro, R. D. C., Adler, I., and Resende, M. G. C., A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension, Mathematics of Operations Research, Vol. 15, pp. 191–214, 1990. · Zbl 0714.90060 · doi:10.1287/moor.15.2.191 |
| [22] | Megiddo, N., Pathways to the Optimal Set in Linear Programming, Progress in Mathematical Programming: Interior-Point and Related Methods, Edited by N. Megiddo, Springer Verlag, New York, New York, pp. 131–158, 1989. |
| [23] | Kojima, M., Mizuno, S., and Yoshise, A., A Primal-Dual Interior-Point Method for Linear Programming, Progress in Mathematical Programming: Interior-Point and Related Methods, Edited by N. Megiddo, Springer Verlag, New York, New York, pp. 29–47, 1989. · Zbl 0708.90049 |
| [24] | McCormick, G. P., The Superlinear Convergence of a Nonlinear Primal-Dual Algorithm, Technical Report T-550/91, School of Engineering and Applied Science, George Washington University, Washington, DC, 1991. |
| [25] | Yamashita, H., A Globally Convergent Primal-Dual Interior-Point Method for Constrained Optimization, Technical Report, Mathematical Systems Institute, Shinjuku, Shinjuku-ku, Tokyo, Japan, 1992. |
| [26] | El-Bakry, A. S., Tapia, R. A., Tsuchiya, T., and Zhang, Y., On the Formulation and Theory of the Newton Interior-Point Method for Nonlinear Programming, Journal of Optimization Theory and Applications, Vol. 89, pp. 507–542, 1996. · Zbl 0851.90115 · doi:10.1007/BF02275347 |
| [27] | Wang, T., Monteiro, R. D. C., and Pang, J. S., An Interior-Point Potential Reduction Method for Constrained Equations, Mathematical Programming, Vol. 74, pp. 159–196, 1996. · Zbl 0855.90128 · doi:10.1007/BF02592210 |
| [28] | Luenberger, D. G., Linear and Nonlinear Programming, 2nd Edition, Addison-Wesley, Reading, Massachusetts, 1984. · Zbl 0571.90051 |
| [29] | Dennis, J. E., and Schnabel, R., Numerical Methods for Constrained Optimization and Nonlinear Equations, Prentice Hall, Englewood Cliffs, New Jersey, 1983. · Zbl 0579.65058 |
| [30] | Dikin, I. I., About the Convergence of an Iterative Procedure, Soviet Mathematics Doklady, Vol. 8, pp. 674–675, 1967 (in Russian). · Zbl 0189.19504 |
| [31] | Vanderbei, R. J., and Lagarios, J. C., I. I. Dikin’s Convergence Result for the Affine Scaling Algorithm, Technical Report, AT&T Bell Laboratories, Murray Hill, New Jersey, 1988. |
| [32] | Powell, M. J. D., The Convergence of Variable Metric Methods for Nonlinearly Constrained Optimization Calculations, Nonlinear Programming 3, Edited by O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, Academic Press, London, England, pp. 27–64, 1978. |
| [33] | Herskovits, J., A View on Nonlinear Optimization, Advances in Structural Optimization, Edited by J. Herskovits, Kluwer Academic Publishers, Dordrecht, Holland, pp. 71–117, 1995. · Zbl 0856.73045 |
| [34] | Hiriart-Urruty, J. B., and LemarÉchal, C., Convex Analysis and Minimization Algorithms, Springer Verlag, Berlin, Germany, 1993. · Zbl 0795.49001 |
| [35] | Hock, W., and Schittkowski, K., Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Germany, Vol. 187, 1981. · Zbl 0452.90038 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
