Método del punto interior

Algoritmos para resolver problemas de optimización convexa.

Ejemplo de búsqueda de una solución. Las líneas azules muestran restricciones, los puntos rojos muestran soluciones iteradas.

Los métodos de punto interior (también conocidos como métodos de barrera o IPM ) son algoritmos para resolver problemas de optimización convexa lineal y no lineal . Los IPM combinan dos ventajas de algoritmos previamente conocidos:

• Teóricamente, su tiempo de ejecución es polinómico , a diferencia del método simplex , que tiene un tiempo de ejecución exponencial en el peor de los casos.
• En la práctica, se ejecutan tan rápido como el método simplex, en contraste con el método del elipsoide , que tiene un tiempo de ejecución polinomial en teoría pero es muy lento en la práctica.

A diferencia del método simplex que atraviesa el límite de la región factible y del método del elipsoide que limita la región factible desde el exterior , un IPM alcanza la mejor solución al atravesar el interior de la región factible , de ahí el nombre.

Historia

El matemático soviético II Dikin descubrió un método de punto interior en 1967. ^[1] El método fue reinventado en Estados Unidos a mediados de la década de 1980. En 1984, Narendra Karmarkar desarrolló un método para programación lineal llamado algoritmo de Karmarkar , ^[2] que se ejecuta en tiempo demostrablemente polinomial ( operaciones en números de L bits, donde n es el número de variables y constantes), y también es muy eficiente en la práctica. . El artículo de Karmarkar generó un gran interés en los métodos de puntos interiores. Dos años más tarde, James Renegar inventó el primer método de punto interior de seguimiento de ruta , con tiempo de ejecución . Posteriormente, el método se amplió de problemas de optimización lineal a convexo, basándose en una función de barrera autoconcordante utilizada para codificar el conjunto convexo . ^[3] ${\displaystyle O(n^{3.5}L)}$ ${\displaystyle O(n^{3}L)}$

Cualquier problema de optimización convexa se puede transformar para minimizar (o maximizar) una función lineal sobre un conjunto convexo convirtiéndolo a la forma de epígrafe . ^{[4] : 143} La idea de codificar el conjunto factible utilizando una barrera y diseñando métodos de barrera fue estudiada por Anthony V. Fiacco, Garth P. McCormick y otros a principios de la década de 1960. Estas ideas se desarrollaron principalmente para la programación no lineal general , pero luego fueron abandonadas debido a la presencia de métodos más competitivos para esta clase de problemas (por ejemplo, programación cuadrática secuencial ).

Yurii Nesterov y Arkadi Nemirovski idearon una clase especial de barreras que pueden usarse para codificar cualquier conjunto convexo. Garantizan que el número de iteraciones del algoritmo esté limitado por un polinomio en la dimensión y precisión de la solución. ^{[5] [3]}

La clase de métodos de punto interior de seguimiento de ruta dual primal se considera la más exitosa. El algoritmo predictor-corrector de Mehrotra proporciona la base para la mayoría de las implementaciones de esta clase de métodos. ^[6]

Definiciones

Se nos da un programa convexo de la forma:

$${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &x\in G.\end{aligned}}}$$

función convexaconjunto convexopodemos asumir que el objetivo f es una función linealGg _i

$${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &g_{i}(x)\leq 0{\text{ for }}i=1,\dots ,m.\\\end{aligned}}}$$

vector finito de coeficientestamañosolucionador numéricox _ttconvergenteεTεtTx _tε-aproximado,

f ( x ) - f ^* ≤ ε

g _i ( x ) ≤ ε para i en 1,..., m ,

x en sol ,

donde f ^* es la solución óptima. Un solucionador se llama polinomio si el número total de operaciones aritméticas en los primeros T pasos es como máximo

poli(tamaño del problema) * log( V / ε ),

donde V es alguna constante dependiente de los datos, por ejemplo, la diferencia entre el valor mayor y el menor en el conjunto factible. En otras palabras, V / ε es la "precisión relativa" de la solución: la precisión respecto del coeficiente más grande. log( V / ε ) representa el número de "dígitos de precisión". Por lo tanto, un solucionador es 'polinomio' si cada dígito adicional de precisión requiere un número de operaciones que es polinomio en el tamaño del problema.

