About: Interior-point method

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Interior-point method Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. Contrary to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encod

Attributes	Values
rdfs:label	Interior-point method (en)
rdfs:comment	Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. Contrary to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encod (en)
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Optimization_algorithms
Subject	Optimization algorithms and methods
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Interior-point_method?oldid=1069107991&ns=0
Wikipage page ID	1622862 (xsd:integer)
page length (characters) of wiki page	9847 (xsd:nonNegativeInteger)
Wikipage revision ID	1069107991 (xsd:integer)
Link from a Wikipage to another Wikipage	Nonlinear programming Affine scaling Algorithm Arkadi Nemirovski Augmented Lagrangian method Barrier function Self-concordant function Sequential quadratic programming Jacobian matrix and determinant Optimization algorithms and methods Narendra Karmarkar Linear function Linear programming Time complexity Convex optimization Convex set Hessian matrix Newton's method Mehrotra predictor–corrector method Ellipsoid method Epigraph (mathematics) Gradient Karmarkar's algorithm Karush–Kuhn–Tucker conditions Penalty method Diagonal matrix Feasible region Lagrange multiplier Yurii Nesterov Iteration Leonid Khachiyan Simplex algorithm dbr:File:Interior_Point_Trajectory.webm
has abstract	Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. Contrary to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encode the convex set. Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. The idea of encoding the feasible set using a barrier and designing barrier methods was studied by Anthony V. Fiacco, Garth P. McCormick, and others in the early 1960s. These ideas were mainly developed for general nonlinear programming, but they were later abandoned due to the presence of more competitive methods for this class of problems (e.g. sequential quadratic programming). Yurii Nesterov, and Arkadi Nemirovski came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iterations of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution. Karmarkar's breakthrough revitalized the study of interior-point methods and barrier problems, showing that it was possible to create an algorithm for linear programming characterized by polynomial complexity and, moreover, that was competitive with the simplex method.Already Khachiyan's ellipsoid method was a polynomial-time algorithm; however, it was too slow to be of practical interest. The class of primal-dual path-following interior-point methods is considered the most successful.Mehrotra's predictor–corrector algorithm provides the basis for most implementations of this class of methods. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Interior-point_method
is Wikipage redirect of	Interior-point methods Interior point methods Interior point method Primal dual method Barrier method Barrier method (mathematics)
is Link from a Wikipage to another Wikipage of	FortMP Grothendieck inequality Interior-point methods Interior point methods Affine scaling Arkadi Nemirovski Artelys Knitro Augmented Lagrangian method Barrier function Basis pursuit denoising CPLEX James Renegar Differential dynamic programming Donald Knuth Narendra Karmarkar Criss-cross algorithm Linear-fractional programming Linear complementarity problem Linear matrix inequality Linear programming List of numerical analysis topics Constrained optimization Convex optimization List of algorithms Mehrotra predictor–corrector method Ellipsoid method GNU Linear Programming Kit IPM IPOPT Karmarkar's algorithm FICO Xpress Interior point method John von Neumann Klee–Minty cube Memetic algorithm Mathematical optimization Barrier method Barrier method (mathematics)
is known for of	Arkadi Nemirovski John von Neumann
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Interior-point_method

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software