Página 1 dos resultados de 666 itens digitais encontrados em 0.131 segundos

Partial spectral projected gradient method with active-set strategy for linearly constrained optimization

ANDRETTA, Marina; BIRGIN, Ernesto G.; MARTINEZ, J. M.
Fonte: SPRINGER Publicador: SPRINGER
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
37.103105%
A method for linearly constrained optimization which modifies and generalizes recent box-constraint optimization algorithms is introduced. The new algorithm is based on a relaxed form of Spectral Projected Gradient iterations. Intercalated with these projected steps, internal iterations restricted to faces of the polytope are performed, which enhance the efficiency of the algorithm. Convergence proofs are given and numerical experiments are included and commented. Software supporting this paper is available through the Tango Project web page: http://www.ime.usp.br/similar to egbirgin/tango/.; PRONEX-Optimization; PRONEX-Optimization[PRONEX - CNPq/FAPERJ E-26/171.510/2006 - APQ1]; FAPESP[2006/53768-0]; Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP); Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); CNPq

Restrições de manufatura aplicadas ao método de otimização topológica.; Manufacturing constraints applied to the topology optimization method.

Lippi, Tiago Naviskas
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 24/03/2008 PT
Relevância na Pesquisa
37.149302%
O projeto de um componente mecânico é uma atividade muito complexa, onde muitas vezes se tem restrições de projeto como peso do componente e rigidez máxima, e também restrições de manufatura, associada aos processos de fabricação disponíveis para serem utilizados. É fato conhecido que a Otimização Topológica (OT), apesar de ser um método extremamente eficiente para a obtenção de soluções ótimas, gera soluções com geometrias complexas que são ou muito caras de se fabricar ou infactíveis. A técnica de projeção foi escolhida como adequada para implementar as restrições propostas neste trabalho. Esta técnica resolve o problema posto num domínio de variáveis de projeto e projeta essa solução num domínio de pseudo-densidades, que são a resposta do problema. A relação entre os dois domínios e determinada pela função de projeção e pelo mapeamento das variáveis definidos de forma diferente para cada restrição. Neste trabalho foram implementadas restrições de manufatura para OT de modo a restringir a gama possível de soluções no problema de otimização. Como exemplo foi considerado o problema de maximização de rigidez, com restrição de volume. Todas as implementações foram realizadas em linguagem de programação C...

Otimização dinâmica e controle na extração de recursos florestais; Dynamic optimization and control for forest timber harvesting

Pimentel, Carlos Eduardo Hirth
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 23/09/2014 PT
Relevância na Pesquisa
36.967178%
Este trabalho aborda um método de otimização dinâmica baseado em modelos bioeconômicos estabelecidos na teoria do controle ótimo, que visa modelar o resultado econômico-financeiro relacionado à atividade de extração dos recursos naturais, de modo que a otimização do resultado financeiro seja controlada por uma extração sustentável desse recurso. Mais especificamente, consideramos a exploração de madeira florestal restrita a uma série de vínculos econômicos e operacionais, bem como à dinâmica de crescimento natural da floresta. Avaliando o uso efetivo dessa metodologia aplicada ao planejamento das concessões florestais e procurando contribuir com o debate a respeito da viabilidade da forma de gestão florestal baseada em concessões florestais no Brasil.; This work addresses a dynamic optimization method based on bioeconomics models established in optimal control theory, which aims to model the economic-financial result related to the activity of extraction of natural resources, so that the optimization of the financial result is controlled by a sustainable extraction of this resources. More specifically, we consider the exploration of forest wood restricted to a series of economic and operational linkages, as well as the dynamics of natural forest growth. Assessing the effective use of this methodology applied to the planning of forest concessions and seeking to contribute to the debate about the viability of forest management form based on forest concessions in Brazil.

Otimização de processos contendo variaveis de mistura pelo metodo "split-plot"; Split-plot process optimization containing mixture variables