Tipos

Los tipos de métodos de puntos interiores incluyen:

• Métodos de reducción potenciales : el algoritmo de Karmarkar fue el primero.
• Métodos de seguimiento de caminos : los algoritmos de James Renegar ^[7] y Clovis Gonzaga ^[8] fueron los primeros.
• Métodos primario-dual .

Métodos de seguimiento de caminos

Idea

Dado un programa de optimización convexo (P) con restricciones, podemos convertirlo en un programa sin restricciones agregando una función de barrera . Específicamente, sea b una función convexa suave, definida en el interior de la región factible G , tal que para cualquier secuencia { x _j en interior (G)} cuyo límite esté en el límite de G :. También asumimos que b no es degenerado, es decir: es definido positivo para todo x en el interior (G). Ahora, considere la familia de programas: ${\displaystyle \lim _{j\to \infty }b(x_{j})=\infty }$ ${\displaystyle b''(x)}$

( P _t ) minimizar t * f(x) + b(x)

Técnicamente el programa está restringido, ya que b está definido sólo en el interior de G . Pero en la práctica, es posible resolverlo como un programa sin restricciones, ya que cualquier solucionador que intente minimizar la función no se acercará a la frontera, donde b tiende a infinito. Por lo tanto, ( P _t ) tiene una solución única: denotarla por x *( t ). La función x * es una función continua de t , que se llama camino central . Todos los puntos límite de x *, cuando t tiende a infinito, son soluciones óptimas del programa original (P).

Un método de seguimiento de ruta es un método para rastrear la función x * a lo largo de una cierta secuencia creciente t ₁ ,t ₂ ,..., es decir: calcular una aproximación suficientemente buena x _i al punto x *( t _i ), tal que la diferencia x _i - x *( t _i ) se acerca a 0 cuando i se acerca al infinito; entonces la secuencia x _i se aproxima a la solución óptima de (P). Esto requiere especificar tres cosas:

