無中文摘要

In this thesis, we apply smoothing methods for solving two optimization problems over a second-order cone, namely the absolute value equation associated with second-order cone (abbreviated as SOCAVE) and convex second-order cone programming (abbreviated as CSOCP). For SOCAVE, numerical comparisons are presented to illustrate the kind of smoothing functions which work well along with the smoothing Newton algorithm. In particular, the numerical experiments show that the well-known loss function widely used in engineering community is the worst one among the constructed smoothing functions. It indicates that other proposed smoothing functions can be considered for solving engineering problems.
For CSOCP, we use the penalty and barrier functions as smoothing functions. These methods are motivated by the work presented in [2]. Under the usual hypothesis that the CSOCP has a nonempty and compact optimal set, we show that the penalty and barrier problems also have a nonempty and compact optimal set. Moreover, any sequence of approximate solutions of these penalty and barrier problems is shown to be bounded whose accumulation points are solutions of the CSOCP. Finally, we provide numerical simulations to illustrate the theoretical results. More specifically, we use various penalty and barrier functions in solving the CSOCP and compare their efficiency by means of performance profiles.

Bibliography

[1] F. Alizadeh and D. Goldfarb, Second-order cone programming, Mathematical Programming, vol. 95, pp. 3-51, 2003.

[2] A. Auslender, R. Cominetti and M. Haddou, Asymptotic analysis of penalty and barrier methods in convex and linear programming, Mathematics of Operations Research, 22, pp. 43-62, 1997.

[3] A. Auslender, Penalty and barrier methods: A unified framework, SIAM Journal on Optimization, 10, pp. 211--230, 1999.

[4] A. Auslender, Variational inequalities over the cone of semidefinite positive matrices and over the Lorentz cone, Optimization methods and software, pp. 359-376, 2003.

[5] A. Auslender and M. Teboulle, Asymptotic cones and functions in optimization and variational inequalities, Springer monographs in mathematics, Springer, Berlin Heidelberg New York, 2003.

[6] A. Auslender and H. Ram´ırez C, Penalty and barrier methods for convex semidefinite programming, Mathematics of Operations Research, 63, pp.195-219, 2006.

[7] M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, 3rd Edition, Wiley - Interscience, 2006.

[8] H. H. Bauschke and P. L. Combettes, The Baillon-Haddad theorem revisited, Journal of Convex Analysis 17, pp. 781-787, 2010.

[9] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer-Verlag, New York, 2011.

[10] A. Beck, First-Order Methods in Optimization, MOS-SIAM Series on Optimization, 2017.

[11] A. Beck and M. Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters 31, pp. 167-175, 2003.

[12] A. Beck and M. Teboulle, Gradient-based algorithms with applications to
signal recovery problems, in Convex Optimization in Signal Processing and Communications, (D. Palomar and Y. Eldar, eds.), pp. 42-88, Cambridge University Press, 2010.

[13] A. Beck and M. Teboulle, Smoothing and first-order methods: a unified framework, SIAM Journal on Optimization, vol. 22, pp. 557-580, 2012.

[14] A. Ben-Tal and M. Teboulle, A smoothing technique for nondifferentiable optimization problems, in Optimization, Lecture Notes in Math. 1405, Springer-Verlag, New York, pp. 1-11, 1989.

[15] A. Ben-Tal and M. Zibulevsky, Penalty-barrier multiplier methods for convex programming problems, SIAM Journal on Optimization Vol 7, No. 2, pp. 347-366, 1997.

[16] D. P. Bertsekas, Nondifferentiable optimization via approximation, Mathematical Programming Study, pp. 1-25, 1975.

[17] D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers, Academic Press, New York, 1982.

[18] J. V. Burke and T. Hoheisel, Epi-convergence Properties of Smoothing by Infimal Convolution, Set-Valued and Variational Analysis, vol. 25, pp. 1-23, 2017.

[19] L. Caccetta, B. Qu, and G.-L. Zhou, A globally and quadratically convergent method for absolute value equations, Computational Optimization and Applications, vol. 48, pp. 45-58, 2011.

[20] B. Chen and P. T. Harker, Smooth Approximations to Nonlinear Complementarity Problems, SIAM Journal on Optimization, vol. 7, pp. 403-420, 1997.

[21] C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications, vol. 5, pp. 97-138, 1996.

[22] X.-D. Chen, D. Sun, and J. Sun, Complementarity functions and numerical experiments for second-order cone complementarity problems, ComputationalOptimization and Applications, vol. 25, pp. 39-56, 2003.

