Optimality condition and complexity of order-value optimization problems and low order-value optimization problems | Journal of Global Optimization Skip to main content
Springer Nature Link
Log in

Optimality condition and complexity of order-value optimization problems and low order-value optimization problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Order-value optimization problems and low order-value optimization problems are new subclasses of optimization problems which arise from decision-making problems under uncertainty and robust estimation problems. In this paper, We present KKT necessary and sufficient conditions for low order-value optimization problems under convexity hypothesis in this paper. A smooth reformulation of low order-value optimization problems are presented whose local solutions satisfy the KKT necessary conditions. we prove that order-value optimization problems is NP-hard in the strong sense even when constraints are polytope. Order-value optimization problems and low order-value optimization problems are NP-hard even when their presentation functions are linear and constraints are polytope. Some special cases that could be solved in polynomial time are proposed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Andreani, R., Dunder, C., Martinez, J.M.: Order-value optimization: formulation and solution by means of a primal Cauchy method. Math. Methods Oper. Res. 55, 387–399 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  2. Andreani, R., Dunder, C., Martinez, J.M.: Nonlinear-programming reformulation of the order-value optimization problem. Math. Methods Oper. Res. 61, 365–384 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  3. Andreani, R., Martinez, J.M., Salvatierra, M.: Global Order-Value Optimization by Means of a Multistart Harmonic Oscillator Tunneling Strategy. Global Optimization. Springer, New York (2006)

    Book  MATH  Google Scholar 

  4. Andreani, R., Martinez, J.M., Salvatierra, M., Yano, F.S.: Quasi-Newton methods for order-value optimization and value-at-risk calculation. Pac. J. Optim. 2, 11–33 (2006)

    MathSciNet  MATH  Google Scholar 

  5. Andreani, R., Martinez, J.M., Martinez, L.: Trust-region superposition methods for protein alignment. IMA J. Numer. Anal. 28, 690–710 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Andreani, R., Martinez, J.M., Martinez, L., Yano, F.S.: Continuous optimization methods for structural alignment. Math. Program. 112, 93–124 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Andreani, R., Martinez, J.M., Martinez, L., Yano, F.S.: Low order-value optimization and applications. J. Glob. Optim. 43, 1–10 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, New York City (2006)

    Book  MATH  Google Scholar 

  9. Birgin, E.G., Bueno, L.F., Krejic, N., Martinez, J.M.: Low order-value approach for solving VaR-constrained optimization problems. J. Glob. Optim. 51, 715–742 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  10. Carvalho, E.P., Pisnitchenko, F., Mezzomo, N.: Low order-value multiple fitting for supercritical fluid extraction models. Comput. Chem. Eng. 40, 148–156 (2012)

    Article  Google Scholar 

  11. Garey, M.R., Johnson, D.S.: Computers and Intractability a Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  12. Gouveia, P., Andreani, R., Friedlander, A.: Global improvements of a protein alignment algorithm and comparison with a global optimization solver. Bull. Comput. Appl. Math 1, 37–50 (2012)

    Google Scholar 

  13. Huber, P.J.: Robust Statistics. Wiley, New York (1981)

    Book  MATH  Google Scholar 

  14. Jorion, P.: Value at Risk: The New Benchmark for Managing Financial Risk, 2nd edn. Mc Graw-Hill, New York (2001)

    Google Scholar 

  15. Martinez, L., Andreani, R., Martinez, J.M.: Convergent algorithms for protein structural alignment. BMC Bioinform. 8, 306 (2007)

    Article  Google Scholar 

  16. Martinez, J.M.: Generalized order-value optimizaiton. TOP 20, 75–89 (2012)

    Article  MathSciNet  Google Scholar 

  17. Natarajan, B.K.: Sparse approximate solutions to linear systerms. SIAM J. Comput. 24, 227–234 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  18. Nesterov, Yu., Nemirovsky, A.: Interior-Point Polynomial Methods in Convex Programming, Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia (1994)

    Google Scholar 

  19. Pang, J.S., Leyffer, S.: On the global minimization of the value-at-risk. Optim. Methods Softw. 19, 611–631 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are very grateful for the reviewers’ valuable comments to improve the quality of the paper.

Author information

Authors and Affiliations

  1. Department of Management Science, School of Management, Fudan University, Shanghai, 200433, People’s Republic of China

    Zhongyi Jiang & Qiying Hu

  2. School of Information Science, Changzhou University, Jiangsu, 203164, People’s Republic of China

    Zhongyi Jiang

  3. School of Economics and Management, Tongji University, Shanghai, 200092, People’s Republic of China

    Xiaojin Zheng

Authors
  1. Zhongyi Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qiying Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaojin Zheng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiaojin Zheng.

Additional information

This research is supported in part by National Natural Science Foundation of China under Grants 11371103; 71671046 and 11671300.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiang, Z., Hu, Q. & Zheng, X. Optimality condition and complexity of order-value optimization problems and low order-value optimization problems. J Glob Optim 69, 511–523 (2017). https://doi.org/10.1007/s10898-017-0520-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-017-0520-2

Keywords

Mathematics Subject Classification

Search

Navigation