TY - JOUR
T1 - A Feasible Direction Algorithm Without Line Search for Solving Max-Bisection Problems
AU - Feng-Min Xu, Cheng-Xian Xu & Hong-Gang Xue
JO - Journal of Computational Mathematics
VL - 6
SP - 619
EP - 634
PY - 2005
DA - 2005/12
SN - 23
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jcm/8842.html
KW - Max-Bisection problem, Feasible direction algorithm, NCP function, Convergence.
AB - <p style="text-align: justify;">This paper concerns the solution of the NP-hard max-bisection problems. NCP functions are employed to convert max-bisection problems into continuous nonlinear programming problems. Solving the resulting continuous nonlinear programming problem generates a solution that gives an upper bound on the optimal value of the max-bisection problem. From the solution, the greedy strategy is used to generate a satisfactory approximate solution of the max-bisection problem. A feasible direction method without line searches is proposed to solve the resulting continuous nonlinear programming, and the convergence of the algorithm to KKT point of the resulting problem is proved. Numerical experiments and comparisons on well-known test problems, and on randomly generated test problems show that the proposed method is robust, and very efficient.</p>