Función autoconcordante

Una función autoconcordante es una función que satisface una cierta desigualdad diferencial , lo que la hace particularmente fácil para la optimización utilizando el método de Newton ^{[1] : Sub.6.2.4.2} Una barrera autoconcordante es una función autoconcordante particular, que también es una función de barrera para un conjunto convexo particular. Las barreras autoconcordantes son ingredientes importantes en los métodos de punto interior para la optimización.

Funciones autoconcordantes

Función autoconcordante multivariante

A continuación se presenta la definición general de una función autoconcordante. ^{[2] : Def.2.0.1}

Sea C un conjunto abierto no vacío convexo en R ⁿ . Sea f una función que es tres veces continuamente diferenciable definida en C . Decimos que f es autoconcordante en C si satisface las siguientes propiedades:

1. Propiedad de barrera : en cualquier secuencia de puntos en C que converge a un punto límite de C , f converge a ∞.

2. Desigualdad diferencial : para cada punto x en C , y cualquier dirección h en R ⁿ , sea g _h la función f restringida a la dirección h , es decir: g _h ( t ) = f ( x + t* h ). Entonces la función unidimensional g _h debe satisfacer la siguiente desigualdad diferencial:

${\displaystyle |g_{h}'''(x)|\leq 2g_{h}''(x)^{3/2}}$.

Equivalentemente: ^[3]

${\displaystyle \left.{\frac {d}{d\alpha }}\nabla ^{2}f(x+\alpha y)\right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)}$

Función autoconcordante univariante

Una función es autoconcordante si: ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }$ ${\displaystyle \mathbb {R} }$

${\displaystyle |f'''(x)|\leq 2f''(x)^{3/2}}$

Equivalentemente: si dondequiera que se cumpla: ${\displaystyle f''(x)>0}$

${\displaystyle \left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1}$

y satisface en otros lugares. ${\displaystyle f'''(x)=0}$

Ejemplos

• Las funciones cuadráticas lineales y convexas son autoconcordantes, ya que su tercera derivada es cero.
• Cualquier función donde está definida y es convexa para todos y verifica , es autoconcordante en su dominio que es . Algunos ejemplos son ${\displaystyle f(x)=-\log(-g(x))-\log x}$ ${\displaystyle g(x)}$ ${\displaystyle x>0}$ ${\displaystyle |g'''(x)|\leq 3g''(x)/x}$ ${\displaystyle \{x\mid x>0,g(x)<0\}}$
  • ${\displaystyle g(x)=-x^{p}}$para ${\displaystyle 0<p\leq 1}$
  • ${\displaystyle g(x)=-\log x}$
  • ${\displaystyle g(x)=x^{p}}$para ${\displaystyle -1\leq p\leq 0}$
  • ${\displaystyle g(x)=(ax+b)^{2}/x}$
  • Para cualquier función que satisfaga las condiciones, la función con también satisface las condiciones. ${\displaystyle g}$ ${\displaystyle g(x)+ax^{2}+bx+c}$ ${\displaystyle a\geq 0}$

Algunas funciones que no son autoconcordantes:

• ${\displaystyle f(x)=e^{x}}$
• ${\displaystyle f(x)={\frac {1}{x^{p}}},x>0,p>0}$
• ${\displaystyle f(x)=|x^{p}|,p>2}$

Barreras autoconcordantes

A continuación se presenta la definición general de una barrera autoconcordante (SCB). ^{[2] : Def.3.1.1}

Sea C un conjunto cerrado convexo en R ⁿ con un interior no vacío. Sea f una función de interior( C ) a R. Sea M > 0 un parámetro real. Decimos que f es una barrera M -autoconcordante para C si satisface lo siguiente:

1. f es una función autoconcordante en el interior ( C ).

2. Para cada punto x en interior( C ), y cualquier dirección h en R ⁿ , sea g _h la función f restringida a la dirección h , es decir: g _h ( t ) = f ( x +t* h ). Entonces la función unidimensional g _h debe satisfacer la siguiente desigualdad diferencial:

