We focus on some convex separable optimization problems, considered by the author in previous papers, for which problems, necessary and sufficient conditions or sufficient conditions have been proved, and convergent algorithms of polynomial computational complexity have been proposed for solving these problems. The concepts of well-posedness of optimization problems in the sense of Tychonov, Hadamard, and in a generalized sense, as well as calmness in the sense of Clarke, are discussed. It is shown that the convex separable optimization problems under consideration are calm in the sense of Clarke. The concept of stability of the set of saddle points of the Lagrangian in the sense of Gol'shtein is also discussed, and it is shown that this set is not stable for the “classical” Lagrangian. However, it turns out that despite this instability, due to the specificity of the approach, suggested by the author for solving problems under consideration, it is not necessary to use modified Lagrangians but only the “classical” Lagrangians. Also, a primal-dual analysis for problems under consideration in view of methods for solving them is presented. 1. Introduction 1.1. Statement of Problems under Consideration: Preliminary Results In this paper, we study well-posedness and present primal-dual analysis of some convex separable optimization problems, considered by the author in previous papers. For the sake of convenience, in this subsection we recall main results of earlier papers that are used in this study. In paper [1], the following convex separable optimization problem was considered: where are twice differentiable strictly convex functions, and are twice differentiable convex functions, defined on the open convex sets in？？ , respectively, for every ,？？ , and . Assumptions for problem are as follows. for all . If for some , then the value is determined a priori.( ) . Otherwise, the constraints (2) and (3) are inconsistent and the feasible set , defined by (2)-(3), is empty. In addition to this assumption, we suppose that in some cases which are specified below.( ) (Slater’s constraint qualification) There exists a point such that . Under these assumptions, the following characterization theorem (necessary and sufficient condition) for problem was proved in [1]. Denote by the values of , for which for the three problems under consideration in this paper, respectively. Theorem 1 (characterization of the optimal solution to problem ). Under the above assumptions, a feasible solution is an optimal solution to problem if and only if there exists a such that The
References
[1]
S. M. Stefanov, “Convex separable minimization subject to bounded variables,” Computational Optimization and Applications, vol. 18, no. 1, pp. 27–48, 2001.
[2]
S. M. Stefanov, “Convex separable minimization problems with a linear constraint and bounded variables,” International Journal of Mathematics and Mathematical Sciences, no. 9, pp. 1339–1363, 2005.
[3]
F. H. Clarke, Optimization and Nonsmooth Analysis, vol. 5 of Classics in Applied Mathematics, SIAM, Philadelphia, Pa, USA, 1990.
[4]
A. W. Roberts and D. E. Varberg, “Another proof that convex functions are locally Lipschitz,” The American Mathematical Monthly, vol. 81, pp. 1014–1016, 1974.
[5]
E. G. Gol'shtein, “Generalized gradient method for finding saddle points,” Economics and Mathematical Methods, vol. 8, no. 4, pp. 569–579, 1972 (Russian).
[6]
V. G. Karmanov, Mathematical Programming, Mir, Moscow, Russia, 1989.
[7]
A. N. Tychonov, “On the stability of the functional optimization problems,” USSR Computational Mathematics and Mathematical Physics, vol. 6, no. 4, pp. 631–634, 1966 (Russian).
[8]
E. Cavazzuti and J. Morgan, “Well-posed saddle point problems,” in Optimization: Theory and Algorithms, J. B. Hiriart-Urruty, W. Oettli, and J. Stoer, Eds., vol. 86 of Lecture Notes in Pure and Applied Mathematics, pp. 61–76, Marcel Dekker, New York, NY, USA, 1983.
[9]
A. L. Dontchev and T. Zolezzi, Well-Posed Optimization Problems, vol. 1543 of Lecture Notes in Mathematics, Springer, Berlin, Germany, 1993.
[10]
J. Hadamard, “Sur les problemes aux dérives partielles et leur signification physique,” Bulletin Princeton University, vol. 13, pp. 49–52, 1902.
[11]
J. Hadamard, Lectures on Cauchy's Problem in Linear Partial Differential Equations, Dover, New York, NY, USA, 1953.
[12]
A. N. Tychonov, “Stability of inverse problems,” Doklady Akademii Nauk SSSR, vol. 39, no. 5, pp. 195–198, 1943 (Russian).
[13]
A. N. Tihonov, “On the solution of ill-posed problems and the method of regularization,” Doklady Akademii Nauk SSSR, vol. 151, no. 3, pp. 501–504, 1963 (Russian).
[14]
A. N. Tihonov, “On the regularization of ill-posed problems,” Doklady Akademii Nauk SSSR, vol. 153, no. 1, pp. 49–52, 1963 (Russian).
[15]
A. N. Tihonov, “Regularisation methods for optimal control problems,” Doklady Akademii Nauk SSSR, vol. 162, no. 4, pp. 763–765, 1965 (Russian).
[16]
A. N. Tihonov, “ll-posed problems of optimal planning and stable methods for solving them,” Doklady Akademii Nauk SSSR, vol. 164, no. 3, pp. 507–510, 1965 (Russian).
[17]
A. N. Tychonov, “Ill-posed optimal planning problems,” USSR Computational Mathematics and Mathematical Physics, vol. 6, no. 1, pp. 81–89, 1966 (Russian).
[18]
A. N. Tychonov and V. Y. Arsenin, Solutions of Ill-Posed Problems, John Wiley & Sons, New York, NY, USA, 1977.
[19]
A. N. Tychonov and V. Y. Arsenin, Methods for Solving Ill-Posed Problems, Nauka, Moscow, Russia, 1986.
[20]
R. T. Rockafellar and R. J. B. Wets, Variational Analysis, vol. 317 of Fundamental Principles of Mathematical Sciences, Springer, Berlin, Germany, 1998.
[21]
F. H. Clarke, Necessary conditions for nonsmooth problems in optimal control and the calculus of variations [Ph.D. thesis], University of Washington, Seattle, Wash, USA, 1973.
[22]
F. H. Clarke, “A new approach to Lagrange multipliers,” Mathematics of Operations Research, vol. 1, no. 2, pp. 165–174, 1976.
[23]
E. G. Gol'shtein and N. V. Tret'iakov, “Modified Lagrangians,” Economics and Mathematical Methods, vol. 10, no. 3, pp. 568–591, 1974 (Russian).
[24]
S. M. Stefanov, “Method for solving a convex integer programming problem,” International Journal of Mathematics and Mathematical Sciences, no. 44, pp. 2829–2834, 2003.
[25]
S. M. Stefanov, “Convex quadratic minimization subject to a linear constraint and box constraints,” Applied Mathematics Research eXpress, no. 1, pp. 17–42, 2004.
[26]
S. M. Stefanov, “Polynomial algorithms for projecting a point onto a region defined by a linear constraint and box constraints in ,” Journal of Applied Mathematics, no. 5, pp. 409–431, 2004.
[27]
S. M. Stefanov, “An efficient method for minimizing a convex separable logarithmic function subject to a convex inequality constraint or linear equality constraint,” Journal of Applied Mathematics and Decision Sciences, vol. 2006, Article ID 89307, 19 pages, 2006.
[28]
S. M. Stefanov, “Minimization of a convex linear-fractional separable function subject to a convex inequality constraint or linear equality constraint and bounds on the variables,” Applied Mathematics Research eXpress, vol. 2006, no. 4, Article ID 36581, 24 pages, 2006.
[29]
S. M. Stefanov, “Solution of some convex separable resource allocation and production planning problems with bounds on the variables,” Journal of Interdisciplinary Mathematics, vol. 13, no. 5, pp. 541–569, 2010.
