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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

4. Duality and Complementarity

verfasst von : David G. Luenberger, Yinyu Ye

Erschienen in: Linear and Nonlinear Programming

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Associated with every linear program, and intimately related to it, is a corresponding dual linear program. Both programs are constructed from the same underlying cost and constraint coefficients but in such a way that if one of these problems is one of minimization the other is one of maximization, and the optimal values of the corresponding objective functions, if finite, are equal. The variables of the dual problem can be interpreted as prices associated with the constraints of the original (primal) problem, and through this association it is possible to give an economically meaningful characterization to the dual whenever there is such a characterization for the primal.

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 The Simplex Method
Nächstes Kapitel Interior-Point Methods
Fußnoten
1
† The symbol ⇒ means “implies” and \(\Leftarrow\) means “is implied by.”
 
Literatur
[A1]
J. Abadie, J. Carpentier, Generalization of the Wolfe reduced gradient method to the case of nonlinear constraints, in Optimization, ed. by R. Fletcher (Academic, London, 1969), pp. 37–47
[A2]
H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Stat. Math. 11, 1–17 (1959)
[3]
A.Y. Alfakih, A. Khandani, H. Wolkowicz, Solving euclidean distance matrix completion problems via semidefinite programming. Comput. Opt. Appl. 12, 13–30 (1999)
[A3]
F. Alizadeh, Combinatorial optimization with interior point methods and semi-definite matrices, Ph.D. thesis, University of Minnesota, Minneapolis, 1991
[A4]
F. Alizadeh, Optimization over the positive semi-definite cone: interior-point methods and combinatorial applications, in Advances in Optimization and Parallel Computing, ed. by P.M. Pardalos (North Holland, Amsterdam, 1992), pp. 1–25
[6]
[A5]
E.D. Andersen, Y. Ye, On a homogeneous algorithm for the monotone complementarity problem. Math. Prog. 84, 375–400 (1999)
[A6]
K.M. Anstreicher, D. den Hertog, C. Roos, T. Terlaky, A long step barrier method for convex quadratic programming. Algorithmica 10, 365–382 (1993)
[A7]
H.A. Antosiewicz, W.C. Rheinboldt, Numerical analysis and functional analysis, in Survey of Numerical Analysis, ed. by J. Todd, Chap. 14 (McGraw-Hill, New York, 1962)
[A8]
L. Armijo, Minimization of functions having lipschitz continuous first-partial derivatives. Pac. J. Math. 16(1), 1–3 (1966)
[A9]
K.J. Arrow, L. Hurwicz, Gradient method for concave programming, I.: local results, in Studies in Linear and Nonlinear Programming, ed. by K.J. Arrow, L. Hurwicz, H. Uzawa (Stanford University Press, Stanford, CA, 1958)
[12]
E. Balas, S. Ceria, G. Cornuejols, A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58, 295–324 (1993)
[B1]
R.H. Bartels, A numerical investigation of the simplex method. Technical Report No. CS 104, Computer Science Department, Stanford University, Stanford, CA (31 July 1968)
[B2]
R.H. Bartels, G.H Golub, The simplex method of linear programming using LU decomposition. Commun. ACM 12(5), 266–268 (1969)
[15]
A. Barvinok, A remark on the rank of positive semidefinite matrices subject to affine constraints. Discrete Comput. Geom. 25, 23–31 (2001)
[16]
A. Barvinok, A Course in Convexity. Graduate Studies in Mathematics, vol. 54 (American Mathematical Society, Providence, RI, 2002)
[17]
J. Barzilai, J.M. Borwein, Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (2008)
[B3]
D.A., Bayer, J.C. Lagarias, The nonlinear geometry of linear programming, part i: affine and projective scaling trajectories. Trans. Am. Math. Soc 314(2), 499–526 (1989)
[B4]
D.A. Bayer, J.C. Lagarias, The nonlinear geometry of linear programming, part ii: legendre transform coordinates. Trans. Am. Math. Soc. 314(2), 527–581 (1989)
[B5]
M.S. Bazaraa, J.J. Jarvis, Linear Programming and Network Flows (Wiley, New York, 1977)
[B6]
M.S. Bazaraa, J.J. Jarvis, H.F. Sherali, Karmarkar’s projective algorithm (Chap. 8.4), pp. 380–394; Analysis of Karmarkar’s algorithm (Chap. 8.5), pp. 394–418, in Linear Programming and Network Flows, 2nd edn. (Wiley New York, 1990)
[B7]
E.M.L. Beale, in Numerical Methods, Nonlinear Programming, ed. by J. Abadie (North-Holland, Amsterdam, 1967)
[23]
A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)
[B8]
F.S. Beckman, The solution of linear equations by the conjugate gradient method, in Mathematical Methods for Digital Computers, ed. by A. Ralston, H.S. Wilf, vol. 1 (Wiley, New York, 1960)
[25]
S.J. Benson, Y. Ye, X. Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10, 443–461 (2000)
[26]
A. Ben-Tal, A. Nemirovski, Structural design via semidefinite programming, in Handbook on Semidefinite Programming (Kluwer, Boston, 2000), pp. 443–467
[B9]
D.P. Bertsekas, Partial conjugate gradient methods for a class of optimal control problems. IEEE Trans. Autom. Control 19, 209–217 (1973)
[B10]
D.P. Bertsekas, Multiplier methods: a survey. Automatica 12(2), 133–145 (1976)
[B11]
D.P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods (Academic, New York, 1982)
[B12]
D.P. Bertsekas, Nonlinear Programming (Athena Scientific, Belmont, 1995)
[31]
D. Bertsimas, Y. Ye, Semidefinite relaxations, multivariate normal distributions, and order statistics, in Handbook of Combinatorial Optimization (Springer, New York, 1999), pp. 1473–1491
[B13]
D.M. Bertsimas, J.N. Tsitsiklis, Linear Optimization (Athena Scientific, Belmont, 1997)
[B14]
M.C. Biggs, Constrained minimization using recursive quadratic programming: some alternative sub-problem formulations, in Towards Global Optimization, ed. by L.C.W. Dixon, G.P. Szego (North-Holland, Amsterdam, 1975)
[B15]
M.C. Biggs, On the convergence of some constrained minimization algorithms based on recursive quadratic programming. J. Inst. Math. Appl. 21, 67–81 (1978)
[B16]
G. Birkhoff, Three observations on linear algebra. Rev. Univ. Nac. Tucumán, Ser. A. 5, 147–151 (1946)
[B17]
P. Biswas, Y. Ye, Semidefinite programming for ad hoc wireless sensor network localization, in Proceedings of the 3rd IPSN, 2004, pp. 46–54
[B18]
R.E. Bixby, Progress in linear programming. ORSA J. Comput. 6(1), 15–22 (1994)
[B19]
R.G. Bland, New finite pivoting rules for the simplex method. Math. Oper. Res. 2(2), 103–107 (1977)
[B20]
R.G. Bland, D. Goldfarb, M.J. Todd, The ellipsoidal method: a survey. Oper. Res. 29, 1039–1091 (1981)
[B21]
L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1996)
[41]
S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1–122 (2010)
[B22]
S. Boyd, L.E. Ghaoui, E. Feron, V. Balakrishnan, Linear Matrix Inequalities in System and Control Science (SIAM, Philadelphia, 1994)
[B23]
S. Boyd, L. Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, 2004)
[B24]
C.G. Broyden, Quasi-Newton methods and their application to function minimization. Math. Comput. 21, 368–381 (1967)
[B25]
C.G. Broyden, The convergence of a class of double rank minimization algorithms: parts I and II. J. Inst. Math. Appl. 6, 76–90, 222–231 (1970)
[B26]
T. Butler, A.V. Martin, On a method of courant for minimizing functionals. J. Math. Phys. 41, 291–299 (1962)
[C1]
C.W. Carroll, The created response surface technique for optimizing nonlinear restrained systems. Oper. Res. 9(12), 169–184 (1961)
[C2]
A. Charnes, Optimality and degeneracy in linear programming. Econometrica 20, 160–170 (1952)
[C3]
A. Charnes, C.E. Lemke, The bounded variables problem. ONR Research Memorandum 10, Graduate School of Industrial Administration, Carnegie Institute of Technology, Pittsburgh (1954)
[50]
C.H. Chen, B.S. He, Y.Y. Ye, X.M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. (2014). doi:10.1007/s10107-014-0826-5
[C4]
A. Cohen, Rate of convergence for root finding and optimization algorithms. Ph.D. dissertation, University of California, Berkeley, 1970
[C5]
S.A. Cook, The complexity of theorem-proving procedures, in Proceedings of 3rd ACM Symposium on the Theory of Computing, 1971, pp. 151–158
[C6]
R.W. Cottle, Linear Programming. Lecture Notes for MS& E 310 (Stanford University, Stanford, 2002)
[C7]
R. Cottle, J.S. Pang, R.E. Stone, Interior-Point Methods (Chap. 5.9), in The Linear Complementarity Problem (Academic, Boston, 1992), pp. 461–475
[C8]
R. Courant, Calculus of variations and supplementary notes and exercises (mimeographed notes), supplementary notes by M. Kruskal and H. Rubin, revised and amended by J. Moser, New York University (1962)
[C9]
J.B. Crockett, H. Chernoff, Gradient methods of maximization. Pac. J. Math. 5, 33–50 (1955)
[C10]
H. Curry, The method of steepest descent for nonlinear minimization problems. Q. Appl. Math. 2, 258–261 (1944)
[58]
Y.-H. Dai, R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100, 21–47 (2005)
[D1]
J.W. Daniel, The conjugate gradient method for linear and nonlinear operator equations. SIAM J. Numer. Anal. 4(1), 10–26 (1967)
[D2]
G.B. Dantzig, Maximization of a linear function of variables subject to linear inequalities (Chap. XXI), in Activity Analysis of Production and Allocation, ed. by T.C. Koopmans. Cowles Commission Monograph, vol. 13 (Wiley, New York, 1951)
[D3]
G.B., Dantzig, Application of the simplex method to a transportation problem, in Activity Analysis of Production and Allocation, ed. by T.C. Koopmans (Wiley, New York, 1951), pp. 359–373
[D4]
G.B. Dantzig, Computational algorithm of the revised simplex method. RAND Report RM-1266, The RAND Corporation, Santa Monica, CA (1953)
[D5]
G.B. Dantzig, Variables with upper bounds in linear programming. RAND Report RM-1271, The RAND Corporation, Santa Monica, CA (1954)
[D6]
G.B. Dantzig, Linear Programming and Extensions (Princeton University Press, Princeton, 1963)
[D7]
G.B. Dantzig, L.R. Ford Jr., D.R. Fulkerson, A primal-dual algorithm, in Linear Inequalities and Related Systems. Annals of Mathematics Study, vol. 38 (Princeton University Press, Princeton, NJ, 1956), pp. 171–181
[D8]
G.B. Dantzig, A. Orden, P. Wolfe, Generalized simplex method for minimizing a linear form under linear inequality restraints. RAND Report RM-1264, The RAND Corporation, Santa Monica, CA (1954)
[D9]
G.B. Dantzig, M.N. Thapa, Linear Programming 1: Introduction (Springer, New York, 1997)
[D10]
G.B. Dantzig, M.N. Thapa, Linear Programming 2: Theory and Extensions (Springer, New York, 2003)
[D11]
G.B. Dantzig, P. Wolfe, Decomposition principle for linear programs. Oper. Res. 8, 101–111 (1960)
[D12]
W.C. Davidon, Variable metric method for minimization. Research and Development Report ANL-5990 (Ref.) U.S. Atomic Energy Commission, Argonne National Laboratories (1959)
[D13]
W.C. Davidon, Variance algorithm for minimization. Comput. J. 10, 406–410 (1968)
[72]
E. de Klerk, C. Roos, T. Terlaky, Initialization in semidefinite programming via a self–dual skew–symmetric embedding. Oper. Res. Lett. 20, 213–221 (1997)
[D14]
R.S. Dembo, S.C. Eisenstat, T. Steinhaug, Inexact Newton methods. SIAM J. Numer. Anal. 19(2), 400–408 (1982)
[D15]
J.E. Dennis Jr., J.J. Moré, Quasi-Newton methods, motivation and theory. SIAM Rev. 19, 46–89 (1977)
[D16]
J.E. Dennis Jr., R.E. Schnabel, Least change secant updates for quasi-Newton methods. SIAM Rev. 21, 443–469 (1979)
[D17]
L.C.W. Dixon, Quasi-Newton algorithms generate identical points. Math. Prog. 2, 383–387 (1972)
[E1]
B.C. Eaves, W.I. Zangwill, Generalized cutting plane algorithms. Working Paper No. 274, Center for Research in Management Science, University of California, Berkeley (July 1969)
[78]
J. Eckstein, D.P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)
[E2]
H. Everett III, Generalized lagrange multiplier method for solving problems of optimum allocation of resources. Oper. Res. 11, 399–417 (1963)
[F1]
D.K. Faddeev, V.N. Faddeeva, Computational Methods of Linear Algebra (W. H. Freeman, San Francisco, CA, 1963)
[F2]
S.C. Fang, S. Puthenpura, Linear Optimization and Extensions (Prentice-Hall, Englewood Cliffs, NJ, 1994)
[F3]
W. Fenchel, Convex Cones, Sets, and Functions. Lecture Notes (Department of Mathematics, Princeton University, Princeton, NJ, 1953)
[F4]
A.V. Fiacco, G.P. McCormick, Nonlinear Programming: Sequential Uncon-strained Minimization Techniques (Wiley, New York, 1968)
[F5]
A.V. Fiacco, G.P. McCormick, Nonlinear Programming: Sequential Uncon-strained Minimization Techniques (Wiley, New York, 1968). Reprint: Volume 4 of SIAM Classics in Applied Mathematics (SIAM Publications, Philadelphia, PA, 1990)
[F6]
R. Fletcher, A new approach to variable metric algorithms. Comput. J. 13(13), 317–322 (1970)
[F7]
R. Fletcher, An exact penalty function for nonlinear programming with inequalities. Math. Program. 5, 129–150 (1973)
[F8]
R. Fletcher, Conjugate gradient methods for indefinite systems. Numerical Analysis Report, 11. Department of Mathematics, University of Dundee, Scotland (September 1975)
[F9]
R. Fletcher, Practical Methods of Optimization 1: Unconstrained Optimization (Wiley, Chichester, 1980)
[F10]
R. Fletcher, Practical Methods of Optimization 2: Constrained Optimization (Wiley, Chichester, 1981)
[F11]
R. Fletcher, M.J.D. Powell, A rapidly convergent descent method for minimization. Comput. J. 6, 163–168 (1963)
[F12]
R. Fletcher, C.M. Reeves, Function minimization by conjugate gradients. Comput. J. 7, 149–154 (1964)
[F13]
L.K. Ford Jr., D.K. Fulkerson, Flows in Networks (Princeton University Press, Princeton, NJ, 1962)
[F14]
G.E. Forsythe, On the asymptotic directions of the s-dimensional optimum gradient method. Numer. Math. 11, 57–76 (1968)
[F15]
G.E. Forsythe, C.B. Moler, Computer Solution of Linear Algebraic Systems (Prentice-Hall, Englewood Cliffs, NJ, 1967)
[F16]
G.E. Forsythe, W.R. Wasow, Finite-Difference Methods for Partial Differential Equations (Wiley, New York, 1960)
[96]
M. Fortin, R. Glowinski, On decomposition-coordination methods using an augmented Lagrangian, in Augmented Lagrangian Methods: Applications to the Solution of Boundary Problems, ed. by M. Fortin, R. Glowinski (North- Holland, Amsterdam, 1983)
[F17]
K. Fox, An Introduction to Numerical Linear Algebra (Clarendon Press, Oxford, 1964)
[98]
M. Frank, P. Wolfe, An algorithm for quadratic programming. Naval Res. Logist. Q. 3, 95–110 (1956)
[F18]
R.M. Freund, Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Math. Program. 51, 203–222 (1991)
[F19]
K.R. Frisch, The logarithmic potential method for convex programming. Unpublished Manuscript, Institute of Economics, University of Oslo, Oslo (1955)
[G1]
D. Gabay, Reduced quasi-Newton methods with feasibility improvement for nonlinear constrained optimization, in Mathematical Programming Studies, vol. 16 (North-Holland, Amsterdam, 1982), pp. 18–44
[102]
D. Gabay, B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17–40 (1976)
[G2]
D. Gale, The Theory of Linear Economic Models (McGraw-Hill, New York, 1960)
[G3]
U.M. Garcia-Palomares, O.L. Mangasarian, Superlinearly convergent quasi-Newton algorithms for nonlinearly constrained optimization problems. Math. Program. 11, 1–13 (1976)
[G4]
S.I. Gass, Linear Programming, 3rd edn. (McGraw-Hill, New York, 1969)
[G5]
P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin, M.H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method. Math. Program. 36, 183–209 (1986)
[G6]
P.E., Gill, W. Murray, Quasi-Newton methods for unconstrained optimization. J. Inst. Math. Appl. 9, 91–108 (1972)
[G7]
P.E. Gill, W. Murray, M.H. Wright, Practical Optimization (Academic, London, 1981)
[109]
R. Glowinski, A. Marrocco, Approximation par éléments finis d’ordre un et résolution par pénalisation-dualité d’une classe de problèmes non linéaires. R.A.I.R.O. R2 2, 41–76 (1975)
[G8]
M.X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42, 1115–1145 (1995)
[G9]
D. Goldfarb, A family of variable metric methods derived by variational means. Math. Comput. 24, 23–26 (1970)
[112]
D. Goldfarb, G. Iyengar, Robust portfolio selection problems. Math. Oper. Res. 28, 1–38 (2002)
[G10]
D. Goldfarb, M.J. Todd, Linear programming, in Optimization, ed. by G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd. Handbooks in Operations Research and Management Science, vol. 1 (North Holland, Amsterdam, 1989), pp. 141–170
[G11]
D. Goldfarb, D. Xiao, A primal projective interior point method for linear programming. Math. Program. 51, 17–43 (1991)
[G12]
A.A. Goldstein, On steepest descent. SIAM J. Control 3, 147–151 (1965)
[G13]
C.C. Gonzaga, An algorithm for solving linear programming problems in O(n 3 L) operations, in Progress in Mathematical Programming: Interior Point and Related Methods, ed. by N. Megiddo (Springer, New York, 1989), pp. 1–28
[G14]
C.C. Gonzaga, M.J. Todd, An \(O(\sqrt{n}L)\)-iteration large-step primal-dual affine algorithm for linear programming. SIAM J. Optim. 2, 349–359 (1992)
[G15]
J. Greenstadt, Variations on variable metric methods. Math. Comput. 24, 1–22 (1970)
[H1]
G. Hadley, Linear Programming (Addison-Wesley, Reading, MA, 1962)
[H2]
G. Hadley, Nonlinear and Dynamic Programming (Addison-Wesley, Reading, MA, 1964)
[H3]
S.P. Han, A globally convergent method for nonlinear programming. J. Optim. Theory Appl. 22(3), 297–309 (1977)
[H4]
H. Hancock, Theory of Maxima and Minima (Ginn, Boston, 1917)
[H5]
J. Hartmanis, R.E. Stearns, On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285–306 (1965)
[124]
B.S. He, X.M. Yuan, On the O(1∕n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50, 700–709 (2012)
[H6]
D. den Hertog, Interior point approach to linear, quadratic and convex programming, algorithms and complexity, Ph.D. thesis, Faculty of Mathematics and Informatics, TU Delft, BL Delft, 1992
[H7]
M.R. Hestenes, The conjugate gradient method for solving linear systems, in Proceeding of Symposium in Applied Mathematics, vol. VI, Numerical Analysis (McGraw-Hill, New York 1956), pp. 83–102
[H8]
M.R. Hestenes, Multiplier and gradient methods. J. Opt. Theory Appl. 4(5), 303–320 (1969)
[H9]
M.R. Hestenes, Conjugate-Direction Methods in Optimization (Springer, Berlin, 1980)
[H10]
M.R. Hestenes, E.L. Stiefel, Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. Sect. B 49, 409–436 (1952)
[H11]
F.L. Hitchcock, The distribution of a product from several sources to numerous localities. J. Math. Phys. 20, 224–230 (1941)
[H12]
P. Huard, Resolution of mathematical programming with nonlinear constraints by the method of centers, in Nonlinear Programming, ed. by J. Abadie (North Holland, Amsterdam, 1967), pp. 207–219
[H13]
H.Y. Huang, Unified approach to quadratically convergent algorithms for function minimization. J. Optim. Theory Appl. 5, 405–423 (1970)
[H14]
L. Hurwicz, Programming in linear spaces, in Studies in Linear and Nonlinear Programming, ed. by K.J. Arrow, L. Hurwicz, H. Uzawa (Stanford University Press, Stanford, CA, 1958)
[I1]
E. Isaacson, H.B. Keller, Analysis of Numerical Methods (Wiley, New York, 1966)
[J1]
W. Jacobs, The caterer problem. Naval Res. Logist. Q. 1, 154–165 (1954)
[J2]
F. Jarre, Interior-point methods for convex programming. Appl. Math. Optim. 26, 287–311 (1992)
[137]
W.B. Johnson, J. Lindenstrauss, Extensions of lipshitz mapping into Hilbert space. Comtemp. Math. 26, 189–206 (1984)
[K1]
S. Karlin, Mathematical Methods and Theory in Games, Programming, and Economics, vol. I (Addison-Wesley, Reading, MA, 1959)
[K2]
N.K. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)
[K3]
J.E. Kelley, The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. VIII(4), 703–712 (1960)
[K4]
L.G. Khachiyan, A polynomial algorithm for linear programming. Doklady Akad. Nauk USSR 244, 1093–1096 (1979). Translated in Soviet Math. Doklady 20, 191–194 (1979)
[K5]
V. Klee, G.J. Minty, How good is the simplex method, in Inequalities III, ed. by O. Shisha (Academic, New York, 1972)
[K6]
M. Kojima, S. Mizuno, A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44, 1–26 (1989)
[K7]
M. Kojima, S. Mizuno, A. Yoshise, An \(O(\sqrt{n}L)\) iteration potential reduction algorithm for linear complementarity problems. Math. Program. 50, 331–342 (1991)
[K8]
T.C. Koopmans, Optimum utilization of the transportation system, in Proceedings of the International Statistical Conference, Washington, DC, 1947
[K9]
J. Kowalik, M.R. Osborne, Methods for Unconstrained Optimization Problems (Elsevier, New York, 1968)
[K10]
H.W. Kuhn, The Hungarian method for the assignment problem. Naval Res. Logist. Q. 2, 83–97 (1955)
[K11]
H.W. Kuhn, A.W. Tucker, Nonlinear programming, in Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, ed. by J. Neyman (University of California Press, Berkeley/Los Angeles, CA, 1961), pp. 481–492
[L1]
C. Lanczos, Applied Analysis (Prentice-Hall, Englewood Cliffs, NJ, 1956)
[150]
J.B. Lasserre, Global optimization with polynomials and the problem of moments related. SIAM J. Optim. 11, 796–817 (2001)
[151]
M. Laurent, Matrix completion problems. Encycl. Optim. 3, 221–229 (2001)
[L2]
E. Lawler, Combinatorial Optimization: Networks and Matroids (Holt, Rinehart, and Winston, New York, 1976)
[L3]
C. Lemarechal, R. Mifflin, Nonsmooth optimization, in IIASA Proceedings III (Pergamon Press, Oxford, 1978)
[L4]
C.E. Lemke, The dual method of solving the linear programming problem. Naval Res. Logist. Q. 1(1), 36–47 (1954)
[L5]
E.S. Levitin, B.T. Polyak, Constrained minimization methods. Zh. vychisl. Math. Math. Fiz 6(5), 787–823 (1966)
[156]
M.S. Lobo, L. Vandenberghe, S. Boyd, Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)
[L6]
C. Loewner, Über monotone Matrixfunktionen. Math. Zeir. 38, 177–216 (1934). Also see C. Loewner, Advanced matrix theory, mimeo notes, Stanford University, 1957
[L7]
F.A. Lootsma, Boundary properties of penalty functions for constrained minimization, Doctoral dissertation, Technical University, Eindhoven, May 1970
[159]
L. Lovász, A. Shrijver, Cones of matrices and setfunctions, and 0 − 1 optimization. SIAM J. Optim. 1, 166–190 (1990)
[160]
Z. Lu, L. Xiao, On the complexity analysis of randomized block-coordinate descent methods. Math. Program. (2013). doi: 10.1007/s10107-014-0800-2
[L8]
D.G. Luenberger, Optimization by Vector Space Methods (Wiley, New York, 1969)
[L9]
D.G. Luenberger, Hyperbolic pairs in the method of conjugate gradients. SIAM J. Appl. Math. 17(6), 1263–1267 (1969)
[L10]
D.G. Luenberger, A combined penalty function and gradient projection method for nonlinear programming, Internal Memo, Department of Engineering-Economic Systems, Stanford University (June 1970)
[L11]
D. G. Luenberger, The conjugate residual method for constrained minimization problems. SIAM J. Numer. Anal. 7(3), 390–398 (1970)
[L12]
D.G. Luenberger, Control problems with kinks. IEEE Trans. Autom. Control AC-15(5), 570–575 (1970)
[L13]
D.G. Luenberger, Convergence rate of a penalty-function scheme. J. Optim. Theory Appl. 7(1), 39–51 (1971)
[L14]
D.G. Luenberger, The gradient projection method along geodesics. Manag. Sci. 18(11), 620–631 (1972)
[L15]
D.G. Luenberger, Introduction to Linear and Nonlinear Programming, 1st edn. (Addison-Wesley, Reading, MA, 1973)
[L16]
D.G. Luenberger, Linear and Nonlinear Programming, 2nd edn. (Addison-Wesley, Reading, MA, 1984)
[L17]
D.G. Luenberger, An approach to nonlinear programming. J. Optim. Theory Appl. 11(3), 219–227 (1973)
[171]
Z.Q. Luo, W. Ma, A.M. So, Y. Ye, S. Zhang, Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27, 20–34 (2010)
[L18]
Z.Q. Luo, J. Sturm, S. Zhang, Conic convex programming and self-dual embedding. Optim. Methods Softw. 14, 169–218 (2000)
[L19]
I.J. Lustig, R.E. Marsten, D.F. Shanno, On implementing mehrotra’s predictor-corrector interior point method for linear programming. SIAM J. Optim. 2, 435–449 (1992)
[M1]
N. Maratos, Exact penalty function algorithms for finite dimensional and control optimization problems, Ph.D. thesis, Imperial College Sci. Tech., University of London, 1978
[M2]
G.P. McCormick, Optimality criteria in nonlinear programming, in Nonlinear Programming, SIAM-AMS Proceedings, vol. IX, 1976, pp. 27–38
[M3]
L. McLinden, The analogue of Moreau’s proximation theorem, with applications to the nonlinear complementarity problem. Pac. J. Math. 88, 101–161 (1980)
[M4]
N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming: Interior Point and Related Methods, ed. by N. Megiddo (Springer, New York, 1989), pp. 131–158
[M5]
S. Mehrotra, On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4), 575–601 (1992)
[M6]
S. Mizuno, M.J. Todd, Y. Ye, On adaptive step primal-dual interior point algorithms for linear programming. Math. Oper. Res. 18, 964–981 (1993)
[180]
R.D.C. Monteiro, B.F. Svaiter, Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23, 475–507 (2013)
[M7]
R.D.C. Monteiro, I. Adler, Interior path following primal-dual algorithms: part i: linear programming. Math. Program. 44, 27–41 (1989)
[M8]
D.D. Morrison, Optimization by least squares. SIAM J. Numer. Anal. 5, 83–88 (1968)
[M9]
B.A. Murtagh, Advanced Linear Programming (McGraw-Hill, New York, 1981)
[M10]
B.A. Murtagh, R.W.H. Sargent, A constrained minimization method with quadratic convergence (Chap. 14), in Optimization, ed. by R. Fletcher (Academic, London, 1969)
[M11]
K.G. Murty, Linear and Combinatorial Programming (Wiley, New York, 1976)
[M12]
K.G. Murty, The Karmarkar’s algorithm for linear programming (Chap. 11.4.1), in Linear Complementarity, Linear and Nonlinear Programming. Sigma Series in Applied Mathematics, vol. 3 (Heldermann Verlag, Berlin, 1988), pp. 469–494
[N1]
S.G., Nash, A. Sofer Linear and Nonlinear Programming (McGraw-Hill Companies, New York, 1996)
[188]
Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22, 341–362 (2012)
[189]
Y.E. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9, 141–160 (1998)
[190]
Y. Nesterov, A method of solving a convex programming problem with convergence rate O((1∕k 2)). Soviet Math. Doklady 27(2), 372–376 (1983)
[191]
Y. Nesterov, M.J. Todd, Y. Ye, Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems. Math. Program. 84, 227–267 (1999)
[N2]
Y. Nesterov, A. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms (SIAM Publications, Philadelphia, 1994)
[N3]
Y. Nesterov, M.J. Todd, Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1) 1–42 (1997)
[N4]
Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course (Kluwer, Boston, 2004)
[O1]
W. Orchard-Hays, Background development and extensions of the revised simplex method. RAND Report RM-1433, The RAND Corporation, Santa Monica, CA (1954)
[O2]
A. Orden, Application of the simplex method to a variety of matrix problems, in Directorate of Management Analysis: “Symposium on Linear Inequalities and Programming”, ed. by A. Orden, L. Goldstein (DCS/Comptroller, Headquarters, U.S. Air Force, Washington, DC, 1952), pp. 28–50
[O3]
A. Orden, The transshipment problem. Manag. Sci. 2(3), 276–285 (1956)
[O4]
S.S. Oren, Self-scaling variable metric (ssvm) algorithms ii: implementation and experiments. Manag. Sci. 20, 863–874 (1974)
[O5]
S.S. Oren, D.G. Luenberger, Self-scaling variable metric (ssvm) algorithms i: criteria and sufficient conditions for scaling a class of algorithms. Manag. Sci. 20, 845–862 (1974)
[O6]
S.S. Oren, E. Spedicato, Optimal conditioning of self-scaling variable metric algorithms. Math. Program. 10, 70–90 (1976)
[O7]
J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic, New York, 1970)
[P1]
C.C. Paige, M.A. Saunders, Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12(4), 617–629 (1975)
[P2]
C. Papadimitriou, K. Steiglitz, Combinatorial Optimization Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982)
[204]
P. Parrilo, Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96, 293–320 (2003)
[205]
G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23, 339–358 (1998)
[P3]
A. Perry, A modified conjugate gradient algorithm, Discussion Paper No. 229, Center for Mathematical Studies in Economics and Management Science, North-Western University, Evanston, IL (1976)
[P4]
E. Polak, Computational Methods in Optimization: A Unified Approach (Academic, New York, 1971)
[P5]
E. Polak, G. Ribiere, Note sur la Convergence de Methods de Directions Conjugres. Revue Francaise Informat. Recherche Operationnelle 16, 35–43 (1969)
[P6]
M.J.D. Powell, An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput. J. 7, 155–162 (1964)
[P7]
M.J.D. Powell, A method for nonlinear constraints in minimization problems, in Optimization, ed. by R. Fletcher Powell (Academic, London, 1969), pp. 283–298
[P8]
M.J.D. Powell, On the convergence of the variable metric algorithm. Mathematics Branch, Atomic Energy Research Establishment, Harwell, Berkshire, England, (October 1969)
[P9]
M.J.D. Powell, Algorithms for nonlinear constraints that use lagrangian functions. Math. Program. 14, 224–248 (1978)
[P10]
B.N. Pshenichny, Y.M. Danilin, Numerical Methods in Extremal Problems (translated from Russian by V. Zhitomirsky) (MIR Publishers, Moscow, 1978)
[214]
M. Ramana, An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77, 129–162 (1997)
[215]
M. Ramana, L. Tuncel H. Wolkowicz, Strong duality for semidefinite programming. SIAM J. Optim. 7, 641–662 (1997)
[R1]
J. Renegar, A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Program. 40, 59–93 (1988)
[R2]
J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization (Society for Industrial and Applied Mathematics, Philadelphia, 2001)
[R3]
R.T. Rockafellar, The multiplier method of hestenes and powell applied to convex programming. J. Optim. Theory Appl. 12, 555–562 (1973)
[219]
R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, NJ, 1970)
[R4]
C. Roos, T. Terlaky, J.-Ph. Vial, Theory and Algorithms for Linear Optimization: An Interior Point Approach (Wiley, Chichester, 1997)
[R5]
J. Rosen, The gradient projection method for nonlinear programming, I. Linear contraints. J. Soc. Ind. Appl. Math. 8, 181–217 (1960)
[R6]
J. Rosen, The gradient projection method for nonlinear programming, II. Non-linear constraints. J. Soc. Ind. Appl. Math. 9, 514–532 (1961)
[S1]
R. Saigal, Linear Programming: Modern Integrated Analysis (Kluwer Academic Publisher, Boston, 1995)
[S2]
B. Shah, R. Buehler, O. Kempthorne, Some algorithms for minimizing a function of several variables. J. Soc. Ind. Appl. Math. 12, 74–92 (1964)
[S3]
D.F. Shanno, Conditioning of quasi-Newton methods for function minimization. Math. Comput. 24, 647–656 (1970)
[S4]
D.F. Shanno, Conjugate gradient methods with inexact line searches. Math. Oper. Res. 3(3) 244–2560 (1978)
[S5]
A. Shefi, Reduction of linear inequality constraints and determination of all feasible extreme points, Ph.D. dissertation, Department of Engineering-Economic Systems, Stanford University, Stanford, CA, October 1969
[228]
W.F. Sheppard, On the calculation of the double integral expressing normal correlation. Trans. Camb. Philos. Soc. 19, 23–66 (1900)
[S6]
M. Simonnard, Linear Programming, translated by William S. Jewell (Prentice-Hall, Englewood Cliffs, NJ, 1966)
[S7]
M. Slater, Lagrange multipliers revisited: a contribution to non-linear programming. Cowles Commission Discussion Paper, Math 403 (November 1950)
[231]
A.M. So, Y. Ye, Theory of semidefinite programming for sensor network localization. Math. Program. 109, 367–384 (2007)
[232]
A.M. So, Y. Ye, J. Zhang, A unified theorem on SDP rank reduction. Math. Oper. Res. 33, 910–920 (2008)
[S8]
G. Sonnevend, An ‘analytic center’ for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in System Modelling and Optimization: Proceedings of the 12th IFIP-Conference held in Budapest, Hungary, September 1985, ed. by A. Prekopa, J. Szelezsan, B. Strazicky. Lecture Notes in Control and Information Sciences, vol. 84 (Springer, Berlin, 1986), pp. 866–876
[S9]
G.W. Stewart, A modification of Davidon’s minimization method to accept difference approximations of derivatives. J. ACM 14, 72–83 (1967)
[S10]
E.L. Stiefel, Kernel polynomials in linear algebra and their numerical applications. Nat. Bur. Stand. Appl. Math. Ser. 49, 1–22 (1958)
[S11]
J.F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11&12, 625–633 (1999)
[S12]
J. Sun, L. Qi, An interior point algorithm of \(O(\sqrt{n}\vert \ln (\epsilon )\vert )\) iterations for C 1-convex programming. Math. Program. 57, 239–257 (1992)
[T1]
A. Tamir, Line search techniques based on interpolating polynomials using function values only. Manag. Sci. 22(5), 576–586 (1976)
[T2]
K. Tanabe, Complementarity-enforced centered Newton method for mathematical programming, in New Methods for Linear Programming, ed. by K. Tone (The Institute of Statistical Mathematics, Tokyo, 1987), pp. 118–144
[T3]
R.A. Tapia, Quasi-Newton methods for equality constrained optimization: equivalents of existing methods and new implementation, in Symposium on Nonlinear Programming III, ed. by O. Mangasarian, R. Meyer, S. Robinson (Academic, New York, 1978), pp. 125–164
[T4]
M.J. Todd, A low complexity interior point algorithm for linear programming. SIAM J. Optim. 2, 198–209 (1992)
[T5]
M.J. Todd, Y. Ye, A centered projective algorithm for linear programming. Math. Oper. Res. 15, 508–529 (1990)
[T6]
K. Tone, Revisions of constraint approximations in the successive qp method for nonlinear programming problems. Math. Program. 26(2), 144–152 (1983)
[T7]
D.M. Topkis, A note on cutting-plane methods without nested constraint sets. ORC 69-36, Operations Research Center, College of Engineering, Berkeley, CA (December 1969)
[T8]
D.M. Topkis, A.F. Veinott Jr., On the convergence of some feasible direction algorithms for nonlinear programming. J. SIAM Control 5(2), 268–279 (1967)
[T9]
J.F. Traub, Iterative Methods for the Solution of Equations (Prentice-Hall, Englewood Cliffs, NJ, 1964)
[T10]
L. Tunçel, Constant potential primal-dual algorithms: a framework. Math. Prog. 66, 145–159 (1994)
[T11]
R. Tutuncu, An infeasible-interior-point potential-reduction algorithm for linear programming, Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1995
[T12]
P. Tseng, Complexity analysis of a linear complementarity algorithm based on a Lyapunov function. Math. Program. 53, 297–306 (1992)
[V1]
P.M. Vaidya, An algorithm for linear programming which requires \(O((m + n)n^{2} + (m + n)^{1.5}nL)\) arithmetic operations. Math. Prog. 47, 175–201 (1990). Condensed version in: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 29–38
[V2]
L. Vandenberghe, S. Boyd, Semidefinite programming. SIAM Rev. 38(1) 49–95 (1996)
[V3]
R.J. Vanderbei, Linear Programming: Foundations and Extensions (Kluwer Academic Publishers, Boston, 1997)
[V4]
S.A. Vavasis, Nonlinear Optimization: Complexity Issues (Oxford Science, New York, NY, 1991)
[V5]
A.F. Veinott Jr., The supporting hyperplane method for unimodal programming. Oper. Res. XV 1, 147–152 (1967)
[V6]
Y.V. Vorobyev, Methods of Moments in Applied Mathematics (Gordon and Breach, New York, 1965)
[W1]
D.J. Wilde, C.S. Beightler, Foundations of Optimization (Prentice-Hall, Englewood Cliffs, NJ, 1967)
[W2]
R.B. Wilson, A simplicial algorithm for concave programming, Ph.D. dissertation, Harvard University Graduate School of Business Administration, 1963
[W3]
P. Wolfe, A duality theorem for nonlinear programming. Q. Appl. Math. 19, 239–244 (1961)
[W4]
P. Wolfe, On the convergence of gradient methods under constraints. IBM Research Report RZ 204, Zurich (1966)
[W5]
P. Wolfe, Methods of nonlinear programming (Chap. 6), in Nonlinear Programming, ed. by J. Abadie. Interscience (Wiley, New York, 1967), pp. 97–131
[W6]
P. Wolfe, Convergence conditions for ascent methods. SIAM Rev. 11, 226–235 (1969)
[W7]
P. Wolfe, Convergence theory in nonlinear programming (Chap. 1), in Integer and Nonlinear Programming, ed. by J. Abadie (North-Holland Publishing Company, Amsterdam, 1970)
[W8]
S.J. Wright, Primal-Dual Interior-Point Methods (SIAM, Philadelphia, 1996)
[264]
G. Xue, Y. Ye, Efficient algorithms for minimizing a sum of Euclidean norms with applications. SIAM J. Optim. 7, 1017–1036 (1997)
[265]
Y. Ye, Approximating quadratic programming with bound and quadratic constraints. Math. Program. 84, 219–226 (1999)
[Y1]
Y. Ye, An O(n 3 L) potential reduction algorithm for linear programming. Math. Program. 50, 239–258 (1991)
[Y2]
Y. Ye, M.J. Todd, S. Mizuno, An \(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)
[Y3]
Y. Ye, Interior Point Algorithms (Wiley, New York, 1997)
[269]
Y. Ye, A new complexity result on solving the markov decision problem. Math. Oper. Res. 30, 733–749 (2005)
[Z1]
W.I. Zangwill, Nonlinear programming via penalty functions. Manag. Sci. 13(5), 344–358 (1967)
[Z2]
W.I. Zangwill, Nonlinear Programming: A Unified Approach (Prentice-Hall, Englewood Cliffs, NJ, 1969)
[Z3]
Y. Zhang, D. Zhang, On polynomiality of the mehrotra-type predictor-corrector interior-point algorithms. Math. Program. 68, 303–317 (1995)
[Z4]
G. Zoutendijk, Methods of Feasible Directions (Elsevier, Amsterdam, 1960)
Metadaten
Titel
Duality and Complementarity
verfasst von
David G. Luenberger
Yinyu Ye
Copyright-Jahr
2016
Buch
Linear and Nonlinear Programming

Print ISBN: 978-3-319-18841-6

Electronic ISBN: 978-3-319-18842-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-18842-3_4

Premium Partner

    Bildnachweise