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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Mathematics: As an Infrastructure of Technology and Science Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Strict Feasibility of Conic Optimization Problems

verfasst von : Hayato Waki

Erschienen in: A Mathematical Approach to Research Problems of Science and Technology

Verlag: Springer Japan

Einloggen

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

search-config
loading …

Abstract

A conic optimization problem (COP) is the problem of minimizing a given linear objective function over the intersection of an affine space and a closed convex cone. Conic optimization problem is often used for solving nonconvex optimization problems. The strict feasibility of COP is important from the viewpoint of computation. The lack of the strict feasibility may cause the instability of computation. This article provides a brief introduction of COP and a characterization of the strict feasibility of COP. We also explain a facial reduction algorithm (FRA), which is based on the characterization. This algorithm can generate a strictly feasible COP which is equivalent to the original COP, or detect the infeasibility of COP.

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

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Discrete Optimization: Network Flows and Matchings
Nächstes Kapitel Theory of Automata, Abstraction and Applications
Fußnoten
1
We remark that the formulation (3) of SDP in this article is different from one in the article of Dr. Fujisawa. However, one can obtain the form in the article of Dr. Fujisawa by applying the following replacement:
$$ \begin{array}{cc} b \rightarrow -c,&L_i \rightarrow -F_i. \end{array} $$
Then, (3) can be reformulated as a minimization problem on \(y\).
 
2
For a given convex set \(C\subset \mathbb {R}^n\), a face of \(C\) is a convex subset \(D\) of \(C\) such that every \(x, y\in C\), \(x+y\in D\) implies that \(x, y\in D\). If \(C\) is polyhedral, then the definition is simpler. In fact, a face of polyhedral set \(C\) is the intersection with a hyperplane and \(C\). Such a face is called exposed face. See [10, 14] for more details.
 
Literatur
1.
A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization (Society for Industrial and Applied Mathematics, Philadelphia, 2001)
2.
3.
S. Burer, On the copositive representation of binary and continuous non convex quadratic programs. Math. Programm. 120, 479–495 (2009)MathSciNetCrossRefMATH
4.
S. Burer, in Copositive Programming, ed. by M.F. Anjos, J.B. Lasserre. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York, 2012), pp 201–218
5.
F. Burkowski, Y. Cheung, H. Wolkowicz, Efficient use of semidefinite programming for selection of rotamers in protein conformations, preprint (2013)
6.
N. Krislock, H. Wolkowicz, Explicit sensor network localization using semidefinite representations and facial reductions. SIAM J. Optim. 20, 2679–2708 (2010)MathSciNetCrossRefMATH
7.
8.
M. Lobo, L. Vandenberghe, S. Boyd, H. Lebret, Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)MathSciNetCrossRefMATH
9.
Z.-Q. Luo, F.J. Sturm, S. Zhang, Duality results for conic convex programming, Econometric institute report no. 9719/A. Econometric Institute, Erasmus University Rotterdam (1997)
10.
G. Pataki, in The Geometry of Cone-LP’s, ed. by H. Wolkowicz, R. Saigal, L. Vandenberghe. The Handbook of Semidefinite Programming (Springer, Berlin, 2000), pp. 29–65
11.
12.
V.M. Ramana, An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77, 129–162 (1997)MathSciNetMATH
13.
14.
R.T. Rockafellar, in Convex Analysis. Princeton Landmarks in Mathematics and Physics (Princeton University Press, Princeton, 1970)
15.
A. Schrijver, Theory of Linear and Integer Programming (Wiley, New York, 1979)
16.
F.J. Sturm, Primal-Dual Interior Point Approach to Semidefinite Programming, Ph.D. Thesis, Erasmus University Rotterdam (1997)
17.
F.J. Sturm, in Theory and Algorithms of Semidefinite Programming, ed. by H. Frenk, K. Roos, T. Terlaky. High performance optimization, pp. 1–194 (Kluwer Academic Publishers, Dordrecht, 2000)
18.
19.
20.
L. Tunçel, in Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization. Fields Institute Monographs (2010)
21.
L. Tunçel, H. Wolkowicz, Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. 53, 619–648 (2013)
22.
H. Waki, M. Muramatsu, Facial reduction algorithms for finding sparse SOS representations. Oper. Res. Lett. 38, 361–365 (2010)MathSciNetCrossRefMATH
23.
H. Waki, M. Muramatsu, An extension of the elimination method for a sparse SOS polynomial. J. Oper. Res. Soc. Jpn 54, 161–190 (2011)MathSciNetMATH
24.
H. Waki, M. Muramatsu, Facial reduction algorithms for conic optimization problems. J. Optim. Theor. Appl. 158, 188–215 (2013)
25.
H. Waki, M. Nakata, M. Muramatsu, Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization. Comput. Optim. Appl. 53, 823–844 (2012)MathSciNetCrossRefMATH
26.
H. Wolkowicz, Q. Zhao, Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97, 461–479 (1999)MathSciNetCrossRef
27.
Q. Zhao, S.E. Karisch, F. Rendl, H. Wolkowicz, Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2, 71–109 (1998)MathSciNetCrossRefMATH
Metadaten
Titel
Strict Feasibility of Conic Optimization Problems
verfasst von
Hayato Waki
Copyright-Jahr
2014
Verlag
Springer Japan
Buch
A Mathematical Approach to Research Problems of Science and Technology

Print ISBN: 978-4-431-55059-4

Electronic ISBN: 978-4-431-55060-0

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-4-431-55060-0_24

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