Download PFC Emilio Mejia Fernandez Velasco PDF

TitlePFC Emilio Mejia Fernandez Velasco
TagsMathematics Design Mathematical Optimization Theory
File Size3.2 MB
Total Pages260
Table of Contents
                            Agradecimientos
Resumen
Abstract
Tabla de contenidos
Lista de figuras
Lista de tablas
Lista de algoritmos
1 Introducción
	1.1 Motivación
	1.2 Objetivos del proyecto
		1.2.1 Identificación y evaluación de herramientas
		1.2.2 Sistemas de modelado y de resolución
		1.2.3 Casos de aplicación
		1.2.4 Marco teórico
	1.3 Método de trabajo
	1.4 Medios utilizados
	1.5 Casos prácticos desarrollados
		1.5.1 Conformación de haz
		1.5.2 Canales MIMO
	1.6 Estructura de la memoria
I Fundamentos de optimización convexa.
	2 Conceptos teóricos
		2.1 Optimización convexa
			2.1.0.1 Métodos de resolución
			2.1.0.2 Optimización no lineal
			2.1.1 Optimización convexa
		2.2 Conjuntos convexos
			2.2.1 Definiciones importantes
				2.2.1.1 Conjuntos afines, convexos y conos
				2.2.1.2 Hiperplanos y semiespacios
				2.2.1.3 Elipsoides
			2.2.2 Operaciones que conservan la convexidad
				2.2.2.1 Intersecciones
				2.2.2.2 Funciones afines
			2.2.3 Desigualdades generalizadas
				2.2.3.1 Conos propios y desigualdades generalizadas
				2.2.3.2 Elemento mínimo y minimal
			2.2.4 Conos duales y desigualdades generalizadas
				2.2.4.1 Elemento mínimo y minimal
		2.3 Funciones convexas
			2.3.1 Condiciones necesarias
				2.3.1.1 Condición de primer orden
				2.3.1.2 Condición de segundo orden
				2.3.1.3 Ejemplos
				2.3.1.4 Condición del epígrafo
			2.3.2 Operaciones que conservan la convexidad
				2.3.2.1 Suma ponderada con pesos no negativos
				2.3.2.2 Función compuesta con un mapa afín
				2.3.2.3 Máximo y supremo puntual
				2.3.2.4 Minimización de componentes
				2.3.2.5 Perspectiva de una función
				2.3.2.6 Composición
			2.3.3 Funciones cuasi-convexas
				2.3.3.1 Definición
				2.3.3.2 Condición de primer orden
				2.3.3.3 Condición de segundo orden
				2.3.3.4 Operaciones que conservan la cuasi-convexidad
			2.3.4 Convexidad con desigualdades generalizadas
				2.3.4.1 Funciones monótonas
				2.3.4.2 Funciones convexas
		2.4 Dualidad
			2.4.1 Función dual de Lagrange
			2.4.2 El problema dual de Lagrange
				2.4.2.1 Dualidad débil
				2.4.2.2 Condición de Slater
			2.4.3 Condiciones de punto óptimo
				2.4.3.1 Holgura complementaria
				2.4.3.2 Condiciones KKT
			2.4.4 Sensibilidad frente a perturbaciones
				2.4.4.1 Funciones diferenciables
	3 Planteamiento de problemas
		3.1 Problemas equivalentes
			3.1.1 Cambio de variables
			3.1.2 Transformación de las funciones
			3.1.3 Variables de holgura
			3.1.4 Eliminación de restricciones de igualdad
				3.1.4.1 Eliminación de las restricciones lineales de igualdad
			3.1.5 Introducción de restricciones de igualdad
			3.1.6 Optimización sobre algunas variables
			3.1.7 Problema en forma de epígrafo
			3.1.8 Restricciones implícitas y explícitas
		3.2 Optimización cuasi-convexa
			3.2.1 Definición
			3.2.2 Solución por medio de problemas de viabilidad
		3.3 Clasificación de problemas convexos
			3.3.1 Problemas de optimización lineal
				3.3.1.1 LP en formato estándar y en formato desigualdad
				3.3.1.2 Ejemplos
			3.3.2 Problemas de optimización cuadráticos
			3.3.3 Programación cónica de segundo orden
			3.3.4 Programación con desigualdades generalizadas
				3.3.4.1 Problemas en forma cónica
				3.3.4.2 Programación semidefinida
			3.3.5 Programación geométrica
				3.3.5.1 Programación geométrica en forma convexa
		3.4 Optimización vectorial
			3.4.1 Óptimos de Pareto
			3.4.2 Escalarización
				3.4.2.1 Escalarización en problemas convexos
				3.4.2.2 Optimización multicriterio
	4 Algoritmos de minimización
		4.1 Minimización sin restricciones
			4.1.1 Métodos de descenso
				4.1.1.1 Descenso de gradiente
				4.1.1.2 Búsqueda lineal exacta
				4.1.1.3 Búsqueda lineal con retroceso
			4.1.2 Método de Newton
				4.1.2.1 Independencia afín
				4.1.2.2 Decremento de Newton
				4.1.2.3 Algoritmo de Newton
		4.2 Minimización con restricciones de igualdad
			4.2.1 Minimización cuadrática con restricciones de igualdad
			4.2.2 Método de Newton con restricciones de igualdad
			4.2.3 Método de Newton desde un punto inicial no viable
				4.2.3.1 Interpretación como método primal-dual
				4.2.3.2 Reducción de la norma residual
				4.2.3.3 Viabilidad con el paso completo
				4.2.3.4 Algoritmo de Newton desde un punto no viable
				4.2.3.5 Inicialización simplificada
		4.3 Métodos de punto interior
			4.3.1 Método de barrera
				4.3.1.1 Camino central
				4.3.1.2 Condiciones KKT
				4.3.1.3 Algoritmo de barrera
			4.3.2 Método de fase I
				4.3.2.1 Método de Newton desde un punto inicial no viable
			4.3.3 Problemas con desigualdades generalizadas
				4.3.3.1 Logaritmo generalizado
				4.3.3.2 Funciones barrera logarítmica
				4.3.3.3 Camino central
				4.3.3.4 Puntos duales en el camino central
			4.3.4 Métodos de punto interior primal-dual
				4.3.4.1 Dirección de búsqueda primal-dual
				4.3.4.2 Distancia alternativa de dualidad
				4.3.4.3 Algoritmo de punto interior primal-dual
		4.4 Algoritmo símplex
		4.5 Problemas con variables enteras