${\displaystyle |g_{h}'(x)|\leq M^{1/2}\cdot g_{h}''(x)^{1/2}}$.

Construcción de SCB

Debido a la importancia de los SCB en los métodos de punto interior, es importante saber cómo construir SCB para varios dominios.

En teoría, se puede demostrar que todo dominio convexo cerrado en R ⁿ tiene una barrera autoconcordante con parámetro O( n ). Pero esta “barrera universal” está dada por algunas integrales multivariadas y es demasiado complicada para los cálculos reales. Por lo tanto, el objetivo principal es construir SCB que sean computables de manera eficiente. ^{[4] : Sec.9.2.3.3}

Los SCB se pueden construir a partir de algunos SCB básicos , que se combinan para producir SCB para dominios más complejos, utilizando varias reglas de combinación .

SCB básicos

Toda constante es una barrera autoconcordante para todo R ⁿ , con parámetro M=0. Es la única barrera autoconcordante para todo el espacio, y la única barrera autoconcordante con M < 1. ^{[2] : Ejemplo 3.1.1} [Nótese que las funciones lineales y cuadráticas son funciones autoconcordantes, pero no son barreras autoconcordantes].

Para la semirrecta positiva ( ), es una barrera autoconcordante con parámetro . Esto se puede demostrar directamente a partir de la definición. ${\displaystyle \mathbb {R} _{+}}$ ${\displaystyle x>0}$ ${\displaystyle f(x)=-\ln x}$ ${\displaystyle M=1}$

Regla de sustitución

Sea G un dominio convexo cerrado en R ⁿ , y g un M -SCB para G . Sea x = Ay + b una función afín de R ^k a R ⁿ con su imagen intersectando el interior de G . Sea H la imagen inversa de G bajo la función: H = { y en R ^k | Ay+b en G }. Sea h la función compuesta h ( y ) := g( Ay + b ). Entonces, h es un M -SCB para H . ^{[2] : Prop.3.1.1}

Por ejemplo, tome n = 1, G la semirrecta positiva y . Para cualquier k , sea a un vector de k elementos y b un escalar. Sea H = { y en R ^k | a ^T y+b ≥ 0} = un semiespacio k -dimensional. Por la regla de sustitución, es un 1-SCB para H . Un formato más común es H = { x en R ^k | a ^T x ≤ b}, para el cual el SCB es . ${\displaystyle g(x)=-\ln x}$ ${\displaystyle h(y)=-\ln(a^{T}y+b)}$ ${\displaystyle h(y)=-\ln(b-a^{T}y)}$

La regla de sustitución se puede extender desde aplicaciones afines a una cierta clase de aplicaciones "apropiadas", ^{[2] : Thm.9.1.1} y a aplicaciones cuadráticas. ^{[2] : Sub.9.3}

Regla del producto cartesiano

Para todo i en 1,..., m , sea G _i un dominio convexo cerrado en R ⁿⁱ , y sea g _i un M _i -SCB para G _i . Sea G el producto cartesiano de todo G _i . Sea g(x ₁ ,...,x _m )  := suma _i g _i ( x _i ). Entonces, g es un SCB para G , con parámetro suma _i M _i . ^{[2] : Prop.3.1.1}

Por ejemplo, supongamos que todos _los Gi son semirrectas positivas, de modo que G es el ortante positivo . Sea un m -SCB para G. ${\displaystyle \mathbb {R} _{+}^{m}}$ ${\displaystyle g(x)=-\sum _{i=1}^{m}\ln x_{i}}$

Ahora podemos aplicar la regla de sustitución. Obtenemos que, para el politopo definido por las desigualdades lineales a _j ^T x ≤ b _j para j en 1,..., m , si satisface la condición de Slater , entonces es un m -SCB. Las funciones lineales pueden ser reemplazadas por funciones cuadráticas . ${\displaystyle f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)}$ ${\displaystyle b_{j}-a_{j}^{T}x}$

Regla de intersección

Sean G ₁ ,..., G _m dominios convexos cerrados en R ⁿ . Para cada i en 1,..., m , sea g _i un M _i -SCB para G _i , y r _i un número real. Sea G la intersección de todos los G _i , y supongamos que su interior no está vacío. Sea g  := sum _i r _i *g _i . Entonces, g es un SCB para G , con parámetro sum _i r _i *M _i . ^{[2] : Prop.3.1.1}

