Globally convergent homotopy method for designing piecewise linear deterministic contractual function

Previous Article
Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints
JIMO Home
This Issue
Next Article
Cyber-physical logistics system-based vehicle routing optimization

July 2014, 10(3): 717-741. doi: 10.3934/jimo.2014.10.717

Globally convergent homotopy method for designing piecewise linear deterministic contractual function

Zhichuan Zhu ^1, , Bo Yu ^2, and Li Yang ^3,

1.	School of Mathematical Sciences, Dalian University of Technology, Dalian, Liaoning 116024, China
2.	School of Mathematical Science, Dalian University of Technology, Dalian, Liaoning 116024
3.	Faculty of Management and Economics, Dalian University of Technology, Dalian, Liaoning, 116024, China

Received November 2012 Revised March 2013 Published November 2013

Abstract
Related Papers

In this paper, to design a piecewise linear contractual function, we consider to solve the single-level nonconvex programming with integral operator which is equivalent to the principal-agent bilevel programming model with continuous distribution. A modified constraint shifting homotopy method for solving the Karush-Kuhn-Tucker system of the discrete nonconvex programming is proposed and the global convergence from any initial point in shifted feasible set is proven under some mild conditions. A simple homotopy path tracing algorithm is given and is implemented in Matlab. For some typical risk averse utility functions and the typical distribution functions which simultaneously satisfy monotone likelihood ratio condition and convexity of the distribution function condition, some numerical tests to design the piecewise linear contract are done by our homotopy method as well as by using fmincon in Matlab, LOQO and MINOS and, as a comparison, the piecewise constant contracts are also designed by solving the single-level nonconvex programming which is equivalent to the principal-agent bilevel programming model with corresponding discrete distributions. Numerical tests show that: to design a piecewise linear contract, which is much better than a piecewise constant contract, it needs only to solve a much lower dimensional optimization problem and hence needs much less computing time. Numerical experiences also show that the modified constraint shifting homotopy method is feasible and robust.

Keywords: nonconvex programming., homotopy method, bilevel programming, Principal-agent model, piecewise linear contractual function.

Mathematics Subject Classification: Primary: 91-08, 90C30, 91B4.

Citation: Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial and Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717

References:

[1]	J. A. Mirrlees, The theory of moral hazard and unobservable behavior: Part I, Mimeo, 1975, Nuffild College, Oxford. Reprinted in Rev. Econ. Stud., 66 (1999), 3-21.
[2]	J. A. Mirrlees, The Implication of Moral Hazard for Optimal Insurance, Seminar Given at Conference Held in Honor of Karl Borch. Mimeo, 1979, Bergen, Norway.
[3]	W. P. Rogerson, The first-order approach to principal-agent problems, Economica, 53 (1985), 1357-1367. doi: 10.2307/1913212.
[4]	M. LiCalzi and S. Spaeter, Distributions for the first-order approach to principal-agent problems, Economic Theory, 21 (2003), 167-173. doi: 10.1007/s00199-001-0250-y.
[5]	S. Shao and Q. Xu, Distributions for the validity of the first-order approach to principal-agent problems, Journal of Fudan University, 48 (2009), 277-280.
[6]	S. J. Grossman and O. D. Hart, An Analysis of the principal-agent problem, Econometrica, 51 (1983), 7-45. doi: 10.2307/1912246.
[7]	I. Jewitt, Justifying the first-order approach to principal-agent problems, Economica, 56 (1988), 1177-1190. doi: 10.2307/1911363.
[8]	B. Sinclair-Desgagné, The first-order approach to multi-signal principal-agent problems, Econometrica, 62 (1994), 459-465. doi: 10.2307/2951619.
[9]	E. Alvi, First-order approach to principal-agent problems: A generalization, The Geneva Risk and Insurance Review, 22 (1997), 59-65. doi: 10.1023/A:1008663531322.
[10]	John R. Conlon, Two new conditions supporting the first-order approach to multisignal principal-agent problems, Econometrica, 77 (2009), 249-278. doi: 10.3982/ECTA6688.
[11]	S. Koehne, The first-order approach to moral hazard problems with hidden saving, Working Paper, (2010), University of Mannheim, Mannheim, Germany. doi: 10.2139/ssrn.1444780.
[12]	R. B. Myerson, Optimal coordination mechanisms in generalized principal-agent problems, J. Math. Econ., 10 (1982), 67-81. doi: 10.1016/0304-4068(82)90006-4.
[13]	E. S. Prescott, A primer on Moral-Hazard models, Federal Reserve Bank of Richmond Quanterly Review, 85 (1999), 47-77.
[14]	E. S. Prescott, Computing solutions to moral-hazard programs using the Dantzig-Wolfe decomposition algorithm, J. Econ. Dynam. Control, 28 (2004), 777-800. doi: 10.1016/S0165-1889(03)00053-8.
[15]	C. L. Su and K. L. Judd, Computation of moral-hazard problems, Working Paper, (2007), CMS-EMS, Kellogg School of Management, Northwestern University, Evanston, llinois, USA.
[16]	R. B. Kellogg, T. Y. Li and J. A. Yorke, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Num. Anal., 13 (1976), 473-483. doi: 10.1137/0713041.
[17]	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.
[18]	S. N. Chow, J. Mallet-Paret and J. A. Yorke, Finding zeros of maps: Homotopy methods that are constructive with probability one, Math. Comput., 32 (1978), 887-899. doi: 10.1090/S0025-5718-1978-0492046-9.
[19]	G. C. Feng and B. Yu, Combined homotopy interior point method for nonlinear programming problems, Advances in Numerical Mathematics; Proceeding of the second Japan-China Seminar on Numerical Mathematics (Eds. H. Fujita and M. Yamaguti), Tokyo, 1994, 9-16, Lecture Notes in Numerical and Applied Analysis, 14, Kinokuniya, Tokyo, Japan, 1995.
[20]	G. C. Feng, Z. H. Lin and B. Yu, Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Anal., 32 (1998), 761-768. doi: 10.1016/S0362-546X(97)00516-6.
[21]	Y. F. Shang and B. Yu, Boundary moving combined homotopy method for nonconvex nonlinear programming and its convergence, (Chinese), J. Jilin Univ. Sci., 44 (2006), 357-361.
[22]	Z. H. Lin, Y. Li and B. Yu, A combined homotopy interior point method for general nonlinear programming problems, Appl. Math. Comput., 80 (1996), 209-224. doi: 10.1016/0096-3003(95)00295-2.
[23]	L. Yang, B. Yu and Q. Xu, A constraint shifting homotopy method for general nonlinear programming, Optim., 2012. doi: 10.1080/02331934.2012.668189.
[24]	L. Qi and Z. Wei, On the constant positive linear dependence condition and its application to SQP methods, SIAM J. Optim., 10 (2000), 963-981.
[25]	L. T. Watson, S. C. Billups and A. P. Morgan, Algorithm 652 hompack: A suite of codes for globally convergent homotopy algorithms, ACM Trans. Math. Softw., 13 (1987), 281-310. doi: 10.1145/29380.214343.
[26]	E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods, 2nd edition, SIAM Society for Industrial and Applied Mathematics, Philadelphia, America, 2003. doi: 10.1137/1.9780898719154.

show all references

References:

[1]	J. A. Mirrlees, The theory of moral hazard and unobservable behavior: Part I, Mimeo, 1975, Nuffild College, Oxford. Reprinted in Rev. Econ. Stud., 66 (1999), 3-21.
[2]	J. A. Mirrlees, The Implication of Moral Hazard for Optimal Insurance, Seminar Given at Conference Held in Honor of Karl Borch. Mimeo, 1979, Bergen, Norway.
[3]	W. P. Rogerson, The first-order approach to principal-agent problems, Economica, 53 (1985), 1357-1367. doi: 10.2307/1913212.
[4]	M. LiCalzi and S. Spaeter, Distributions for the first-order approach to principal-agent problems, Economic Theory, 21 (2003), 167-173. doi: 10.1007/s00199-001-0250-y.
[5]	S. Shao and Q. Xu, Distributions for the validity of the first-order approach to principal-agent problems, Journal of Fudan University, 48 (2009), 277-280.
[6]	S. J. Grossman and O. D. Hart, An Analysis of the principal-agent problem, Econometrica, 51 (1983), 7-45. doi: 10.2307/1912246.
[7]	I. Jewitt, Justifying the first-order approach to principal-agent problems, Economica, 56 (1988), 1177-1190. doi: 10.2307/1911363.
[8]	B. Sinclair-Desgagné, The first-order approach to multi-signal principal-agent problems, Econometrica, 62 (1994), 459-465. doi: 10.2307/2951619.
[9]	E. Alvi, First-order approach to principal-agent problems: A generalization, The Geneva Risk and Insurance Review, 22 (1997), 59-65. doi: 10.1023/A:1008663531322.
[10]	John R. Conlon, Two new conditions supporting the first-order approach to multisignal principal-agent problems, Econometrica, 77 (2009), 249-278. doi: 10.3982/ECTA6688.
[11]	S. Koehne, The first-order approach to moral hazard problems with hidden saving, Working Paper, (2010), University of Mannheim, Mannheim, Germany. doi: 10.2139/ssrn.1444780.
[12]	R. B. Myerson, Optimal coordination mechanisms in generalized principal-agent problems, J. Math. Econ., 10 (1982), 67-81. doi: 10.1016/0304-4068(82)90006-4.
[13]	E. S. Prescott, A primer on Moral-Hazard models, Federal Reserve Bank of Richmond Quanterly Review, 85 (1999), 47-77.
[14]	E. S. Prescott, Computing solutions to moral-hazard programs using the Dantzig-Wolfe decomposition algorithm, J. Econ. Dynam. Control, 28 (2004), 777-800. doi: 10.1016/S0165-1889(03)00053-8.
[15]	C. L. Su and K. L. Judd, Computation of moral-hazard problems, Working Paper, (2007), CMS-EMS, Kellogg School of Management, Northwestern University, Evanston, llinois, USA.
[16]	R. B. Kellogg, T. Y. Li and J. A. Yorke, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Num. Anal., 13 (1976), 473-483. doi: 10.1137/0713041.
[17]	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.
[18]	S. N. Chow, J. Mallet-Paret and J. A. Yorke, Finding zeros of maps: Homotopy methods that are constructive with probability one, Math. Comput., 32 (1978), 887-899. doi: 10.1090/S0025-5718-1978-0492046-9.
[19]	G. C. Feng and B. Yu, Combined homotopy interior point method for nonlinear programming problems, Advances in Numerical Mathematics; Proceeding of the second Japan-China Seminar on Numerical Mathematics (Eds. H. Fujita and M. Yamaguti), Tokyo, 1994, 9-16, Lecture Notes in Numerical and Applied Analysis, 14, Kinokuniya, Tokyo, Japan, 1995.
[20]	G. C. Feng, Z. H. Lin and B. Yu, Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Anal., 32 (1998), 761-768. doi: 10.1016/S0362-546X(97)00516-6.
[21]	Y. F. Shang and B. Yu, Boundary moving combined homotopy method for nonconvex nonlinear programming and its convergence, (Chinese), J. Jilin Univ. Sci., 44 (2006), 357-361.
[22]	Z. H. Lin, Y. Li and B. Yu, A combined homotopy interior point method for general nonlinear programming problems, Appl. Math. Comput., 80 (1996), 209-224. doi: 10.1016/0096-3003(95)00295-2.
[23]	L. Yang, B. Yu and Q. Xu, A constraint shifting homotopy method for general nonlinear programming, Optim., 2012. doi: 10.1080/02331934.2012.668189.
[24]	L. Qi and Z. Wei, On the constant positive linear dependence condition and its application to SQP methods, SIAM J. Optim., 10 (2000), 963-981.
[25]	L. T. Watson, S. C. Billups and A. P. Morgan, Algorithm 652 hompack: A suite of codes for globally convergent homotopy algorithms, ACM Trans. Math. Softw., 13 (1987), 281-310. doi: 10.1145/29380.214343.
[26]	E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods, 2nd edition, SIAM Society for Industrial and Applied Mathematics, Philadelphia, America, 2003. doi: 10.1137/1.9780898719154.

[1]	Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529
[2]	Chong Lai, Lishan Liu, Rui Li. The optimal solution to a principal-agent problem with unknown agent ability. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2579-2605. doi: 10.3934/jimo.2020084
[3]	Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[4]	Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[5]	Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[6]	Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[7]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[8]	Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[9]	Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[10]	Behrouz Kheirfam, Kamal mirnia. Multi-parametric sensitivity analysis in piecewise linear fractional programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 343-351. doi: 10.3934/jimo.2008.4.343
[11]	Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete and Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33
[12]	Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[13]	Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[14]	Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial and Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[15]	Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[16]	Behrouz Kheirfam. Multi-parametric sensitivity analysis of the constraint matrix in piecewise linear fractional programming. Journal of Industrial and Management Optimization, 2010, 6 (2) : 347-361. doi: 10.3934/jimo.2010.6.347
[17]	Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[18]	Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3209-3221. doi: 10.3934/jimo.2020114
[19]	Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049
[20]	Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Zhichuan Zhu Bo Yu Li Yang
on Google Scholar
Zhichuan Zhu Bo Yu Li Yang

[Back to Top]