arrow
Volume 23, Issue 6
A Feasible Direction Algorithm Without Line Search for Solving Max-Bisection Problems

Feng-Min Xu, Cheng-Xian Xu & Hong-Gang Xue

J. Comp. Math., 23 (2005), pp. 619-634.

Published online: 2005-12

Export citation
  • Abstract

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.

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-23-619, author = {Feng-Min Xu, Cheng-Xian Xu and Hong-Gang Xue}, title = {A Feasible Direction Algorithm Without Line Search for Solving Max-Bisection Problems}, journal = {Journal of Computational Mathematics}, year = {2005}, volume = {23}, number = {6}, pages = {619--634}, abstract = {

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.

}, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/8842.html} }
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 -

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.

Feng-Min Xu, Cheng-Xian Xu and Hong-Gang Xue. (2005). A Feasible Direction Algorithm Without Line Search for Solving Max-Bisection Problems. Journal of Computational Mathematics. 23 (6). 619-634. doi:
Copy to clipboard
The citation has been copied to your clipboard