[23] J.-S. Chen, The convex and monotone functions associated with second-order cone, Optimization, vol. 55, no. 4, pp. 363-385, 2006.

[24] J.-S. Chen, Two classes of merit functions for the second-order cone complementarity problem, Mathematical Methods of Operations Research, vol. 64, pp. 495-519, 2006.

[25] J.-S. Chen, SOC Functions and Their Applications, Springer Optimization and Its Applications 143, Springer, Singapore, 2019.

[26] J.-S. Chen, X. Chen, and P. Tseng, Analysis of nonsmooth vector-valued functions associated with second-order cones, Mathematical Programming, vol. 101, no. 1, pp. 95-117, 2004.

[27] J.-S. Chen, T.-K. Liao, and S.-H. Pan, Using Schur complement theorem to prove convexity of some soc-functions, Journal of Nonlinear and Convex Analysis, vol 13, pp. 421-431, 2012.

[28] J.-S. Chen and S.-H. Pan, A survey on SOC complementarity functions and solution methods for SOCPs and SOCCPs, Pacific Journal of Optimization, vol. 8, no. 1, pp. 33-74, 2012.

[29] J.-S. Chen and P. Tseng, An unconstrained smooth minimization reformulation of second-order cone complementarity problem, Mathematical Programming, vol. 104, pp. 293-327, 2005.

[30] X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Mathematical Programming, vol. 134, pp. 71-99, 2012.

[31] E. D. Dolan and J. J. More, Benchmarking optimization software with performance profiles, Mathematical Programming, vol. 91, pp. 201-213, 2002.

[32] U. Faraut and A. Koranyi, Analysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford University Press, New York, 1994.

[33] M. Fukushima, Z.-Q. Luo, and P. Tseng, Smoothing functions for second-order cone complementarity problems, SIAM Journal on Optimization, vol. 12, pp. 436-460, 2002.

[34] F. Facchinei and J. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.

[35] S. Hayashi, N. Yamashita, and M. Fukushima, A combined smoothing and regularization method for monotone second-order cone complementarity problems, SIAM Journal on Optimization, 15, pp. 593-615, 2005.

[36] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985.

[37] S.-L. Hu and Z.-H. Huang, A note on absolute value equations, Optimization Letters, vol. 4, pp. 417-424, 2010.

[38] S.-L. Hu, Z.-H. Huang, and P. Wang, A nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems, Optimization Methods
and Software, Vol. 24, No. 3, pp. 447-460, 2009.

[39] S.-L. Hu, Z.-H. Huang, and Q. Zhang, A generalized Newton method for absolute value equations associated with second-order cones, Journal of Computational and Applied Mathematics, vol. 235, pp. 1490-1501, 2011.

[40] Z.-H. Huang, Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms, Mathematical Methods of Operations Research, vol. 61, pp. 41-55, 2005.

[41] Z.-H. Huang, J. Han, and Z. Chen, A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problem with a P0 function, Journal of Optimization Theory and Applications, vol. 117, pp. 39-68, 2003.

[42] Z.-H. Huang, Y. Zhang, and W. Wu, A smoothing-type algorithm for solving system of inequalities, Journal of Computational and Applied Mathematics, vol. 220, pp. 355-363, 2008.

[43] X.-Q. Jiang, A smoothing Newton method for solving absolute value equations, Advanced Materials Research, vol. 765-767, pp. 703-708, 2013.

[44] X.-Q. Jiang and Y. Zhang, A smoothing-type algorithm for absolute value equations, Journal of Industrial and Management Optimization, vol. 9, pp. 789-798, 2013.

[45] C. Kanzow, I. Ferenczi, and M. Fukushima, On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity, SIAM Journal on Optimization, vol. 20, pp. 297-
320, 2009.

[46] H. Kato and M. Fukushima, An SQP-type algorithm for nonlinear second-order cone programs, Optimization Letters, vol. 1, pp. 129-144, 2007.

[47] S. Ketabchi and H. Moosaei, Minimum norm solution to the absolute value equation in the convex case, Journal of Optimization Theory and Applications, vol. 154, pp. 1080-1087, 2012.

[48] L.-C. Kong, J. Sun, and N.-H. Xiu, A regularized smoothing Newton method for symmetric cone complementarity problems, SIAM Journal on Optimization, vol. 19, pp. 1028-1047, 2008.

