Local optimum

In applied mathematics and computer science, a local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. This is in contrast to a global optimum, which is the optimal solution among all possible solutions, not just those in a particular neighborhood of values. Importantly, a global optimum is necessarily a local optimum, but a local optimum is not necessarily a global optimum. Continuous domain When the function to be optimized is continuous, it may be possible to employ calculus to find local optima. If the first derivative exists everywhere, it can be equated to zero; if the function has an unbounded domain, for a point to be a local optimum it is necessary that it satisfy this equation. Then the second derivative test provides a sufficient condition for the point to be a local maximum or local minimum. Search techniques Local search or hill climbing methods for solving

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (25)

Related publications

Related people (2)

Related people

Related units (4)

Related units

Related concepts (5)

Related concepts

Related courses (16)

Related courses

Related lectures (25)

Related lectures

Simulated annealing

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large se

Local search (optimization)

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maxi

Hill climbing

In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a pro

Optimal Control Combining Emulation and Imitation to Acquire Physical Assistance Skills

Sylvain Calinon, Teguh Santoso Lembono, Amirreza Razmjoo Fard

paper studies exploiting action-level learning (imitation) in the optimal control problem context. Cost functions defined by the optimal control methods are similar to the goal-level learning (emulation) in animals. However, imitating the robot's or others' (e.g. human's) previous experiences (demonstrations) could help the system to improve its performances. We propose to use demonstrations more efficiently by predicting an initialization for the optimal control problems (OCPs) and adding an imitation term to the cost functions. While the predicted initial guess initializes the OCPs close to their local optima, the imitation term guides the optimization, resulting in a faster convergence rate. We test our algorithm in a physical assistive task where a robot should help a human perform a sit-to-stand (STS) task. We define this task as two optimal control problems. The first OCP predicts the human's desired assistance and the other one controls the robot. We have tested our method on different experiments with different conditions for the human in which the robot should quickly solve the two optimization problems exploiting some demonstrations of how it can perform the task. Our proposed method reduced the number of iterations by more than 90% and 70% for the human assistance prediction and the robot controller, respectively, compared to the standard problem which does not take the demonstrations into account.

IEEE2021

The Minimization of Public Facilities With Enhanced Genetic Algorithms Using War Elimination

Michael Mark

In this paper, we focus on the problem of minimizing a network of state facilities that provide essential public services (schools, offices, and hospitals). The goal is to reduce the size of the network in order to minimize the costs associated with it. However, it is essential that every customer should be able to access an appropriate service center within a reachable distance. This problem can arise in various scenarios, such as a government cutting back on public service spending in remote areas or as a reaction to changing demographics (population increase/decrease). In general, this task is NP-hard which makes the problem particularly hard to scale. Therefore, for larger problems, heuristic methods must be employed to find an approximation of the optimum. To solve this problem with satisfactory results, we have presented an enhanced version of the genetic algorithm based on war elimination and migration operations. This modification overcomes the well-known shortcoming of GAs when the population becomes gradually more and more similar, these results in a diversity decrease which in turn leads to a sub-optimal local minimum. We test the performance of the novel algorithm against the standard heuristic benchmarks on the widely accepted Beasley OR-library dataset for optimization problems. Finally, we provide a case study based on real data, where a municipality tries to minimize the number of schools in a region while satisfying accessibility and other region-specific constraints.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

Variable space search for graph coloring

Matthieu Plumettaz, Nicolas Zufferey

Let G = (V, E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1, ..., k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms. (c) 2008 Elsevier B.V. All rights reserved.

2008

ME-454: Modelling and optimization of energy systems

The goal of the lecture is to present and apply techniques for the modelling and the thermo-economic optimisation of industrial process and energy systems. The lecture covers the problem statement, the solving methods for the simulation and the single and multi-objective optimisation problems.

MICRO-455: Applied machine learning

Real-world engineering applications must cope with a large dataset of dynamic variables, which cannot be well approximated by classical or deterministic models. This course gives an overview of methods from Machine Learning for the analysis of non-linear, highly noisy and multi dimensional data

MATH-600: Optimization and simulation

Master state-of-the art methods in optimization with heuristics and simulation. Work involves:

reading the material beforehand
class hours to discuss the material and solve problems
homework