×

zbMATH — the first resource for mathematics

Partial linearization methods in nonlinear programming. (English) Zbl 0796.90058
Summary: We characterize a class of feasible direction methods in nonlinear programming through the concept of partial linearization of the objective function. Based on a feasible point, the objective is replaced by an arbitrary convex and continuously differentiable function, and the error is taken into account by a first-order approximation of it. A new feasible point is defined through a line search with respect to the original objective, toward the solution of the approximate problem. Global convergence results are given for exact and approximate line searches, and possible interpretations are made. We present some instances of the general algorithm and discuss extensions to nondifferentiable programming.

MSC:
90C30 Nonlinear programming
49J52 Nonsmooth analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bazaraa, M. S., andShetty, C. M.,Nonlinear Programming: Theory and Algorithms, John Wiley and Sons, New York, New York, 1979. · Zbl 0476.90035
[2] Larsson, T., andMigdalas, A.,An Algorithm for Nonlinear Programs over Cartesian Product Sets, Optimization, Vol. 21, pp. 535-542, 1990. · Zbl 0726.90069
[3] Larsson, T., andPatriksson, M.,A Class of Gap Functions for Variational Inequalities, Report LiTH-MAT-R-90-18, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1990. (To appear in Mathematical Programming.)
[4] Martos, B.,Nonlinear Programming Theory and Methods, North-Holland, Amsterdam, Holland, 1975. · Zbl 0357.90027
[5] Rockafellar, R. T.,The Theory of Subgradients and Its Applications to Problems of Optimization: Convex and Nonconvex Functions, Heldermann-Verlag, Berlin, Germany, 1981. · Zbl 0462.90052
[6] Armijo, L.,Minimization of Functions Having Lipschitz Continuous First Partial Derivatives, Pacific Journal of Mathematics, Vol. 16, pp. 1-3, 1964. · Zbl 0202.46105
[7] Pshenichny, B. N., andDanilin, Yu. M.,Numerical Methods in Extremal Problems, Mir, Moscow, Russia, 1978.
[8] Frank, M., andWolfe, P.,An Algorithm for Quadratic Programming, Naval Research Logistics Quarterly, Vol. 3, pp. 95-110, 1956.
[9] Migdalas, A.,A Regularization of the Frank-Wolfe Algorithm, Report LiTH-MAT-R-90-10, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1990.
[10] Larsson, T., Migdalas, A., andPatriksson, M.,A Partial Linearization Method for the Traffic Assignment Problem, Report LiTH-MAT-R-89-06 Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1989. (To appear in optimization) · Zbl 0818.90046
[11] Patriksson, M.,A Unified Description of Iterative Algorithms for Traffic Equilibria, European Journal of Operational Research (to appear). · Zbl 0802.90074
[12] Polyak, B. T.,Introduction to Optimization, Optimization Software, New York, New York, 1987. · Zbl 0708.90083
[13] Rockafellar, R. T.,Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming, Mathematics of Operations Research, Vol. 1, pp. 97-116, 1976. · Zbl 0402.90076
[14] Mine, H., andFukushima, M.,A Minimization Method for the Sum of a Convex Function and a Continuously Differentiable Function, Journal of Optimization Theory and Applications, Vol. 33, pp. 9-23, 1981. · Zbl 0422.90070
[15] Clarke, F. H.,Generalized Gradients and Applications, Transactions of the American Mathematical Society, Vol. 205, pp. 247-262, 1975. · Zbl 0307.26012
[16] Fukushima, M., andMine, H.,A Generalized Proximal Point Algorithm for Certain Nonconvex Minimization Problems, International Journal of Systems Sciences, Vol. 12, pp. 989-1000, 1981. · Zbl 0467.65028
[17] Fukushima, M.,A Successive Quadratic Programming Method for a Class of Constrained Nonsmooth Optimization Problems, Mathematical Programming, Vol. 49, pp. 231-251, 1990. · Zbl 0735.90062
[18] Kiwiel, K. C.,A Method for Minimizing the Sum of a Convex Function and a Continuously Differentiable Function, Journal of Optimization Theory and Applications, Vol. 48, pp. 437-449, 1986. · Zbl 0562.90073
[19] Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[20] Rudin, W.,Principles of Mathematical Analysis, 3rd Edition, McGraw-Hill, Singapore, Republic of Singapore, 1985. · Zbl 0613.26001
[21] Shor, N. Z.,Minimization Methods for Nondifferentiable Functions, Springer-Verlag, Berlin, Germany, 1985. · Zbl 0561.90058
[22] Canon, M. D., andCullum, C. D.,A Tight Upper Bound on the Rate of Convergence of the Frank-Wolfe Algorithm, SIAM Journal on Control, Vol. 6, pp. 509-516, 1968. · Zbl 0186.24002
[23] Florian, M., andNguyen, S.,A Method for Computing Network Equilibrium with Elastic Demands, Transportation Science, Vol. 8, pp. 321-332, 1974.
[24] Holmberg, K., andJörnsten, K. O.,Cross Decomposition Applied to the Stochastic Transportation Problem, European Journal of Operational Research, Vol. 17, pp. 361-368, 1984. · Zbl 0547.90078
[25] Fukushima, M.,Equivalent Differentiable Optimization Problems and Descent Methods for Asymmetric Variational Inequality Problems, Mathematical Programming, Vol. 53, pp. 99-110, 1992. · Zbl 0756.90081
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.