Método del punto interior

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

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

En teoría, su tiempo de ejecución es polinomial , a diferencia del método simplex , que tiene un tiempo de ejecución exponencial en el peor de los casos.
En la práctica, son tan rápidos como el método simplex, a diferencia del método elipsoidal , que en teoría tiene un tiempo de ejecución polinomial, pero es muy lento en la práctica.

A diferencia de los métodos de conjunto activo (como el método simplex), que recorre el límite de la región factible, y del método elipsoidal, que delimita la región factible desde fuera , un IPM alcanza la mejor solución recorriendo el interior de la región factible ; de ahí su nombre.

Historia

Un método de punto interior fue descubierto por el matemático soviético II Dikin en 1967. ^{[ 1 ]} El método fue reinventado en los EE. UU. 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 polinomial ( $O(n^{3.5}L)$ operaciones sobre 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 punto interior. Dos años después, James Renegar inventó el primer método de punto interior de seguimiento de ruta , con tiempo de ejecución $O(n^{3}L)$ . Posteriormente, el método se extendió de problemas de optimización lineal a convexos, basándose en una función de barrera autoconcordante utilizada para codificar el conjunto convexo . ^[³^]

Cualquier problema de optimización convexa puede transformarse en minimizar (o maximizar) una función lineal sobre un conjunto convexo mediante la conversión a la forma de epígrafe . ^{[ 4 ]}^{: 143} La idea de codificar el conjunto factible usando una barrera y diseñar 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 utilizarse para codificar cualquier conjunto convexo. Garantizan que el número de iteraciones del algoritmo está acotado 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 trayectoria primal-dual 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: ${\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimizar}}}\quad &f(x)\\{\text{sujeto a}}\quad &x\in G.\end{aligned}}$ donde f es una función convexa y G es un conjunto convexo . Sin pérdida de generalidad, podemos suponer que la función objetivo f es una función lineal . Por lo general, el conjunto convexo G se representa mediante un conjunto de desigualdades convexas e igualdades lineales; las igualdades lineales se pueden eliminar usando álgebra lineal , por lo que, para simplificar, suponemos que solo hay desigualdades convexas, y el programa se puede describir de la siguiente manera, donde las g _i son funciones convexas: ${\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimizar}}}\quad &f(x)\\{\text{sujeto a}}\quad &g_{i}(x)\leq 0{\text{ para }}i=1,\dots ,m.\\\end{aligned}}$ Suponemos que las funciones de restricción pertenecen a alguna familia (por ejemplo, funciones cuadráticas), de modo que el programa puede representarse mediante un vector finito de coeficientes (por ejemplo, los coeficientes de las funciones cuadráticas). La dimensión de este vector de coeficientes se denomina tamaño del programa. Un solucionador numérico para una familia de programas dada es un algoritmo que, dado el vector de coeficientes, genera una secuencia de soluciones aproximadas x _t para t = 1, 2, ..., utilizando un número finito de operaciones aritméticas. Un solucionador numérico se denomina convergente si, para cualquier programa de la familia y cualquier ε > 0 positivo, existe algún T (que puede depender del programa y de ε ) tal que, para cualquier t > T , la solución aproximada x _t es ε-aproximada, es decir: ${\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{para}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}$ dónde $f^{*}$ es la solución óptima. Un solucionador se denomina polinomial 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 una constante que depende de los datos, por ejemplo, la diferencia entre el valor máximo y el mínimo del conjunto factible. En otras palabras, V / ε es la "precisión relativa" de la solución, es decir, la precisión con respecto al coeficiente más grande. log( V / ε ) representa el número de "dígitos de precisión". Por lo tanto, un solucionador es "polinomial" si cada dígito adicional de precisión requiere un número de operaciones que es polinomial en función del tamaño del problema.

Tipos

Los tipos de métodos de punto interior incluyen:

Métodos de reducción de potencial : El algoritmo de Karmarkar fue el primero.
Métodos de seguimiento de ruta : los algoritmos de James Renegar ^{[ 7 ]} y Clovis Gonzaga ^{[ 8 ]} fueron los primeros.
Métodos primales-duales .

Métodos de seguimiento de trayectoria

Idea

Dado un programa de optimización convexa (P) con restricciones, podemos convertirlo en un programa sin restricciones agregando una función 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}\in {\textbf {G}}\}$ cuyo límite está en la frontera de G : $\lim _{j\to \infty }b(x_{j})=\infty$ . También suponemos que b no es degenerado, es decir: $b''(x)$ es definida positiva para todo x en interior(G). Ahora, consideremos la familia de programas: $P_{t}=t\cdot f(x)+b(x)$

