Time trials on second-order and variable-learning-rate algorithms

The performance of seven minimization algorithms are compared on five neural network problems. These include a variable-step-size algorithm, conjugate gradient, and several methods with explicit analytic or numerical approximations to the Hessian.

Convex analysis for minimizing and learning submodular set functions

The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions.

First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques.

Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set.

Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.

Reformulation of variational inequalities on a simplex and compactification of complementarity problems

Many variational inequality problems (VIPs) can be reduced, by a compactification procedure, to a VIP on the canonical simplex. Reformulations of this problem are studied, including smooth reformulations with simple constraints and unconstrained reformulations based on the penalized Fischer-Burmeister function. It is proved that bounded level set results hold for these reformulations under quite general assumptions on the operator. Therefore, it can be guaranteed that minimization algorithms generate bounded sequences and, under monotonicity conditions, these algorithms necessarily nd solutions of the original problem. Some numerical experiments are presented.

On the regularization of mixed complementarity problems

A variational inequality problem (VIP) satisfying a constraint qualification can be reduced to a mixed complementarity problem (MCP). Monotonicity of the VIP implies that the MCP is also monotone. Introducing regularizing perturbations, a sequence of strictly monotone mixed complementarity problems is generated. It is shown that, if the original problem is solvable, the sequence of computable inexact solutions of the strictly monotone MCP's is bounded and every accumulation point is a solution. Under an additional condition on the precision used for solving each subproblem, the sequence converges to the minimum norm solution of the MCP. Copyright © 2000 by Marcel Dekker, Inc.

On the solution of bounded and unbounded mixed complementarity problems

A reformulation of the bounded mixed complementarity problem is introduced. It is proved that the level sets of the objective function are bounded and, under reasonable assumptions, stationary points coincide with solutions of the original variational inequality problem. Therefore, standard minimization algorithms applied to the new reformulation must succeed. This result is applied to the compactification of unbounded mixed complementarity problems. © 2001 OPA (Overseas Publishers Association) N.V. Published by license under the Gordon and Breach Science Publishers imprint, a member of the Taylor & Francis Group.

On the solution of mathematical programming problems with equilibrium constraints

Mathematical programming problems with equilibrium constraints (MPEC) are nonlinear programming problems where the constraints have a form that is analogous to first-order optimality conditions of constrained optimization. We prove that, under reasonable sufficient conditions, stationary points of the sum of squares of the constraints are feasible points of the MPEC. In usual formulations of MPEC all the feasible points are nonregular in the sense that they do not satisfy the Mangasarian-Fromovitz constraint qualification of nonlinear programming. Therefore, all the feasible points satisfy the classical Fritz-John necessary optimality conditions. In principle, this can cause serious difficulties for nonlinear programming algorithms applied to MPEC. However, we show that most feasible points do not satisfy a recently introduced stronger optimality condition for nonlinear programming. This is the reason why, in general, nonlinear programming algorithms are successful when applied to MPEC.

Blind Deconvolution via Lower-Bounded Logarithmic Image Priors

In this work we devise two novel algorithms for blind deconvolution based on a family of logarithmic image priors. In contrast to recent approaches, we consider a minimalistic formulation of the blind deconvolution problem where there are only two energy terms: a least-squares term for the data fidelity and an image prior based on a lower-bounded logarithm of the norm of the image gradients. We show that this energy formulation is sufficient to achieve the state of the art in blind deconvolution with a good margin over previous methods. Much of the performance is due to the chosen prior. On the one hand, this prior is very effective in favoring sparsity of the image gradients. On the other hand, this prior is non convex. Therefore, solutions that can deal effectively with local minima of the energy become necessary. We devise two iterative minimization algorithms that at each iteration solve convex problems: one obtained via the primal-dual approach and one via majorization-minimization. While the former is computationally efficient, the latter achieves state-of-the-art performance on a public dataset.

A Logarithmic Image Prior for Blind Deconvolution