II Herramientas de optimización convexa
	5 Herramientas disponibles
		5.1 Motivación
		5.2 Herramientas de resolución
			5.2.1 Efectividad de las herramientas de resolución
			5.2.2 Problemas lineales
				5.2.2.1 lp_solve
				5.2.2.2 GLPK
				5.2.2.3 BPMPD
				5.2.2.4 MINOS
			5.2.3 Problemas cuadráticos
				5.2.3.1 CPLEX
				5.2.3.2 Gurobi
				5.2.3.3 Xpress-Optimizer
				5.2.3.4 OOQP
			5.2.4 Problemas cónicos
				5.2.4.1 Mosek
				5.2.4.2 SeDuMi
				5.2.4.3 SDPT3
				5.2.4.4 PENSDP
		5.3 Sistemas de modelado
			5.3.1 CVX
				5.3.1.1 Programas de resolución
				5.3.1.2 Licencias
			5.3.2 AMPL
				5.3.2.1 Características del lenguaje de modelado
				5.3.2.2 Características del entorno de modelado
				5.3.2.3 Herramientas de resolución utilizadas
				5.3.2.4 Licencias
			5.3.3 GAMS
				5.3.3.1 Características del programa
				5.3.3.2 Herramientas de resolución utilizadas
				5.3.3.3 Licencias
			5.3.4 YALIMP
				5.3.4.1 Herramientas de resolución
				5.3.4.2 Licencias
		5.4 Programas de optimización global
			5.4.1 Matlab Optimization Toolbox
				5.4.1.1 Licencias
			5.4.2 Mathematica
				5.4.2.1 Licencias
			5.4.3 MathOptimizer Professional
				5.4.3.1 Licencias
		5.5 Ejemplo
			5.5.1 Resolución por CVX
			5.5.2 Resolución por Mosek
			5.5.3 Resolución por SeDuMi
			5.5.4 Resolución por Mathematica
			5.5.5 Resolución por Matlab Optimization Toolbox
			5.5.6 Comparación entre los resultados obtenidos
		5.6 Conclusiones
