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. BaoP. 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. ChowJ. 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. GuoG. 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. KelloggT. 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. LinB. 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. LiuB. 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. XuB. 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. BaoP. 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. ChowJ. 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. GuoG. 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. KelloggT. 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. LinB. 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. LiuB. 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. XuB. 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

Table 1.  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)
Table 2.  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]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[2]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[3]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[4]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[5]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[6]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[7]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[8]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[9]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[10]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[11]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[12]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[13]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[14]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[15]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[16]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[17]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[18]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[19]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (83)
  • HTML views (419)
  • Cited by (1)

Other articles
by authors

[Back to Top]