Méthodes de points intérieurs

Résumé

vignette|Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre. vignette|Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre vignette|Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique. Elles ont l'intérêt d'être polynomiales lorsqu'on les applique aux problèmes d'optimisation linéaire, quadratique convexe, semi-définie positive ; et plus généralement aux problèmes d'optimisation convexe, pourvu que l'on dispose d'une barrière auto-concordante représentant l'ensemble admissible, calculable en temps polynomial (ce n'est pas toujours le cas, car certains problèmes d'optimisation convexe sont NP-difficiles (voir Problème NP-complet)). Les méthodes de points intérieurs se répartissent en plusieurs familles :

les méthodes de chemin central
les méthodes de réduction de p

Source officielle

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

A Non-Euclidean Gradient Descent Framework for Non-Convex Matrix Factorization

Volkan Cevher, Ya-Ping Hsieh, Yu-Chun Kao, Rabeeh Karimi Mahabadi, Anastasios Kyrillidis

We study convex optimization problems that feature low-rank matrix solutions. In such scenarios, non-convex methods offer significant advantages over convex methods due to their lower space complexity as well as faster convergence speed. Moreover, many of these methods feature rigorous approximation guarantees. Non-convex algorithms are simple to analyze and implement as they perform Euclidean gradient descent on matrix factors. In contrast, this paper derives non-Euclidean optimization frame- work in the non-convex setting that takes nonlinear gradient steps on the factors. We prove convergence rates to the global minimum under appropriate assumptions. We provide numerical evidence with Fourier Ptychography and FastText applications using real data that shows our approach can significantly enhance solution quality

2018

Chargement

Smoothing technique for nonsmooth composite minimization with linear operator

Volkan Cevher, Van Quang Nguyen

We introduce and analyze an algorithm for the minimization of convex functions that are the sum of differentiable terms and proximable terms composed with linear operators. The method builds upon the recently developed smoothed gap technique. In addition to a precise convergence rate result, valid even in the presence of linear inclusion constraints, this new method allows an explicit treatment of the gradient of differentiable functions and can be enhanced with line-search. We also study the consequences of restarting the acceleration of the algorithm at a given frequency. These new features are not classical for primal-dual methods and allow us to solve difficult large scale convex optimization problems. We numerically illustrate the superior performance of the algorithm on basis pursuit, TV-regularized least squares regression and L1 regression problems against the state-of-the-art.

2017

Chargement

This paper addresses the reconstruction of high resolution omnidirectional images from multiple low resolution images with inexact registration. When omnidirectional images from low resolution vision sensors can be uniquely mapped on the 2-sphere, such a reconstruction can be described as a transform domain super-resolution problem in the spherical imaging framework. We describe how several spherical images with arbitrary rotations in the SO(3) rotation group contribute to the reconstruction of a high resolution image with help of the Spherical Fourier Transform (SFT). As low resolution images might not be perfectly registered in practice, the impact of inaccurate alignment on the transform coefficients is further analyzed. We then cast the joint registration and super- resolution problem as a total least squares norm minimization problem in the SFT domain. A l1- regularized total least squares problem is also considered. The regularized problem is solved efficiently by interior point methods. Experiments with synthetic and natural images show that the proposed scheme leads to effective reconstruction of high resolution images even when large registration errors exist in the low resolution images. The quality of the reconstructed images also increases rapidly with the number of low resolution images, which demonstrates the benefits of the proposed solution in super-resolution schemes. Finally, we highlight the benefit of the additional regularization constraint that clearly leads to reduced noise and improved reconstruction quality.

Institute of Electrical and Electronics Engineers2011

Chargement