uv-分解理论在数学规划中的应用
|
摘要
在非光滑优化中,非光滑函数的二阶展开对于最优性条件的研究以及设计具有高阶收敛性的算法都是不可缺少的工具,因此,对非光滑函数的二阶性质与展开的理论研究一直倍受关注。
2000年,Lemaréchal,Miffilin,Sagastizábal及Oustry等人提出的关于凸函数的UV-分解理论,给出了研究非光滑凸函数的二阶性质的新方法。UV-分解理论的基本思想是将R~n分解为两个正交的子空间U和V的直和,使原函数在U空间上的一阶逼近是线性的,而其不光滑特征集中于V中,借助于一个中间函数,U-Lagrange函数,来得到函数在切于U的某个光滑轨道上的二阶展开式。
本文研究了具有原始对偶梯度结构(pdg)结构的一类凸函数,对这类特殊结构的函数,可以在一系列的限制条件下,如V-最优性条件,可行性及横截性条件等,得到U-Hesse阵存在的相对较弱的充分条件,以及U-Lagrange函数的最优点集W(u)的存在和其产生的切于U的光滑轨道(?)+u(?)W(u)的刻画,进而得出f在其上的二阶展开,
本文将UV-分解理论应用于非线性规划中,首先对于具有不等式约束的非线性规划问题,将结果推广到选取一般次梯度的情形,以便更好地应用UV-分解算法,其次,将UV-分解理论应用于非线性互补问题,引入全指标集和可行指标集的概念,研究了其精确罚函数的UA-Lagrange函数及其性质。
In nonsmooth optimization, second-order expansion theory is significant both for deriving optimalty optimality conditions and developing algorithms . Therefore, the study concerning the theory of the second-order properties of nonsmooth functions have been paid much attention.Lemarechal, Miffilin, Sagastizabal and Oustry(2000) introduced the UV—theory, which opens a way to defining a suitable restricted second-order derivative of a convex function f at a nondifferentible point x. The basic idea is to decompose R~n into two orthogonal subspaces U and V depending on x so that f's nonsmoothness near the point is concentrated essentially in V. A certain Lagangian associated with the convex functin was introduced, called U—Lagrangian. When f satisfies certain structural properties, it is possible to find smooth trajectories, via the intermediate function , yielding α second-order expansion for f.Under a set of conditions such as V— optimality , feasibility and transervality, we obtain a set of relative weak sufficient conditions for the existence of U—Hessiian. the existence of optimal solution set W(u) of the U—Lagrangian and the characterization of the associated smooth trajectary x + u + W(u) tangential to U, so that the second order expansion of f can be develped.In the paper, the UV—decomposition theory is applied to NLP. The results on the penalty function of constrained minimization with a finit number of constraints are gen-eralied. The UV—decomposition theory to the exact penalty functions in NLP for a nonlinear complementary problem with a basic index set and a feasible basic index set are established.
2000年,Lemaréchal,Miffilin,Sagastizábal及Oustry等人提出的关于凸函数的UV-分解理论,给出了研究非光滑凸函数的二阶性质的新方法。UV-分解理论的基本思想是将R~n分解为两个正交的子空间U和V的直和,使原函数在U空间上的一阶逼近是线性的,而其不光滑特征集中于V中,借助于一个中间函数,U-Lagrange函数,来得到函数在切于U的某个光滑轨道上的二阶展开式。
本文研究了具有原始对偶梯度结构(pdg)结构的一类凸函数,对这类特殊结构的函数,可以在一系列的限制条件下,如V-最优性条件,可行性及横截性条件等,得到U-Hesse阵存在的相对较弱的充分条件,以及U-Lagrange函数的最优点集W(u)的存在和其产生的切于U的光滑轨道(?)+u(?)W(u)的刻画,进而得出f在其上的二阶展开,
本文将UV-分解理论应用于非线性规划中,首先对于具有不等式约束的非线性规划问题,将结果推广到选取一般次梯度的情形,以便更好地应用UV-分解算法,其次,将UV-分解理论应用于非线性互补问题,引入全指标集和可行指标集的概念,研究了其精确罚函数的UA-Lagrange函数及其性质。
In nonsmooth optimization, second-order expansion theory is significant both for deriving optimalty optimality conditions and developing algorithms . Therefore, the study concerning the theory of the second-order properties of nonsmooth functions have been paid much attention.Lemarechal, Miffilin, Sagastizabal and Oustry(2000) introduced the UV—theory, which opens a way to defining a suitable restricted second-order derivative of a convex function f at a nondifferentible point x. The basic idea is to decompose R~n into two orthogonal subspaces U and V depending on x so that f's nonsmoothness near the point is concentrated essentially in V. A certain Lagangian associated with the convex functin was introduced, called U—Lagrangian. When f satisfies certain structural properties, it is possible to find smooth trajectories, via the intermediate function , yielding α second-order expansion for f.Under a set of conditions such as V— optimality , feasibility and transervality, we obtain a set of relative weak sufficient conditions for the existence of U—Hessiian. the existence of optimal solution set W(u) of the U—Lagrangian and the characterization of the associated smooth trajectary x + u + W(u) tangential to U, so that the second order expansion of f can be develped.In the paper, the UV—decomposition theory is applied to NLP. The results on the penalty function of constrained minimization with a finit number of constraints are gen-eralied. The UV—decomposition theory to the exact penalty functions in NLP for a nonlinear complementary problem with a basic index set and a feasible basic index set are established.
引文
[1] A. Auslender, Numerical methods for nondifferentiable convex optimization, Mathematical Programming Study, 30, 1987, 102-126.
[2] R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Analysis: Theory, Methods and Applications 9(11), 1985, 1189-1209.
[3] J. -PCrouzeix, A relationship between the second derivative of a convex function and its conjugate, Mathematical Programming, 13, 1977, 364-365.
[4] J. -B. Hiriart-Urruty, Lipschitz r-continuity of the approximate subdifferential of a convex function, Mathematical Scandinavica, 47, 1980, 123-134.
[5] J. -B. Hiriart-Urruty, The approximate first-order and second-order directional derivatives for a convex function, In J. -P. Ceccooni and T. Zolezzi, Editors, Mathematical Theories of Optimization, number 979 in Lecture Notes in Mathematicas, Springer-Verlag, 1983, 154-166.
[6] M. L. Overton and R. S. Womersley, Second derivatives for optimizing eigenvalues of symmetric matrices, Journal of Mathematical Analysis and Applications, 3, 1995, 667-718.
[7] M. L. Overton and X. J. Ye, Towards second-order methods for structured nonsmooth opitimiziation, Advances in Optimization and Numerical Analysis (S.Gomez and J. P. Hennart, eds.), Kluwer, 1994, 97-109.
[8] R. T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14, 1976, 877-898.
[9] R. T. Rockafellar, First and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc., 307, 1988, 75-107.
[10] R. T. Rockafellar, Generalized second derivatives of convex function and saddle function, Transactions of the American Methematical Society, 322(1), 1990, 51-78.
[11] C. Lemarechal, F. Oustry, C. Sagastizabal. The U-Lagrangian of a convex function. Trans. Amer. Math. Soc., 352, 2000, 711-729.
[12] J. -B. Hiriart-Urruty, A new set-valued second order derivative for convex function, Fermat Days 85: Mathematics for Optimazation(J. -B. Hiriar-Urruty, ed.), Mathematics Studdies, 129, North-Holland, 1986, 157-182.
[13] B. S. Mordukhovich, Generalized differential calculus for nonsmooth and set-valued mappings Journal of Mathematical Analysis and Applications 183(1), 1993, 250-288.
[14] R. A. Poliquin, Proto-differentiation of subgradient set-valued mappings, Canadian Journal of Mathematics, 42(3), 1990, 520-532.
[15] J. P. Aubin, Contigent derivatives of set-valued maps and existence of solutions to nonlinear inclusions and differential equations, Mathematical Analysis and Applications(L. Nachbin, ed.), Academic Press, 1981, 159-229.
[16] H. T. Banks and M. Q. Jacobs, A differential calculus for multifunctions, Journal of Mathmatical Analysis and Applications 29(1970), 246-272.
[17] A. D. Ioffe, Nonsmooth analysis and the theory of fans, Convex analysis and Optimazation(J. P. Aubin and R. B. Vinter, eds.), Pitman, 1982, pp.93-118.
[18] C. Lemarechal and J. Zowe, The eclipsing concept to approximate a multi-valued mapping, Optimization 22(1991), no.1, 3-37.
[19] J. -P. Penot, Differentiability of relations and differential stability of perturbed optimization problems, SIAM Journal on Control and Optimization 22(1984), no. 4, 529-551.
[20] C. Lemarechal and C. Sagastizabal, More than first-order developments of convex function:primal-dule relations, Journal of Convex Analysis, 3(2), 1996, 1-14.
[21] C. Lemarechal and C. Sagastizabal, Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries. SIAM Journal on Optimization, 7(2), 1997, 367-385.
[22] F. Oustry, The U-Lagrangian of the maximum eigenvalue function. SIAM Journal on Optimization, 9, 1999, 526-549.
[23] F. Oustry, A second-order bundle method to minimize the maximum eigenvalue function. Mathematical Programming. 89(1), 2000, 1-33.
[24] F. Oustry, U-Newton algorithm to minimize the structured maximum eigenvalue function. SIAM Journal on Optimization, Submitted.
[25] R. Miffilin and C. Lemarechal, VU-decomposition derivatives convex max-function, In Ⅲ-posed Variational Problems and Regularization Techniques, Tichatschke R. and Thera M., editors, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag Berlin Heidelberg, 477, 1999, 167-186.
[26] R. Miffilin and C. Sagastizabal, Functions with primal-dule gradient structure and UHessians. In G. Di Pillo and F. Gianneddi, editors, Nonlinear Optimization and Related Topics, number 36 in Applied Optimization. Kluwer Academic Publishiers B. V., 2000, 219-133.
[27] R. Miffilin and C. Sagastizabal, Primal-dule gradient structure functions: second-order results;links to epi-derivatives and partly smooth functions, SIAM Journal on Optimization, 13(4), 2003.
[28] R. Miffilin and C. Sagastizabal, On VU-theory for functions with primal-dule gradient structure. SIAM Journal on Optimization, 11(2), 2000, 547-571.
[29] R. T. Rockafellar, Convex Analysis, Princedon University Press, Princedon, New Jersey, 1970.
[2] R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Analysis: Theory, Methods and Applications 9(11), 1985, 1189-1209.
[3] J. -PCrouzeix, A relationship between the second derivative of a convex function and its conjugate, Mathematical Programming, 13, 1977, 364-365.
[4] J. -B. Hiriart-Urruty, Lipschitz r-continuity of the approximate subdifferential of a convex function, Mathematical Scandinavica, 47, 1980, 123-134.
[5] J. -B. Hiriart-Urruty, The approximate first-order and second-order directional derivatives for a convex function, In J. -P. Ceccooni and T. Zolezzi, Editors, Mathematical Theories of Optimization, number 979 in Lecture Notes in Mathematicas, Springer-Verlag, 1983, 154-166.
[6] M. L. Overton and R. S. Womersley, Second derivatives for optimizing eigenvalues of symmetric matrices, Journal of Mathematical Analysis and Applications, 3, 1995, 667-718.
[7] M. L. Overton and X. J. Ye, Towards second-order methods for structured nonsmooth opitimiziation, Advances in Optimization and Numerical Analysis (S.Gomez and J. P. Hennart, eds.), Kluwer, 1994, 97-109.
[8] R. T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14, 1976, 877-898.
[9] R. T. Rockafellar, First and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc., 307, 1988, 75-107.
[10] R. T. Rockafellar, Generalized second derivatives of convex function and saddle function, Transactions of the American Methematical Society, 322(1), 1990, 51-78.
[11] C. Lemarechal, F. Oustry, C. Sagastizabal. The U-Lagrangian of a convex function. Trans. Amer. Math. Soc., 352, 2000, 711-729.
[12] J. -B. Hiriart-Urruty, A new set-valued second order derivative for convex function, Fermat Days 85: Mathematics for Optimazation(J. -B. Hiriar-Urruty, ed.), Mathematics Studdies, 129, North-Holland, 1986, 157-182.
[13] B. S. Mordukhovich, Generalized differential calculus for nonsmooth and set-valued mappings Journal of Mathematical Analysis and Applications 183(1), 1993, 250-288.
[14] R. A. Poliquin, Proto-differentiation of subgradient set-valued mappings, Canadian Journal of Mathematics, 42(3), 1990, 520-532.
[15] J. P. Aubin, Contigent derivatives of set-valued maps and existence of solutions to nonlinear inclusions and differential equations, Mathematical Analysis and Applications(L. Nachbin, ed.), Academic Press, 1981, 159-229.
[16] H. T. Banks and M. Q. Jacobs, A differential calculus for multifunctions, Journal of Mathmatical Analysis and Applications 29(1970), 246-272.
[17] A. D. Ioffe, Nonsmooth analysis and the theory of fans, Convex analysis and Optimazation(J. P. Aubin and R. B. Vinter, eds.), Pitman, 1982, pp.93-118.
[18] C. Lemarechal and J. Zowe, The eclipsing concept to approximate a multi-valued mapping, Optimization 22(1991), no.1, 3-37.
[19] J. -P. Penot, Differentiability of relations and differential stability of perturbed optimization problems, SIAM Journal on Control and Optimization 22(1984), no. 4, 529-551.
[20] C. Lemarechal and C. Sagastizabal, More than first-order developments of convex function:primal-dule relations, Journal of Convex Analysis, 3(2), 1996, 1-14.
[21] C. Lemarechal and C. Sagastizabal, Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries. SIAM Journal on Optimization, 7(2), 1997, 367-385.
[22] F. Oustry, The U-Lagrangian of the maximum eigenvalue function. SIAM Journal on Optimization, 9, 1999, 526-549.
[23] F. Oustry, A second-order bundle method to minimize the maximum eigenvalue function. Mathematical Programming. 89(1), 2000, 1-33.
[24] F. Oustry, U-Newton algorithm to minimize the structured maximum eigenvalue function. SIAM Journal on Optimization, Submitted.
[25] R. Miffilin and C. Lemarechal, VU-decomposition derivatives convex max-function, In Ⅲ-posed Variational Problems and Regularization Techniques, Tichatschke R. and Thera M., editors, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag Berlin Heidelberg, 477, 1999, 167-186.
[26] R. Miffilin and C. Sagastizabal, Functions with primal-dule gradient structure and UHessians. In G. Di Pillo and F. Gianneddi, editors, Nonlinear Optimization and Related Topics, number 36 in Applied Optimization. Kluwer Academic Publishiers B. V., 2000, 219-133.
[27] R. Miffilin and C. Sagastizabal, Primal-dule gradient structure functions: second-order results;links to epi-derivatives and partly smooth functions, SIAM Journal on Optimization, 13(4), 2003.
[28] R. Miffilin and C. Sagastizabal, On VU-theory for functions with primal-dule gradient structure. SIAM Journal on Optimization, 11(2), 2000, 547-571.
[29] R. T. Rockafellar, Convex Analysis, Princedon University Press, Princedon, New Jersey, 1970.