Blind Deconvolution consists in the estimation of a sharp image and a blur kernel from an observed blurry image. Because the blur model admits several solutions it is necessary to devise an image prior that favors the true blur kernel and sharp image. Many successful image priors enforce the sparsity of the sharp image gradients. Ideally the L0 “norm” is the best choice for promoting sparsity, but because it is computationally intractable, some methods have used a logarithmic approximation. In this work we also study a logarithmic image prior. We show empirically how well the prior suits the blind deconvolution problem. Our analysis confirms experimentally the hypothesis that a prior should not necessarily model natural image statistics to correctly estimate the blur kernel. Furthermore, we show that a simple Maximum a Posteriori formulation is enough to achieve state of the art results. To minimize such formulation we devise two iterative minimization algorithms that cope with the non-convexity of the logarithmic prior: one obtained via the primal-dual approach and one via majorization-minimization.

Analysis and Design Considerations of an Electric Vehicle Powertrain regarding Energy Efficiency and Magnetic Field Exposure

En esta tesis se analiza el sistema de tracción de un vehículo eléctrico de batería desde el punto de vista de la eficiencia energética y de la exposición a campos magnéticos por parte de los pasajeros (radiación electromagnética). Este estudio incluye tanto el sistema de almacenamiento de energía como la máquina eléctrica, junto con la electrónica de potencia y los sistemas de control asociados a ambos. Los análisis y los resultados presentados en este texto están basados en modelos matemáticos, simulaciones por ordenador y ensayos experimentales a escala de laboratorio. La investigación llevada a cabo durante esta tesis tuvo siempre un marcado enfoque industrial, a pesar de estar desarrollada en un entorno de considerable carácter universitario. Las líneas de investigación acometidas tuvieron como destinatario final al diseñador y al fabricante del vehículo, a pesar de lo cual algunos de los resultados obtenidos son preliminares y/o excesivamente académicos para resultar de interés industrial. En el ámbito de la eficiencia energética, esta tesis estudia sistemas híbridos de almacenamiento de energía basados en una combinación de baterías de litio y supercondensadores. Este tipo de sistemas son analizados desde el punto de vista de la eficiencia mediante modelos matemáticos y simulaciones, cuantificando el impacto de ésta en otros parámetros tales como el envejecimiento de las baterías. Respecto a la máquina eléctrica, el estudio se ha centrado en máquinas síncronas de imanes permanentes. El análisis de la eficiencia considera tanto el diseño de la máquina como la estrategia de control, dejando parcialmente de lado el inversor y la técnica de modulación (que son incluidos en el estudio como fuentes adicionales de pérdidas, pero no como potenciales fuentes de optimización de la eficiencia). En este sentido, tanto la topología del inversor (trifásico, basado en IGBTs) como la técnica de modulación (control de corriente en banda de histéresis) se establecen desde el principio. El segundo aspecto estudiado en esta tesis es la exposición a campos magnéticos por parte de los pasajeros. Este tema se enfoca desde un punto de vista predictivo, y no desde un punto de vista de diagnóstico, puesto que se ha desarrollado una metodología para estimar el campo magnético generado por los dispositivos de potencia de un vehículo eléctrico. Esta metodología ha sido validada mediante ensayos de laboratorio. Otros aspectos importantes de esta contribución, además de la metodología en sí misma, son las consecuencias que se derivan de ella (por ejemplo, recomendaciones de diseño) y la comprensión del problema proporcionada por esta. Las principales contribuciones de esta tesis se listan a continuación: una recopilación de modelos de pérdidas correspondientes a la mayoría de dispositivos de potencia presentes en un vehículo eléctrico de batería, una metodología para analizar el funcionamiento de un sistema híbrido de almacenamiento de energía para aplicaciones de tracción, una explicación de cómo ponderar energéticamente los puntos de operación par-velocidad de un vehículo eléctrico (de utilidad para evaluar el rendimiento de una máquina eléctrica, por ejemplo), una propuesta de incluir un convertidor DC-DC en el sistema de tracción para minimizar las pérdidas globales del accionamiento (a pesar de las nuevas pérdidas introducidas por el propio DC-DC), una breve comparación entre dos tipos distintos de algoritmos de minimización de pérdidas para máquinas síncronas de imanes permanentes, una metodología predictiva para estimar la exposición a campos magnéticos por parte de los pasajeros de un vehículo eléctrico (debida a los equipos de potencia), y finalmente algunas conclusiones y recomendaciones de diseño respecto a dicha exposición a campos magnéticos. ABSTRACT This dissertation analyzes the powertrain of a battery electric vehicle, focusing on energy efficiency and passenger exposure to electromagnetic fields (electromagnetic radiation). This study comprises the energy storage system as well as the electric machine, along with their associated power electronics and control systems. The analysis and conclusions presented in this dissertation are based on mathematical models, computer simulations and laboratory scale tests. The research performed during this thesis was intended to be of industrial nature, despite being developed in a university. In this sense, the work described in this document was carried out thinking of both the designer and the manufacturer of the vehicle. However, some of the results obtained lack industrial readiness, and therefore they remain utterly academic. Regarding energy efficiency, hybrid energy storage systems consisting in lithium batteries, supercapacitors and up to two DC-DC power converters are considered. These kind of systems are analyzed by means of mathematical models and simulations from the energy efficiency point of view, quantifying its impact on other relevant aspects such as battery aging. Concerning the electric machine, permanent magnet synchronous machines are studied in this work. The energy efficiency analysis comprises the machine design and the control strategy, while the inverter and its modulation technique are taken into account but only as sources of further power losses, and not as potential sources for further efficiency optimization. In this sense, both the inverter topology (3-phase IGBT-based inverter) and the switching technique (hysteresis current control) are fixed from the beginning. The second aspect studied in this work is passenger exposure to magnetic fields. This topic is approached from the prediction point of view, rather than from the diagnosis point of view. In other words, a methodology to estimate the magnetic field generated by the power devices of an electric vehicle is proposed and analyzed in this dissertation. This methodology has been validated by laboratory tests. The most important aspects of this contribution, apart from the methodology itself, are the consequences (for instance, design guidelines) and the understanding of the magnetic radiation issue provided by it. The main contributions of this dissertation are listed next: a compilation of loss models for most of the power devices found in a battery electric vehicle powertrain, a simulation-based methodology to analyze hybrid energy storage performance in traction applications, an explanation of how to assign energy-based weights to different operating points in traction drives (useful when assessing electrical machine performance, for instance), a proposal to include one DC-DC converter in electric powertrains to minimize overall power losses in the system (despite the new losses added by the DC-DC), a brief comparison between two kinds of loss-minimization algorithms for permanent magnet synchronous machines in terms of adaptability and energy efficiency, a predictive methodology to estimate passenger magnetic field exposure due to power devices in an electric vehicle, and finally some useful conclusions and design guidelines concerning magnetic field exposure.

