Función autoconcordante

Una función autoconcordante es una función que satisface una cierta desigualdad diferencial , lo que hace que sea particularmente fácil de optimizar usando 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 optimización de puntos interiores .

Funciones autoconcordantes

Función multivariante autoconcordante

Aquí está la definición general de una función autoconcordante. ^{[2] : Definición 2.0.1}

Sea C un conjunto abierto no vacío convexo en R ⁿ . Sea f una función tres veces diferenciable continuamente definida en C . Decimos que f es autoconcordante con 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 todo 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 debería 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 univariada autoconcordante

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 satisfaga: ${\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 que esté definida y sea convexa para todos y se verifique , 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 cumpla 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

Aquí está la definición general de barrera autoconcordante (SCB). ^{[2] : Definición 3.1.1}

Sea C un conjunto cerrado convexo en R ⁿ con un interior no vacío. Sea f una función desde el interior ( C ) hasta 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 el 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 debería satisfacer la siguiente desigualdad diferencial:

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

Construyendo SCB

Debido a la importancia de los SCB en los métodos de puntos interiores, es importante saber cómo construir SCB para diversos dominios.

En teoría, se puede demostrar que todo dominio convexo cerrado en R ⁿ tiene una barrera autoconcordante con el parámetro O( n ). Pero esta “barrera universal” viene dada por algunas integrales multivariadas y es demasiado complicada para realizar cálculos reales. Por lo tanto, el objetivo principal es construir SCB que sean computables de manera eficiente. ^{[4] : Sección 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

Cada 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} [Tenga en cuenta que las funciones lineales y cuadráticas son funciones autoconcordantes, pero no lo son barreras autoconcordantes].

Para la media línea positiva ( ), es una barrera autoconcordante con el 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 aplicación afín de R ^k a R ⁿ con su imagen intersectando el interior de G . Sea H la imagen inversa de G bajo el mapeo: H = { y en R ^k | Ay+b en Sol }. Sea h la función compuesta h ( y ) := g ( Ay + b ). Entonces, h es un M -SCB para H. ^{[2] : Proposición 3.1.1}

Por ejemplo, tome n =1, G la media línea 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 asignaciones afines a una cierta clase de asignaciones "apropiadas", ^{[2] : Thm.9.1.1} y a asignaciones 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 suma de parámetros _i M _i . ^{[2] : Proposición 3.1.1}

Por ejemplo, tome todo G _i como la media línea positiva, de modo que G sea 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 se pueden sustituir 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 todo G _i y supongamos que su interior no está vacío. Sea g  := suma _i r _i *g _i . Entonces, g es un SCB para G , con suma de parámetros _i r _i *M _i . ^{[2] : Proposición 3.1.1}

Por lo tanto, si G se define mediante una lista de restricciones, podemos encontrar un SCB para cada restricción por separado y luego simplemente sumarlos 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 . Luego 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 sobre la gráfica de la función, es decir, . El epígrafe de f es un conjunto convexo si y sólo 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 continuamente diferenciable 3 veces en t >0, tal que esté acotada por una constante (denotada como 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] : Proposición 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 ). Luego tiene un 2-SCB. Del mismo modo, 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\}}$
• Sean g ( t ) = ln ( t ) y b = 2/3. Luego tiene un 2-SCB. ${\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:e^{x}\leq t\}}$

Ahora podemos construir un SCB para el problema de minimizar la norma p : , donde v _j son escalares constantes, u _j son vectores constantes y p > 0 es una constante. Primero lo convertimos en minimización de un objetivo lineal: , con las restricciones: para todo j en [ m ]. Para cada restricción, tenemos un 4-SCB según la regla de sustitución afín. Usando la regla de intersección, obtenemos un (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: cierre({ ( t,x ) en 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] : Proposición 9.2.2} ${\displaystyle x\cdot |g'''(x)|/|g''(x)|\leq 3b}$

Ejemplos:

• Sea g ( x ) = x ^{- p} , para algunos p >0, y b=(2+ p )/3. Luego tiene un 2-SCB. ${\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:x^{-p}\leq t,x\geq 0\}}$
• Sean g ( x ) = x ln ( x ) y b = 1/3. Luego 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 de m*m, la función es una barrera autoconcordante. ${\displaystyle f(A)=-\log \det A}$
• Para la región cuadrática definida por donde 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 con 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 de forma recursiva ${\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 Lipschitz es continua , es decir, para alguna constante . Si suponemos que es 3 veces continuamente diferenciable, entonces esto equivale 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}}$para todos ${\displaystyle u,v\in \mathbb {R} ^{n}}$

dónde . 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 . Luego llegan 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 constantes y y , entonces son autoconcordantes con constantes . ${\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})}$

Transformacion afin

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 lo es. ^{[11] [12]} ${\displaystyle f}$ ${\displaystyle f^{*}}$

Arpillera no singular

Si es autoconcordante y el dominio de no contiene una línea recta (infinita 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 los cuales están en el dominio de y entonces es lineal y no puede tener un máximo, por lo que todos están 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 métodos de puntos interiores para optimización convexa y no lineal. El análisis habitual del método de Newton no funcionaría para funciones de barrera ya que su segunda derivada no puede ser continua de Lipschitz, 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 restringidos
• 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 se puede minimizar con un método de Newton modificado donde 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, que 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 para 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, basándose en 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 podamos continuar usando el método de Newton hasta la convergencia. Tenga en cuenta que para algunos tenemos convergencia cuadrática de a 0 como . Esto da entonces una convergencia cuadrática de to y de to , donde , según 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 algunos entonces tenemos que comenzar usando 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. Tenga en cuenta que es una función creciente para so que para cualquiera , 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) . Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3. Consultado 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 de la bibliografía). Sociedad de Matemática Industrial y Aplicada. doi :10.1137/1.9781611970791.bm. ISBN 978-0-89871-319-0.
6. Nesterov, I︠U︡. E. (1994). Algoritmos polinómicos 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, págs. 324-326. (En ruso.)
8. Yu. E. NESTEROV, Métodos iterativos de tiempo polinómico 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 polinómico 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. Conferencias introductorias sobre optimización convexa: un curso básico. Bostón. 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ática Aplicada y Numérica . doi :10.1137/1.9781611970791. ISBN 978-0-89871-319-0.
12. Sol, 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 .