Skip to main content
SpringerLink
Log in

Generalized order-value optimization

  • Original Article
  • Published:
TOP Aims and scope Submit manuscript

Abstract

Generalized Order-Value Optimization (GOVO) problems involve functions whose evaluation depends on order relations on some representation functional set. We give examples of GOVO problems that may be analyzed in the context of Piecewise-Smooth Optimization. Generalizations of algorithms that have been proved to be effective for proving special classes of GOVO problems are introduced. The case of Low Order-Value Optimization (LOVO) is considered as an example of GOVO in which one needs specialized algorithms with stronger convergence results. Applications of constrained LOVO problems and problems with OVO constraints are presented. The state-of-the-art of Protein Alignment problems from the LOVO point of view are discussed.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Andreani R, Dunder C, Martínez JM (2003) Order-Value Optimization: formulation and solution by means of a primal Cauchy method. Math Methods Oper Res 58:387–399

    Article  Google Scholar 

  • Andreani R, Dunder C, Martínez JM (2005a) Nonlinear-programming reformulation of the Order-Value Optimization Problem. Math Methods Oper Res 61:365–384

    Article  Google Scholar 

  • Andreani R, Martínez JM, Schuverdt ML (2005b) On the relation between the Constant Positive Linear Dependence condition and quasinormality constraint qualification. J Optim Theory Appl 125:473–485

    Article  Google Scholar 

  • Andreani R, Martínez JM, Salvatierra M, Yano FS (2006) Quasi-Newton methods for Order-Value Optimization and Value-at-Risk calculations. Pac J Optim 2:11–33

    Google Scholar 

  • Andreani R, Birgin EG, Martínez JM, Schuverdt ML (2007) On Augmented Lagrangian methods with general lower-level constraints. SIAM J Optim 18:1286–1309

    Article  Google Scholar 

  • Andreani R, Martínez JM, Martínez L (2008a) Trust-region superposition methods for Protein Alignment. IMA J Numer Anal 28:690–710

    Article  Google Scholar 

  • Andreani R, Martínez JM, Martínez L, Yano FS (2008b) Continuous Optimization methods for Structural Alignment. Math Program 112:93–124

    Article  Google Scholar 

  • Andreani R, Martínez JM, Martínez L, Yano FS (2009) Low Order-Value Optimization and applications. J Glob Optim 43:1–10

    Article  Google Scholar 

  • Bezdek JC, Keller J, Krisnapuram R, Pal M (eds) (1999) Fuzzy models and algorithms for pattern recognition and image processing. Kluwer Academic, Dordrecht

    Google Scholar 

  • Birgin EG, Martínez JM, Ronconi DP (2003) Minimization subproblems and heuristics for an applied clustering problem. Eur J Oper Res 146:19–34

    Article  Google Scholar 

  • Birgin EG, Bueno LF, Krejić N, Martínez JM (2010a) Low order-value approach for solving VaR-constrained optimization problems. Technical Report, Department of Applied Mathematics, State University of Campinas. Available in Optimization on line

  • Birgin EG, Floudas CA, Martínez JM (2010b) Global minimization using an Augmented Lagrangian method with variable lower-level constraints. Math Program 125:139–162

    Article  Google Scholar 

  • Clarke FH (1990) Optimization and nonsmooth analysis. Classic in applied mathematics. SIAM, Philadelphia

    Book  Google Scholar 

  • Conn AR, Scheinberg K, Vicente LN (2009) Introduction to derivative-free optimization. MPS–SIAM series on optimization. SIAM, Philadelphia

    Book  Google Scholar 

  • Fuduli A, Gaudioso M, Gallombardo G (2004a) Minimizing nonconvex nonsmooth functions via cutting planes and proximity control. SIAM J Optim 14:743–756

    Article  Google Scholar 

  • Fuduli A, Gaudioso M, Gallombardo G (2004b) A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization. Optim Methods Softw 19:89–102

    Article  Google Scholar 

  • Gini C (1921) Measurement of inequality of incomes. Econ J 31:124–126

    Article  Google Scholar 

  • Gouveia P (2010) Global optimization methods for protein alignment. Tese de Doutorado, Departamento de Matemática Aplicada, Universidade Estadual de Campinas (in progress)

  • Grothey A (2002) A second order trust region bundle method for nonconvex nonsmooth optimization. Technical Report MS 02-001, University of Edinburgh

  • Haakala N, Miettinen K, Makela MM (2007) Globally convergent limited memory bundle method for large-scale nonsmooth optimization. Math Program 109:181–205

    Article  Google Scholar 

  • Hare W, Sagastizábal C (2010) A redistributed proximal bundle method for nonconvex optimization. SIAM J Optim 20:2443–2473

    Article  Google Scholar 

  • Holm L, Sander C (1996) Mapping the protein Universe. Science 273:595–602

    Article  Google Scholar 

  • Huber PJ (1981) Robust statistics. Wiley, New York

    Book  Google Scholar 

  • Jorion P (2001) Value at risk: the new benchmark for managing financial risk, 2nd edn. McGraw-Hill, New York

    Google Scholar 

  • Kiwiel KC (1985) Methods of descent for nondifferentiable optimization. Lecture notes in mathematics, vol 1133. Springer, Berlin, New York

    Google Scholar 

  • Kiwiel KC (1996) Restricted step and Levenberg–Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization. SIAM J Optim 6:227–249

    Article  Google Scholar 

  • Kolodny R, Linial N (2004) Approximate protein structural alignment in polynomial time. Proc Natl Acad Sci USA 101:12201–12206

    Article  Google Scholar 

  • Kolodny R, Koehl P, Levitt M (2005) Comprehensive evaluation of protein structure alignment methods: scoring by geometric measures. J Mol Biol 346:1173–1188

    Article  Google Scholar 

  • Lewis AS, Overton ML (2010) Nonsmooth optimization via BFGS. SIAM J Optim (submitted)

  • Lima R (2010) Protein maps and quick alignments. Tese de Doutorado, Departamento de Matemática Aplicada, Universidade Estadual de Campinas, Brazil (in progress)

  • Lukv̌san L, Vlćek J (1998) A bundle method for nonsmooth unconstrained minimization. Math Program 83:373–391

    Google Scholar 

  • Martínez L, Andreani R, Martínez JM (2007) Convergent algorithms for Protein Structural Alignment. BMC Bioinform 8:306

    Article  Google Scholar 

  • Needleman B, Wunsch CD (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 48:443–453

    Article  Google Scholar 

  • Noll D, Prot O, Rondepierre A (2008) A proximity control algorithm to minimize nonsmooth and nonconvex functions. Pac J Optim 4:569–602

    Google Scholar 

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

    Article  Google Scholar 

  • Qi L, Tseng P (2007) On almost smooth functions and piecewise smooth functions. Nonlinear Anal Theory Methods Appl 67:773–794

    Article  Google Scholar 

  • Rockafellar RT, Uryasev S (2002) Conditional value-at-risk for general loss distributions. J Bank Finance 26:1443–1471

    Article  Google Scholar 

  • Schramm H, Zowe J (1992) A version of the bundle idea for minimizing a smooth function: Conceptual idea, convergence analysis, numerical results. SIAM J Optim 2:121–152

    Article  Google Scholar 

  • Skajaa A (2010) Limited memory BFGS method for nonsmooth optimization. Master’s thesis, Courant Institute of Mathematical Science, New York University

  • Subbiah S, Laurents DV, Levitt M (1993) Structural similarity of DNA-binding domains of bacteriophage repressors and the globin core. Curr Biol 3:141–148

    Article  Google Scholar 

  • Vlcék J, Lukv̌san L (2001) Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization. J Optim Theory Appl 111:407–430

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, Statistics and Scientific Computing, State University of Campinas, CP 6065, 13081-970, Campinas, SP, Brazil

    José Mario Martínez

Authors
  1. José Mario Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to José Mario Martínez.

Additional information

This work was supported by PRONEX, FAPESP (PT 2006-53768-0), CNPq, FAEP-UNICAMP.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Martínez, J.M. Generalized order-value optimization. TOP 20, 75–98 (2012). https://doi.org/10.1007/s11750-010-0169-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-010-0169-1

Keywords

Mathematics Subject Classification (2000)

Search

Navigation