American Institute of Mathematical Sciences

Advanced
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

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 & 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]

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
[2]

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
[3]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055
[4]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[5]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[6]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[7]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[8]

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
[9]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[10]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[11]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203
[12]

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
[13]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[14]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[15]

Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024
[16]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[17]

Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161
[18]

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
[19]

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
[20]

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

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences