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

DOI:

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

Published online: 2005-12

Preview Full PDF 158 1794
Export citation

Cited by

google scholar semantic scholar
  • 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.

  • Keywords

Max-Bisection problem Feasible direction algorithm NCP function Convergence

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-23-619, author = {}, 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 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 KW - Feasible direction algorithm KW - NCP function KW - 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 & Hong-Gang Xue. (1970). A Feasible Direction Algorithm Without Line Search for Solving Max-Bisection Problems. Journal of Computational Mathematics. 23 (6). 619-634. doi:
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard