American Institute of Mathematical Sciences

January  2017, 13(1): 81-92. doi: 10.3934/jimo.2016005

Homotopy method for a class of multiobjective optimization problems with equilibrium constraints

 1 Department of Mathematics, Jilin University, Changchun 130012, China 2 Institute of Applied Mathematics, Changchun, University of Technology, Changchun 130012, China

*Corresponding author: Qinghuai Liu

Received  December 2014 Revised  December 2015 Published  March 2016

Fund Project: The first author is supported by (Grant No.51278065) and the Jilin Province Natural Science Foundation (Grant No.20130101061 JC.)

In this paper, we present a combined homotopy interior point method for solving multiobjective programs with equilibrium constraints. Under suitable conditions, we prove the existence and convergence of a smooth homotopy path from almost any interior point to a solution of the K-K-T system. Numerical results are presented to show the effectiveness of this algorithm.

Citation: Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005
References:
 [1] E. L. Allgower and K. Georg, Numerical Continuation Methods: An Introduction, Springer-Verlag, Berlin-New York, 1990. doi: 10.1007/978-3-642-61257-2. Google Scholar [2] T. Q. Bao, P. Gupta and B. S. Mordukhovich, Necessary conditions in multiobjective optimization with equilibrium constraints, J. Optim. Theory Appl., 135 (2007), 179-203. doi: 10.1007/s10957-007-9209-x. Google Scholar [3] S. N. Chow, J. Mallet-Paret and J. A. Yorke, Finding zeros of maps: Homotopy methods that are constructive with probability one, Math. Compu., 13 (1978), 887-899. doi: 10.1090/S0025-5718-1978-0492046-9. Google Scholar [4] S. Dempe, Annotated bibliographa on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), 333-359. doi: 10.1080/0233193031000149894. Google Scholar [5] X. N. Fan and Q. L. Yan, Homotopy method for solving ball-constrained variational inequalities, Nonlinear Analysis, 74 (2011), 1539-1544. doi: 10.1016/j.na.2010.09.041. Google Scholar [6] M. Fukushima and P. Tseng, An Implementable Active-Set Algorithm for Computing a B-Stationary Point of the Mathematical Program with Linear Complementarity Constraints, Manuscript, Department of Applied Mathematics and Physics, Graduate School of Informations, Kyoto University, Japan, 1999.Google Scholar [7] M. Fukushima and P. Tseng, An Implementable active-set algorithm for computing a b-stationary point of mathematical program with linear complemetarity constraints, SIAM J. Optim., 12 (2002), 724-739. doi: 10.1137/S1052623499363232. Google Scholar [8] L. Guo and G. H. Lin, Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations, Journal of Industrial and Management Optimization, 9 (2013), 305-322. doi: 10.3934/jimo.2013.9.305. Google Scholar [9] L. Guo, G. H. Lin and J. J. Ye, Stability analysis for parametric mathematical programs with geometric constraints and its applications, SIAM Journal on Optimization, 22 (2012), 1151-1176. doi: 10.1137/120868657. Google Scholar [10] P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and non-linear complementarity problem: A survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220. doi: 10.1007/BF01582255. Google Scholar [11] R. B. Kellogg, T. Y. Li and J. Yorke, A constructive proof the Brouwer fixed-point theorem and computational results, SIAM J. Numer. Anal., 13 (1976), 473-483. doi: 10.1137/0713041. Google Scholar [12] M. Ko$\overset{''}{\mathop{\text{c}}}\,$vara and J. V. Outrata, Optimization problems with equilibrium constraints and their numerical solution, Math. Program. Ser. B, 101 (2004), 119-149. doi: 10.1007/s10107-004-0539-2. Google Scholar [13] J. M. Li, Combined Homotopy Interior-Point Method for Solving Mathematical Programs with Equilibrium Constraints, Ph. D. thesis, Ji Lin University, 2007.Google Scholar [14] Z. H. Lin, B. Yu and D. L. Zhu, A continuation method for solving fixed points of self-mappings in general nonconvex sets, Nonlinear Analysis, 52 (2003), 905-915. doi: 10.1016/S0362-546X(02)00140-2. Google Scholar [15] X. W. Liu and J. Sun, Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints, Math. Program. Ser. B, 101 (2004), 231-261. doi: 10.1007/s10107-004-0543-6. Google Scholar [16] Q. H. Liu, B. Yu and G. C. Feng, An interior point path-following method for convex programming with quasi normal cone condition, Advances in Mathematics, 29 (2000), 281-282. Google Scholar [17] Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, 1996. doi: 10.1017/CBO9780511983658. Google Scholar [18] M. M. M$\overset{''}{\mathop{\text{a}}}\,$kel$\overset{''}{\mathop{\text{a}}}\,$ and P. Neittaanm$\overset{''}{\mathop{\text{a}}}\,$ki, Nonsmooth Optimization: Analysis And Algorithms with Applications to Optimal Control, World Scientific Publishing Co. Pte. Ltd., 1992.Google Scholar [19] O. L. Mangasarian, Nonlinear Programming, McGraw-Hill Book Company, New York, 1969; Japanese Edition, 1971; SIAM Classics in Applied Mathematics, 10, Philadelphia, 1994. doi: 10.1137/1.9781611971255. Google Scholar [20] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, Ⅱ: Applications, Grundlehren Series (Fundamental Principles of Mathematical Sciences), Springer, Berlin, 2006. Google Scholar [21] B. S. Mordukhovich, Multiobjective optimization problems with equilibrium constraints, Math. Program. Ser. B, 117 (2009), 331-354. doi: 10.1007/s10107-007-0172-y. Google Scholar [22] G. L. Naber, Topological Methods in Euclidean Spaces, Cambridge University Press, Cambridge, UK, 1980. Google Scholar [23] S. Smale, A convergent process of price adjustment and global Newton methods, J. Math. Econom., 3 (1976), 107-120. doi: 10.1016/0304-4068(76)90019-7. Google Scholar [24] W. Song and G. M. Yao, Homotopy method for a general multiobjective programming problem, Journal of Optimization Theory and Applications, 138 (2008), 139-153. doi: 10.1007/s10957-008-9366-6. Google Scholar [25] Q. Xu, B. Yu and G. C. Feng, Homotopy method for solving variational inequalities in unbounded sets, Journal of Global Optimization, 31 (2005), 121-131. doi: 10.1007/s10898-004-4272-4. Google Scholar [26] Q. Xu and B. Yu, Solving the Karush-Kuhn-Tucker system of a nonconvex programming problem on an unbounded sets, Nonlinear Analysis, 70 (2009), 757-763. doi: 10.1016/j.na.2008.01.008. Google Scholar [27] J. J. Ye and Q. J. Zhu, Multiobjective optimization problem with variational inequality constraints, Math. Program. Ser. A, 96 (2003), 139-160. doi: 10.1007/s10107-002-0365-3. Google Scholar [28] Z. S. Zhang, Introduction to Differential Topology, Beijing University Press, Beijing, China, 2002.Google Scholar [29] X. Zhao, S. G. Zhang and Q. H. Liu, Homotopy interior-point method for a general multiobjective programming problem Journal of Applied Mathematics, (2012), Art. ID 497345, 12pp. doi: 10.1155/2012/497345. Google Scholar [30] Z. Y. Zhou and B. Yu, A smoothing homotopy method for variational inequality problems on polyhedral convex sets, J. Glob Optim., 58 (2013), 151-168. doi: 10.1007/s10898-013-0033-6. Google Scholar

show all references

References:
 [1] E. L. Allgower and K. Georg, Numerical Continuation Methods: An Introduction, Springer-Verlag, Berlin-New York, 1990. doi: 10.1007/978-3-642-61257-2. Google Scholar [2] T. Q. Bao, P. Gupta and B. S. Mordukhovich, Necessary conditions in multiobjective optimization with equilibrium constraints, J. Optim. Theory Appl., 135 (2007), 179-203. doi: 10.1007/s10957-007-9209-x. Google Scholar [3] S. N. Chow, J. Mallet-Paret and J. A. Yorke, Finding zeros of maps: Homotopy methods that are constructive with probability one, Math. Compu., 13 (1978), 887-899. doi: 10.1090/S0025-5718-1978-0492046-9. Google Scholar [4] S. Dempe, Annotated bibliographa on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), 333-359. doi: 10.1080/0233193031000149894. Google Scholar [5] X. N. Fan and Q. L. Yan, Homotopy method for solving ball-constrained variational inequalities, Nonlinear Analysis, 74 (2011), 1539-1544. doi: 10.1016/j.na.2010.09.041. Google Scholar [6] M. Fukushima and P. Tseng, An Implementable Active-Set Algorithm for Computing a B-Stationary Point of the Mathematical Program with Linear Complementarity Constraints, Manuscript, Department of Applied Mathematics and Physics, Graduate School of Informations, Kyoto University, Japan, 1999.Google Scholar [7] M. Fukushima and P. Tseng, An Implementable active-set algorithm for computing a b-stationary point of mathematical program with linear complemetarity constraints, SIAM J. Optim., 12 (2002), 724-739. doi: 10.1137/S1052623499363232. Google Scholar [8] L. Guo and G. H. Lin, Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations, Journal of Industrial and Management Optimization, 9 (2013), 305-322. doi: 10.3934/jimo.2013.9.305. Google Scholar [9] L. Guo, G. H. Lin and J. J. Ye, Stability analysis for parametric mathematical programs with geometric constraints and its applications, SIAM Journal on Optimization, 22 (2012), 1151-1176. doi: 10.1137/120868657. Google Scholar [10] P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and non-linear complementarity problem: A survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220. doi: 10.1007/BF01582255. Google Scholar [11] R. B. Kellogg, T. Y. Li and J. Yorke, A constructive proof the Brouwer fixed-point theorem and computational results, SIAM J. Numer. Anal., 13 (1976), 473-483. doi: 10.1137/0713041. Google Scholar [12] M. Ko$\overset{''}{\mathop{\text{c}}}\,$vara and J. V. Outrata, Optimization problems with equilibrium constraints and their numerical solution, Math. Program. Ser. B, 101 (2004), 119-149. doi: 10.1007/s10107-004-0539-2. Google Scholar [13] J. M. Li, Combined Homotopy Interior-Point Method for Solving Mathematical Programs with Equilibrium Constraints, Ph. D. thesis, Ji Lin University, 2007.Google Scholar [14] Z. H. Lin, B. Yu and D. L. Zhu, A continuation method for solving fixed points of self-mappings in general nonconvex sets, Nonlinear Analysis, 52 (2003), 905-915. doi: 10.1016/S0362-546X(02)00140-2. Google Scholar [15] X. W. Liu and J. Sun, Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints, Math. Program. Ser. B, 101 (2004), 231-261. doi: 10.1007/s10107-004-0543-6. Google Scholar [16] Q. H. Liu, B. Yu and G. C. Feng, An interior point path-following method for convex programming with quasi normal cone condition, Advances in Mathematics, 29 (2000), 281-282. Google Scholar [17] Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, 1996. doi: 10.1017/CBO9780511983658. Google Scholar [18] M. M. M$\overset{''}{\mathop{\text{a}}}\,$kel$\overset{''}{\mathop{\text{a}}}\,$ and P. Neittaanm$\overset{''}{\mathop{\text{a}}}\,$ki, Nonsmooth Optimization: Analysis And Algorithms with Applications to Optimal Control, World Scientific Publishing Co. Pte. Ltd., 1992.Google Scholar [19] O. L. Mangasarian, Nonlinear Programming, McGraw-Hill Book Company, New York, 1969; Japanese Edition, 1971; SIAM Classics in Applied Mathematics, 10, Philadelphia, 1994. doi: 10.1137/1.9781611971255. Google Scholar [20] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, Ⅱ: Applications, Grundlehren Series (Fundamental Principles of Mathematical Sciences), Springer, Berlin, 2006. Google Scholar [21] B. S. Mordukhovich, Multiobjective optimization problems with equilibrium constraints, Math. Program. Ser. B, 117 (2009), 331-354. doi: 10.1007/s10107-007-0172-y. Google Scholar [22] G. L. Naber, Topological Methods in Euclidean Spaces, Cambridge University Press, Cambridge, UK, 1980. Google Scholar [23] S. Smale, A convergent process of price adjustment and global Newton methods, J. Math. Econom., 3 (1976), 107-120. doi: 10.1016/0304-4068(76)90019-7. Google Scholar [24] W. Song and G. M. Yao, Homotopy method for a general multiobjective programming problem, Journal of Optimization Theory and Applications, 138 (2008), 139-153. doi: 10.1007/s10957-008-9366-6. Google Scholar [25] Q. Xu, B. Yu and G. C. Feng, Homotopy method for solving variational inequalities in unbounded sets, Journal of Global Optimization, 31 (2005), 121-131. doi: 10.1007/s10898-004-4272-4. Google Scholar [26] Q. Xu and B. Yu, Solving the Karush-Kuhn-Tucker system of a nonconvex programming problem on an unbounded sets, Nonlinear Analysis, 70 (2009), 757-763. doi: 10.1016/j.na.2008.01.008. Google Scholar [27] J. J. Ye and Q. J. Zhu, Multiobjective optimization problem with variational inequality constraints, Math. Program. Ser. A, 96 (2003), 139-160. doi: 10.1007/s10107-002-0365-3. Google Scholar [28] Z. S. Zhang, Introduction to Differential Topology, Beijing University Press, Beijing, China, 2002.Google Scholar [29] X. Zhao, S. G. Zhang and Q. H. Liu, Homotopy interior-point method for a general multiobjective programming problem Journal of Applied Mathematics, (2012), Art. ID 497345, 12pp. doi: 10.1155/2012/497345. Google Scholar [30] Z. Y. Zhou and B. Yu, A smoothing homotopy method for variational inequality problems on polyhedral convex sets, J. Glob Optim., 58 (2013), 151-168. doi: 10.1007/s10898-013-0033-6. Google Scholar