[49] J. Kreimer and R. Y. Rubinstein, Nondifferentiable optimization via smooth approximation: General analytical approach, Annals of Operations Research, vol. 39, pp. 97-119, 1992.

[50] X.-H. Liu and W.-Z. Gu, Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones, Journal of Industrial and Management Optimization,
vol. 6, pp. 363-380, 2010.

[51] M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret, Application of second-order cone programming, Linear Algebra and its Applications, vol. 284, pp. 193-228, 1998.

[52] N. Lu and Z.-H. Huang, Convergence of a non-interior continuation algorithm for the monotone SCCP, Acta Mathematicae Applicatae Sinica (English Series), vol. 26, pp. 543-556, 2010.

[53] N. Lu and Y. Zhang, A smoothing-type algorithm for solving inequalities under the order induced by a symmetric cone, Journal of Inequalities and Applications, Article 2011:4, 2011.

[54] O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications, vol. 36, pp. 43-53, 2007.

[55] O. L. Mangasarian, Absolute value equation solution via concave minimization, Optimization Letters, vol. 1, pp. 3-5, 2007.

[56] O. L. Mangasarian, A generalized Newton method for absolute value equations, Optimization Letters, vol. 3, pp. 101-108, 2009.

[57] O. L. Mangasarian, Knapsack feasibility as an absolute value equation solvable by successive linear programming, Optimization Letters, vol. 3, pp. 161-170, 2009.

[58] O. L. Mangasarian, Primal-dual bilinear programming solution of the absolute value equation, Optimization Letters, vol. 6, pp. 1527-1533, 2012.

[59] O.L. Mangasarian, Absolute value equation solution via dual complementarity, Optimization Letters, vol. 7, pp. 625-630, 2013.

[60] O. L. Mangasarian, Linear complementarity as absolute value equation solution, Optimization Letters, vol. 8, pp. 1529-1534, 2014.

[61] O. L. Mangasarian, Absolute value equation solution via linear programming, Journal of Optimization Theory and Applications, vol. 161, pp. 870-876, 2014.

[62] O. L. Mangasarian and R. R. Meyer, Absolute value equation, Linear Algebra and Its Applications, vol. 419, pp. 359-367, 2006.

[63] X.-H. Miao, W.-M. Hsu, and J.-S. Chen, The solvabilities of three optimization problems associated with second-order cone, submitted manuscript, 2018.

[64] X.-H. Miao, J.-T. Yang, and S.-L. Hu, A generalized Newton method for absolute value equations associated with circular cones, Applied Mathematics and Computation, vol. 269, August, pp. 155-168, 2017.

[65] X.-H. Miao, J.-T. Yang, B. Saheya and J.-S. Chen, A smoothing Newton method for absolute value equation associated with second-order cone, Applied Numerical Mathematics, vol. 120, October, pp. 82-96, 2017.

[66] R. D. C. Monteiro and T. Tsuchiya, Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ-family of directions, Mathematical Programming, vol. 88, pp. 61-83, 2000.

[67] L. Mosheyev and M. Zibulevsky, Penalty-barrier multiplier algorithm for semidefinite programming, Optimization Methods and Software, Vol. 13, pp. 235-261, 2000.

[68] J. J. Moreau, Proximit´e et dualit´e dans un espace Hilbertien, Bulletin de la Soci´et´e Math´ematique de France, vol. 93, pp. 273-299, 1965.

[69] Y. Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming, vol. 103, May, pp. 127-152, 2005.