• La función de barrera b(x).
• Una política para determinar los parámetros de penalización t _i .
• El solucionador de optimización sin restricciones utilizado para resolver ( _P i ₎ y encontrar xi , como el método de Newton . Tenga en cuenta que podemos usar cada x _i como punto de partida para resolver el siguiente problema ( P _i+1 ).

El principal desafío al demostrar que el método es politiempo es que, a medida que crece el parámetro de penalización, la solución se acerca al límite y la función se vuelve más pronunciada. El tiempo de ejecución de solucionadores como el método de Newton se vuelve más largo y es difícil demostrar que el tiempo de ejecución total es polinómico.

Renegar ^[7] y Gonzaga ^[8] demostraron que un caso específico de un método de seguimiento de ruta es politiempo:

• Las restricciones (y el objetivo) son funciones lineales;
• La función de barrera es logarítmica : b(x) := - suma _j log( -g _j ( x )).
• El parámetro de penalización t se actualiza geométricamente, es decir, donde μ es una constante (tomaron donde m es el número de restricciones de desigualdad); ${\displaystyle t_{i+1}:=\mu \cdot t_{i}}$ ${\displaystyle \mu =1+0.001\cdot {\sqrt {m}}}$
• El solucionador es el método de Newton, y se realiza un solo paso de Newton para cada paso en t .

Demostraron que, en este caso, la diferencia x _i - x *( t _i ) sigue siendo como máximo 0,01, y f( x _i ) - f* es como máximo 2* m / ti _. Por lo tanto, la precisión de la solución es proporcional a 1/ _ti , por lo que para agregar un solo dígito de precisión, es suficiente multiplicar _ti por 2 (o cualquier otro factor constante), lo que requiere O(sqrt( m )) pasos de Newton. . Dado que cada paso de Newton requiere O( mn ² ) operaciones, la complejidad total es O( m ^3/2 n ² ) operaciones para dígitos de precisión.

Yuri Nesterov amplió la idea de los programas lineales a los no lineales. Observó que la propiedad principal de la barrera logarítmica, utilizada en las pruebas anteriores, es que es autoconcordante con un parámetro de barrera finito. Por lo tanto, muchas otras clases de programas convexos se pueden resolver en politiempo utilizando un método de seguimiento de ruta, si podemos encontrar una función de barrera autoconcordante adecuada para su región factible. ^{[3] : Sección 1}

Detalles

Se nos presenta un problema de optimización convexo (P) en "forma estándar":

minimizar c ^T x st x en G ,

donde G es convexo y cerrado. También podemos suponer que G está acotado (podemos hacerlo fácilmente acotado agregando una restricción | x |≤ R para un R suficientemente grande ). ^{[3] : Sección 4}

Para utilizar el método del punto interior, necesitamos una barrera autoconcordante para G. Sea b una barrera M -autoconcordante para G , donde M ≥1 es el parámetro de autoconcordancia. Suponemos que podemos calcular eficientemente el valor de b , su gradiente y su hessiano , para cada punto x en el interior de G.

Para cada t >0, definimos el objetivo penalizado f _t (x) := c ^T x + b( x ) . Definimos la ruta de los minimizadores por: x*(t) := arg min f _t (x) . Aproximamos este camino a lo largo de una secuencia _creciente ti . La secuencia se inicializa mediante un determinado procedimiento de inicialización de dos fases no trivial. Luego, se actualiza según la siguiente regla: . ${\displaystyle t_{i+1}:=\mu \cdot t_{i}}$

Para cada ti _, encontramos un mínimo aproximado de f _ti , denotado por x _i . El mínimo aproximado se elige para satisfacer la siguiente "condición de cercanía" (donde L es la tolerancia de trayectoria ):

${\displaystyle {\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L}$.

Para encontrar x _{i +1} , comenzamos con x _i y aplicamos el método de Newton amortiguado . Aplicamos varios pasos de este método, hasta que se satisfaga la "relación de cercanía" anterior. El primer punto que satisface esta relación se denota por x _{i +1} . ^{[3] : Sección 4}

Convergencia y complejidad

La tasa de convergencia del método viene dada por la siguiente fórmula, para cada i : ^{[3] : Prop.4.4.1}

${\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}}$

Tomando , el número de pasos de Newton necesarios para pasar de x _i a x _{i +1} es como máximo un número fijo, que depende sólo de r y L. En particular, el número total de pasos de Newton necesarios para encontrar una solución aproximada de ε (es decir, encontrar x en G tal que c ^T x - c* ≤ ε ) es como máximo: ^{[3] : Thm.4.4.1} ${\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}$

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)}$

donde el factor constante O(1) depende sólo de r y L . El número de pasos de Newton necesarios para el procedimiento de inicialización de dos pasos es como máximo: ^{[3] : Thm.4.5.1}

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)}$^{[ se necesita aclaración ]}

donde el factor constante O(1) depende sólo de r y L , y , y es algún punto en el interior de G . En general, la complejidad general de Newton para encontrar una solución aproximada de ε es como máximo ${\displaystyle {\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}$ ${\displaystyle {\bar {x}}}$

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)}$, donde V es alguna constante dependiente del problema: . ${\displaystyle V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}}$

Cada paso de Newton requiere O( n ³ ) operaciones aritméticas.

Inicialización: métodos de fase I

Para inicializar los métodos de seguimiento de trayectoria, necesitamos un punto en el interior relativo de la región factible G. En otras palabras: si G está definido por las desigualdades g _i ( x ) ≤ 0, entonces necesitamos algo de x para el cual g _i ( x ) < 0 para todo i en 1,..., m . Si no tenemos ese punto, necesitamos encontrar uno usando el llamado método de fase I. ^{[4] : 11.4} Un método simple de fase I consiste en resolver el siguiente programa convexo:

$${\displaystyle {\begin{aligned}{\text{minimize}}\quad &s\\{\text{subject to}}\quad &g_{i}(x)\leq s{\text{ for }}i=1,\dots ,m\end{aligned}}}$$

s

• Si s *<0, entonces sabemos que x* es un punto interior del problema original y podemos pasar a la "fase II", que es resolver el problema original.
• Si s *>0, entonces sabemos que el programa original no es factible: la región factible está vacía.
• Si s *=0 y se logra mediante alguna solución x*, entonces el problema es factible pero no tiene punto interior; si no se logra, entonces el problema es inviable.