The numerical results of Example1.
 $(x_1^{(0)}, x_2^{(0)}, y_1^{(0)}, y_2^{(0)}, t^{(0)})$ $(x_1^*, x_2^*, y_1^*, y_2^*, t^*)$ $(f_1^*, f_2^*)$ (3.3750, 9.2500, -6.2500, -0.3750, 1) (0.2230, -0.0470, -1.8319, 0.3554, 0.0001) (2.2732, 0.0373) (2.0625, 7.3750, -5.3750, -0.0625, 1) (0.2231, -0.0473, -1.8318, 0.3554, 0.0001) (2.2735, 0.0372) (4.8750, 13.4500, -9.6500, -1.0750, 1) (-4.2060, 1.0421, 2.9579, -4.9790, 0.0001) (61.9144, 2.2810) (4.6875, 12.6250, -8.875, -0.9375, 1) (-4.2059, 1.0423, 2.9577, -4.9788, 0.0001) (61.9122, 2.2811)
 $(x_1^{(0)}, x_2^{(0)}, y_1^{(0)}, y_2^{(0)}, t^{(0)})$ $(x_1^*, x_2^*, y_1^*, y_2^*, t^*)$ $(f_1^*, f_2^*)$ (3.3750, 9.2500, -6.2500, -0.3750, 1) (0.2230, -0.0470, -1.8319, 0.3554, 0.0001) (2.2732, 0.0373) (2.0625, 7.3750, -5.3750, -0.0625, 1) (0.2231, -0.0473, -1.8318, 0.3554, 0.0001) (2.2735, 0.0372) (4.8750, 13.4500, -9.6500, -1.0750, 1) (-4.2060, 1.0421, 2.9579, -4.9790, 0.0001) (61.9144, 2.2810) (4.6875, 12.6250, -8.875, -0.9375, 1) (-4.2059, 1.0423, 2.9577, -4.9788, 0.0001) (61.9122, 2.2811)