III Aplicaciones en telecomunicaciones
	6 Conformación de Haz
		6.1 Agrupaciones de antenas
		6.2 Conformación de haz en recepción
			6.2.1 Contexto
			6.2.2 Extensiones de los diseños de caso peor
		6.3 Implementación del optimizador
			6.3.1 CVX
			6.3.2 SeDuMi
			6.3.3 Mosek
			6.3.4 Matlab Optimization Toolbox
				6.3.4.1 Descripción directa
				6.3.4.2 Planteamiento estándar SOCP
			6.3.5 Mathematica
				6.3.5.1 Descripción directa
				6.3.5.2 Planteamiento estándar SOCP
		6.4 Simulaciones
			6.4.1 Matriz de covarianza
			6.4.2 Perturbación en el vector de apuntamiento
			6.4.3 Selección de la región de incertidumbre
				6.4.3.1 Gráfica de CVX, SeDuMi y Mosek
				6.4.3.2 Gráficas de Matlab Optimization Toolbox
				6.4.3.3 Gráfica de Mathematica
			6.4.4 SINR en función de SNR
				6.4.4.1 Gráfica de CVX, SeDuMi y Mosek
				6.4.4.2 Gráfica de Matlab Optimization Toolbox
				6.4.4.3 Gráfica de Mathematica
			6.4.5 Tiempos de ejecución
				6.4.5.1 Gráficas de CVX, SeDuMi y Mosek
				6.4.5.2 Gráfica de Matlab Optimization Toolbox
				6.4.5.3 Gráfica de Mathematica
			6.4.6 Diagramas de radiación
				6.4.6.1 Gráfica con 10 antenas
				6.4.6.2 Gráfica con 100 antenas
		6.5 Conclusiones
	7 Canales MIMO
		7.1 Motivación
		7.2 Modelo del canal
			7.2.1 Ganancias en canales MIMO y sus propiedades
				7.2.1.1 Subcanales y flujos
			7.2.2 Compatibilidad entre ganancias
			7.2.3 Técnicas de transmisión
				7.2.3.1 Técnicas de transmisión MIMO sin CSIT
				7.2.3.2 Técnicas de transmisión MIMO con CSIT exacto
				7.2.3.3 Técnicas de transmisión MIMO con CSIT parcial
		7.3 Procesamiento lineal
			7.3.1 Parámetros de calidad del sistema
			7.3.2 Receptor lineal
			7.3.3 Diseño del transmisor
				7.3.3.1 Canal MIMO simple
				7.3.3.2 Múltiples canales MIMO
			7.3.4 Criterios de optimización utilizados
				7.3.4.1 Suma de MSE
				7.3.4.2 Información mutua
			7.3.5 Restricciones adicionales
		7.4 Implementación del optimizador
			7.4.1 CVX
				7.4.1.1 Criterio de suma de MSE
				7.4.1.2 Criterio de información mutua
			7.4.2 Sedumi
			7.4.3 Mosek
		7.5 Arquitectura del sistema de simulación
		7.6 Simulaciones
			7.6.1 Comparativa de herramientas de optimización
			7.6.2 Comparativa de criterios
			7.6.3 Efecto de la restricción de PAR
		7.7 Conclusiones
8 Conclusiones y líneas futuras
	8.1 Líneas futuras
A Resolución de ecuaciones lineales
	A.1 Factorización LU
	A.2 Factorización de Cholesky
	A.3 Complemento de Schur
	A.4 El lema de inversión matricial
B Presupuesto del proyecto
	B.1 Fases del proyecto
	B.2 Desglose presupuestario
Bibliografía
Acrónimos
                        
Document Text Contents
Page 1