A Clearer Picture of Total Variation Blind Deconvolution

Blind deconvolution is the problem of recovering a sharp image and a blur kernel from a noisy blurry image. Recently, there has been a significant effort on understanding the basic mechanisms to solve blind deconvolution. While this effort resulted in the deployment of effective algorithms, the theoretical findings generated contrasting views on why these approaches worked. On the one hand, one could observe experimentally that alternating energy minimization algorithms converge to the desired solution. On the other hand, it has been shown that such alternating minimization algorithms should fail to converge and one should instead use a so-called Variational Bayes approach. To clarify this conundrum, recent work showed that a good image and blur prior is instead what makes a blind deconvolution algorithm work. Unfortunately, this analysis did not apply to algorithms based on total variation regularization. In this manuscript, we provide both analysis and experiments to get a clearer picture of blind deconvolution. Our analysis reveals the very reason why an algorithm based on total variation works. We also introduce an implementation of this algorithm and show that, in spite of its extreme simplicity, it is very robust and achieves a performance comparable to the top performing algorithms.

The moving targets algorithm for difficult temporal credit assignment problems

The 'moving targets' algorithm for training recurrent networks is reviewed and applied to a task which demonstrates the ability of this algorithm to use distant contextual information. Some practical difficulties are discussed, especially with regard to the minimization process. Results on performance and computational requirements of several different 2nd-order minimization algorithms are presented for moving target problems.

