Solving the Perceptron Problem by deterministic optimization approach based on DC programming and DCA
Hoai An Le Thi, Hoai Minh Le, Pham Dinh Tao, Pascal Bouvry · 2009
The perceptron problem (PP) appeared for the first time in the learning machines and is very useful for zero-knowledge identification schemes in cryptology. The problem is NP-complete and no deterministic algorithm is known to date. In this paper we develop a deterministic method based on DC (Difference of Convex functions) programming and DCA (DC optimization Algorithms), an innovative approach in nonconvex programming framework. We first formulate the PP as a concave minimization programming problem. Then, we show how to apply DC programming and DCA for the resulting problem. Numerical results demonstrate that the proposed algorithm is promising: its is very fast and can efficiently solve the Perceptron Problem with large sizes.