Por lo tanto, si G está definido por una lista de restricciones, podemos encontrar un SCB para cada restricción por separado y luego simplemente sumarlas para obtener un SCB para G.

Por ejemplo, supongamos que el dominio está definido por m restricciones lineales de la forma a _j ^T x ≤ b _j , para j en 1,..., m . Entonces podemos usar la regla de intersección para construir el m -SCB (el mismo que calculamos previamente usando la regla del producto cartesiano). ${\displaystyle f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)}$

SCB para epígrafes

El epígrafe de una función f ( x ) es el área que se encuentra por encima de la gráfica de la función, es decir, . El epígrafe de f es un conjunto convexo si y solo si f es una función convexa . Los siguientes teoremas presentan algunas funciones f para las cuales el epígrafe tiene un SCB. ${\displaystyle \{(x,t)\in \mathbb {R} ^{2}:t\geq f(x)\}}$

Sea g ( t ) una función cóncava 3 veces continuamente diferenciable en t > 0, tal que está acotada por una constante (denotada 3* b ) para todo t > 0. Sea G el dominio convexo bidimensional: Entonces, la función f ( x , t ) = -ln(f(t)-x) - max[1,b ² ]*ln(t) es una barrera autoconcordante para G , con parámetro (1+max[1,b ² ]). ^{[2] : Prop.9.2.1} ${\displaystyle t\cdot |g'''(t)|/|g''(t)|}$ ${\displaystyle G={\text{closure}}(\{(x,t)\in \mathbb {R} ^{2}:t>0,x\leq g(t)\}).}$

Ejemplos:

• Sea g ( t ) = t ^{1/ p} , para algún p ≥1, y b =(2 p -1)/(3 p ). Entonces tiene un 2-SCB. De manera similar, tiene un 2-SCB. Usando la regla de intersección, obtenemos que tiene un 4-SCB. ${\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:(x_{+})^{p}\leq t\}}$ ${\displaystyle G_{2}=\{(x,t)\in \mathbb {R} ^{2}:([-x]_{+})^{p}\leq t\}}$ ${\displaystyle G=G_{1}\cap G_{2}=\{(x,t)\in \mathbb {R} ^{2}:|x|^{p}\leq t\}}$
• Sea g ( t )=ln( t ) y b =2/3. Entonces tiene un 2-SCB. ${\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:e^{x}\leq t\}}$

Ahora podemos construir una SCB para el problema de minimizar la p -norma: , donde v _j son escalares constantes, u _j son vectores constantes y p >0 es una constante. Primero la convertimos en minimización de un objetivo lineal: , con las restricciones: para todo j en [ m ]. Para cada restricción, tenemos una 4-SCB por la regla de sustitución afín. Usando la regla de intersección, obtenemos una (4 n )-SCB ​​para todo el dominio factible. ${\displaystyle \min _{x}\sum _{j=1}^{n}|v_{j}-x^{T}u_{j}|^{p}}$ ${\displaystyle \min _{x}\sum _{j=1}^{n}t_{j}}$ ${\displaystyle t_{j}\geq |v_{j}-x^{T}u_{j}|^{p}}$

De manera similar, sea g una función convexa 3 veces continuamente diferenciable en el rayo x > 0, tal que: para todo x > 0. Sea G el dominio convexo bidimensional: closure({ ( t,x ) in R ² : x>0, t ≥ g ( x ) }). Entonces, la función f ( x , t ) = -ln(tf(x)) - max[1,b ² ]*ln(x) es una barrera autoconcordante para G, con parámetro (1+max[1,b ² ]). ^{[2] : Prop.9.2.2} ${\displaystyle x\cdot |g'''(x)|/|g''(x)|\leq 3b}$

Ejemplos:

• Sea g ( x ) = x ^{- p} , para algún p > 0, y b = (2+ p )/3. Entonces tiene un 2-SCB. ${\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:x^{-p}\leq t,x\geq 0\}}$
• Sea g ( x )= x ln( x ) y b = 1/3. Entonces tiene un 2-SCB. ${\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:x\ln x\leq t,x\geq 0\}}$

SCB para conos