João Alexandre Bortoloti
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 22/06/2006 PT
Relevância na Pesquisa
37.240457%
O método "split-plot" é uma importante ferramenta para a otimização simultânea de sistemas contendo variáveis de processo e de mistura. Porém sua aplicação a problemas químicos ainda foi pouco explorada. Este método simplifica o trabalho no laboratório, mas o tratamento dos resultados é mais complexo. Neste trabalho foram realizados estudos de forma minuciosa sobre suas etapas, desde a elaboração do planejamento até a validação dos resultados. Pontos como a ANOVA (análise de variância), e métodos como ML (maximum likelihood), OLS (ordinary least squares) e REML (restricted maximum likelihood) foram discutidos e empregados em estudos comparativos com dados reais e simulados. Com o objetivo de permitir a popularização do método "split-plot" foram realizados estudos que permitissem a diminuição do número de experimentos executados. Também foram criados programas computacionais para a realização dos cálculos necessários, assim como a análise gráfica dos resultados. Um programa foi gerado para ser executado em ambiente Windows, enquanto outro foi desenvolvido para trabalhar em Matlab com grande flexibilidade para adaptações, ambos os programas estão disponíveis à comunidade. Os programas criados foram aplicados a estudos com dados reais e simulados...

Seleção de projetos de desenvolvimento integrada à análise de risco; Field development projects optimization integrated to risk analysis

