Page 1 Next

Displaying 1 – 20 of 53

Showing per page

A globally convergent non-interior point algorithm with full Newton step for second-order cone programming

Liang Fang, Guoping He, Li Sun (2009)

Applications of Mathematics

A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary...

A logarithm barrier method for semi-definite programming

Jean-Pierre Crouzeix, Bachir Merikhi (2008)

RAIRO - Operations Research

This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.

A modified algorithm for the strict feasibility problem

D. Benterki, B. Merikhi (2001)

RAIRO - Operations Research - Recherche Opérationnelle

In this note, we present a slight modification of an algorithm for the strict feasibility problem. This modification reduces the number of iterations.

A modified standard embedding for linear complementarity problems

Sira Allende Allonso, Jürgen Guddat, Dieter Nowack (2004)

Kybernetika

We propose a modified standard embedding for solving the linear complementarity problem (LCP). This embedding is a special one-parametric optimization problem P ( t ) , t [ 0 , 1 ] . Under the conditions (A3) (the Mangasarian–Fromovitz Constraint Qualification is satisfied for the feasible set M ( t ) depending on the parameter t ), (A4) ( P ( t ) is Jongen–Jonker– Twilt regular) and two technical assumptions, (A1) and (A2), there exists a path in the set of stationary points connecting the chosen starting point for P ( 0 ) with a certain...

A new barrier for a class of semidefinite problems

Erik A. Papa Quiroz, Paolo Roberto Oliveira (2006)

RAIRO - Operations Research

We introduce a new barrier function to solve a class of Semidefinite Optimization Problems (SOP) with bounded variables. That class is motivated by some (SOP) as the minimization of the sum of the first few eigenvalues of symmetric matrices and graph partitioning problems. We study the primal-dual central path defined by the new barrier and we show that this path is analytic, bounded and that all cluster points are optimal solutions of the primal-dual pair of problems. Then, using some ideas from semi-analytic...

A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ

Marcia Fampa, Nelson Maculan (2010)

RAIRO - Operations Research

In this paper, we present a new mathematical programming formulation for the Euclidean Steiner Tree Problem (ESTP) in ℜ. We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ-optimal solution for this latter problem using interior-point algorithm.

A new relaxation in conic form for the euclidean Steiner problem in n

Marcia Fampa, Nelson Maculan (2001)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in n . We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ -optimal solution for this latter problem using interior-point algorithm.

A numerical feasible interior point method for linear semidefinite programs

Djamel Benterki, Jean-Pierre Crouzeix, Bachir Merikhi (2007)

RAIRO - Operations Research

This paper presents a feasible primal algorithm for linear semidefinite programming. The algorithm starts with a strictly feasible solution, but in case where no such a solution is known, an application of the algorithm to an associate problem allows to obtain one. Finally, we present some numerical experiments which show that the algorithm works properly.

A Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization

Y. Q. Bai, F. Y. Wang, X. W. Luo (2010)

RAIRO - Operations Research

In this paper we propose a primal-dual interior-point algorithm for convex quadratic semidefinite optimization problem. The search direction of algorithm is defined in terms of a matrix function and the iteration is generated by full-Newton step. Furthermore, we derive the iteration bound for the algorithm with small-update method, namely, O( n log n ε ), which is best-known bound so far.

A self-adaptive trust region method for the extended linear complementarity problems

Zhensheng Yu, Qiang Li (2009)

Applications of Mathematics

By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under...

An adaptive long step interior point algorithm for linear optimization

Maziar Salahi (2010)

Kybernetika

It is well known that a large neighborhood interior point algorithm for linear optimization performs much better in implementation than its small neighborhood counterparts. One of the key elements of interior point algorithms is how to update the barrier parameter. The main goal of this paper is to introduce an “adaptive” long step interior-point algorithm in a large neighborhood of central path using the classical logarithmic barrier function having O ( n log ( x 0 ) T s 0 ϵ ) iteration complexity analogous to the classical...

An analytic center cutting plane algorithm for finding equilibrium points

Fernanda M.P. Raupp, Wilfredo Sosa (2006)

RAIRO - Operations Research

We present a variant of the analytic center cutting plane algorithm proposed by Goffin et al. (1996) to approximately solve equilibrium problems as proposed by Blum and Oettli (1994), which include as particular problems the variational inequalities problem, the Nash equilibria problem in non-cooperative games, the convex minimization problem, and the fixed point problem. Furthermore, we analyze the convergence and complexity of the modified algorithm.

An interior point algorithm for convex quadratic programming with strict equilibrium constraints

Rachid Benouahboun, Abdelatif Mansouri (2010)

RAIRO - Operations Research

We describe an interior point algorithm for convex quadratic problem with a strict complementarity constraints. We show that under some assumptions the approach requires a total of O ( n L ) number of iterations, where L is the input size of the problem. The algorithm generates a sequence of problems, each of which is approximately solved by Newton's method.

An interior point algorithm for convex quadratic programming with strict equilibrium constraints

Rachid Benouahboun, Abdelatif Mansouri (2005)

RAIRO - Operations Research - Recherche Opérationnelle

We describe an interior point algorithm for convex quadratic problem with a strict complementarity constraints. We show that under some assumptions the approach requires a total of O ( n L ) number of iterations, where L is the input size of the problem. The algorithm generates a sequence of problems, each of which is approximately solved by Newton’s method.

Currently displaying 1 – 20 of 53

Page 1 Next