• Para el cono de segundo orden , la función es una barrera autoconcordante. ${\displaystyle \{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}}$ ${\displaystyle f(x,y)=-\log(y^{2}-x^{T}x)}$
• Para el cono de matrices simétricas semidefinidas positivas m*m, la función es una barrera autoconcordante. ${\displaystyle f(A)=-\log \det A}$
• Para la región cuadrática definida por donde es una matriz simétrica semidefinida positiva , la barrera logarítmica es autoconcordante con ${\displaystyle \phi (x)>0}$ ${\displaystyle \phi (x)=\alpha +\langle a,x\rangle -{\frac {1}{2}}\langle Ax,x\rangle }$ ${\displaystyle A=A^{T}\geq 0}$ ${\displaystyle f(x)=-\log \phi (x)}$ ${\displaystyle M=2}$
• Para el cono exponencial , la función es una barrera autoconcordante. ${\displaystyle \{(x,y,z)\in \mathbb {R} ^{3}\mid ye^{x/y}\leq z,y>0\}}$ ${\displaystyle f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y}$
• Para el cono de potencia , la función es una barrera autoconcordante. ${\displaystyle \{(x_{1},x_{2},y)\in \mathbb {R} _{+}^{2}\times \mathbb {R} \mid |y|\leq x_{1}^{\alpha }x_{2}^{1-\alpha }\}}$ ${\displaystyle f(x_{1},x_{2},y)=-\log(x_{1}^{2\alpha }x_{2}^{2(1-\alpha )}-y^{2})-\log x_{1}-\log x_{2}}$

Historia

Como se menciona en los "Comentarios de la bibliografía" ^[5] de su libro de 1994, ^[6] las funciones autoconcordantes fueron introducidas en 1988 por Yurii Nesterov ^{[7] [8]} y desarrolladas posteriormente por Arkadi Nemirovski . ^[9] Como se explica en ^[10] su observación básica fue que el método de Newton es invariante afín, en el sentido de que si para una función tenemos pasos de Newton entonces para una función donde es una transformación lineal no degenerada, a partir de tenemos los pasos de Newton que se pueden mostrar recursivamente. ${\displaystyle f(x)}$ ${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})}$ ${\displaystyle \phi (y)=f(Ay)}$ ${\displaystyle A}$ ${\displaystyle y_{0}=A^{-1}x_{0}}$ ${\displaystyle y_{k}=A^{-1}x_{k}}$

${\displaystyle y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k+1}}$.

Sin embargo, el análisis estándar del método de Newton supone que la hessiana de es Lipschitz continua , es decir, para alguna constante . Si suponemos que es 3 veces continuamente diferenciable, entonces esto es equivalente a ${\displaystyle f}$ ${\displaystyle \|f''(x)-f''(y)\|\leq M\|x-y\|}$ ${\displaystyle M}$ ${\displaystyle f}$

${\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}}$a pesar de ${\displaystyle u,v\in \mathbb {R} ^{n}}$

donde . Entonces, el lado izquierdo de la desigualdad anterior es invariante bajo la transformación afín , sin embargo, el lado derecho no lo es. ${\displaystyle f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]}$ ${\displaystyle f(x)\to \phi (y)=f(Ay),u\to A^{-1}u,v\to A^{-1}v}$

Los autores señalan que el lado derecho también puede hacerse invariante si reemplazamos la métrica euclidiana por el producto escalar definido por el hessiano de definido como para . Llegan entonces a la definición de una función autoconcordante como ${\displaystyle f}$ ${\displaystyle \|w\|_{f''(x)}=\langle f''(x)w,w\rangle ^{1/2}}$ ${\displaystyle w\in \mathbb {R} ^{n}}$

${\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}}$.

Propiedades

Combinación lineal

Si y son autoconcordantes con las constantes y y , entonces es autoconcordante con la constante . ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$ ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle \alpha ,\beta >0}$ ${\displaystyle \alpha f_{1}+\beta f_{2}}$ ${\displaystyle \max(\alpha ^{-1/2}M_{1},\beta ^{-1/2}M_{2})}$

Transformación afín

