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...

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.

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

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

We propose a modified standard embedding for solving the linear complementarity problem (LCP). This embedding is a special one-parametric optimization problem $P\left(t\right),t\in [0,1]$. Under the conditions (A3) (the Mangasarian–Fromovitz Constraint Qualification is satisfied for the feasible set $M\left(t\right)$ depending on the parameter $t$), (A4) ($P\left(t\right)$ 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\left(0\right)$ with a certain...

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...

In this paper, we propose a large-update primal-dual interior point algorithm for linear optimization. The method is based on a new class of kernel functions which differs from the existing kernel functions in which it has a double barrier term. The investigation according to it yields the best known iteration bound $O(\sqrt{n}log\left(n\right)log\left(\frac{n}{\epsilon }\right))$ for large-update algorithm with the special choice of its parameter $m$ and thus improves the iteration bound obtained in Bai et al. [El Ghami2004] for large-update algorithm.

In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in ${\Re }^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.

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.

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.

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($\sqrt{n}$ log $\frac{n}{\epsilon }$), which is best-known bound so far.

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...

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(nlog\frac{{\left(x^0\right)}^T{s}^0}{ϵ})$ iteration complexity analogous to the classical...

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.

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\left(\sqrt{n}L\right)$ 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.