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

Globally convergent homotopy method for designing piecewise linear deterministic contractual function

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

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.
Citation: 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
References:
[1]

J. A. Mirrlees, The theory of moral hazard and unobservable behavior: Part I,, Mimeo, 66 (1999), 3. Google Scholar

[2]

J. A. Mirrlees, The Implication of Moral Hazard for Optimal Insurance,, Seminar Given at Conference Held in Honor of Karl Borch. Mimeo, (1979). Google Scholar

[3]

W. P. Rogerson, The first-order approach to principal-agent problems,, Economica, 53 (1985), 1357. doi: 10.2307/1913212. Google Scholar

[4]

M. LiCalzi and S. Spaeter, Distributions for the first-order approach to principal-agent problems,, Economic Theory, 21 (2003), 167. doi: 10.1007/s00199-001-0250-y. Google Scholar

[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. Google Scholar

[6]

S. J. Grossman and O. D. Hart, An Analysis of the principal-agent problem,, Econometrica, 51 (1983), 7. doi: 10.2307/1912246. Google Scholar

[7]

I. Jewitt, Justifying the first-order approach to principal-agent problems,, Economica, 56 (1988), 1177. doi: 10.2307/1911363. Google Scholar

[8]

B. Sinclair-Desgagné, The first-order approach to multi-signal principal-agent problems,, Econometrica, 62 (1994), 459. doi: 10.2307/2951619. Google Scholar

[9]

E. Alvi, First-order approach to principal-agent problems: A generalization,, The Geneva Risk and Insurance Review, 22 (1997), 59. doi: 10.1023/A:1008663531322. Google Scholar

[10]

John R. Conlon, Two new conditions supporting the first-order approach to multisignal principal-agent problems,, Econometrica, 77 (2009), 249. doi: 10.3982/ECTA6688. Google Scholar

[11]

S. Koehne, The first-order approach to moral hazard problems with hidden saving,, Working Paper, (2010). doi: 10.2139/ssrn.1444780. Google Scholar

[12]

R. B. Myerson, Optimal coordination mechanisms in generalized principal-agent problems,, J. Math. Econ., 10 (1982), 67. doi: 10.1016/0304-4068(82)90006-4. Google Scholar

[13]

E. S. Prescott, A primer on Moral-Hazard models,, Federal Reserve Bank of Richmond Quanterly Review, 85 (1999), 47. Google Scholar

[14]

E. S. Prescott, Computing solutions to moral-hazard programs using the Dantzig-Wolfe decomposition algorithm,, J. Econ. Dynam. Control, 28 (2004), 777. doi: 10.1016/S0165-1889(03)00053-8. Google Scholar

[15]

C. L. Su and K. L. Judd, Computation of moral-hazard problems,, Working Paper, (2007). Google Scholar

[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. doi: 10.1137/0713041. Google Scholar

[17]

S. Smale, A convergent process of price adjustment and global newton methods,, J. Math. Econom., 3 (1976), 107. doi: 10.1016/0304-4068(76)90019-7. Google Scholar

[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. doi: 10.1090/S0025-5718-1978-0492046-9. Google Scholar

[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), (1994), 9. Google Scholar

[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. doi: 10.1016/S0362-546X(97)00516-6. Google Scholar

[21]

Y. F. Shang and B. Yu, Boundary moving combined homotopy method for nonconvex nonlinear programming and its convergence,, (Chinese), 44 (2006), 357. Google Scholar

[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. doi: 10.1016/0096-3003(95)00295-2. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. doi: 10.1145/29380.214343. Google Scholar

[26]

E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods,, 2nd edition, (2003). doi: 10.1137/1.9780898719154. Google Scholar

show all references

References:
[1]

J. A. Mirrlees, The theory of moral hazard and unobservable behavior: Part I,, Mimeo, 66 (1999), 3. Google Scholar

[2]

J. A. Mirrlees, The Implication of Moral Hazard for Optimal Insurance,, Seminar Given at Conference Held in Honor of Karl Borch. Mimeo, (1979). Google Scholar

[3]

W. P. Rogerson, The first-order approach to principal-agent problems,, Economica, 53 (1985), 1357. doi: 10.2307/1913212. Google Scholar

[4]

M. LiCalzi and S. Spaeter, Distributions for the first-order approach to principal-agent problems,, Economic Theory, 21 (2003), 167. doi: 10.1007/s00199-001-0250-y. Google Scholar

[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. Google Scholar

[6]

S. J. Grossman and O. D. Hart, An Analysis of the principal-agent problem,, Econometrica, 51 (1983), 7. doi: 10.2307/1912246. Google Scholar

[7]

I. Jewitt, Justifying the first-order approach to principal-agent problems,, Economica, 56 (1988), 1177. doi: 10.2307/1911363. Google Scholar

[8]

B. Sinclair-Desgagné, The first-order approach to multi-signal principal-agent problems,, Econometrica, 62 (1994), 459. doi: 10.2307/2951619. Google Scholar

[9]

E. Alvi, First-order approach to principal-agent problems: A generalization,, The Geneva Risk and Insurance Review, 22 (1997), 59. doi: 10.1023/A:1008663531322. Google Scholar

[10]

John R. Conlon, Two new conditions supporting the first-order approach to multisignal principal-agent problems,, Econometrica, 77 (2009), 249. doi: 10.3982/ECTA6688. Google Scholar

[11]

S. Koehne, The first-order approach to moral hazard problems with hidden saving,, Working Paper, (2010). doi: 10.2139/ssrn.1444780. Google Scholar

[12]

R. B. Myerson, Optimal coordination mechanisms in generalized principal-agent problems,, J. Math. Econ., 10 (1982), 67. doi: 10.1016/0304-4068(82)90006-4. Google Scholar

[13]

E. S. Prescott, A primer on Moral-Hazard models,, Federal Reserve Bank of Richmond Quanterly Review, 85 (1999), 47. Google Scholar

[14]

E. S. Prescott, Computing solutions to moral-hazard programs using the Dantzig-Wolfe decomposition algorithm,, J. Econ. Dynam. Control, 28 (2004), 777. doi: 10.1016/S0165-1889(03)00053-8. Google Scholar

[15]

C. L. Su and K. L. Judd, Computation of moral-hazard problems,, Working Paper, (2007). Google Scholar

[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. doi: 10.1137/0713041. Google Scholar

[17]

S. Smale, A convergent process of price adjustment and global newton methods,, J. Math. Econom., 3 (1976), 107. doi: 10.1016/0304-4068(76)90019-7. Google Scholar

[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. doi: 10.1090/S0025-5718-1978-0492046-9. Google Scholar

[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), (1994), 9. Google Scholar

[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. doi: 10.1016/S0362-546X(97)00516-6. Google Scholar

[21]

Y. F. Shang and B. Yu, Boundary moving combined homotopy method for nonconvex nonlinear programming and its convergence,, (Chinese), 44 (2006), 357. Google Scholar

[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. doi: 10.1016/0096-3003(95)00295-2. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. doi: 10.1145/29380.214343. Google Scholar

[26]

E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods,, 2nd edition, (2003). doi: 10.1137/1.9780898719154. Google Scholar

[1]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[2]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651

[3]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[4]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[5]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[6]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[7]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032

[8]

Behrouz Kheirfam, Kamal mirnia. Multi-parametric sensitivity analysis in piecewise linear fractional programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 343-351. doi: 10.3934/jimo.2008.4.343

[9]

Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33

[10]

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 & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[11]

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 & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65

[12]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825

[13]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477

[14]

Behrouz Kheirfam. Multi-parametric sensitivity analysis of the constraint matrix in piecewise linear fractional programming. Journal of Industrial & Management Optimization, 2010, 6 (2) : 347-361. doi: 10.3934/jimo.2010.6.347

[15]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[16]

Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049

[17]

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 & Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167

[18]

Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357

[19]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323

[20]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]