-
Previous Article
A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty
- JIMO Home
- This Issue
-
Next Article
The stable duality of DC programs for composite convex functions
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 |
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.
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. |
[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. |
[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. |
[4] |
S. Dempe,
Annotated bibliographa on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), 333-359.
doi: 10.1080/0233193031000149894. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[20] |
B. S. Mordukhovich,
Variational Analysis and Generalized Differentiation, Ⅱ: Applications, Grundlehren Series (Fundamental Principles of Mathematical Sciences), Springer, Berlin, 2006. |
[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. |
[22] |
G. L. Naber,
Topological Methods in Euclidean Spaces, Cambridge University Press, Cambridge, UK, 1980. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
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. |
[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. |
[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. |
[4] |
S. Dempe,
Annotated bibliographa on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), 333-359.
doi: 10.1080/0233193031000149894. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[20] |
B. S. Mordukhovich,
Variational Analysis and Generalized Differentiation, Ⅱ: Applications, Grundlehren Series (Fundamental Principles of Mathematical Sciences), Springer, Berlin, 2006. |
[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. |
[22] |
G. L. Naber,
Topological Methods in Euclidean Spaces, Cambridge University Press, Cambridge, UK, 1980. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
(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) |
(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) |
| ||
(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) |
| ||
(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] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[2] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[3] |
Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006 |
[4] |
David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 |
[5] |
Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 |
[6] |
Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233 |
[7] |
Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 |
[8] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[9] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[10] |
Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397 |
[11] |
Mansour Shrahili, Ravi Shanker Dubey, Ahmed Shafay. Inclusion of fading memory to Banister model of changes in physical condition. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 881-888. doi: 10.3934/dcdss.2020051 |
[12] |
Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223 |
[13] |
Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 |
[14] |
Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 |
[15] |
Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018 |
[16] |
Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002 |
[17] |
Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 |
[18] |
Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149 |
[19] |
Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825 |
[20] |
Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]