Método de puntos interiores

Algoritmos para resolver problemas de optimización convexa

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

Los métodos de punto interior (también denominados 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 los algoritmos conocidos anteriormente:

• 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, se ejecutan tan rápido como el método símplex, a diferencia del método 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 recorre el límite de la región factible, y del método elipsoide, que limita la región factible desde afuera , un IPM alcanza la mejor solución al recorrer 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 se reinventó 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 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 creó una oleada de interés en los métodos de punto interior. Dos años más tarde, James Renegar inventó el primer método de punto interior de seguimiento de trayectorias , con tiempo de ejecución . El método se extendió más tarde de problemas de optimización lineal a convexos, 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 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 utilizando 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 se abandonaron debido a la presencia de métodos más competitivos para esta clase de problemas (por ejemplo, la programación cuadrática secuencial ).

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

La clase de métodos de seguimiento de trayectorias de punto interior 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: donde f es una función convexa y G es un conjunto convexo . Sin pérdida de generalidad, podemos suponer que el 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 utilizando álgebra lineal, por lo que para simplificar suponemos que solo hay desigualdades convexas, y el programa se puede describir de la siguiente manera, donde g _i son funciones convexas: Suponemos que las funciones de restricción pertenecen a alguna familia (por ejemplo, funciones cuadráticas), de modo que el programa se puede representar 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 dada de programas 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 ε positivo > 0, 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: donde es la solución óptima. Un solucionador se denomina polinómico si el número total de operaciones aritméticas en los primeros T pasos es como máximo $${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &x\in G.\end{aligned}}}$$ $${\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}}}$$ $${\displaystyle {\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{for}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}}$$ ${\displaystyle f^{*}}$

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

donde V es una constante dependiente de los datos, por ejemplo, la diferencia entre el valor más grande y el más pequeño del conjunto factible. En otras palabras, V / ε es la "precisión relativa" de la solución (la precisión con respecto al coeficiente más grande). log( V / ε ) representa la cantidad de "dígitos de precisión". Por lo tanto, un solucionador es "polinómico" si cada dígito adicional de precisión requiere una cantidad de operaciones que es polinómica en el tamaño del problema.

Tipos

Los tipos de métodos de puntos interiores incluyen:

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

Métodos de seguimiento de trayectorias

Idea

Dado un programa de optimización convexa (P) con restricciones, podemos convertirlo en un programa sin restricciones añadiendo una función de barrera . En concreto, 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 la frontera de G : . También suponemos que b no es degenerada, es decir: es definida positiva para todo x en interior(G). Ahora, consideremos 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 solo en el interior de G . Pero prácticamente, es posible resolverlo como un programa sin restricciones, ya que cualquier solucionador que intente minimizar la función no se acercará al límite, donde b tiende al infinito. Por lo tanto, ( P _t ) tiene una solución única - denotándola 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 al infinito, son soluciones óptimas del programa original (P).

Un método de seguimiento de trayectorias es un método de seguimiento de la función x * a lo largo de una cierta secuencia creciente t1 _, t2 _, ..., es decir: calcular una aproximación suficientemente buena x _i al punto x *( t _i ), de modo que la diferencia x _i - x *( t _i ) se acerque a 0 cuando i se aproxima al 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 . 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 para demostrar que el método es polinómico es que, a medida que el parámetro de penalización crece, la solución se acerca al límite y la función se vuelve más empinada. El tiempo de ejecución de los solucionadores como el método de Newton se hace 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 una instancia específica de un método de seguimiento de trayectoria es politemporal:

• 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 por cada paso 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 2* m / t _i . Por lo tanto, la precisión de la solución es proporcional a 1/ t _i , 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. Como cada paso de Newton requiere O( mn ² ) operaciones, la complejidad total es O( m ^3/2 n ² ) operaciones por 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 se pueden resolver en politiempo utilizando un método de seguimiento de trayectorias, si podemos encontrar una función de barrera autoconcordante adecuada para su región factible. ^{[3] : Sec.1}

Detalles

Se nos presenta un problema de optimización convexa (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 acotarlo fácilmente añadiendo una restricción | x |≤ R para un R suficientemente grande ). ^{[3] : Sec.4}

Para utilizar el método de puntos interiores, necesitamos una barrera autoconcordante para G . Sea b una barrera autoconcordante M para G , donde M ≥1 es el parámetro de autoconcordancia. Suponemos que podemos calcular de manera eficiente 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 minimizadores mediante: x*(t) := arg min f _t (x) . Aproximamos esta ruta a lo largo de una secuencia creciente t _i . La secuencia se inicializa mediante un determinado procedimiento de inicialización de dos fases no trivial. Luego, se actualiza de acuerdo con la siguiente regla: . ${\displaystyle 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 ):