Para este programa es fácil obtener un punto interior: podemos tomar arbitrariamente x =0, y tomar s como cualquier número mayor que max( f ₁ (0),..., f _m (0)). Por tanto, se puede resolver utilizando métodos de punto interior. Sin embargo, el tiempo de ejecución es proporcional a log(1/ s *). A medida que s* se acerca a 0, se vuelve cada vez más difícil encontrar una solución exacta al problema de la fase I y, por tanto, más difícil decidir si el problema original es factible.

Consideraciones prácticas

Las garantías teóricas suponen que el parámetro de penalización aumenta a razón de , por lo que el número de pasos de Newton requeridos en el peor de los casos es . En teoría, si μ es mayor (por ejemplo, 2 o más), entonces el número de pasos de Newton requeridos en el peor de los casos es . Sin embargo, en la práctica, un μ más grande conduce a una convergencia mucho más rápida. Estos métodos se denominan métodos de pasos largos . ^{[3] : Sec.4.6} En la práctica, si μ está entre 3 y 100, entonces el programa converge dentro de 20-40 pasos de Newton, independientemente del número de restricciones (aunque el tiempo de ejecución de cada paso de Newton, por supuesto, crece con el número de restricciones). El valor exacto de μ dentro de este rango tiene poco efecto sobre el rendimiento. ^{[4] : capítulo 11} ${\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}$ ${\displaystyle O({\sqrt {M}})}$ ${\displaystyle O(M)}$

Métodos de reducción de potencial

Para los métodos de reducción de potencial, el problema se presenta en forma cónica : ^{[3] : Sección 5}

minimizar c ^T x st x en {b+L} ᚢ K ,

donde b es un vector en R ⁿ , L es un subespacio lineal en R ⁿ (por lo que b + L es un plano afín ) y K es un cono convexo puntiagudo cerrado con un interior no vacío. Todo programa convexo se puede convertir a la forma cónica. Para utilizar el método de reducción de potencial (específicamente, la extensión del algoritmo de Karmarkar a la programación convexa), necesitamos los siguientes supuestos: ^{[3] : Sección 6}

• A. El conjunto factible {b+L } ᚢ K está acotado y corta el interior del cono K.
• B. Se nos da de antemano una solución estrictamente factible x ^, es decir, una solución factible en el interior de K .
• C. Conocemos de antemano el valor objetivo óptimo, c*, del problema.
• D. Se nos da una barrera F autoconcordante logarítmicamente homogénea para el cono K.

Los supuestos A, B y D son necesarios en la mayoría de los métodos de puntos interiores. El supuesto C es específico del enfoque de Karmarkar; se puede aliviar utilizando un "valor objetivo móvil". Es posible reducir aún más el programa al formato Karmarkar :

minimizar s ^T x st x en M ᚢ K y e ^T x = 1

donde M es un subespacio lineal de en R ⁿ y el valor objetivo óptimo es 0. El método se basa en la siguiente función de potencial escalar :

v ( x ) = F ( x ) + M ln ( s ^T x )

donde F es la barrera autoconcordante M para el cono factible. Es posible demostrar que, cuando x es estrictamente factible y v ( x ) es muy pequeño (-muy negativo), x es aproximadamente óptimo. La idea del método de reducción de potencial es modificar x de manera que el potencial en cada iteración caiga al menos en una constante fija X (específicamente, X =1/3-ln(4/3)). Esto implica que, después de i iteraciones, la diferencia entre el valor objetivo y el valor objetivo óptimo es como máximo V * exp(- i X / M ), donde V es una constante dependiente de los datos. Por lo tanto, el número de pasos de Newton necesarios para una solución aproximada de ε es como máximo . ${\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1}$

Tenga en cuenta que en los métodos de seguimiento de ruta la expresión es en lugar de M , que es mejor en teoría. Pero en la práctica, el método de Karmarkar permite dar pasos mucho mayores hacia el objetivo, por lo que puede converger mucho más rápido que las garantías teóricas. ${\displaystyle {\sqrt {M}}}$

Métodos duales primarios