UNIVERSIDAD CARLOS III DE MADRID
ESCUELA POLITÉCNICA SUPERIOR

Departamento de
TEORÍA DE LA SEÑAL Y COMUNICACIONES

Ingeniería de Telecomunicación
Proyecto de Fin de Carrera

Herramientas de optimización
convexa

y
aplicaciones en

telecomunicaciones

Autor: Emilio Mejía Fernández de Velasco
Director: José Joaquín Escudero Garzás
Tutora: Ana García Armada

Leganés, 2011

Page 130

104 CAPÍTULO 5. HERRAMIENTAS DISPONIBLES

Nombre Algoritmos Problemas Licencia Limitaciones
en demo

Mathematica símplex LP comercial 15 días
p. interior op. local
Nelder-Mead op. global
algoritmos genéticos
temple simulado

MathOptimizer Lipschitz Global Opt. op. global comercial por solicitud
Matlab p. interior op. local comercial para empresas
Optimization Nelder-Mead op. global
Toolbox Quasi Newton

Región de confianza

Tabla 5.5: Resumen de las herramientas de resolución no convexa.

También es posible conseguir una versión de prueba, aunque esta opción
no está disponible para estudiantes.

5.4.2 Mathematica

Mathematica es una plataforma de cálculo simbólico y numérico cuyo rango
de aplicaciones es mucho más amplio del que se utiliza en este proyecto.
Está compuesta por un núcleo que interpreta expresiones y devuelve los
resultados, y un sistema de gestión de entrada de datos que permite la
creación y edición de documentos que contienen código en un formato que
visualmente se asemeja a la formulación matemática de un editor de texto.
En cuanto a sus capacidades de optimización, en esta herramienta no se
requiere que el problema a optimizar sea convexo. Simplemente se distin-
gue entre problemas lineales y no lineales. En el primer caso se utiliza el
comando LinearProgramming. Cuando el problema no es lineal, podemos
buscar una solución global con el comando Minimize o una solución local
con FindMinimum.

Las restricciones se describen como una combinación booleana de ecua-
ciones que pueden ser igualdades, desigualdades estrictas y no estrictas, y
también declaraciones de variables enteras x ∈ Z

Los algoritmos de punto interior se encuentran en lo que este softwa-
re clasifica como optimización local, porque efectivamente, si aplicamos las
técnicas que hemos visto en el tema 4 en funciones no convexas, la solución
puede converger hacia un mínimo local.

La información sobre esta herramienta procede de [Wol10].

Page 131

5.4. PROGRAMAS DE OPTIMIZACIÓN GLOBAL 105

5.4.2.1 Licencias

Wolfram Mathematica se puede conseguir bajo licencia comercial. La versión
actual es 8. Su venta se clasifica según vaya a ser su utilización, bien para
industria, gobierno o educación. En el primer caso encontramos licencias
individuales o de grupo y de empresa; igual que en el caso gubernamental;
y en el caso de uso académico, además de las licencias individuales, para
departamentos y entidades docentes, también hay licencias para estudiantes
a precios más asequibles. Se ofrecen diferentes precios para investigadores
y docentes de educación superior, para escuelas técnicas y para educación
primaria y secundaria.

Existe una versión de evaluación completamente funcional durante 15
días.

5.4.3 MathOptimizer Professional

Esta herramienta funciona como complemento para Mathematica, y utiliza
como herramienta de resolución el optimizador global de Lipschitz (LGO),
que permite la solución global y local de problemas de optimización con-
tinuos en general. Los datos sobre esta herramienta proceden de [Pin10] y
de información directa enviada por su autor, según la cual, este software
puede resolver modelos con algunos miles de variables y funciones objetivo
y restricciones, y este límite depende de la infraestructura de hardware utili-
zada y del tiempo de ejecución que podamos tolerar. En pruebas numéricas
y en algunas aplicaciones para clientes se han resuelto algunos problemas
complejos con estas dimensiones. Sin embargo, dependiendo de cada tipo
concreto de problema a resolver, la variación del tiempo de resolución puede
abarcar desde minutos hasta algunos días. En algunos casos simplemente
la evaluación de las funciones ya puede requerir bastante tiempo, por lo
que la optimización global aplicada tiene que adaptarse para manejar esta
situación.