${\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 hallar 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 satisface la "relación de proximidad" anterior. El primer punto que satisface esta relación se denota por x _{i +1} . ^{[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}

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

Si tomamos , el número de pasos de Newton necesarios para ir 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 (es decir, encontrar x en G tal que c ^T x - c* ≤ ε ) es como máximo: ^{[3] : Teoría 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 únicamente 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] : Teoría 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)}$^{[ aclaración necesaria ]}

donde el factor constante O(1) depende únicamente 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 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 una 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 trayectorias, 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 dicho punto, necesitamos encontrar uno usando el llamado método de fase I . ^{[4] : 11.4} Un método de fase I simple es resolver el siguiente programa convexo: Denotemos la solución óptima por x*, s *. $${\displaystyle {\begin{aligned}{\text{minimize}}\quad &s\\{\text{subject to}}\quad &g_{i}(x)\leq s{\text{ for }}i=1,\dots ,m\end{aligned}}}$$

• 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 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 tomar 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, se hace cada vez más difícil encontrar una solución exacta al problema de la fase I y, por lo 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 se incrementa a una tasa , 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 está en . Sin embargo, en la práctica, un μ mayor 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, 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 en el rendimiento. ^{[4] : cap.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] : Sec.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 las siguientes suposiciones: ^{[3] : Sec.6}

• A. El conjunto factible {b+L} ᚢ K está 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 objetivo óptimo, c*, del problema.
• D. Se nos da una barrera autoconcordante M - logarítmicamente homogénea F 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 deslizante". Es posible reducir aún más el programa al formato de 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 potencial escalar :

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

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ña (- muy negativa), x es aproximadamente óptima. La idea del método de reducción de potencial es modificar x de modo 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 es como máximo . ${\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1}$

Obsérvese que en los métodos de seguimiento de trayectorias la expresión es en lugar de M , lo 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 primal-duales

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 desigualdades se resuelve convirtiéndolo en una función objetivo sin restricciones cuyo mínimo esperamos encontrar de manera eficiente. En concreto, 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". Como converge a cero, el mínimo de debería converger a una solución de (1). ${\displaystyle \mu }$ ${\displaystyle \mu }$ ${\displaystyle B(x,\mu )}$

El gradiente de una función diferenciable se denota por . El gradiente de la función 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 que el gradiente de la función barrera es cero. ${\displaystyle (x_{\mu },\lambda _{\mu })}$

Sustituyendo (4) en (3), obtenemos una ecuación para el gradiente: donde la matriz es el jacobiano de las restricciones . ${\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)}$$ ${\displaystyle J}$ ${\displaystyle c(x)}$

La intuición detrás de (5) es que el gradiente de debe estar en el subespacio abarcado por los gradientes de las restricciones. La "complementariedad perturbada" con (4) pequeña 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 normal del componente de restricción 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 actualizar iterativamente . 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 hessiana 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}$

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

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

Trayectoria de los iterados de x utilizando el método del punto interior.

Tipos de programas convexos que se pueden resolver mediante métodos de puntos interiores

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

Programas lineales

Consideremos un programa lineal de la forma: Podemos aplicar métodos de seguimiento de trayectorias con la barrera La función 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 trayectorias es O( mn ² ), y la complejidad total del tiempo de ejecución es O( m ^3/2 n ² ). ^{[ aclaración necesaria ]} $${\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).}$$ ${\displaystyle b}$

Programas cuadráticos con restricciones cuadráticas

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

yopagaproximación de norma

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

Véase también

• Escala 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. Akad. Nauk SSSR . 174 (1): 747–748.
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 desde el original (PDF) el 28 de diciembre de 2013.
3. Arkadi Nemirovsky (2004). Métodos de tiempo polinomial de punto interior en programación convexa.
4. Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa . Cambridge: Cambridge University Press . ISBN 978-0-521-83378-3.Sr. 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 American Mathematical Society . 42 : 39–57. doi : 10.1090/S0273-0979-04-01040-7 . MR  2115066.
6. Potra, Florian A.; Stephen J. Wright (2000). "Métodos de puntos interiores". 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 polinomial, 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)", Progress in Mathematical Programming: Interior-Point and Related Methods , Nueva York, NY: Springer, págs. 1–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 dual-primal". Revista SIAM sobre optimización . 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.

• 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-1.Señor 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 puntos interiores". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado desde el original el 11 de agosto de 2011 . Consultado el 12 de agosto de 2011 .