Si es autoconcordante con la constante y es una transformación afín de , entonces también es autoconcordante con el parámetro . ${\displaystyle f}$ ${\displaystyle M}$ ${\displaystyle Ax+b}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \phi (x)=f(Ax+b)}$ ${\displaystyle M}$

Conjugado convexo

Si es autoconcordante, entonces su conjugado convexo también es autoconcordante. ^{[11] [12]} ${\displaystyle f}$ ${\displaystyle f^{*}}$

Hessiano no singular

Si es autoconcordante y el dominio de no contiene ninguna línea recta (infinito en ambas direcciones), entonces no es singular. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f''}$

Por el contrario, si para algunos en el dominio de y tenemos , entonces para todos para los cuales está en el dominio de y entonces es lineal y no puede tener un máximo por lo que todos de está en el dominio de . Observamos también que no puede tener un mínimo dentro de su dominio. ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle u\in \mathbb {R} ^{n},u\neq 0}$ ${\displaystyle \langle f''(x)u,u\rangle =0}$ ${\displaystyle \langle f''(x+\alpha u)u,u\rangle =0}$ ${\displaystyle \alpha }$ ${\displaystyle x+\alpha u}$ ${\displaystyle f}$ ${\displaystyle f(x+\alpha u)}$ ${\displaystyle x+\alpha u,\alpha \in \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle f}$

Aplicaciones

Entre otras cosas, las funciones autoconcordantes son útiles en el análisis del método de Newton . Las funciones de barrera autoconcordantes se utilizan para desarrollar las funciones de barrera utilizadas en los métodos de punto interior para la optimización convexa y no lineal. El análisis habitual del método de Newton no funcionaría para las funciones de barrera, ya que su segunda derivada no puede ser Lipschitz continua, de lo contrario estarían acotadas en cualquier subconjunto compacto de . ${\displaystyle \mathbb {R} ^{n}}$

Funciones de barrera autoconcordantes

• Son una clase de funciones que pueden usarse como barreras en métodos de optimización restringida.
• se puede minimizar utilizando el algoritmo de Newton con propiedades de convergencia demostrables análogas al caso habitual (pero estos resultados son algo más difíciles de derivar)
• Para tener ambas cosas anteriores, el límite constante habitual en la tercera derivada de la función (requerido para obtener los resultados de convergencia habituales para el método de Newton) se reemplaza por un límite relativo al hessiano.

Minimizar una función autoconcordante

Una función autoconcordante puede minimizarse con un método de Newton modificado en el que tenemos un límite en el número de pasos necesarios para la convergencia. Suponemos aquí que es una función autoconcordante estándar , es decir, es autoconcordante con el parámetro . ${\displaystyle f}$ ${\displaystyle M=2}$

Definimos el decremento de Newton de at como el tamaño del paso de Newton en la norma local definida por el hessiano de at ${\displaystyle \lambda _{f}(x)}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle [f''(x)]^{-1}f'(x)}$ ${\displaystyle f}$ ${\displaystyle x}$

${\displaystyle \lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2}}$

Entonces , en el dominio de , si entonces es posible demostrar que la iteración de Newton ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle \lambda _{f}(x)<1}$

${\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)}$

también estará en el dominio de . Esto se debe a que, en base a la autoconcordancia de , es posible dar algunos límites finitos al valor de . Además, tenemos ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f(x_{+})}$

${\displaystyle \lambda _{f}(x_{+})\leq {\Bigg (}{\frac {\lambda _{f}(x)}{1-\lambda _{f}(x)}}{\Bigg )}^{2}}$

Entonces si tenemos

${\displaystyle \lambda _{f}(x)<{\bar {\lambda }}={\frac {3-{\sqrt {5}}}{2}}}$

entonces también se garantiza que , de modo que podemos seguir usando el método de Newton hasta la convergencia. Nótese que para para algunos tenemos convergencia cuadrática de a 0 como . Esto entonces da convergencia cuadrática de a y de a , donde , por el siguiente teorema. Si entonces ${\displaystyle \lambda _{f}(x_{+})<\lambda _{f}(x)}$ ${\displaystyle \lambda _{f}(x_{+})<\beta }$ ${\displaystyle \beta \in (0,{\bar {\lambda }})}$ ${\displaystyle \lambda _{f}}$ ${\displaystyle \lambda _{f}(x_{+})\leq (1-\beta )^{-2}\lambda _{f}(x)^{2}}$ ${\displaystyle f(x_{k})}$ ${\displaystyle f(x^{*})}$ ${\displaystyle x}$ ${\displaystyle x^{*}}$ ${\displaystyle x^{*}=\arg \min f(x)}$ ${\displaystyle \lambda _{f}(x)<1}$

