# Self-regular functions and new search directions for linear and semidefinite optimization

@article{Peng2002SelfregularFA, title={Self-regular functions and new search directions for linear and semidefinite optimization}, author={Jiming Peng and Kees Roos and Tam{\'a}s Terlaky}, journal={Mathematical Programming}, year={2002}, volume={93}, pages={129-171} }

Abstract.In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n$\frac{q+1}{2q}$log$\frac{n… Expand

#### Topics from this paper

#### 212 Citations

A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function

- Mathematics
- 2012

AbstractIn this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It… Expand

A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function

- Mathematics
- 2020

As indicated in the recent studies about primal-dual interior-point methods (IPMs) based on kernel functions, a kernel function not only serves to determine the search direction and measure the… Expand

Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

- Mathematics, Computer Science
- J. Math. Model. Algorithms
- 2005

This paper presents a primal-dual interior-point algorithm for SDO problems based on a simple kernel function which was first presented at the Proceedings of Industrial Symposium and Optimization Day, Australia, November 2002; the function is not self-regular. Expand

An interior Point Approach for Semidefinite Optimization Using New Proximity Functions

- Mathematics, Computer Science
- Asia Pac. J. Oper. Res.
- 2009

It is proved with simple analysis that the new class-based large-update primal-dual IPMs enjoy an iteration bound to solve Semidefinite Optimization (SDO) problems with special choice of the parameters of the newclass. Expand

New parameterized kernel functions for linear optimization

- Mathematics, Computer Science
- J. Glob. Optim.
- 2012

A new class of parameterized kernel functions is proposed for the development of primal-dual interior-point algorithms for solving linear programming problems and leads to a complexity bounds of O(\sqrt{n}\,{\rm log}\,n\,log}\,\frac{n}{\epsilon}\right)} for the large-update primal- dual interior point methods. Expand

A Comparative Study of Kernel Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization

- Mathematics, Computer Science
- SIAM J. Optim.
- 2004

It is shown that small-update methods based on the new kernel functions all have the same complexity as the classical primal-dual IPM, namely, $O(\sqrt{n}(\log n)\log\frac{n}{\e})$. Expand

Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term

- Mathematics
- 2015

AbstractIn this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization (SDO) problems. The proposed algorithm is… Expand

A Class of Large-and Small-update Primal-dual Interior-point Algorithms for Linear Optimization ∗

- 2006

In this paper we present a class of polynomial primal-dual interior-point algorithms for linear optimization based on a new class of kernel functions. This class is fairly general and includes the… Expand

A Class of Large-Update and Small-Update Primal-Dual Interior-Point Algorithms for Linear Optimization

- Mathematics
- 2008

In this paper we present a class of polynomial primal-dual interior-point algorithms for linear optimization based on a new class of kernel functions. This class is fairly general and includes the… Expand

A primal-dual large-update interior-point algorithm for P*(κ)-LCP based on a new class of kernel functions

- Mathematics
- 2018

AbstractIn this paper, we propose a large-update primal-dual interior point algorithm for P*(κ)-linear complementarity problem. The method is based on a new class of kernel functions which is neither… Expand

#### References

SHOWING 1-10 OF 30 REFERENCES

A new class of polynomial primal-dual methods for linear and semidefinite optimization

- Mathematics, Computer Science
- Eur. J. Oper. Res.
- 2002

By using some new analysis tools, it is proved that the large-update method for LO based on the new search direction has a polynomial complexity of O(n4/(4+ρ)log(n/e)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. Expand

Primal-dual algorithms for linear programming based on the logarithmic barrier method

- Mathematics
- 1994

AbstractIn this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive… Expand

A study of search directions in primal-dual interior-point methods for semidefinite programming

- Mathematics
- 1999

We discuss several different search directions which can be used in primal-dual interior-point methods for semidefinite programming problems and investigate their theoretical properties, including… Expand

An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming

- Mathematics
- 1986

For an arbitrary, finite intersection of halfspaces bi≥ i=1,...,m, xeRn, i.e. a bounded, convex polyhedron P(am, bm) we define a "central" point x(am,bm)eP, which has the following properties: x… Expand

Self-Scaled Barriers and Interior-Point Methods for Convex Programming

- Mathematics, Computer Science
- Math. Oper. Res.
- 1997

This paper provides a theoretical foundation for efficient interior-point algorithms for convex programming problems expressed in conic form, when the cone and its associated barrier are self-scaled, with long-step and symmetric primal-dual methods. Expand

On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms

- Mathematics, Computer Science
- Math. Program.
- 1995

Under the monotonicity assumption, polynomial complexity bounds are established for two variants of the Mehrotra-type predictor—corrector interior-point algorithms. Expand

A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension

- Mathematics, Computer Science
- Math. Oper. Res.
- 1990

An algorithm for linear and convex quadratic programming problems that uses power series approximation of the weighted barrier path that passes through the current iterate in order to find the next iterate that can be interpreted as an affine scaling algorithm in the primal-dual setup is described. Expand

Primal-Dual Interior-Point Methods

- Mathematics, Computer Science
- Other Titles in Applied Mathematics
- 1997

This chapter discusses Primal Method Primal-Dual Methods, Path-Following Algorithm, and Infeasible-Interior-Point Algorithms, and their applications to Linear Programming and Interior-Point Methods. Expand

New Complexity Analysis of the Primal—Dual Newton Method for Linear Optimization

- Mathematics, Computer Science
- Ann. Oper. Res.
- 2000

This work presents some new analysis tools, based on a proximity measure introduced by Jansen et al., in 1994, that may help to close the gap between the practical behavior of the algorithms and the theoretical performance results, especially for so-called large-update methods. Expand

Interior-point polynomial algorithms in convex programming

- Mathematics, Computer Science
- Siam studies in applied mathematics
- 1994

This book describes the first unified theory of polynomial-time interior-point methods, and describes several of the new algorithms described, e.g., the projective method, which have been implemented, tested on "real world" problems, and found to be extremely efficient in practice. Expand