The numerical results of Example2.
 $(x_1^{(0)}, x_2^{(0)}, y_1^{(0)}, y_2^{(0)}, t^{(0)})$ $(x_1^*, x_2^*, y_1^*, y_2^*, t^*)$ $(f_1^*, f_2^*)$ (0, 3.1380, 0.9653, -2.0545, 1) (-2.2955, -0.7998, 1.1667, -2.6666, 0.0001) (9.4784, 0.9151) (3.5326, 0, 0.8932, -1.8410, 1) (-2.2954, -0.7999, 1.1666, -2.6666, 0.0001) (9.4773, 0.9154) (4.2426, 0, 0.7826, -1.5217, 0.5, 1) (-2.9356, -1.1234, 1.2501, -2.9256, 0.0001) (12.0080, 1.2622) (7.4907, 0, 0.8333, -1.6667, 0.4, 1) (-2.9356, -1.1234, 1.2501, -2.9254, 0.0001) (12.0072, 1.2622)
 $(x_1^{(0)}, x_2^{(0)}, y_1^{(0)}, y_2^{(0)}, t^{(0)})$ $(x_1^*, x_2^*, y_1^*, y_2^*, t^*)$ $(f_1^*, f_2^*)$ (0, 3.1380, 0.9653, -2.0545, 1) (-2.2955, -0.7998, 1.1667, -2.6666, 0.0001) (9.4784, 0.9151) (3.5326, 0, 0.8932, -1.8410, 1) (-2.2954, -0.7999, 1.1666, -2.6666, 0.0001) (9.4773, 0.9154) (4.2426, 0, 0.7826, -1.5217, 0.5, 1) (-2.9356, -1.1234, 1.2501, -2.9256, 0.0001) (12.0080, 1.2622) (7.4907, 0, 0.8333, -1.6667, 0.4, 1) (-2.9356, -1.1234, 1.2501, -2.9254, 0.0001) (12.0072, 1.2622)
 [1] Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123 [2] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 [3] Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033 [4] Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 [5] M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407 [6] Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733 [7] Zhengyong Zhou, Bo Yu. A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 977-989. doi: 10.3934/jimo.2011.7.977 [8] Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269 [9] Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157 [10] Giancarlo Bigi. Componentwise versus global approaches to nonsmooth multiobjective optimization. Journal of Industrial & Management Optimization, 2005, 1 (1) : 21-32. doi: 10.3934/jimo.2005.1.21 [11] Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092 [12] M. S. Lee, B. S. Goh, H. G. Harno, K. H. Lim. On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 315-326. doi: 10.3934/naco.2018020 [13] Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015 [14] Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086 [15] Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial & Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717 [16] Figen Özpinar, Fethi Bin Muhammad Belgacem. The discrete homotopy perturbation Sumudu transform method for solving partial difference equations. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 615-624. doi: 10.3934/dcdss.2019039 [17] Peiyu Li. Solving normalized stationary points of a class of equilibrium problem with equilibrium constraints. Journal of Industrial & Management Optimization, 2018, 14 (2) : 637-646. doi: 10.3934/jimo.2017065 [18] K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026 [19] Qiu-Sheng Qiu. Optimality conditions for vector equilibrium problems with constraints. Journal of Industrial & Management Optimization, 2009, 5 (4) : 783-790. doi: 10.3934/jimo.2009.5.783 [20] Vadim Azhmyakov. An approach to controlled mechanical systems based on the multiobjective optimization technique. Journal of Industrial & Management Optimization, 2008, 4 (4) : 697-712. doi: 10.3934/jimo.2008.4.697

2018 Impact Factor: 1.025

Tools

Article outline

Figures and Tables