${\displaystyle \omega (\lambda _{f}(x))\leq f(x)-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))}$

${\displaystyle \omega '(\lambda _{f}(x))\leq \|x-x^{*}\|_{x}\leq \omega _{*}'(\lambda _{f}(x))}$

con las siguientes definiciones

${\displaystyle \omega (t)=t-\log(1+t)}$

${\displaystyle \omega _{*}(t)=-t-\log(1-t)}$

${\displaystyle \|u\|_{x}=\langle f''(x)u,u\rangle ^{1/2}}$

Si comenzamos el método de Newton desde algún punto con entonces tenemos que comenzar utilizando un método de Newton amortiguado definido por ${\displaystyle x_{0}}$ ${\displaystyle \lambda _{f}(x_{0})\geq {\bar {\lambda }}}$

${\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}$

Para esto se puede demostrar que con como se definió anteriormente. Nótese que es una función creciente para de modo que para cualquier , por lo que se garantiza que el valor de disminuirá en una cierta cantidad en cada iteración, lo que también demuestra que está en el dominio de . ${\displaystyle f(x_{k+1})\leq f(x_{k})-\omega (\lambda _{f}(x_{k}))}$ ${\displaystyle \omega }$ ${\displaystyle \omega (t)}$ ${\displaystyle t>0}$ ${\displaystyle \omega (t)\geq \omega ({\bar {\lambda }})}$ ${\displaystyle t\geq {\bar {\lambda }}}$ ${\displaystyle f}$ ${\displaystyle x_{k+1}}$ ${\displaystyle f}$

Referencias

1. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .
2. Arkadi Nemirovsky (2004). "Métodos de tiempo polinomial de punto interior en programación convexa".
3. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Recuperado el 15 de octubre de 2011 .
4. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .
5. Nesterov, Yurii; Nemirovskii, Arkadii (enero de 1994). Algoritmos polinomiales de punto interior en programación convexa (comentarios bibliográficos). Sociedad de Matemáticas Industriales y Aplicadas. doi :10.1137/1.9781611970791.bm. ISBN 978-0-89871-319-0.
6. Nesterov, I︠U︡. E. (1994). Algoritmos polinomiales de punto interior en programación convexa. Nemirovskiĭ, Arkadiĭ Semenovich. Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 0-89871-319-6.OCLC 29310677  .
7. Yu. E. NESTEROV, Métodos de tiempo polinomial en programación lineal y cuadrática, Izvestija AN SSSR, Tekhnitcheskaya kibernetika, No. 3, 1988, pp. 324-326. (En ruso.)
8. Yu. E. NESTEROV, Métodos iterativos en tiempo polinomial en programación lineal y cuadrática, Voprosy kibernetiki, Moscú, 1988, págs. 102-125. (En ruso.)
9. YE Nesterov y AS Nemirovski, Funciones autoconcordantes y métodos de tiempo polinomial en programación convexa, Informe técnico, Instituto Central Económico y Matemático, Academia de Ciencias de la URSS, Moscú, URSS, 1989.
10. Nesterov, I︠U︡. E. Lecciones introductorias sobre optimización convexa: un curso básico. Boston. ISBN 978-1-4419-8853-9.OCLC 883391994  .
11. Nesterov, Yurii; Nemirovskii, Arkadii (1994). "Algoritmos polinomiales de punto interior en programación convexa". Estudios en matemáticas numéricas y aplicadas . doi :10.1137/1.9781611970791. ISBN . 978-0-89871-319-0.
12. Sun, Tianxiao; Tran-Dinh, Quoc (2018). "Funciones autoconcordantes generalizadas: una receta para métodos de tipo Newton". Programación matemática : Proposición 6. arXiv : 1703.04599 .