[70] Y. Nesterov, Excessive gap technique in nonsmooth convex minimization, SIAM Journal on Optimization, vol. 16, pp. 235{249, 2005.

[71] Y. Nesterov, Smoothing Technique and its Applications in Semidefinite Optimization, Mathematical Programming, vol. 110, July, pp. 245-259, 2007.

[72] C.T. Nguyen, B. Saheya, Y.-L Chang and J.-S. Chen, Unified smoothing functions for absolute value equation associated with second-order cone, Applied Numerical Mathematics, vol. 135, January, pp. 206-227, 2019.

[73] B. Saheya, C.T. Nguyen and J.-S. Chen, Neural network based on systematically generated smoothing functions for absolute value equation, to appear in Journal of Applied Mathematics and Computing, DOI: 10.1007/s12190-019-01262-1, 2019.

[74] N. Parikh and S. Boyd, Proximal Algorithms, Foundations and Trends in Optimization, vol. 1, pp. 123-231, 2013.

[75] S.-H. Pan and J.-S. Chen, A proximal-like algorithm using quasi D-function for convex second-order cone programming, Journal of Optimization Theory and Applications, 138, pp. 95-113, 2008.

[76] S.-H. Pan and J.-S. Chen, A class of interior proximal-like algorithms for convex second-order cone programming, SIAM Journal on Optimization, vol. 19, pp. 883-910, 2008.

[77] S.-H. Pan and J.-S. Chen, A damped Gauss-Newton method for the second-order cone complementarity problem, Applied Mathematics and Optimization, vol. 59, pp. 293-318, 2009.

[78] S.-H. Pan and J.-S. Chen, Interior proximal methods and central paths for convex second-order cone programming, Nonlinear Analysis: Theory, Methods and Applications, Vol. 73, No. 9, pp. 3083-3100, 2010.

[79] J. Peng, C. Roos, and T. Terlaky Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities, SIAM Journal on Optimization, vol. 13, pp. 179-203, 2002.

[80] O. A. Prokopyev, On equivalent reformulations for absolute value equations, Computational Optimization and Applications, vol. 44, 363-372, 2009.

[81] L. Qi and D. Sun, Smoothing functions and smoothing Newton method for complementarity and variational inequality problems, Journal Of Optimization Theory And Applications, vol. 113, pp. 121-147, 2002.

[82] L. Qi and J. Sun, A nonsmooth version of Newton’s method, Mathematical Programming, vol. 58, pp. 353-367, 1993.

[83] L. Qi, D. Sun and G. L. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Mathematical Programming, vol. 87, pp. 1-35, 2000.

[84] J. Rohn, A theorem of the alternative for the equation Ax+Bjxj = b, Linear and Multilinear Algebra, vol. 52, pp. 421-426, 2004.

[85] J. Rohn, Solvability of systems of interval linear equations and inequalities, in Linear Optimization Problems with Inexact Data edited by. M. Fiedler, J. Nedoma, J. Ramik, J. Rohn and K. Zimmermann, Springer, pp. 35-77, 2006.

[86] J. Rohn, An algorithm for solving the absolute value equation, Electronic Journal of Linear Algebra, vol. 18, 589-599, 2009.

[87] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

[88] R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Grundlehren der mathematischen Wissenschaften 317, Springer-Verlag, Berlin, 1998.

[89] B. Saheya, C.-H. Yu and J.-S. Chen, Numerical comparisons based on four smoothing functions for absolute value equation, Journal of Applied Mathematics and Computing, DOI: 10.1007/s12190-016-1065-0, 2017.

[90] D. Sun and L. Qi, Solving Variational Inequality Problems via SmoothingNonsmooth Reformulations, Journal of Computational and Applied Mathematics, vol. 129, pp. 37-62, 2001.

[91] M. Teboulle, A Unified Continuous Optimization Framework for Center-Based Clustering Methods, Journal of Machine Learning Research 8, pp. 65-102, 2007.

[92] M. Teboulle, Lecture: First Order Optimization Methods, PGMO Lecture Series, Ecole Polytechnique, Paris, 2017.

[93] T. Tsuchiya, A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, Optimization Methods and Software, vol. 11, pp. 141-182, 1999.

[94] L. Vandenberghe, Optimization Methods for Large-Scale Systems, Lecture notes for EE236C, UCLA, Spring 2016.

[95] S. Voronin, G. Ozkaya, and D. Yoshida, Convolution based smooth approximations to the absolute value function with application to non-smooth regularization, arXiv:1408.6795v2 [math.NA] 1, July 2015.

[96] S. Yamanaka and M. Fukushima, A branch and bound method for the absolute value programs, Optimization, vol. 63, pp. 305{319, 2014.

[97] Yang, Smoothing approximations to nonsmooth optimization problems, The Journal of the Australian Mathematical Society Series B Applied Mathematics, vol.36, pp. 274-285, 1995.

[98] C. Zalinescu, Convex Analysis in General Vector Spaces, World Scientific, July 2002.

[99] L. Zhang, J. Gu and X. Xiao, A class of nonlinear Lagrangians for nonconvex second-order cone programming, Computational Optimization and Applications. Vol. 49, pp. 61-99, 2011.

[100] J. G. Zhu, H. W. Liu, and X. L. Li, A regularized smoothing-type algorithm for solving a system of inequalities with a P0-function, Journal of Computational and Applied Mathematics, vol. 233, pp. 2611-2619, 2010.