Técnicamente, el programa está restringido, ya que b solo está definido en el interior de G. Sin embargo, en la práctica, es posible resolverlo como un programa sin restricciones, puesto que cualquier solucionador que intente minimizar la función no se aproximará al límite, donde b tiende a infinito. Por lo tanto, ( Pt ₎ tiene una solución única, que denotaremos por x *( t ). La función x * es una función continua de t , denominada trayectoria 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 trayectoria 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 ), de tal manera que la diferencia x _i - x *( t _i ) se aproxime a 0 cuando i se aproxime a infinito; entonces la secuencia x _i se aproxima a la solución óptima de (P). Esto requiere especificar tres cosas:

La función 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 x _i , como el método de Newton . Nótese que podemos usar cada x _i como punto de partida para resolver el siguiente problema ( P _i+1 ).

El principal desafío para demostrar que el método es polinomial radica en que, a medida que aumenta el parámetro de penalización, la solución se aproxima 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 alarga, y resulta difícil demostrar que el tiempo total de ejecución sea polinomial.

Renegar ^{[ 7 ]} y Gonzaga ^{[ 8 ]} demostraron que una instancia específica de un método de seguimiento de ruta es politemporal:

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

Demostraron que, en este caso, la diferencia x _i - x *( t _i ) permanece como máximo 0.01, y f( x _i ) - f* es como máximo ${\frac {2m}{t_{j}}}$ Por lo tanto, la precisión de la solución es proporcional a ${\frac {1}{t_{j}}}$ , por lo que para agregar un solo dígito de precisión, es suficiente multiplicar t _i 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³ ^/ 2n² ) operaciones para ^un dígito de precisión.

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

Detalles

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

minimizar c ^Tx st x en G ,

donde G es convexo y cerrado. También podemos suponer que G es acotado (podemos acotarlo fácilmente añadiendo una restricción | x |≤ R para algún R suficientemente grande ). ^{[ 3 ]}^{: Sec.4}

Para utilizar el método de 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 la función objetivo penalizada f _t (x) := t c ^Tx + b( x ) . Definimos la trayectoria de minimizadores mediante: x*(t) := arg min f _t (x) . Aproximamos esta trayectoria a lo largo de una secuencia creciente t _i . La secuencia se inicializa mediante un procedimiento de inicialización de dos fases no trivial. Luego, se actualiza según la siguiente regla: $t_{i+1}:=\mu \cdot t_{i}$ .

Para cada t _i , 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 proximidad" (donde L es la tolerancia de la trayectoria ):

${\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 hallar x _i₊₁ , partimos de x _i y aplicamos el método de Newton amortiguado . Aplicamos varios pasos de este método hasta que se cumpla la "relación de proximidad" anterior. El primer punto que satisface esta relación se denota por x _i₊₁ . ^{[ 3 ]}^{: Sec.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}

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

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

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

donde el factor constante O(1) depende solo 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}

$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)$

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

$O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)$ donde V es una constante que depende del problema: $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 la 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 se define por las desigualdades g _i ( x ) ≤ 0, entonces necesitamos algún x para el cual g _i ( x ) < 0 para todo i en 1,..., m . Si no tenemos tal punto, necesitamos encontrar uno utilizando un método denominado de fase I. ^{[ 4 ]}^{: 11.4} Un método simple de fase I consiste en resolver el siguiente programa convexo: ${\begin{aligned}{\text{minimizar}}\quad &s\\{\text{sujeto a}}\quad &g_{i}(x)\leq s{\text{ para }}i=1,\dots ,m\end{aligned}}$ Denotemos la solución óptima por x*, 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 es inviable: la región factible está vacía.
Si s *=0 y se alcanza mediante alguna solución x*, entonces el problema es factible pero no tiene punto interior; si no se alcanza, entonces el problema es infactible.

Para este programa, es fácil obtener un punto interior: podemos tomar arbitrariamente x = 0 y s como cualquier número mayor que max( f ₁ (0),..., f _m (0)). Por lo 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, resulta cada vez más difícil encontrar una solución exacta al problema de la fase I y, por consiguiente, determinar si el problema original es factible.

Consideraciones prácticas

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

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 ]}^{: Sec.5}

minimizar c ^Tx 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 cerrado y puntiagudo con un interior no vacío. Todo programa convexo puede convertirse 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 las siguientes suposiciones: ^{[ 3 ]}^{: Sec.6}

A. El conjunto factible { b+L} ∩ K es acotado e interseca 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 óptimo de la función objetivo, c*, del problema.
D. Se nos da una barrera autoconcordante M -logarítmicamente homogénea F para el cono K.

Las suposiciones A, B y D son necesarias en la mayoría de los métodos de punto interior. La suposición C es específica del enfoque de Karmarkar; se puede mitigar utilizando un "valor objetivo deslizante". Es posible reducir aún más el programa al formato de Karmarkar :

