Home // INFOCOMP 2018, The Eighth International Conference on Advanced Communications and Computation // View article

A Simplex Algorithm with the Smallest Index Rule for Concave Quadratic Programming

Authors:
Mohand Bentobache
Mohamed Telli
Abdelkader Mokhtari

Keywords: Concave quadratic programming; Local minimum; Global minimum, Simplex algorithm, Numerical experiments.

Abstract:
In this work, we propose a new algorithm called "Simplex Algorithm with the Smallest Index Rule" for finding a local minimum of a concave quadratic function subject to linear equality and nonnegativity constraints. First, we present and prove a new sufficient and necessary condition for local optimality, then we describe the developed algorithm and we give a numerical example for illustration purpose. In order to prove the efficiency of our algorithm, we developed an implementation using MATLAB, then we conducted numerical experiments on randomly generated and Rusakov's concave quadratic test problems. The obtained numerical results show that our algorithm outperforms the branch and bound algorithm suggested by Rusakov in terms of CPU time and it gives the global optimal solution for the Rusakov's test problems. Furthermore, it gives the global optimum for some generated test problems and it finds, for other problems, a local minimizer which can be used to initialize global optimization algorithms.

Pages: 88 to 93

Copyright: Copyright (c) IARIA, 2018

Publication date: July 22, 2018

Published in: conference

ISSN: 2308-3484

ISBN: 978-1-61208-655-2

Location: Barcelona, Spain

Dates: from July 22, 2018 to July 26, 2018