Cristina Cledia Mezzomo
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 19/10/2005 PT
Relevância na Pesquisa
36.967178%
A elaboração de projetas de desenvolvimento é um processo bastante complexo devido às incertezas devido à quantidade limitada de informações disponíveis para o grande número de variáveis envolvidas com compot1amento dinâmico. A ferramenta mais utilizada para este processo é a simulação numérica de reservatórios, que fornece a previsão de produção dos campos e pode ser associada a algoritmos de otimizaçào para a maximização de uma função objetiva previamente estabelecida segundo os objetivos de cada projeto. Embora o processo seja complexo, usualmente, são utilizados procedimentos manuais para a escolha da estratégia de produção. Algumas tentativas têm sido publicadas com o objetivo de tornar o processo automático. Entretanto, nenhuma dessas duas formas parece ser a mais adequada, pois (l) a forma manual demanda excessivo tempo dos profissionais envolvidos e pode não considerar todos os cenários necessários para evitar tempos longos de preparação dos projetas e (2) as formas automáticas apresentadas até agora demandam um número muito grande de simulações, o que inviabiliza a aplicação em reservatórios reais. O procedimento para seleção de planos de desenvolvimento proposto neste trabalho procura tirar proveito das duas formas de trabalho c é composta por procedimentos seqüenciais manuais e automatizada. Isso possibilita que a definição dos parâmetros do plano de desenvolvimento esteja integrada à análise de risco (técnico...

Partial spectral projected gradient method with active-set strategy for linearly constrained optimization

ANDRETTA, Marina; BIRGIN, Ernesto G.; MARTINEZ, J. M.
Fonte: SPRINGER Publicador: SPRINGER
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
36.967178%
A method for linearly constrained optimization which modifies and generalizes recent box-constraint optimization algorithms is introduced. The new algorithm is based on a relaxed form of Spectral Projected Gradient iterations. Intercalated with these projected steps, internal iterations restricted to faces of the polytope are performed, which enhance the efficiency of the algorithm. Convergence proofs are given and numerical experiments are included and commented. Software supporting this paper is available through the Tango Project web page: http://www.ime.usp.br/similar to egbirgin/tango/.; Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP); Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Topology optimization of structures: a minimum weight approach with stress constraints

Navarrina, F.; Muíños Pantín, Iago; Colominas Ezponda, Ignasi; Casteleiro, M.
Fonte: Elsevier Publicador: Elsevier
Tipo: Pré-impressão
ENG
Relevância na Pesquisa
37.07038%
Enviado a "Advances in engineering software" el 26/10/2004; Sizing and shape structural optimization problems are normally stated in terms of a minimum weight approach with constraints that limit the maximum allowable stresses and displacements. However, topology structural optimization problems have been usually stated in terms of a maximum stiffness (minimum compliance) approach. In this kind of formulations, the aim is to distribute a given amount of material in a certain domain, so that the stiffness of the resulting structure is maximized (the compliance, or energy of deformation, is minimized) for a given load case. Thus, the material mass is restricted to a predefined percentage of the maximum possible mass, while no stress or displacement constraints are taken into account. In this paper we analyze and compare both approaches, and we present a FEM minimum weight with stress constraints (MWSC) formulation for topology structural optimization problems. This approach does not require any stabilization technique to produce acceptable optimized results, while no truss-like final solutions are necessarily obtained. Several 2D examples are presented. The optimized solutions seem to be correct from the engineering point of view, and their appearence could be considered closer to the engineering intuition than the traditional truss-like results obtained by means of the widespread maximum stiffness (minimum compliance) approaches.

A minimum weight with stress constraints FEM approach for topology structural optimization problems

Muíños Pantín, Iago; Colominas Ezponda, Ignasi; Navarrina, F.; Casteleiro, M.
Fonte: Universidade da Corunha Publicador: Universidade da Corunha
Tipo: Conferência ou Objeto de Conferência
ENG
Relevância na Pesquisa
37.103105%
WCCM V, Fifth World Congress on Computational Mechanics, July 7–12, 2002, Vienna, Austria; Sizing and shape structural optimization problems are normally stated in terms of a minimum weight approach with constraints that limit the maximum allowable stresses and displacements. However, topology structural optimization problems have been traditionally stated in terms of a maximum stiffness (minimum compliance) approach. In this kind of formulations, the aim is to distribute a given amount of material in a certain domain, so that the stiffness of the resulting structure is maximized (the compliance, or energy of deformation, is minimized) for a given load case. Thus, the material mass is restricted to a predefined percentage of the maximum possible mass, while no stress or displacement constraints are taken into account. In this paper we analyze and compare both approaches, and we present a FEM minimum weight with stress constraints (MWSC) formulation for topology structural optimization problems. This approach does not require any stabilization technique to produce acceptable optimized results, while no truss-like final solutions are necessarily obtained. Several 2D examples are presented. The optimized solutions seem to be correct from the engineering point of view...

A minimum weight FEM formulation for Structural Topological Optimization with local stress constraints

París López, José; Muíños Pantín, Iago; Navarrina, F.; Colominas Ezponda, Ignasi; Casteleiro, M.
Fonte: Universidade da Corunha Publicador: Universidade da Corunha
Tipo: Conferência ou Objeto de Conferência
ENG
Relevância na Pesquisa
37.103105%
6th World Congresses of Structural and Multidisciplinary Optimization, Rio de Janeiro, 30 May - 03 June 2005, Brazil; Since Bendsoe and Kikuchi proposed the basic concepts in 1988, most of topology structural optimization results have been obtained so far by means of a maximum stiffness (minimum strain energy, minimum compliance) approach. In this kind of approaches, the mass is normally restricted to a given percent- age of the total maximum possible mass, while no stress constraints are taken into account. On the other hand, size and shape structural optimization problems are normally stated in terms of a minimum weight with stress constraint approach. These traditional minimum compliance statements for topology optimization problems offer some obvious advantages, since one avoids dealing with a large number of highly non-linear stress constraints. However, one can argue that this kind of statements has several important drawbacks. Thus, different solutions are obtained for different restrictions on the mass, and the final design could be unfeasible in practice since no constraints are imposed on the maximum allowed stress. On the other hand, the minimum compliance problem is said to be ill-posed, since the solution oscillates as the discretization refinement is increased. This dificulty can be easily overcome by introducing porous materials. However...

Evaluating the Impact of Climate Change Mitigation Strategies on Water Distribution System Design and Optimization

MacLeod, Stephanie Patricia
Fonte: Quens University Publicador: Quens University
Tipo: Tese de Doutorado
EN; EN
Relevância na Pesquisa
36.967178%
In response to growing environmental concerns, policy makers in Canada have been developing climate change mitigation strategies that will enable Canada to meet medium and long-term greenhouse gas (GHG) emission reduction targets. The water industry is energy- and carbon-intensive, thus the magnitude and long-term uncertainty of proposed carbon mitigation policies could have implications for water distribution system capital planning decisions that are made today. The intent of this thesis was to examine the implications of discount rate and carbon price uncertainty on cost, energy use and GHG emissions in the design/optimization of the Amherstview water distribution system in Loyalist Township, Ontario, Canada. A non-dominated sorting genetic algorithm is coupled with the hydraulic solver EPANET2 in a single-objective optimization approach to identify network expansion designs that minimize total cost as the sum of: i) capital cost of installing new and parallel pipes and of cleaning and lining existing pipes; ii) operation cost of electricity for pumping water; and iii) carbon cost levied on electricity used for pumping water. The Amherstview system was optimized for a range of discount rates and carbon prices reflective of possible climate change mitigation strategies in Canada over the next 50 years. The problem formulation framework was developed according to a “real-world” municipal approach to water distribution system design and expansion. Decision variables such as pipe sizes are restricted to “real-world” commercially-available pipe diameters and parameter values are chosen according to engineering judgment and best-estimates. Parameter uncertainty is characterized by sensitivity analysis rather than the more computationally-demanding and data-intensive Monte Carlo simulation method. The impact of pipe material selection on energy use and GHG emissions was investigated for polyvinyl chloride and cement-mortar lined ductile iron pipes. Results from this first-ever study indicate that the discount rate and carbon prices investigated had no significant influence on energy use and GHG emissions in the Amherstview system. Pipe material selection was also found to minimally affect the amount of GHG emitted in the Amherstview system.; Thesis (Master...

Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization

De Loera, J. A.; La Haye, R. N.; Oliveros, D.; Roldán-Pensado, E.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
37.166213%
The scenario approach developed by Calafiore and Campi to attack chance-constrained convex programs utilizes random sampling on the uncertainty parameter to substitute the original problem with a representative continuous convex optimization with $N$ convex constraints which is a relaxation of the original. Calafiore and Campi provided an explicit estimate on the size $N$ of the sampling relaxation to yield high-likelihood feasible solutions of the chance-constrained problem. They measured the probability of the original constraints to be violated by the random optimal solution from the relaxation of size $N$. This paper has two main contributions. First, we present a generalization of the Calafiore-Campi results to both integer and mixed-integer variables. In fact, we demonstrate that their sampling estimates work naturally for variables restricted to some subset $S$ of $\mathbb R^d$. The key elements are generalizations of Helly's theorem where the convex sets are required to intersect $S \subset \mathbb R^d$. The size of samples in both algorithms will be directly determined by the $S$-Helly numbers. Motivated by the first half of the paper, for any subset $S \subset \mathbb R^d$, we introduce the notion of an $S$-optimization problem...

Greedy Sparsity-Constrained Optimization

Bahmani, Sohail; Raj, Bhiksha; Boufounos, Petros
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
37.30038%
Sparsity-constrained optimization has wide applicability in machine learning, statistics, and signal processing problems such as feature selection and compressive Sensing. A vast body of work has studied the sparsity-constrained optimization from theoretical, algorithmic, and application aspects in the context of sparse estimation in linear models where the fidelity of the estimate is measured by the squared error. In contrast, relatively less effort has been made in the study of sparsity-constrained optimization in cases where nonlinear models are involved or the cost function is not quadratic. In this paper we propose a greedy algorithm, Gradient Support Pursuit (GraSP), to approximate sparse minima of cost functions of arbitrary form. Should a cost function have a Stable Restricted Hessian (SRH) or a Stable Restricted Linearization (SRL), both of which are introduced in this paper, our algorithm is guaranteed to produce a sparse vector within a bounded distance from the true sparse optimum. Our approach generalizes known results for quadratic cost functions that arise in sparse linear regression and Compressive Sensing. We also evaluate the performance of GraSP through numerical simulations on synthetic data, where the algorithm is employed for sparse logistic regression with and without $\ell_2$-regularization.

Learning restricted Bayesian network structures

Hemmecke, Raymond; Lindner, Silvia; Studený, Milan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/11/2010
Relevância na Pesquisa
37.151396%
Bayesian networks are basic graphical models, used widely both in statistics and artificial intelligence. These statistical models of conditional independence structure are described by acyclic directed graphs whose nodes correspond to (random) variables in consideration. A quite important topic is the learning of Bayesian network structures, which is determining the best fitting statistical model on the basis of given data. Although there are learning methods based on statistical conditional independence tests, contemporary methods are mainly based on maximization of a suitable quality criterion that evaluates how good the graph explains the occurrence of the observed data. This leads to a nonlinear combinatorial optimization problem that is in general NP-hard to solve. In this paper we deal with the complexity of learning restricted Bayesian network structures, that is, we wish to find network structures of highest score within a given subset of all possible network structures. For this, we introduce a new unique algebraic representative for these structures, called the characteristic imset. We show that these imsets are always 0-1-vectors and that they have many nice properties that allow us to simplify long proofs for some known results and to easily establish new complexity results for learning restricted Bayes network structures.

EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

Shi, Wei; Ling, Qing; Wu, Gang; Yin, Wotao
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
37.027102%
Recently, there have been growing interests in solving consensus optimization problems in a multi-agent network. In this paper, we develop a decentralized algorithm for the consensus optimization problem $$\min\limits_{x\in\mathbb{R}^p}~\bar{f}(x)=\frac{1}{n}\sum\limits_{i=1}^n f_i(x),$$ which is defined over a connected network of $n$ agents, where each function $f_i$ is held privately by agent $i$ and encodes the agent's data and objective. All the agents shall collaboratively find the minimizer while each agent can only communicate with its neighbors. Such a computation scheme avoids a data fusion center or long-distance communication and offers better load balance to the network. This paper proposes a novel decentralized EXact firsT-ordeR Algorithm (abbreviated as EXTRA) to solve the consensus optimization problem. "exact" means that it can converge to the exact solution. EXTRA can use a fixed large step size, {which is independent of the network size}, and has synchronized iterations. The local variable of every agent $i$ converges uniformly and consensually to an exact minimizer of $\bar{f}$. In contrast, the well-known decentralized gradient descent (DGD) method must use diminishing step sizes in order to converge to an exact minimizer. EXTRA and DGD have the same choice of mixing matrices and similar per-iteration complexity. EXTRA...

Distributed Convex Optimization for Continuous-Time Dynamics with Time-Varying Cost Functions

Rahili, Salar; Ren, Wei
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 17/07/2015
Relevância na Pesquisa
37.027102%
In this paper, a time-varying distributed convex optimization problem is studied for continuous-time multi-agent systems. The objective is to minimize the sum of local time-varying cost functions, each of which is known to only an individual agent, through local interaction. Here the optimal point is time varying and creates an optimal trajectory. Control algorithms are designed for the cases of single-integrator and double-integrator dynamics. In both cases, a centralized approach is first introduced to solve the optimization problem. Then this problem is solved in a distributed manner and an algorithm based on the signum function is proposed where each agent relies only on its own position and the relative positions between itself and its neighbors. To relax the restricted assumption imposed on feasible cost functions, an estimator based algorithm using the signum function is proposed where each agent uses dynamic average tracking as a tool to estimate the centralized control input. As a trade-off the estimator based algorithm necessitates communication between neighbors. Then in the case of double-integrator dynamics, we consider further extensions of our proposed algorithms. Two continuous algorithms based on respectively, a time-varying and a fixed boundary layer are proposed as continuous approximations of the signum function. Inter-agent collision is another problem that may arise when implementing the proposed algorithms for physical agents. A distributed convex optimization problem with swarm tracking behavior is hence introduced for both single-integrator and double-integrator dynamics. It is shown that the center of the agents tracks the optimal trajectory...

Convergence of the restricted Nelder-Mead algorithm in two dimensions

Lagarias, Jeffrey C.; Poonen, Bjorn; Wright, Margaret H.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/04/2011
Relevância na Pesquisa
37.151997%
The Nelder-Mead algorithm, a longstanding direct search method for unconstrained optimization published in 1965, is designed to minimize a scalar-valued function f of n real variables using only function values, without any derivative information. Each Nelder-Mead iteration is associated with a nondegenerate simplex defined by n+1 vertices and their function values; a typical iteration produces a new simplex by replacing the worst vertex by a new point. Despite the method's widespread use, theoretical results have been limited: for strictly convex objective functions of one variable with bounded level sets, the algorithm always converges to the minimizer; for such functions of two variables, the diameter of the simplex converges to zero, but examples constructed by McKinnon show that the algorithm may converge to a nonminimizing point. This paper considers the restricted Nelder-Mead algorithm, a variant that does not allow expansion steps. In two dimensions we show that, for any nondegenerate starting simplex and any twice-continuously differentiable function with positive definite Hessian and bounded level sets, the algorithm always converges to the minimizer. The proof is based on treating the method as a discrete dynamical system...

Restricted normal cones and sparsity optimization with affine constraints

Bauschke, Heinz H.; Luke, D. Russell; Phan, Hung M.; Wang, Xianfu
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 02/05/2012
Relevância na Pesquisa
37.443525%
The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved non convex relaxations. In this paper we consider the elementary method of alternating projections (MAP) for solving the sparsity optimization problem without employing convex heuristics. In a parallel paper we recently introduced the restricted normal cone which generalizes the classical Mordukhovich normal cone and reconciles some fundamental gaps in the theory of sufficient conditions for local linear convergence of the MAP algorithm. We use the restricted normal cone together with the notion of superregularity, which is naturally satisfied for the affine sparse optimization problem, to obtain local linear convergence results with estimates for the radius of convergence of the MAP algorithm applied to sparsity optimization with an affine constraint.

Fault-Tolerant Distributed Optimization (Part IV): Constrained Optimization with Arbitrary Directed Networks

Su, Lili; Vaidya, Nitin H.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/11/2015
Relevância na Pesquisa
37.103105%
We study the problem of constrained distributed optimization in multi-agent networks when some of the computing agents may be faulty. In this problem, the system goal is to have all the non-faulty agents collectively minimize a global objective given by weighted average of local cost functions, each of which is initially known to a non-faulty agent only. In particular, we are interested in the scenario when the computing agents are connected by an arbitrary directed communication network, some of the agents may suffer from crash faults or Byzantine faults, and the estimate of each agent is restricted to lie in a common constraint set. This problem finds its applications in social computing and distributed large-scale machine learning. The fault-tolerant multi-agent optimization problem was first formulated by Su and Vaidya, and is solved when the local functions are defined over the whole real line, and the networks are fully-connected. In this report, we consider arbitrary directed communication networks and focus on the scenario where, local estimates at the non-faulty agents are constrained, and only local communication and minimal memory carried across iterations are allowed. In particular, we generalize our previous results on fully-connected networks and unconstrained optimization to arbitrary directed networks and constrained optimization. As a byproduct...

Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles

Ollivier, Yann; Arnold, Ludovic; Auger, Anne; Hansen, Nikolaus
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
37.376382%
We present a canonical way to turn any smooth parametric family of probability distributions on an arbitrary search space $X$ into a continuous-time black-box optimization method on $X$, the \emph{information-geometric optimization} (IGO) method. Invariance as a design principle minimizes the number of arbitrary choices. The resulting \emph{IGO flow} conducts the natural gradient ascent of an adaptive, time-dependent, quantile-based transformation of the objective function. It makes no assumptions on the objective function to be optimized. The IGO method produces explicit IGO algorithms through time discretization. It naturally recovers versions of known algorithms and offers a systematic way to derive new ones. The cross-entropy method is recovered in a particular case, and can be extended into a smoothed, parametrization-independent maximum likelihood update (IGO-ML). For Gaussian distributions on $\mathbb{R}^d$, IGO is related to natural evolution strategies (NES) and recovers a version of the CMA-ES algorithm. For Bernoulli distributions on $\{0,1\}^d$, we recover the PBIL algorithm. From restricted Boltzmann machines, we obtain a novel algorithm for optimization on $\{0,1\}^d$. All these algorithms are unified under a single information-geometric optimization framework. Thanks to its intrinsic formulation...

Dropping Convexity for Faster Semi-definite Optimization

Bhojanapalli, Srinadh; Kyrillidis, Anastasios; Sanghavi, Sujay
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
37.00825%
In this paper, we study the minimization of a convex function $f(X)$ over the space of $n\times n$ positive semidefinite matrices $X\succeq 0$, but when the problem is recast as the non-convex problem $\min_U g(U)$ where $g(U) := f(UU^\top)$, with $U$ being an $n\times r$ matrix and $r\leq n$. We study the performance of gradient descent on $g$ -- which we refer to as Factored Gradient Descent (FGD) -- under standard assumptions on the original function $f$. We provide a rule for selecting the step size, and with this choice show that the local convergence rate of FGD mirrors that of standard gradient descent on the original $f$ -- the error after $k$ steps is $O(1/k)$ for smooth $f$, and exponentially small in $k$ when $f$ is (restricted) strongly convex. Note that $g$ is not locally convex. In addition, we provide a procedure to initialize FGD for (restricted) strongly convex objectives and when one only has access to $f$ via a first-order oracle. FGD and similar procedures are widely used in practice for problems that can be posed as matrix factorization; to the best of our knowledge, ours is the first paper to provide precise convergence rate guarantees for general convex functions under standard convex assumptions.; Comment: 42 pages