minimizar s ^Tx st x en M ∩ K y e ^Tx = 1

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

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

donde F es la barrera M -autoconcordante 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 tal manera que el potencial en cada iteración disminuya 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 requeridos para una solución ε -aproximada es como máximo $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 ${\sqrt {M}}$ en lugar de M , que en teoría es mejor. 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 de lo que garantizan las teorías.

métodos primales-duales

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

${\begin{aligned}\operatorname {minimizar} \quad &f(x)\\{\text{sujeto a}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{\text{ para }}i=1,\ldots ,m,\\{\text{donde}}\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 con restricciones de desigualdad se resuelve convirtiéndolo en una función objetivo sin restricciones cuyo mínimo esperamos encontrar de manera eficiente. Específicamente, la función de barrera logarítmica asociada con (1) es $B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)$

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

El gradiente de una función diferenciable $h:\mathbb {R} ^{n}\to \mathbb {R}$ se denota $\nabla h$ . El gradiente de la función barrera es $\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") $x$ Introducimos una variable dual inspirada en el multiplicador de Lagrange. $\lambda \in \mathbb {R} ^{m}$ $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 semejanza con la "holgura complementaria" en las condiciones KKT .

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

Sustituyendo $1/c_{i}(x)=\lambda _{i}/\mu$ Sustituyendo (4) en (3), obtenemos una ecuación para el gradiente: $\nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)$ donde la matriz $J$ es el jacobiano de las restricciones $c(x)$ .

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

Dejar $(p_{x},p_{\lambda })$ ser la dirección de búsqueda para la actualización iterativa $(x,\lambda )$ Aplicando el método de Newton a (4) y (5), obtenemos una ecuación para $(p_{x},p_{\lambda })$ : ${\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}},$

dónde $H$ es la matriz hessiana de $B(x,\mu )$ , $\operatorname {diag} (\lambda )$ es una matriz diagonal de $\lambda$ , y $\operatorname {diag} (c(x))$ es la matriz diagonal de $c(x)$ .

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

\lambda \geq 0

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

(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 resolubles mediante métodos de punto interior

Aquí se presentan algunos casos especiales de programas convexos que pueden resolverse eficientemente mediante métodos de punto interior. ^{[ 3 ]}^{: Sec.10}

Programas lineales

Consideremos un programa lineal de la forma: ${\begin{aligned}\operatorname {minimize} \quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b.\end{aligned}}.$ Podemos aplicar métodos de seguimiento de trayectoria con la barrera $b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).$ La función $b$ es autoconcordante con el parámetro ^M= m ( el número de restricciones). Por lo tanto, el número de pasos de Newton necesarios para el método de seguimiento de ruta es O( mn² ), y la complejidad de tiempo de ejecución total es O( m³ ^/2n² ⁾ .

Programas cuadráticos con restricciones cuadráticas

Dado un programa cuadrático con restricciones cuadráticas de la forma: ${\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}}$ donde todas las matrices A _j son matrices semidefinidas positivas . Podemos aplicar métodos de seguimiento de trayectoria con la barrera. $b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).$ La función $b$ es una barrera autoconcordante con parámetro M = m . La complejidad de Newton es O( (m+n)n ² ), y la complejidad total del tiempo de ejecución es O( m ^1/2 (m+n) n ² ).

aproximación de la norma L _p

Consideremos un problema de la forma ${\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},$ donde cada $u_{j}$ es un vector, cada $v_{j}$ es un escalar, y $|\cdot |_{p}$ es una norma L _p con $1<p<\infty .$ Después de convertirlo a la forma estándar, podemos aplicar métodos de seguimiento de trayectoria con una barrera autoconcordante con parámetro M = 4 m . La complejidad de Newton es O( (m+n)n ² ), y la complejidad total del tiempo de ejecución es O( m ^1/2 (m+n) n ² ).

Programas geométricos

Consideremos el problema

