Interior-point method

Summary

Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s. In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. In contrast to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encode the convex set. Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. The idea of encoding

Official source

https://en.wikipedia.org/wiki/Interior-point_method

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 (16)

Related publications

Related people (1)

Related people

Related units (1)

Related units

Related concepts (13)

Related concepts

Related courses (12)

The course provides an introduction to scientific computing. Several numerical methods are presented for the computer solution of mathematical problems arising in different applications. The software MATLAB is used to solve the problems and verify the theoretical properties of the numerical methods.

This course presents numerical methods for the solution of mathematical problems such as systems of linear and non-linear equations, functions approximation, integration and differentiation and differential equations.

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems.

Related courses

Related lectures (28)

Related lectures

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

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

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