# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Approximations in proximal bundle methods and decomposition of convex programs. (English) Zbl 0824.90110
Summary: A proximal bundle method is presented for minimizing a nonsmooth convex function $f$. At each iteration, it requires only one approximate evaluation of $f$ and its $\epsilon$-subgradient, and it finds a search direction via quadratic programming. When applied to the Lagrangian decomposition of convex programs, it allows for inexact solutions of decomposed subproblems; yet, increasing their required accuracy automatically, it asymptotically finds both the primal and dual solutions. It is an implementable approximate version of the proximal point algorithm. Some encouraging numerical experience is reported.
##### MSC:
 90C25 Convex programming 49J52 Nonsmooth analysis (other weak concepts of optimality) 90C06 Large-scale problems (mathematical programming)
##### References:
 [1] Kiwiel, K. C.,Proximity Control in Bundle Methods for Convex Nondifferentiable Minimization, Mathematical Programming, Vol. 46, pp. 105–122, 1990. · Zbl 0697.90060 · doi:10.1007/BF01585731 [2] Kiwiel, K. C., andToczylowski, E.,Aggregate Subgradients in Lagrange Relaxations of Discrete Optimization Problems, Zeszyty Naukowe Politechniki Ślaskiej Automatyka, Vol. 84, pp. 119–129, 1986 (in Polish). [3] Golshtein, E. G., andTretyakov, N. V.,Modified Lagrange Functions: Theory and Optimization Methods, Nauka, Moscow, Russia, 1989 (in Russian). [4] Demyanov, V. F., andVasilev, L. V.,Nondifferentiable Optimization, Nauka, Moscow, Russia, 1981 (in Russian); English Translation, Optimization Software, New York, New York, 1985. [5] Shor, N. Z.,Minimization Methods for Nondifferentiable Functions, Naukova Dumka, Kiev, Ukraine, 1979 (in Russian); English Translation, Springer Verlag, Berlin, Germany, 1985. [6] Gabasov, R., Kirillova, F. M., Kostyukova, O. I., andRaketskii, V. M.,Constructive Optimization Methods, Part 4: Convex Problems, Izdatelstvo Universitetskoye, Minsk, Russia, 1987 (in Russian). [7] Kiwiel, K. C.,Exact Penalty Functions in Proximal Bundle Methods for Constrained Convex Nondifferentiable Minimization, Mathematical Programming, Vol. 52, pp. 285–302, 1991. · Zbl 0754.90045 · doi:10.1007/BF01582892 [8] Bertsekas, D. P., andTsitsiklis, J. N.,Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1989. [9] Eckstein, J., andBertsekas, D. P.,On the Douglas-Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators, Mathematical Programming, Vol. 55, pp. 293–318, 1992. · Zbl 0765.90073 · doi:10.1007/BF01581204 [10] Lemaréchal, C.,Lagrangian Decomposition and Nonsmooth Optimization: Bundle Algorithm, Prox Iteration, Augmented Lagrangian, Nonsmooth Optimization: Methods and Applications, Edited by F. Giannessi, Gordon and Breach, Philadelphia, Pennsylvania, pp. 201–216, 1992. [11] Sen, S., andSherali, H. D.,A Class of Convergent Primal-Dual Subgradient Algorithms for Decomposable Convex Programs, Mathematical Programming, Vol. 35, pp. 279–297, 1986. · Zbl 0594.90074 · doi:10.1007/BF01580881 [12] Sherali, H. D., andUlular, O.,A Primal-Dual Conjugate Subgradient Algorithm for Specially Structured Linear and Convex Programming Problems, Applied Mathematics and Optimization, Vol. 20, pp. 193–221, 1989. · Zbl 0675.90069 · doi:10.1007/BF01447654 [13] Spingarn, J. E.,Applications of the Method of Partial Inverses to Convex Programming: Decomposition, Mathematical Programming, Vol. 32, pp. 199–223, 1985. · Zbl 0565.90058 · doi:10.1007/BF01586091 [14] Tseng, P.,Further Applications of a Splitting Algorithm to Decomposition in Variational Inequalities and Convex Programming Mathematical Programming, Vol. 48, pp. 249–263, 1990. · Zbl 0725.90079 · doi:10.1007/BF01582258 [15] Tseng, P.,Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities, SIAM Journal on Control and Optimization, Vol. 29, pp. 119–138, 1991. · Zbl 0737.90048 · doi:10.1137/0329006 [16] Dantzig, G. B., andWolfe, P.,Decomposition Principle for Linear Programs, Operations Research, Vol. 8, pp. 101–111, 1960. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101 [17] Golshtein, E. G.,A General Approach to Decomposition of Optimization Systems, Izvestia Akademii Nauk SSSR, Tekhnicheskaya Kibernetika, No. 1, pp. 59–69, 1987 (in Russian); English Translation, Soviet Journal of Computing and Systems Science, Vol. 25, pp. 105–114, 1987. [18] Rockafellar, R. T.,Monotone Operators and the Proximal Point Algorithm, SIAM Journal on Control and Optimization, Vol. 14, pp. 877–898, 1976. · Zbl 0358.90053 · doi:10.1137/0314056 [19] Correa, R., andLemaréchal, C.,Convergence of Some Algorithms for Convex Minimization, Mathematical Programming, Vol. 62, pp. 261–275, 1993. · Zbl 0805.90083 · doi:10.1007/BF01585170 [20] Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982. [21] Lasdon, S.,Optimization Theory for Large Systems, Macmillan, New York, New York, 1970. [22] Kiwiel, K. C.,An Algorithm for Nonsmooth Convex Minimization with Errors, Mathematics of Computation, Vol. 45, pp. 173–180, 1985. · doi:10.1090/S0025-5718-1985-0790650-5 [23] Rzhevskii, S. V., andKuncevich, A. V.,An Application of the Subgradient Method to the Solution of the Dual and Primal Problems of Convex Programming, Kibernetika, No. 5, pp. 51–54, 1985 (in Russian). [24] Robinson, S. M.,Bundle-Based Decomposition: Description and Preliminary Results, System Modelling and Optimization, Edited by A. Prékopa, J. Szelezsán, and B. Strazicky, Springer Verlag, Berlin, Germany, pp. 751–756, 1986. [25] Robinson, S. M.,Bundle-Based Decomposition: Conditions for Convergence, Annales de l’Institut H. Poincaré, Analyse Non-Linéaire, Vol. 6, pp. 435–447, 1989. [26] Hiriart-Urruty, J. B., andLemaréchal, C.,Convex Analysis and Minimization Algorithms, Springer Verlag, Berlin, Germany, 1993. [27] Kiwiel, K. C.,Approximations in Decomposition of Large-Scale Convex Programs via a Nondifferentiable Optimization Method, Proceedings of the 11th Triennial IFAC World Congress, Tallin, Estonia, 1990; Edited byÜ. Jaaksoo andV. I. Utkin, Pergamon Press, Oxford, England, Vol. 1, pp. 161–166, 1991. [28] Kiwiel, K. C.,Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Springer Verlag, Berlin, Germany, Vol. 1133, 1985. [29] Schramm, H., andZowe, J.,A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results, SIAM Journal on Optimization, Vol. 2, pp. 121–152, 1992. · Zbl 0761.90090 · doi:10.1137/0802008 [30] Kiwiel, K. C.,A Dual Method for Certain Positive-Semidefinite Quadratic Programming Problems, SIAM Journal on Scientific and Statistical Computing, Vol. 10, pp. 175–186, 1989. · Zbl 0663.65063 · doi:10.1137/0910013 [31] Kiwiel, K. C.,A Cholesky Dual Method for Proximal Piecewise Linear Programming, Numerische Mathematik, Vol. 68, pp. 325–340, 1994. · Zbl 0822.65038 · doi:10.1007/s002110050065 [32] Lemaréchal, C.,Numerical Experiments in Nonsmooth Optimization, Progress in Nondifferentiable Optimization, Edited by E. A. Nurminski, International Institute for Applied Systems Analysis, Laxenburg, Austria, Report CP-82-S8, pp. 61–84, 1982. [33] Kiwiel, K. C.,A Method for Solving Certain Quadratic Programming Problems Arising in Nonsmooth Optimization, IMA Journal on Numerical Analysis, Vol. 6, pp. 137–152, 1986. · Zbl 0603.65041 · doi:10.1093/imanum/6.2.137