La idea del método primal-dual es fácil de demostrar para la optimización no lineal restringida . ^{[9] [10]} Para simplificar, considere el siguiente problema de optimización no lineal con restricciones de desigualdad:

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f(x)\\{\text{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{\text{ for }}i=1,\ldots ,m,\\{\text{where}}\quad &f:\mathbb {R} ^{n}\to \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n}\to \mathbb {R} .\end{aligned}}\quad (1)}$$

Este problema de optimización restringido por desigualdad se resuelve convirtiéndolo en una función objetivo no restringida cuyo mínimo esperamos encontrar de manera eficiente. Específicamente, la función de barrera logarítmica asociada con (1) es

$${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}$$

Aquí hay un pequeño escalar positivo, a veces llamado "parámetro de barrera". Cuando converge a cero, el mínimo de debería converger a una solución de (1). ${\displaystyle \mu }$ ${\displaystyle \mu }$ ${\displaystyle B(x,\mu )}$

Se denota el gradiente de una función diferenciable . El gradiente de la función de barrera es ${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle \nabla h}$

$${\displaystyle \nabla B(x,\mu )=\nabla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x).\quad (3)}$$

Además de la variable original ("primal"), introducimos una variable dual inspirada en el multiplicador de Lagrange. ${\displaystyle x}$ ${\displaystyle \lambda \in \mathbb {R} ^{m}}$

$${\displaystyle c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4)}$$

La ecuación (4) a veces se denomina condición de "complementariedad perturbada", por su parecido con la "holgura complementaria" en las condiciones KKT .

Intentamos encontrar aquellos para los cuales el gradiente de la función de barrera es cero. ${\displaystyle (x_{\mu },\lambda _{\mu })}$

Sustituyendo de (4) a (3), obtenemos una ecuación para el gradiente: ${\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }$

$${\displaystyle \nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)}$$

jacobiana ${\displaystyle J}$ ${\displaystyle c(x)}$

La intuición detrás de (5) es que el gradiente de debería estar en el subespacio abarcado por los gradientes de las restricciones. La "complementariedad perturbada" con pequeño (4) puede entenderse como la condición de que la solución debe estar cerca del límite o que la proyección del gradiente sobre la componente de restricción normal debe ser casi cero. ${\displaystyle f(x)}$ ${\displaystyle \mu }$ ${\displaystyle c_{i}(x)=0}$ ${\displaystyle \nabla f}$ ${\displaystyle c_{i}(x)}$

Sea la dirección de búsqueda para la actualización iterativa . Aplicando el método de Newton a (4) y (5), obtenemos una ecuación para : ${\displaystyle (p_{x},p_{\lambda })}$ ${\displaystyle (x,\lambda )}$ ${\displaystyle (p_{x},p_{\lambda })}$

$${\displaystyle {\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-\nabla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},}$$

donde es la matriz de Hesse de , es una matriz diagonal de y es la matriz diagonal de . ${\displaystyle H}$ ${\displaystyle B(x,\mu )}$ ${\displaystyle \operatorname {diag} (\lambda )}$ ${\displaystyle \lambda }$ ${\displaystyle \operatorname {diag} (c(x))}$ ${\displaystyle c(x)}$

Debido a (1), (4) la condición

${\displaystyle \lambda \geq 0}$

debe aplicarse en cada paso. Esto se puede hacer eligiendo apropiado : ${\displaystyle \alpha }$

${\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}$

Trayectoria de las iteraciones de x utilizando el método del punto interior.

Tipos de programas convexos que se pueden resolver mediante métodos de punto interior

A continuación se muestran algunos casos especiales de programas convexos que pueden resolverse eficientemente mediante métodos de puntos interiores. ^{[3] : Sección 10}

Programas lineales

Considere un programa lineal de la forma:

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b.\end{aligned}}.}$$

$${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).}$$

Mmmn ²m ^3/2 n ^{2[ se necesita aclaración ]} ${\displaystyle b}$

Programas cuadráticos restringidos cuadráticamente

Dado un programa cuadrático restringido cuadráticamente de la forma:

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &d^{\top }x\\{\text{subject to}}\quad &f_{j}(x):=x^{\top }A_{j}x+b_{j}^{\top }x+c_{j}\leq 0\quad {\text{ for all }}j=1,\dots ,m,\end{aligned}}}$$

