80 research outputs found
Hybrid conjugate gradient-BFGS methods based on Wolfe line search
No full textIn this paper, we present some hybrid methods for solving unconstrained optimization problems. These methods are defined using proper combinations of the search directions and included parameters in conjugate gradient and quasi-Newton method of Broyden–Fletcher–Goldfarb–Shanno (CG-BFGS). Their global convergence under the Wolfe line search is analyzed for general objective functions. Numerical experiments show the superiority of the modified hybrid (CG-BFGS) method with respect to some existing methods.
Mathematics Subject Classification (2010): 65K05, 90C26, 90C30.
Received 23 December 2019; Accepted 08 February 2020
New effective projection method for variational inequalities problem
No full textAmong the most used methods to solve the variational inequalities problem (VIP), there
exists an important class known as projection methods, these last are based primarily on
the fixed point reformulation. The first proposed methods of projection suffered from
major theoretical and algorithmic difficulties. Several studies were completed, in
particular, those of Iusem, Solodov and Svaiter and that of Wang et al.
with an aim to overcome these difficulties. Consequently, many developments were
brought to improve the algorithmic behavior of this type of methods. In the same form of
the algorithms of projection presented by the authors quoted above and under the same
convergence hypotheses, we propose in this paper a new algorithm with a new displacement
step which must satisfy a certain condition, this last ensures a faster convergence
towards a solution. The algorithm is well defined and the theoretical results of
convergence are suitably established. A comparative numerical study is carried out between
the two algorithms (the algorithm of Solodov and Svaiter, the algorithm Wang et
al.) and the new one. The results obtained by the new algorithm were very
encouraging and show clearly the impact of our modifications
A relaxed logarithmic barrier method for semidefinite programming
No full textInterior point methods applied to optimization problems have known a remarkable evolution in the last decades. They are used with success in linear, quadratic and semidefinite programming. Among these methods, primal-dual central trajectory methods have a polynomial convergence and are credited of a good numerical behavior. In this paper, we propose a new central trajectory method where a relaxation parameter is introduced in order to give more flexibility to the theoretical and numerical aspects of the perturbed problems and accelerate the convergence of the algorithm. This claim is confirmed by numerical tests showing the good behavior of the algorithm which is proposed in this paper
Improving complexity of Karmarkar's approach for linear programming
No full textIn this paper, we are interested in the performance of Karmarkar's projective algorithm for linear programming. Based on the work of Schrijver, we offer a new displacement step better than Schrijver's one which led to a moderate improvement in the behavior of the algorithm shift. We show later that the algorithm converges after iterations.
This purpose is confirmed by numerical experiments showing the efficiency of the obtained algorithm, which are presented in the end of the paper
Comparative numerical study between line search methods and majorant functions in barrier logarithmic methods for linear programming
No full textThis paper presents a comparative numerical study between line search methods and majorant functions to compute the displacement step in barrier logarithmic method for linear programming. This study favorate majorant function on line search which is promoted by numerical experiments
Comparative numerical study between line search methods and majorant functions in barrier logarithmic methods for linear programming
No full textThis paper presents a comparative numerical study between line search methods and majorant functions to compute the displacement step in barrier logarithmic method for linear programming. This study favorate majorant function on line search which is promoted by numerical experiments
Interior point methods and their applications to semidefinite optimization problems.
No full textLes méthodes de points intérieurs sont bien connues comme les plus efficaces pour résoudre les problèmes d’optimisation. Ces méthodes possèdent une convergence polynômiale et un bon comportement numérique. Dans cette recherche, nous nous sommes intéressés à une étude théorique, algorithmique et numérique des méthodes de points intérieurs pour la programmation semi-définie.En effet, on présente dans une première partie un algorithme réalisable projectif primal-dual de points intérieurs de type polynômial à deux phases, où on a introduit trois nouvelles alternatives efficaces pour calculer le pas de déplacement.Ensuite, dans la deuxième partie, on s’intéresse aux méthodes de type trajectoire centrale primale-duale via une fonction noyau, nous proposons deux nouvelles fonctions noyaux à terme logarithmique qui donnent la meilleure complexité algorithmique, obtenue jusqu’à présent.Interior point methods are well known as the most efficient to solve optimization problems. These methods have a polynomial convergence and good behavior. In this research, we are interested in a theoretical, numerical and an algorithmic study of interior-point methods for semidefinite programming.Indeed, we present in a first part, a primal-dual projective interior point algorithm of polynomial type with two phases, where we introduced three new effective alternatives for computing the displacement step.Then, in the second part, we are interested in a primal-dual central trajectory method via a kernel function, we proposed two new kernel functions with a logarithmic term that give the best-known complexity results
A New and Efficient Interior Point Method Based on a Weight Vector for Solving LCCO Problems
No full textIn this paper, we propose a new full-Newton step weighted interior point method for solving linearly constrained convex optimization problems (LCCO). This method is based on relaxing the complementarity condition using a non-negative variable weight vector to overcome the difficulty of finding an initial point in the neighborhood of central path required to start the classical interior point algorithms. With a zero of variable weight vector, the limit of the weighted path exists and satisfies the complementarity condition, this limit yields an optimal solution of LCCO problem. The advantage of this method is the use of a full-Newton step, which eliminates the step-size calculations with a quadratic rate of convergence. We study the complexity analysis of our method and derive a new iteration bound for small-update methods. Finally, some comparative numerical tests are stated to validate the effectiveness of our new method
- …
