Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Optimization and Engineering
Erschienen in: Optimization and Engineering 2/2016

05.11.2015

Variations and extension of the convex–concave procedure

verfasst von: Thomas Lipp, Stephen Boyd

Erschienen in: Optimization and Engineering | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We investigate the convex–concave procedure, a local heuristic that utilizes the tools of convex optimization to find local optima of difference of convex (DC) programming problems. The class of DC problems includes many difficult problems such as the traveling salesman problem. We extend the standard procedure in two major ways and describe several variations. First, we allow for the algorithm to be initialized without a feasible point. Second, we generalize the algorithm to include vector inequalities. We then present several examples to demonstrate these algorithms.
Nächster Artikel Data-driven construction of Convex Region Surrogate models

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Literatur
Absil PA, Mahony R, Sepulchre R (2009) Optimization algorithms on matrix manifolds. Princeton University Press, PrincetonMATH
Agin N (1966) Optimum seeking with branch and bound. Manag Sci 13:176–185CrossRef
Beck A, Ben-Tal A, Tetrushvili L (2010) A sequential parametric convex approximation method with applications to nonconvex truss topology design problems. J Glob Optim 47(1):29–51MathSciNetMATHCrossRef
Belkin M, Niyogi P (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput 15(6):1373–1396MATHCrossRef
Boyd S, Hast M, Åström KJ (2015) MIMO PID tuning via iterated LMI restriction. Int J Robust Nonlinear Control To appear
Byrd RH, Gilbert JC, Nocedal J (2000) A trust region method based on interior point techniques for nonlinear programming. Math Program 89(1):149–185MathSciNetMATHCrossRef
Byrne C (2000) Block-iterative interior point optimization methods for image reconstruction from limited data. Inverse Probl 16(5):1405MathSciNetMATHCrossRef
Crawford JM, Auton LD (1996) Experimental results on the crossover point in random 3-SAT. Artif Intell 81(1):31–57MathSciNetCrossRef
De Leeuw J (1977) Applications of convex analysis to multidimensional scaling. In: Barra JR, Brodeau F, Romier G, Van Cutsem B (eds) Recent developments in statistics. North Holland Publishing, Amsterdam, pp 133–146
Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J R Stat Soc Ser B (Methodol) 39:1–38MathSciNetMATH
Diamond S, Boyd S (2015) CVXPY: a python-embedded modeling language for convex optimization. J Mach Learn Res Mach Learn Open Sour Softw To appear
Domahidi A, Chu E, Boyd S (2013) ECOS: an SOCP solver for embedded systems. In: European control conference, pp 3071–3076
Drira A, Pierreval H, Hajri-Gabouh S (2007) Facility layout problems: a survey. Annu Rev Control 31(2):255–267CrossRef
Edelman A, Tomás AA, Smith TS (1998) The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 20(2):303–353MathSciNetMATHCrossRef
Falk JE, Hoffmann KR (1976) A successive underestimation method for concave minimization problems. Math Oper Res 1(3):251–259MATHCrossRef
Fardad M, Jovanović MR (2014) On the design of optimal structured and sparse feedback gains via sequential convex programming. In: American control conference, pp 2426–2431
Garcia Palomares UM, Mangasarian OL (1976) Superlinearly convergent quasi-newton algorithms for nonlinearly constrained optimization problems. Math Program 11(1):1–13MathSciNetMATHCrossRef
Gill PE, Wong E (2012) Sequential quadratic programming methods. In: Mixed integer nonlinear programming, Springer, pp 147–224
Hanan M, Kurtzberg J (1972) Placement techniques. In: Breuer MA (ed) Design automation of digital systems, vol 1. Prentice-Hall, Upper Saddle River, pp 213–282
Hillestad RJ, Jacobsen SE (1980a) Linear programs with an additional reverse convex constraint. Appl Math Optim 6(1):257–269MathSciNetMATHCrossRef
Horst R (1986) A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization. J Optim Theory Appl 51(2):271–291MathSciNetMATHCrossRef
Horst R, Phong TQ, Thoai NV, De Vries J (1991a) On solving a DC programming problem by a sequence of linear programs. J Glob Optim 1(2):183–203MATHCrossRef
Horst R, Thoai NV, Benson HP (1991b) Concave minimization via conical partitions and polyhedral outer approximation. Math Program 50:259–274MathSciNetMATHCrossRef
Horst R, Pardalos PM, Thoai NV (1995) Introduction to global optimization. Kluwer Academic Publishers, DordrechtMATH
Karp RM (1972) Reducibility among combinatorial problems. In: Thatcher JW, Miller RE (eds) Complexity of computer computation. Plenum, Berlin, pp 85–104CrossRef
Lanckreit GR, Sriperumbudur BK (2009) On the convergence of the concave-convex procedure. Adv Neural Inf Process Syst, 1759–1767
Lange K (2004) Optimization. Springer texts in statistics. Springer, New York
Lange K, Hunter DR, Yang I (2000) Optimization transfer using surrogate objective functions. J Comput Graph Stat 9(1):1–20MathSciNet
Le HM, Le Thi HA, Pham Dinh T, Bouvry P (2010) A combined DCA: GA for constructing highly nonlinear balanced Boolean functions in cryptography. J Glob Optim 47(4):597–613MathSciNetMATHCrossRef
Le Thi HA (2003) Solving large scale molecular distance geometry problems by a smoothing technique via the Gaussian transform and DC programming. J Glob Optim 27(4):375–397MathSciNetMATHCrossRef
Le Thi HA, Pham Dinh T (1997) Solving a class of linearly constrainted indefinite quadratic problems by DC algorithms. J Glob Optim 11(3):253–285MATHCrossRef
Le Thi HA, Pham Dinh T (2003) Large-scale molecular optimization for distance matrices by a DC optimization approach. SIAM J Optim 14(1):77–114MathSciNetMATHCrossRef
Le Thi HA, Pham Dinh T (2008) A continuous approach for the concave cost supply problem via DC programming and DCA. Discret Appl Math 156(3):325–338MathSciNetMATHCrossRef
Le Thi HA, Pham Dinh T, Muu LD (1996) Numerical solution for optimization over the efficient set by d.c. optimization algorithms. Oper Res Lett 19:117–128MathSciNetMATHCrossRef
Le Thi HA, Pham Dinh T, Muu LD (1998) A combined D.C. optimization-ellipsoidal branch-and-bound algorithm for solving nonconvex quadratic programming problems. J Comb Optim 2(1):9–28MathSciNetMATHCrossRef
Le Thi HA, Pham Dinh T, Thoai NV (2002) Combination between global and local methods for solving an optimization problem over the efficient set. Eur J Oper Res 142(2):258–270MathSciNetMATHCrossRef
Le Thi HA, Moeini M, Pham Dinh T (2009a) DC programming approach for portfolio optimization under step increasing transaction costs. Optimization 58(3):267–289MathSciNetMATHCrossRef
Le Thi HA, Pham Dinh T, Nguyen CN, Thoai NV (2009b) DC programming techniques for solving a class of nonlinear bilevel programs. J Glob Optim 44(3):313–337MathSciNetMATHCrossRef
Le Thi HA, Huynh VN, Pham Dinh T (2014) DC programming and DCA for general DC programs. Adv Comput Methods Knowl Eng, 15–35
Little RJA, Rubin DB (1987) Statistical analysis with missing data. Wiley, New YorkMATH
Maranas CD, Floudas CA (1997) Global optimization in generalized geometric programming. Comput Chem Eng 21(4):351–369MathSciNetCrossRef
McLachlan G, Krishnan T (2007) The EM algorithm and extensions. Wiley, HobokenMATH
Mitchell D, Selman B, Levesque H (1992) Hard and easy distributions and SAT problems. Proc Tenth Natl Conf Artif Intell 92:459–465
Mueller JB, Larsson R (2008) Collision avoidance maneuver planning with robust optimization. In: International ESA conference on guidance, navigation and control systems, Tralee
Mutapcic A, Boyd S (2009) Cutting-set methods for robust convex optimization with pessimizing oracles. Optim Methods Softw 24(3):381–406MathSciNetMATHCrossRef
Muu LD (1985) A convergent algorithm for solving linear programs with an additional reverse convex constraint. Kybernetika 21(6):428–435MathSciNetMATH
Naghsh MM, Modarres-Hashemi M, ShahbazPanahi S, Soltanalian M, Stoica P (2013) Unified optimization framework for multi-static radar code design using information-theoretic criteria. IEEE Trans Signal Process 61(21):5401–5416CrossRef
Nam GJ, Cong J (eds) (2007) Modern circuit placement. Springer, New York
Ndiaye BM, Pham Dinh T, Le Thi HA (2012) DC programming and DCA for large-scale two-dimensional packing problems. Springer, New YorkCrossRef
Niu YS, Pham Dinh T (2014) DC programming approaches for BMI and QMI feasibility problems. Adv Comput Methods Knowl Eng 6:37–63MATHCrossRef
Nocedal J, Wright SJ (2006) Numerical optimization. Springer, New YorkMATH
Pham Dinh T, Le Thi HA (1997) Convex analysis approach to DC programming: theory, algorithms, and applications. Acta Math Vietnam 22(1):289–355MathSciNetMATH
Pham Dinh T, Le Thi HA (1998) A DC optimization algorithm for solving the trust-region subproblem. SIAM J Optim 8(2):476–505MathSciNetMATHCrossRef
Pham Dinh T, Le Thi HA (2014) Recent advances in DC programming and DCA. Trans Comput Intell XIII 13:1–37CrossRef
Pham Dinh T, Souad EB (1986) Algorithms for solving a class of nonconvex optimization problems. Methods of subgradients. In: Hiriart-Urruty JB (ed) FERMAT Days 85: mathematics for optimization. Elsevier Scince Publishers B. V., Amsterdam, pp 249–271
Pham Dinh T, Souad EB (1988) Duality in D.C. (difference of convex functions) optimization. subgradient methods. In: International Series of Numerical Mathematics, vol 84, Birkhäuser Basel
Pham Dinh T, Le Thi HA, Akoa F (2008) Combining DCA (DC algorithms) and interior point techniques for large-scale nonconvex quadratic programming. Optim Methods Softw 23(4):609–629MathSciNetMATHCrossRef
Pham Dinh T, Nguyen CN, Le Thi HA (2010) An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs. J Glob Optim 48(4):595–632MathSciNetMATHCrossRef
Powell MJD (1978) A fast algorithm for nonlinearly constrained optimization calculations. Springer, New York, pp 144–157MATH
Robinson SM (1972) A quadratically-convergent algorithm for general nonlinear programming problems. Math Program 3(1):145–156MathSciNetMATHCrossRef
Shulman J, Ho J, Lee A, Awwal I, Bradlow H, Abbeel P (2013) Finding locally optimal, collision-free trajectories with sequential convex optimization. In: Robotics: science and systems, vol 9. pp 1–10
Singh SP, Sharma RRK (2006) A review of different approaches to the facility layout problems. Int J Adv Manuf Technol 30(5):425–433CrossRef
Smola AJ, Vishwanathan SVN, Hofmann T (2005) Kernel methods for missing variables. In: Proceedings of 10th international workshop on artificial intelligence and statistics
Soland RM (1971) An algorithm for separable nonconvex programming problems II: nonconvex constraints. Manag Sci 17(11):759–773MathSciNetMATHCrossRef
Stiefel E (1935–1936) Richtungsfelder und fernparallelismus in n-dimensionalem mannig faltigkeiten. Comment Math Helv 8:305–353
Stoica P, Babu P (2012) SPICE and LIKES: two hyperparameter-free methods for sparse-parameter estimation. Signal Process 92(8):1580–1590CrossRef
Svanberg K (1987) The method of moving asymptotes-a new method for structural optimization. Int J Numer Methods Eng 24(2):359–373MathSciNetMATHCrossRef
Toh KC, Todd MJ, Tutuncu RH (1999) SDPT3—a MATLAB software package for semidefinite programming. Optim Methods Softw 11:545–581MathSciNetMATHCrossRef
Tuy H (1983) On outer approximation methods for solving concave minimization problems. Acta Math Vietnam 8(2):3–34MathSciNetMATH
Tuy H, Horst R (1988) Convergence and restart in branch-and-bound algorithms for global optimization. Applications to concave minimization and DC optimization problems. Math Program 41(2):161–183MathSciNetMATHCrossRef
Wilson RB (1963) A simplicial algorithm for concave programming. PhD thesis, Gradaute School of Business Administration, Harvard University
Yamada S, Tanino T, Inuiguchi M (2000) Inner approximation method for a reverse convex programming problem. J Optim Theory Appl 107(2):355–389MathSciNetMATHCrossRef
Yu CNJ, Joachims T (2009) Learning structural SVMs with latent variables. In: Proceedings of the 26th annual international conference on machine learning, pp 1169–1176
Yuille AL, Rangarajan A (2003) The concave-convex procedure. Neural Comput 15(4):915–936MATHCrossRef
Zangwill WI (1969) Nonlinear programming: a unified approach. Prentice-Hall Inc, Englewood CliffsMATH
Zillober C (2001) Global convergence of a nonlinear programming method using convex optimization. Numer Algorithms 27(3):265–289MathSciNetMATHCrossRef
Metadaten
Titel
Variations and extension of the convex–concave procedure
verfasst von
Thomas Lipp
Stephen Boyd
Publikationsdatum
05.11.2015
Verlag
Springer US
Erschienen in
Optimization and Engineering / Ausgabe 2/2016
Print ISSN: 1389-4420
Elektronische ISSN: 1573-2924
DOI
https://doi.org/10.1007/s11081-015-9294-x

Weitere Artikel der Ausgabe 2/2016

Optimization and Engineering 2/2016 Zur Ausgabe

OriginalPaper

A matrix-free augmented lagrangian algorithm with application to large-scale structural design optimization

OriginalPaper

High detail stationary optimization models for gas networks: validation and results

OriginalPaper

Variation-aware clock network buffer sizing using robust multi-objective optimization

OriginalPaper

Robust design optimization for improving automotive shift quality

OriginalPaper

Dynamic scaling in the mesh adaptive direct search algorithm for blackbox optimization

OriginalPaper

An S $$\ell _1$$ ℓ 1 LP-active set approach for feasibility restoration in power systems

Premium Partner

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen. 

    Zur Marktübersicht
    Bildnachweise