Performance evaluation of typical approximation algorithms for nonconvex l(p)-minimization in diffuse optical tomography

The sparse estimation methods that utilize the l(p)-norm, with p being between 0 and 1, have shown better utility in providing optimal solutions to the inverse problem in diffuse optical tomography. These l(p)-norm-based regularizations make the optimization function nonconvex, and algorithms that implement l(p)-norm minimization utilize approximations to the original l(p)-norm function. In this work, three such typical methods for implementing the l(p)-norm were considered, namely, iteratively reweighted l(1)-minimization (IRL1), iteratively reweighted least squares (IRLS), and the iteratively thresholding method (ITM). These methods were deployed for performing diffuse optical tomographic image reconstruction, and a systematic comparison with the help of three numerical and gelatin phantom cases was executed. The results indicate that these three methods in the implementation of l(p)-minimization yields similar results, with IRL1 fairing marginally in cases considered here in terms of shape recovery and quantitative accuracy of the reconstructed diffuse optical tomographic images. (C) 2014 Optical Society of America

Power Minimization for CDMA under Colored Noise

Rate-constrained power minimization (PMIN) over a code division multiple-access (CDMA) channel with correlated noise is studied. PMIN is. shown to be an instance of a separable convex optimization problem subject to linear ascending constraints. PMIN is further reduced to a dual problem of sum-rate maximization (RMAX). The results highlight the underlying unity between PMIN, RMAX, and a problem closely related to PMIN but with linear receiver constraints. Subsequently, conceptually simple sequence design algorithms are proposed to explicitly identify an assignment of sequences and powers that solve PMIN. The algorithms yield an upper bound of 2N - 1 on the number of distinct sequences where N is the processing gain. The sequences generated using the proposed algorithms are in general real-valued. If a rate-splitting and multi-dimensional CDMA approach is allowed, the upper bound reduces to N distinct sequences, in which case the sequences can form an orthogonal set and be binary +/- 1-valued.

SPSA algorithms with measurement reuse

Four algorithms, all variants of Simultaneous Perturbation Stochastic Approximation (SPSA), are proposed. The original one-measurement SPSA uses an estimate of the gradient of objective function L containing an additional bias term not seen in two-measurement SPSA. As a result, the asymptotic covariance matrix of the iterate convergence process has a bias term. We propose a one-measurement algorithm that eliminates this bias, and has asymptotic convergence properties making for easier comparison with the two-measurement SPSA. The algorithm, under certain conditions, outperforms both forms of SPSA with the only overhead being the storage of a single measurement. We also propose a similar algorithm that uses perturbations obtained from normalized Hadamard matrices. The convergence w.p. 1 of both algorithms is established. We extend measurement reuse to design two second-order SPSA algorithms and sketch the convergence analysis. Finally, we present simulation results on an illustrative minimization problem.

Some Algorithms for Eigensubspace Estimation

An important tool in signal processing is the use of eigenvalue and singular value decompositions for extracting information from time-series/sensor array data. These tools are used in the so-called subspace methods that underlie solutions to the harmonic retrieval problem in time series and the directions-of-arrival (DOA) estimation problem in array processing. The subspace methods require the knowledge of eigenvectors of the underlying covariance matrix to estimate the parameters of interest. Eigenstructure estimation in signal processing has two important classes: (i) estimating the eigenstructure of the given covariance matrix and (ii) updating the eigenstructure estimates given the current estimate and new data. In this paper, we survey some algorithms for both these classes useful for harmonic retrieval and DOA estimation problems. We begin by surveying key results in the literature and then describe, in some detail, energy function minimization approaches that underlie a class of feedback neural networks. Our approaches estimate some or all of the eigenvectors corresponding to the repeated minimum eigenvalue and also multiple orthogonal eigenvectors corresponding to the ordered eigenvalues of the covariance matrix. Our presentation includes some supporting analysis and simulation results. We may point out here that eigensubspace estimation is a vast area and all aspects of this cannot be fully covered in a single paper. (C) 1995 Academic Press, Inc.