A partir de las expresiones para Mathematica, esta herramienta es capaz
de generar automáticamente código en C o en Fortran.

La implementación del solver LGO integra las siguientes estrategias:

� Búsqueda global basada en el método de ramificar y acotar, con par-
tición adaptativa y muestreo.

� Búsqueda global estocástica adaptativa.

� Búsqueda global estocástica y adaptativa basada en inicio múltiple.

� Búsqueda local restringida por acotación, basada en el uso de una
función exacta de penalización.

� Búsqueda local con restricciones, basada en una aproximación de gra-
diente reducido generalizado.

Page 259

233

MILP Mixed Integer Linear Program (programa lineal con mezcla
de enteros) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

MIMO Multiple Input Multiple Output (entrada múltiple, salida
múltiple) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

MIP Mixed Integer Program (programa con mezcla de enteros)
74

MIQCP Mixed Integer Quadratically Constrained Program
(programa con mezcla de enteros con restricciones
cuadráticas) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

MIQP Mixed Integer Quadratic Program (programa cuadrático
con mezcla de enteros)

NLP Non-Linear Program (programa no lineal) . . . . . . . . . . . . . . 99
MINLP Mixed Integer Non-Linear Program (programa no lineal

con mezcla de enteros)
MISO Multiple Input, Single Output (entrada múltiple, salida

única) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
ML Maximum Likelihood (máxima verosimilitud) . . . . . . . . . . 173
MPEC Mathematical Program with Equilibrium Constraints

(programa matemático con restricciones de equilibrio) . . 99
MSE Mean Square Error (error cuadrático medio). . . . . . . . . . .175
MTA SZTAKI Magyar Tudományos Akadémia Számítástechnikai és

Automatizálási Kutatóintézete (Instituto de Investigación
de Informática y Automática, Academia Húngara de
Ciencias) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

NT Nesterov-Todd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
OFDM Orthogonal Frequency Division Multiplexing (multiplexado

por división ortogonal en frecuencia) . . . . . . . . . . . . . . . . . . . . . 6
OOQP Object Oriented Quadratic Program (programa cuadrático

orientado a objetos) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
PAPR Peak to Average Power Ratio (relación de potencia de pico

a media) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
PAR Peak to Average Ratio (relación de pico a media) . . . . . . 167
QAM Quadrature Amplitude Modulation (modulación de

amplitud en cuadratura) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
QCQP Quadratically Constrained Quadratic Program (programa

cuadrático con restricciones cuadráticas) . . . . . . . . . . . . . . . . 43
QP Quadratic Program (programa cuadrático) . . . . . . . . . . . . . . 42

Page 260

234 ACRÓNIMOS

SDP SemiDefinite Program (programa semidefinido) . . . . . . . . . 44
SDPA SemiDefinite Programming Algorithm (algoritmo de

programación semidefinida) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
SeDuMi Self Dual Minimization (Minimización autodual) . . . . . . . . .5
SIMO Single Input Multiple Output (entrada única, salida

múltiple) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
SINR Signal to Interference and Noise Ratio (relación señal a

ruido e interferencia) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
SMI Sample Matrix Inversion (inversión de matriz muestral)125
SMI-MV Sample Matrix Inversion based Minimum Variance

(varianza mínima basada en inversión de matriz muestral)
125

SNR Signal to Noise Ratio (relación señal a ruido) . . . . . . . . . . 146
SOCP Second Order Cone Program (programa cónico de segundo

orden) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43
STBC Space-Time Block Coding (codificación espacio-tiempo en

bloque). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172
STC Space-Time Coding (codificación espacio-tiempo) . . . . . . 172
STTC Space-Time Trellis Coding (codificación espacio-tiempo en

rejilla) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
TDD Time Division Duplex (duplexado por división en el

tiempo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
UWB Ultra Wide Band (banda ultra ancha) . . . . . . . . . . . . . . . . . . 37
WLAN Wireless Local Area Network (red de área local

inalámbrica). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195

Similer Documents