${\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 trayectoria tiene una complejidad de Newton O( mk ² + k ³ + n ³ ) y una complejidad total O(( k+m ) ^1/2 [ mk ² + k ³ + n ³ ]).

Programas semidefinidos

Los métodos de punto interior se pueden utilizar para resolver programas semidefinidos. ^{[ 3 ]}^{: Sec.11}

Véase también

Referencias

↑ Dikin, II (1967). "Solución iterativa de problemas de programación lineal y cuadrática" . Dokl. Akad. Nauk SSSR . 174 (1): 747– 748. Zbl 0189.19504 .
↑ Karmarkar, N. (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal" (PDF) . Actas del decimosexto simposio anual de la ACM sobre Teoría de la Computación – STOC '84 . p. 302. doi : 10.1145/800057.808695 . ISBN 0-89791-133-4Archivado del original (PDF) el 28 de diciembre de 2013.
1 2 3 4 5 6 7 8 9 10 11 12 13 Arkadi Nemirovsky (2004). Métodos de tiempo polinomial de punto interior en programación convexa .
1 2 3 Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa . Cambridge: Cambridge University Press . ISBN 978-0-521-83378-3MR 2061575 .
↑ 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 Americana . 42 : 39–57 . doi : 10.1090/S0273-0979-04-01040-7 . MR 2115066 .
↑ Potra, Florian A.; Stephen J. Wright (2000). "Métodos de punto interior" . Journal of Computational and Applied Mathematics . 124 ( 1–2 ): 281–302 . Bibcode : 2000JCoAM.124..281P . doi : 10.1016/S0377-0427(00)00433-7 .
1 2 Renegar, James (1 de enero de 1988). "Un algoritmo de tiempo polinomial, basado en el método de Newton, para programación lineal" . Mathematical Programming . 40 (1): 59– 93. doi : 10.1007/BF01580724 . ISSN 1436-4646 .
1 2 Gonzaga, Clovis C. (1989), "Un algoritmo para resolver problemas de programación lineal en O(n3L) operaciones" , en Megiddo, Nimrod (ed.), Progreso en programación matemática: métodos de punto interior y relacionados , Nueva York, NY: Springer, pp. 1–28 , doi : 10.1007/978-1-4613-9617-8_1 , ISBN 978-1-4613-9617-8Consultado el 22 de noviembre de 2023.
↑ Mehrotra, Sanjay (1992). "Sobre la implementación de un método de punto interior primal-dual". SIAM Journal on Optimization . 2 (4): 575– 601. doi : 10.1137/0802028 .
↑ Wright, Stephen (1997). Métodos de punto interior primal-dual . Filadelfia, PA: 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. pp. xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 978-3-540-35445-1MR 2265882 .
Nocedal, Jorge; Stephen Wright (1999). Optimización numérica . Nueva York, NY: Springer. ISBN 978-0-387-98793-4.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Sección 10.11. Programación lineal: métodos de punto interior» . Numerical Recipes: The Art of Scientific Computing (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado del original el 11 de agosto de 2011. Consultado el 12 de agosto de 2011 .

[1] Dikin, II (1967). "Solución iterativa de problemas de programación lineal y cuadrática" . Dokl. Akad. Nauk SSSR . 174 (1): 747– 748. Zbl 0189.19504 .

[2] Karmarkar, N. (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal" (PDF) . Actas del decimosexto simposio anual de la ACM sobre Teoría de la Computación – STOC '84 . p. 302. doi : 10.1145/800057.808695 . ISBN 0-89791-133-4Archivado del original (PDF) el 28 de diciembre de 2013.

[:0-3] 1 2 3 4 5 6 7 8 9 10 11 12 13 Arkadi Nemirovsky (2004). Métodos de tiempo polinomial de punto interior en programación convexa .

[:3-4] 1 2 3 Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa . Cambridge: Cambridge University Press . ISBN 978-0-521-83378-3MR 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 Americana . 42 : 39–57 . doi : 10.1090/S0273-0979-04-01040-7 . MR 2115066 .

[6] Potra, Florian A.; Stephen J. Wright (2000). "Métodos de punto interior" . Journal of Computational and Applied Mathematics . 124 ( 1–2 ): 281–302 . Bibcode : 2000JCoAM.124..281P . doi : 10.1016/S0377-0427(00)00433-7 .

[:1-7] 1 2 Renegar, James (1 de enero de 1988). "Un algoritmo de tiempo polinomial, basado en el método de Newton, para programación lineal" . Mathematical Programming . 40 (1): 59– 93. doi : 10.1007/BF01580724 . ISSN 1436-4646 .

[:2-8] 1 2 Gonzaga, Clovis C. (1989), "Un algoritmo para resolver problemas de programación lineal en O(n3L) operaciones" , en Megiddo, Nimrod (ed.), Progreso en programación matemática: métodos de punto interior y relacionados , Nueva York, NY: Springer, pp. 1–28 , doi : 10.1007/978-1-4613-9617-8_1 , ISBN 978-1-4613-9617-8Consultado el 22 de noviembre de 2023.

[9] Mehrotra, Sanjay (1992). "Sobre la implementación de un método de punto interior primal-dual". SIAM Journal on Optimization . 2 (4): 575– 601. doi : 10.1137/0802028 .

[10] Wright, Stephen (1997). Métodos de punto interior primal-dual . Filadelfia, PA: SIAM. ISBN 978-0-89871-382-4.

[ 1 ]

[ 2 ]

[ 5 ]

[ 6 ]

[ 9 ]

[ 10 ]