A _jmatrices semidefinidas positivas

$${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).}$$

Mm(m+n)n ²m ^1/2n ² ${\displaystyle b}$

Aproximación a la norma L p

Considere un problema de la forma

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},}$$

norma L pMm(m+n)n ²m ^1/2n ² ${\displaystyle u_{j}}$ ${\displaystyle v_{j}}$ ${\displaystyle |\cdot |_{p}}$ ${\displaystyle 1<p<\infty .}$

Programas geométricos

Considere el problema

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{\top }x)\\{\text{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{\top }x)\leq d_{j}\quad {\text{ for all }}j=1,\dots ,m.\end{aligned}}}$$

Existe una barrera autoconcordante con parámetro 2 k + m . El método de seguimiento de camino tiene complejidad de Newton O ( mk ² + k ³ + n ³ ) y complejidad total O (( k+m ) ^1/2 [ mk ² + k ³ + n ³ ]).

Programas semidefinidos

Los métodos de puntos interiores se pueden utilizar para resolver programas semidefinidos. ^{[3] : Sección 11}

Ver también

• Escalado afín
• Método lagrangiano aumentado
• Algoritmo de Chambolle-Pock
• Condiciones de Karush-Kuhn-Tucker
• Método de penalización

Referencias

1. Dikin, II (1967). "Solución iterativa de problemas de programación lineal y cuadrática". Dokl. Akád. Nauk SSSR . 174 (1): 747–748.
2. Karmarkar, N. (1984). "Un nuevo algoritmo de tiempo polinómico para programación lineal" (PDF) . Actas del decimosexto simposio anual de ACM sobre teoría de la informática - STOC '84 . pag. 302.doi : 10.1145 /800057.808695 . ISBN 0-89791-133-4. Archivado desde el original (PDF) el 28 de diciembre de 2013.
3. Arkadi Nemirovsky (2004). Métodos de tiempo polinómico de puntos interiores en programación convexa.
4. Boyd, Stephen; Vandenberghe, Lieven (2004). Optimizacion convexa . Cambridge: Prensa de la Universidad de Cambridge . ISBN 978-0-521-83378-3. SEÑOR  2061575.
5. Wright, Margaret H. (2004). "La revolución del punto interior en la optimización: historia, desarrollos recientes y consecuencias duraderas". Boletín de la Sociedad Matemática Estadounidense . 42 : 39–57. doi : 10.1090/S0273-0979-04-01040-7 . SEÑOR  2115066.
6. Potra, Florián A.; Stephen J. Wright (2000). "Métodos de punto interior". Revista de Matemática Computacional y Aplicada . 124 (1–2): 281–302. doi : 10.1016/S0377-0427(00)00433-7 .
7. Renegar, James (1 de enero de 1988). "Un algoritmo de tiempo polinómico, basado en el método de Newton, para programación lineal". Programación Matemática . 40 (1): 59–93. doi :10.1007/BF01580724. ISSN  1436-4646.
8. Gonzaga, Clovis C. (1989), Megiddo, Nimrod (ed.), "Un algoritmo para resolver problemas de programación lineal en operaciones O (n3L)", Progreso en programación matemática: punto interior y métodos relacionados , Nueva York, Nueva York: Springer, págs. 1 a 28, doi :10.1007/978-1-4613-9617-8_1, ISBN 978-1-4613-9617-8, consultado el 22 de noviembre de 2023
9. Mehrotra, Sanjay (1992). "Sobre la implementación de un método de punto interior primario-dual". Revista SIAM sobre Optimización . 2 (4): 575–601. doi :10.1137/0802028.
10. Wright, Stephen (1997). "Métodos de punto interior dual-primario ". Filadelfia, Pensilvania: SIAM. ISBN 978-0-89871-382-4.

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimización numérica: Aspectos teóricos y prácticos. Universitext (Segunda edición revisada de la traducción de la edición francesa de 1997). Berlín: Springer-Verlag. págs. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. SEÑOR  2265882.
• Nocedal, Jorge; Stephen Wright (1999). Optimización numérica . Nueva York, Nueva York: Springer. ISBN 978-0-387-98793-4.
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 10.11. Programación lineal: métodos de punto interior". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.