摘要
本文主要研究目标函数和约束函数都是局部Lipschitz函数的非光滑最优化问题。内容涉及到局部Lipschitz函数的广义不变凸性，集值映射的广义单调性，在没有任何约束规格条件下的各种非光滑最优化问题的最优性充分条件和必要条件，混合对偶理论，Lagrange鞍点理论以及非光滑单目标优化问题的非单调线搜索算法和信赖域算法。分四部分介绍如下：
一、局部Lipschitz函数的广义不变凸性和集值映射的广义单调性
利用Jeyakumar和Luc给出的局部Lipschitz函数的J-L次微分(也称为convexificator)的定义，引入了非光滑的广义(严格)不变拟凸函数和广义(严格)不变伪凸函数以及集值映射的广义(严格)不变拟单调性和广义(严格)不变伪单调性，研究了广义不变凸性与广义不变单调性之间的关系，特别地，分别建立了一个局部Lipschitz函数的不变拟凸性和它的J-L次微分映射的不变拟单调性之间的充分必要条件，以及一个局部Lipschitz函数的(严格)不变伪凸性和它的J-L次微分映射的(严格)不变伪单调性之间的充分必要条件。
二、非光滑最优化问题的最优性条件，混合对偶理论以及Lagrange鞍点理论
不需要任何约束规格条件，建立了非光滑数学规划的一阶最优性充分必要条件，以此为基础建立了几类非光滑最优化问题的混合对偶规划，并且在没有任何约束规格条件下证明了弱对偶定理，强对偶定理以及Lagrange函数的鞍点存在性定理。对于极小极大分式规划和凸的广义极小极大分式规划，分别建立了它们的混合对偶规划。该对偶规划统一了著名的Mond-Weir对偶模型，Wolfe对偶模型和参数对偶模型，基本上解决了由Lai、Liu和Tanaka在1999年提出的两个问题。
三、非光滑最优化问题的非单调线搜索算法
把强制函数应用于非单调线搜索技术，并且把该技术应用到目标函数是局部Lipschitz函数的非光滑无约束最优化问题的研究中去，得到了一个非单调线搜索方法的一般框架，并且建立了该方法的全局收敛性结果。作为特殊情况，可以得到非光滑无约束最优化问题的线搜索算法的广义Armijo-准则，广义Goldstein-准则和广义Wolfe-准则。
四、非光滑最优化问题的非单调信赖域算法
研究了无约束非光滑最优化问题的非单调信赖域算法模型，算法中所解的
信赖域子间题是Qi和Sun在阵刁中研究的，子问题含有一个迭代函数，因此
具有一般性.一方面，我们将非单调技术用于Qi和Sun的信赖域算法，给出了
一个非光滑无约束极小化间题的一个非单调信赖域算法，并且证明了该算法是
整体收敛的.非单调信赖域算法可以保证，当迭代点进入弯曲的峡谷中时，算法
有较好的收敛速度.但是，对此非单调信赖域算法我们只能证明，由算法产生的
迭代点列中存在一个聚点是稳定点的收敛性质.因此，我们采用Toint的思想对
算法进行了改进，给出了问题(P)的一个修正的非单调信赖域算法，该算法有
较好的收敛性质，由该算法产生的迭代点列中每一个聚点都是一个临界点.另
一方面，在同样的假设条件下，我们给出一个间题(P)的半径有下界的信赖域
算法.这个算法是也是一个标准的信赖域算法，唯一的区别在于成功迭代后的
信赖域半径的修正，算法选择了一个较小的半径△二‘。做为新的半径的下界.另
外，我们用传统的方法给出算法的收敛性证明.
最后，我们用类似的方法研究了LC‘间题，即目标函数的梯度Vf是一个
局部Lipschitz函数.通过解孙文瑜等人用二阶Dini方向导数建立了的一种新
的信赖域子间题，给出了一个LC‘间题的一个非单调信赖域算法，并且证明了
该算法是整体收敛的.
In this thesis, we study the non-smooth optimization problem where the objective function and constrained functions are all locally Lipschitzian functions. The thesis includes the generalized invexity of locally Lipschitzian functions; the generalized invariant monotonicity of set-value maps and the relationships between the generalized invariant monotonicity of convexificators and the generalized invexity of nonsmooth functions; the optimality necessary and sufficient conditions for non-linear programmings without a constraint qualification; mixed dual theory; Lagrange saddle point theory; nonmonotone line search methods for nonsmooth unconstrained optimization; nonmonotone trust region methods for nonsmooth unconstrained optimization.
Using convexificators and invex functions introduced by Jeyakumar et al. and Hanson, respectively, the generalized convexity of nonsmooth functions and generalized monotonicity of set-valued maps are further extended. The relationships between the generalized invariant monotonicity of convexificators and the generalized invexity of nonsmooth functions are established.
Without any constraint qualification, we establish the first-order optimality necessary and sufficient conditions for non-smooth scale programming, multi-objective programming and minmax fractinal programming involving pseudoin-vex functions, which generalizes the existing results. On the other hand, without the need of a constraint qualification, we establish the necessary and sufficient optimality conditions for generalized fractional programming involving a compact set. Using these optimality conditions, we construct a parametric dual model and a parameter-free mixed dual model, this mixed dual model unifies two dual parameter-free models constructed by Lai and Liu et al.. Several duality theorems are established.
The nonmonotone line search methods have been successfully used in smooth unconstrained optimization and constrained optimization. Combining the forcing functions with the nonmonotone line search technique, we present a general framework of nonmonotone line search methods for the nonsmooth unconstrained optimization problems where the objective function is a locally Lipschitzian func-
tion and establish the global convergence results . As special cases, we can obtain the nonsmooth nonmonotone Armijo rule, Goldstein rule and Wolfe rule.
Combining the trust region algorithm of Qi and Sun with the nonmonotone technique, we present a nonmonotone trust region algorithm for the unconstrained nonsmooth optimization problems where the objective function is locally Lipschitzian, and prove that our nonmonotone trust region algorithm is globally convergent.
引文
[1] M. A. Hanson, On Sufficiency of the Kuhn Tucker Conditions, Journal of Mathematical Analysis and Applications, Vol.80, pp. 545-550, 1981.
[2] X. M. Yang, X. Q. Yang, and K. L. Teo, Generalized Invexity and Generalized Invariant Monotonicity, Journal of Optimization Theorem and Applications, Vol.117,No.3,pp. 607-625(2003).
[3] T. Weir and B. Mond, Pre-invex Functions in Multiple Objective Optimization, Journal of Mathematical Analysis and Applications, Vol. 136, pp. 29-38,1988.
[4] T. Weir and V. Jeyakumar, A Class of Nonconvex Functions and Mathematical Programming, Bulletin of Australian Mathematical Society, Vol. 38, pp. 177-189, 1988.
[5] S. Schaible, Criteria for Gneralized Monotonicity, New Trends in Mathematical Programming(F.Giannessi et al. eds.), Kluwer Academic Publishers, pp277-288, 1998.
[6] X. M. Yang, and D. li., On Properties of Preinvex Functions, Journal of Mathematical Analysis and Applications, Vol. 256, pp. 229-241, 2001.
[7] J. P.,Penot and P. H. Sach, Generalized Monotonicity of Subdifferentials and Generalized convexity, Journal of Optimization Theorem and Applications, Vol. 94, pp. 251-262, 1997.
[8] D. T. Luc, Generalized Monotone Set-Value Maps and Bifunctions, Acta Mathematica Vietnamica, Vol. 21, pp.212-252, 1996.
[9] D. T. Luc, Characterizations of Quasiconvex Functions, Bulletin of the Australian Mathematical Society, Vol. 48, pp. 393-406, 1993.
[10] R. Pini, Invexity and Generalized convexity, Optimization, Vol. 22, pp. 513-525, 1991.
[11] S. R. Mohan and S. K. Neogy, On Invex Sets and Preinvex Functions, Journal of Mathematical Analysis and Applications, 189(1995):901-908.
[12] A. Ben-Israel and B. Mond, What is invexity? J. Austral. Math. Soc. B 28(1986):1-9.
[13] J. B. Hiriart-Urruty, and C. Lemaréchal, Convex Analysis and Minimization Algorithms Ⅰ, Springer-Verlag, Berlin, Heidelberg, 1993.
[14] P.Wolfe, A duality theorem for nonlinear programming, Quart. Appl. Math.
19(1961)239-244.
[15] R.R.Edudo, Efficiency and generalized convex duality for multiobjective programs, J.Math.Anal.Appl., 138(1989) 84-94.
[16] R.R.Edudo, multiobjective duality in mathematical programming, PhD.Thesis, Latrobe University, Bundoora, Victoria, Australia, 1990.
[17] J. C., Liu, C. S. Wu and R. L. Sheu, Duality For fractional minimax programming, Optimization , Vol.41, pp. 117-133, 1997.
[18] C. Singh, Optimality conditions and Duality For fractional minimax programming, Journal of Mathematical Analysis and Applications, Vol. 100, pp. 409-415, 1984.
[19] C. R. Becter, S. Chandra and M. K. Becter , Generalized Fractional Programming Duality: A Parametric Approach, Journal of Optimization Theorem and Applications, Vol. 60, pp. 243-260, 1989.
[20] J. P. Crouzeix, J. A. Ferland and S. Schaible, Duality in Generalized Fractional Programming, Mathematical Programming, Vol. 27, pp. 342-354, 1983.
[21] J. P. Crouzeix, J. A. Ferland and S. Schaible, An Algorithm for Generalized Fractional Programs, Journal of Optimization Theorem and Applications, Vol. 47, pp. 35-49, 1985.
[22] A. Ben-Israel, Ben-Tat, and S. Zlobec, Optimality in Nonlinear Programming: A Feasible Dirction Approach. John Wiley and Sons, New York, 1981.
[23] T. Weir and B. Mond, Duality for Fractional Programming Without a Constriant Qualification, Utilitas Mathematica, vol. 38, pp. 41-55,1990.
[24] T. Weir and B. Mond, Duality generalized programming without a constriant qualification, Utilitas Mathematica, 31(1987):233-242.
[25] G. J. Zalmai, Optimality Conditions and Duality Models for Generalized Fractional Programming Problems Containing Locally Subdifferentiable and ρ-Convex Functions, Optimization, Vol. 32, pp. 95-124, 1995.
[26] R. R. Egudo, T. Weir, and B. Mond, Duality Without a Constriant Qualification in Multiobjective Programming, Journal of the Australian Mathematical Society, Vol. 33B, pp. 531-544, 1992.
[27] A. D. Ioffe, and V. L. Leven, Subdifferentiable Convex Functions, Transactions of the Moscow Mathematical Society, Vol. 26, pp. 1-72, 1972.
[28] H. C. Lai, J. C. Liu and K. Tanaka, Duality Without a Constraint Qualification for Minimax Fractional Programming, Journal of Optimization Theorem and Ap-
plications, Vol.101, No.1. pp. 109-125,1999.
[29] J. Grippo, F. Lampariello and S. Lucidi, A Nonmonotone Line Search Technique for Newton's Methods, SIAM Journal of Numerical Analysis, Vol. 23, pp. 707-716(1986).
[30] P. Toint, An Assessment of Nonmonotone Line Search Techniques for Unconstrained Optimuzation, SIAM Journal on Scientific Computing, Vol. 17, pp. 725-739(1996).
[31] J. Zhou and A. Tits, A Nonmonotone Line Search for Minimax Problems, Journal of Optimization Theorem and Applications, Vol. 26, pp. 455-476(1993).
[32] J. S. Pang, S. P. Han, and N. Rangaraj, Minimization of Locally Lipschitzian Functions, SIAM Journal on Optimization 1:57-82(1991).
[33] Y. Dai, On the Nonmonotone Line Search, Journal of Optimization Theorem and Applications, Vol.112, No. 2,pp. 315-330(2002).
[34] Y. Yuan and W. Sun, Optimization Theory and Methods, Science Press, Beijing, 1997.
[35] W. Sun, J. Han and J. Sun, Global Convergence of Nonmonotone Descent Methods for Unconstrained Optimuzation Problems, Journal of Computational and Applied Mathematics 146:89-98(2002).
[36] M.J.D. Powell, On the global convergence of trust region algorithms for unconstrained optimization, Mathematical Programming 29(1984) 297-303.
[37] J.E. Dennis, S.B.Li and R.A.Tapia, A unified approach to global convergence of trust region algorithm for nonsmooth optimization, Mathematical Sciences Technicel Report, TR 89-5, Rice University(Houston, Texas,1990 revised).
[38] R. Fletcher, Practical Methods of Optimization, Conctrained Optimization, John Wilry and Sons, New York, 1981.
[39] M.J.D. Powell, Convergence properties of a class of minimization algorithms, in Nonlinear Programming 2, O.L.Mangasarian, R.R. Meyer and S.M.Robinson eds., Academic Press, New York, 1975.
[40] Andrew R.Conn, Nicholas 1.M.Gould and Philippe L.Toint, Trust-Region Methods, SIAM.MPS (Philadelphia,2000).
[41] N. Deng, Y. Xiao and F. Zhou, Nonmonotone Trust Region Algorithm, Journal of Optimization Theorem and Applications, Vol. 26, pp. 259-285(1993).
[42] 柯小伍，韩继业，一类新的信赖域算法的全局收敛性，应用数学学报，Vol．18，No．4，(1995)．
[43] 柯小伍，韩继业，约束最优化一类非单调信赖域算法，科学通报，Vol．40．4，(1995)．
[44] P. Toint, A Nonmonotone Trust Region Algorithm for Nonlinear Optimization Subject to Convex Constraints, Mathematical Programming, Vol. 77, pp. 69-94(1997).
[45] Y. Yuan, Conditions for convergence of trust region algorithm for nonsmooth optimization, Mathematical Programming 31:220-228(1985).
[46] Y. Yuan, On the soperlinear of a trust region algorithm for nonsmooth optimization, Mathematical Programming 31:269-285(1985).
[47] L. Qi and Jie Sun, A Trust Region Algorithm for Minimization of locally Lipschitzian functions, Mathematical Programming 66:25-43(1994).
[48] H.Jiang, M.Fukushima, L.Qi and D.Sun, A Trust Region Method for Solving Generalized Complementarity Problems, SIAM Journal on Optimization.
[49] S.A. Gabriel and J.S. Pang, A Trust Region Method for Constrained Nonsmooth Equations. In W.W. Hager, D.W.Hearn and P.M. Pardalos(eds.) : Large Scale Optimization. State of the Art. Kluwer Academic Publishers, Dordrecht, 1994, pp. 155-181.
[50] Christian Kanzow and Martin Zupke, Inexact Trust-Region Methods for Nonlinear Complementarity Problem, Reformulation: Nonsmooth,Piecewise Smooth, Semismooth and Smoothing Methods, Edited by M.Fukushima and L.Qi, 1998 Kluwer Academic Publishers, pp. 211-233.
[51] V. Jeyakumar and D. T. Luc, Nonsmooth Calculus, Minimality, and Monotoinity of Convexificators, Journal of Optimization Theorem and Applications, Vol. 101. pp. 599-621, 1999.
[52] J. Dutta and S. Chandra, Convexificators, Generalized Convexity, and Optimality Conditions, Journal of Optimization Theorem and Applications, Vol. 113, No.1, pp. 41-64, 2002.
[53] X. Wang and V. Jeyakumar, A Sharp Lagrangian Multiplier Rule for Nonsmooth Mathematical Programming Problems Involvng Equality Constraints, SIAM Journal on Optimization, Vol. 10, pp. 1136-1148, 2000.
[54] X. M. Yang, X. Q. Yang, and K. L. Teo, Characterizations and Applications of Prequasiinvex Type Functions, Journal of Optimization Theorem and Applications, Vol. 110, pp.645-668, 2001.
[55] J. C. Liu, Optimality and Duality for Generalized Fractional Programming In-
volving Nonsmooth Pseudoinvex Functions, Journal of Mathematical Analysis and Applications, Vol. 202, 667-685, 1996.
[56] S. Karamardian and S. Schaible, Seven Kinds of Monotone Maps, Journal of Optimization Theorem and Applications, Vol. 66, pp. 37-46, 1990.
[57] A. Ben-Israel and B. Mond, First Order Optimality Conditions for Generalized Convex Functions: A Feasible Directions Approach, Utilitas Mathematica 25 (1984): 249-262.
[58] B. Mond and S. Zlobec, Duality for Nondifferentiable Programming Without a Constraint Qualification, Utilitas Mathematica 15 (1979):291-302.
[59] F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, 1983.
[60] S. Chandra and V. Kumar, Duality in fractional minimax programming, J. Austral Math. Soc. Ser. A. Vol. 58, pp. 376-386, 1995.
[61] J. C. Liu, and C. S. Wu, On minimax Fractional Optimality conditions with (F, ρ)-Convexity, Journal of Mathematical Analysis and Applications , Vol. 219, pp. 36-51, 1999.
[62] H. C. Lai, and L.J. Lin, Moreau-Rockfellar Type Theorem for Convex Set Functions, Journal of Mathematical Analysis and Applications, Vol. 132, pp. 558-571, 1988.
[63] W. Sun, R. J. B. de Sampaio and J. Yuan, Two algorithms for LC~1 unconstrained optimization, Journal of compitational Mathematics, Vol.18, No. 6,(2000) 621-632.
[64] 李正锋，邓乃扬，一类新的非单调信赖域算法及其收敛性，应用数学学报，Vol．22，No．3，(1999)．
[65] Zhou Houchun, Sun Wenyu, Mixed Duality Without a Constraint Qualification for Minimax Fractional Programming, 《Optimization》, Vol.52, No.4-5(2003)617-627.
[66] Zhou Houchun, Sun Wenyu, Optimality and Duality Without a Constraint Qualification for Minimax Programming, 《Bulletin of the Australian Mathematical Society》, Vol.67, No.1(2003)121-130.