DC Programming and DCA

Theory, Algorithms and Applications


DC Programming and DCA constitute the backbone of smooth/nonsmooth nonconvex programming and global optimization. They are inroduced by Pham Dinh Tao in 1985 in their preliminary form and extensively developed by Le Thi Hoai An and Pham Dinh Tao since 1993 to become now classic and more and more popular. This page collects links to papers, software, announcements, etc. that may be of relevance for people working DC Programming and DCA.


DC PROGRAMMING
DC = D ifference of C onvex functions


The DC programming and its DC algorithm (DCA) address the problem of minimizing a function f = g−h (with g, h being lower semicontinuous proper convex functions on R^n) on the whole space.

α= inf {f(x) ):= g(x) )− h(x): x in R^n}

A constrained DC program whose feasible set C is convex can always be transformed into an unconstrained DC program by adding the indicator function of C (it is equal to 0 in C, infinity elsewhere) to the first DC component g.


WHY DC PROGRAMMING ?

In recent years there has been a very active research in the following classes of nonconvex and nondifferentiable optimization problems

(1) sup {f(x) : x in C}, where g, f and C are convex
(2) inf {g(x) - h(x) : x in IR^n} where g, h are convex

(3) inf { g(x) - h(x) : x in C, f_1(x) - f_2(x) <=0} where g, h, f_1, f_2 and C are convex
The reason is quite simple: most real life optimization problems are of nonconvex nature. Moreover industrialists have begin to replace convex models by nonconvex ones which are more complex but more reliable and especially more economic.

Problem (1) is a special case of Problem (2) with g is the indicator function of C and h=f, while the latter (resp. Problem (3)) can be equivalently transformed into the form of (1) (resp. (2)) by introducing an additional scalar variable (resp. via exact penalty relative to the dc constraint f_1(x)-f_2(x)<=0).
Clearly the complexity increases from (1) to (3), the solution of one of them implies the solution of the two others. Problem (2) is called a DC program whose particular structure has been permitting a good deal of development both in qualitative and quantitative studies.

We can say that all most reald world optimization problems can be formulated as DC programs.
The richness of the set of DC functions on X=R^n, denoted by DC(X) :
(i) DC(X) is a subspace containing the class of lower-C2 functions. In particular, DC(X) contains the space C1,1(X) of functions whose gradient is locally Lipschitzian on X.
(ii) DC(X) is closed under all the operations usually considered in optimization.
In particular, a linear combination of fi DC(X) belongs to DC(X), a finite supremum of DC functions is DC. Moreover, the product of two d.c. functions remains DC.
(iii) Under some caution we can say that DC(X) is the subspace generated by the convex cone Γo(X) :
DC(X) = Γo(X) − Γo(X).
This relation marks the passage from convex optimization to nonconvex optimization and also indicates that DC(X) constitutes a minimal realistic extension of Γo(X) - the convex cone of all lower semicontinuous proper convex functions on R^n.

DCA
DCA = DC A lgorithm

WHAT IS DCA ?


DCA is an optimization approach based on local optimality and the duality in DC programming for solving DC programs. DCA have been introduced by Pham Dinh Tao in 1985 as an extension of his subgradient algorithms (for convex maximization programming) to DC programming. Crucial developments and improvements for DCA from both theoretical and computational aspects have been completed since 1993 throughout the joint works of Le Thi Hoai An and Pham Dinh Tao.
WHY DCA ?

  1. Global optimization approaches such as Branch and Bound, Cutting plan for DC programs do not work in large-scale DC programs that we are often faced in real world problems !
  2. DCA is a robust and efficient method for nonsmooth nonconvex programming which allow to solve large-scale DC programs.
  3. DCA is simple to use and easy to implement.
  4. DCA was successfully applied l arge scale setting to a lot of different and various nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods, especially in the

It is worth noting that for suitable DC decompositions , DCA generates almost standard algorithms in convex and nonconvex programming.



AN INTRODUCTION TO DCA


In recent years there has been a very active research in nonconvex programming. There are two different but
complementary approaches we can say two schools in dc programming. A great deal of work involves global optimization (which is concerned with finding global solutions to nonconvex programs) whose main tools and solution methods are developed according to the spirit of the combinatorial optimization, but with the difference that one works in the continuous framework (See R. Horst and H. Tuy 1993, R. Horst, P.M. Pardalos and N.V. Thoai 1995).

Beside this combinatorial approach to global continuous optimization, the convex analysis approach to nonconvex programming has been much less worked. It seemed to take rise in the works of Pham Dinh Tao on the computation of bound-norms of matrices (i.e. maximizing a seminorm over the unit ball of a norm) in 1974. These works are extended in a natural and logical way to the DC (difference of convex functions) program:

α= inf {f(x) := g(x) − h(x): x in X } (P_dc)

where X=R^n is the usual Euclidean space and g,h hare lower semicontinuous proper convex functions on X
Indeed we would like to make an extension of convex programming, not too large to still allow using the arsenal
of powerful tools in convex analysis and convex optimization but sufficiently wide to cover most real world nonconvex optimization problems . There the convexity of the two DC components g and h of the objective function has been used to develop appropriate tools from both theoretical and algorithmic viewpoints. The other support of this approach is the DC duality, which has been first studied by J.F. Toland in 1978 (Toland, 1978, 1979) who generalized, in a very elegant and natural way, the just mentioned works by Pham Dinh Tao on convex maximization programming (g then is the indicator function of a non-empty closed convex set in X). In contrast with the combinatorial approach where many global algorithms have been studied, there have been a very few algorithms for solving DC programs in the convex analysis approach . Here we are interested in local and global optimality conditions, relationships between local and global solutions to primal DC programs and their dual

α=inf {h*(y) − g*(y): y in Y } (D_dc)

(where Y is the dual space of X, which can be identified with X it self, and g*, h* denote the conjugate functions of gand h, respectively) and solution algorithms.

The transportation of global solutions between (P_dc) and (D_dc)is expressed as:

if x* is an optimal solution of (P_dc), then y* in ∂h(x*) is an optimal solution of (D_dc),
if y* is an optimal solution of (D_dc), then x* in ∂g*(x*) is an optimal solution of (P_dc).

Under technical conditions, this transportation holds also for local solutions of (P_dc) and (D_dc).

DC programming investigates the structure of the vector space DC(X), DC duality and optimality conditions for DC programs. The complexity of DC programs resides, of course, in the lack of practical optimal globality conditions. We developed instead the following necessary local optimality conditions for DC programs in their primal part, (by symmetry their dual part is trivial ) :

∂g(x*) \cap ∂h(y*) \neq empty (1)

(such a point x is called critical point of g − h or for (P_dc)), and

∂g(x*) \subset ∂h(y*) (2)

The condition (2) is also sufficient for many important classes of DC programs. In particular it is sufficient for the next cases quite often encountered in practice:


HOW DCA WORKS ?

Based on local optimality conditions and duality in DC programming, the DCA consists in the construction of two sequences {x^k} and {y^k}, candidates to be optimal solutions of primal and dual programs respectively, such that the sequences {g(x^k)−h(x^k)} and {h(y^k)−g(y^k)} are decreasing, and {x^k} (resp. {y^k}) converges to a primal feasible solution x* (resp. a dual feasible solution y*) verifying local optimality conditions and

x* in ∂g*(y*) ; y* in ∂h(x*)

These two sequences {x^k} and {y^k} are determined in the way that x^{k+1} (resp. yk) is a solution
to the convex program (P_k) (resp. (D_k)) defined by

inf{g(x) − h(x^k) − <x − x^k, y^k> : x in R^n}, (P_k)
inf{h*(y) − g*(y^{k−1})− <y − y^{k−1}, x^k> : y in R^n} (D_k).

The first interpretation of DCA is simple : at each iteration one replaces in the primal DC program (P_dc) the second component h by its affine minorization h_k(x) := h(x^k) + <x − x^k>, y^k> at a neighbourhood of x^k to give birth to the convex program (P_k) whose the solution set is nothing but ∂g(y^k). Likewise, the second DC component g of the dual DC program (D_dc) is replaced by its affine minorization (g * )_k(y) := g*(y^k) + <y − y^k>, x^{k+1} at a neighbourhood of y^k to obtain the convex program (D_k) whose ∂h(x^{k+1}) is the solution set. DCA performs so a
double linearization with the help of the subgradients of h and g and the DCA then yields the next scheme:

y^k in ∂h(x^k); x^{k+1} in ∂g*(y^k).

The second interpretation of DCA :
Let x be an optimal solution of primal DC program (P_dc) and y* in ∂h(x*). By the transportation of global solutions between (P_dc) and (D_dc), y is an optimal solution of the dual DC program (D_dc).
Let h be the affine minorization of h defined by h_*(x) := h(x*) + <x − x*, y*>
and consider the next convex program

α* := inf{g(x)− h_*(x) : x in R^n} = inf{f(x) + h(x) − h_*in(x) : x in R^n} (3)

Since the function f_*(x) = f(x) + h(x) − h_*(x) is a convex majorization of f , α*>= α .
But f_*(x*) = f(x*) = α. Hence finally α*= α .
On the other hand, the optimal solution set of (3) is ∂g*(y*) that is contained in the optimal solution set of (P_dc), following the transportation of global solution between (P_dc) and (D_dc). Taking into account of this transportation and the decrease of the sequence {g(x^k)− h(x^k)}, one can understand better the role played by the linearized programs (P_k), (D_k) and (3). and the fact that DCA converges to an optimal solution of (P_dc) from a good initial point.

Finally it is important to point out the deeper insight into DCA . Let h_l and g*_l be the polyhedral convex functions (which underapproximate, respectively, the convex functions h and g* defined by

h_l(x) : = sup{h_i(x) : i = 0, ..., l}, for all x in R^n ,
g*_l (y)= sup{(g*)_i(y) : i = 1, ..., l}, all y in R^n .
Let k := inf{l : g(x_l) − h(x_l) = g(x^{l+1}) − h(x^{l+1})} . If k is finite, then the solution computed by DCA, x^{k+1} and y^k, are global minimizers for the polyhedral DC programs
\beta_k = inf{g(x) − h_k(x) : x in R^n } (P_k)
and
\beta_k = inf{h(y) − (g)_k(y) : y R^n } (D_k)
respectively. This property holds especially in polyhedral DC programs where DCA has a finite convergence.

The hidden features reside in (k is finite or equal to +\infty ):


These nice features explain partially the efficiency of DCA with respect to related standard methods.

KEY PROPERTIES OF DCA:

  1. DCA is constructed from DC components and their conjugates but not from the DC function f itself
  2. A DC function has infinitely many DC decompositions and there are as many DCA as there are DC decompositions.
  3. DCA is a descent method without linesearch which has a linear convergence for general DC programs.
  4. DCA has a finite convergence for polyhedral DC programs .


HOW TO USE DCA ?

(i) Find a DC decomposition g-h of the object if function f
(ii) Compute subgradients of h and g*
(iii) Implement the algorithm that consists of three steps :
  1. Choose x^0 in R^n
  2. Set y^k in ∂h(x^k)
  3. Set x^{k+1} in ∂g(y^k) that leads quite often to solving the convex program
inf{ g(x) )− h^(x^k ) + < x− x^k,y^k > : x in R^n}

until the convergence



IMPORTANT QUESTIONS

  1. How to find a ''good'' DC decomposition ?
  2. How to find a ''good'' starting point ?

From the theoretical point of view, the question of optimal DC decompositions is still open . Of course, this depends strongly on the very specific structure of the problem being considered. In order to tackle the large scale setting, one tries in practice to choose g and h such that sequences {x^k} and {y^k} can be easily calculated, i.e. either they are in explicit form or their computations are inexpensive.


GLOBALIZING

To guarantee globality of sought solutions or to improve their quality it is advised to combine DCA with global optimization techniques,the most popular of which are Branch-and-Bound, SDP and cutting plane techniques....,in a deeper and efficient way. Note that for a DC function f= g - h, a good convex minorization of f can be taken as g + co(-h) where co stands for convex envelope. knowing that the convex envelope of a concave function on a bounded polyhedral convex set can be easily computed.

APPLICATIONS

The major difficulty in nonconvex programming resides in the fact that there is, in general, no practicable global optimality conditions. Thus, checking globalilty of solutions computed by local algorithms is only possible in the cases where optimal values are known a priori or by comparison with global algorithms which, unfortunately, cannot be applied to large scale problems. A pertinent comparison of local algorithms should be based on the following aspects:

DCA seems to meet these features since it was successfully applied to a lot of different and various nonconvex optimization problems:

  1. The Trust Region subproblems
  2. Nonconvex Quadratic Programs
  3. Quadratic Zero-One Programming problems / Mixed Zero-One Programming problems
  4. Minimizing a quadratic function under convex quadratic constraints
  5. Multiple Criteria Optimization: Optimization over the Efficient and Weakly EfficientSets
  6. Linear Complementarity Problem
  7. Nonlinear Bilevel Programming Problems.
  8. Optimization in Mathematical Programming problems with Equilibrium Constraints
  9. Optimization in Mathematics Finance:
    1. Portfolio optimization under DC transaction costs and minimal transaction unit constraints
    2. Portfolio selection problem under buy-in threshold constraints
    3. Downside risk portfolio selection problem under cardinality constraint
    4. Collusive game solutions via optimization
  10. The strategic supply chain design problem from qualified partner set
  11. The concave cost supply chain problem
  12. Nonconvex Multicommodity Network Optimization problems
  13. Molecular Optimization via the Distance Geometry Problems
  14. Molecular Optimization by minimizing the Lennard-Jones Potential Energy
  15. Minimizing Morse potential energy
  16. Multiple alignment of sequences
  17. Phylogenetic analysis
  18. Optimization for Restoration of Signals and Images
  19. Discrete tomography
  20. Tikhonov Regularization for Nonlinear Ill-Posed problems
  21. Engineering structures
  22. Multidimensional Scaling Problems (MDS)
  23. Clustering
  24. Fuzzy Clustering
  25. Multilevel hierarchique clustering and its application to multicast structures
  26. Support Vector Machine
  27. Large margin classification to ψ−learning
  28. Generating highly nonlinear balanced Boolean Functions in Cryptography
To be continued ...


MISCELLANIES

CAVEAT: Neither are the given lists of papers complete nor do they always provide the most recent reference.

BUT: The intention is to provide a useful page for the entire DC Programming community. To make and keep this page sufficiently complete and up to date I need your help. Please do inform me about necessary updates or missing contributions and mail suggestions or comments to
lethi@univ-metz.fr

NOTICE: the works by H. Tuy, R. Horst and N.V.Thoai on DC optimization only concerns global approaches which are generally applicable for small DC programs. This homepage is devoted to the convex analysis approach to nonconvex programming - DC programming and DCA, and the combined DCA - global optimization techniques.


TOOLS OF DC PROGRAMMING AND DCA

  1. Le Thi Hoai An , Analyse numérique des algorithmes de l'optimisation DC. Approches locales et globales. Code et Simulations numériques en grande dimension. Applications. Thèse de Doctorat (PhD) en Mathématiques Appliquées à l'université de Rouen, 12-1994 .

  2. Pham Dinh Tao and Le Thi Hoai An, Convex analysis approach to DC programming: Theory, Algorithm and Applications. Acta Mathematica Vietnamica, Vol. 22, Number 1 (1997), pp. 289-355, dedicated to Professor Hoang Tuy on the occasion of his 70th birthday.

  3. Le Thi Hoai An , Contribution à l'optimisation nonconvexe et l'optimisation globale: Théorie, Algorithmes et Applications , Habilitation à Diriger de Recherches, Université de Rouen, 6-1997.

  4. Pham Dinh Tao and Le Thi Hoai An , DC optimization algorithms for solving the trust region subproblem.
    SIAM J. Optimization, Vol. 8, Number 2 (1998), pp. 476-505.
  5. Le Thi Hoai An, Pham Dinh Tao, Le Dung Muu, Exact penalty in d.c. programming.
    Vietnam Journal of Mathematics, 27:2 (1999), pp. 169-178.
  6. Le Thi Hoai An and Pham Dinh Tao , DC Programming: Theory, Algorithms and Applications. The State of the Proceedings of The First International Workshop on Global Constrained Optimization and Constraint Satisfaction (Cocos' 02), 28 pages, Valbonne-Sophia Antipolis, France, October 2-4, 2002.
  7. Le Thi Hoai An, Pham Dinh Tao: The DC (difference of convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems.
    Annals of Operations Research, 133, pp. 23-46, (2005).
  8. Le Thi Hoai An, Pham Dinh Tao, Huynh Van Ngai, Exact penalty techniques in DC programming. submitted.

WORKS USING DCA

OUR WORKS ON DCA


  1. Le Thi Hoai An, Pham Dinh Tao and Le Dung Muu , Numerical solution for optimization over the efficient set by D.c. optimization algorithms. Operations Research Letters, 19(1996) pp. 117-128.
  2. Pham Dinh Tao, Le Thi Hoai An, D.c. (difference of convex function) optimization algorithms (DCA) for globally minimizing nonconvex quadratic forms on Euclidean balls and spheres. Operations Research Letters 19(1996) pp. 207-216.
  3. Pham Dinh Tao, Le Thi Hoai An, D.c.optimization algorithms for solving the trust region subproblem.
    SIAM J. Optimization, Vol. 8, Number 2 (1998), pp. 476-505.
  4. Le Thi Hoai An, Pham Dinh Tao , Solving a class of linearly constrained indefinite quadratic problems by
    D.c. algorithms. Journal of Global Optimization, 11 (1997), pp. 253-285 .
  5. Le Thi Hoai An, Pham Dinh Tao , A Branch-and-Bound method via D.C. Optimization Algorithm and Ellipsoidal technique for Box Constrained Nonconvex Quadratic Programming Problems.
    Journal of Global Optimization 13(1998), pp. 171-206.
  6. Le Thi Hoai An, Pham Dinh Tao and Le Dung Muu , A combined D.C. Optimization - Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems.
    Journal of Combinatorial Optimization, Vol. 2, No 1, 1998, pp. 9-28.
  7. Pham Dinh Tao, Le Thi Hoai An, D.c.optimization algorithms for solving the trust region subproblem.
    SIAM J. Optimization, Vol. 8, Number 2 (1998), pp. 476-505.
  8. Le Thi Hoai An, Pham Dinh Tao , D.C. programming approach for large-scale molecular optimization via the general distance geometry problem. Nonconvex Optimization and Its Applications: Special Issue:
    “Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches”
    Kluwer Academic Publishers, (2000) pp. 301-339.
  9. Le Thi Hoai An, Pham Dinh Tao, Large Scale Molecular Conformation via the exact distance geometry problem.
    Lecture Notes in Economics and Mathematical Systems Vol 481 "Optimization" Springer-Verlag, Heidelberg, (2000), pp. 260-277.
  10. Le Thi Hoai An, An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints.
    Mathematical Programming, Ser. A, Vol. 87, No 3 (2000), pp. 401-426.
  11. Le Thi Hoai An, Pham Dinh Tao, D.C. Programming Approach for Solving the Multidimensional Scaling Problem. Nonconvex Optimizations and Its Applications, Kluwer Academic Publishers, (2001) pp. 231-276.
  12. Le Thi Hoai An, Pham Dinh Tao, A continuous approach for large-scale constrained quadratic zero-one programming. (In honor of Professor ELSTER, Founder of the Journal Optimization), Optimization Vol 50, Issue 1-2, 2001, pp. 93 – 120.
  13. Le Thi Hoai An, Pham Dinh Tao, DC Optimization Approaches via Markov Models for Restoration of Signals (1-D) and (2-D). Nonconvex Optimization and Its Applications: Special Issue “Advances on Convex Analysis and Global Optimization”, Kluwer Academic Publishers (2001), pp. 303-317.
  14. Le Thi Hoai An, Pham Dinh Tao, D.C. Programming Approaches for Multicommodity Network Optimization Problems with Step Increasing Cost Functions. Journal of Global Optimization (Special Issue dedicated to Professor R. Horst, Founder of the Journal, on the occasion of his 60-th birthday), January 2002, Volume 22, Number 1-4, pp. 204-233.
  15. Le Thi Hoai An, Pham Dinh Tao, Dinh Nho Hao, Towards Tikhonov regularization of nonlinear ill-posed problems: a dc (difference of convex functions) programming approach. CRAS, Ser. I335 (2002), 1073-1078 ( Note presented by Pierre Louis Lions).
  16. Le Thi Hoai An, Pham Dinh Tao, Nguyen Van Thoai , Combination between Local and Global Methods for Solving An Optimization problem Over the Efficient Set. European Journal of Operational Research Vol. 142, pp. 258-270, (2002).
  17. Le Thi Hoai An, Pham Dinh Tao, Large Scale Molecular Optimization From Distance Matrices by a D.C. Optimization Approach. SIAM Journal on Optimization, Vol. 4, N° 1, pp; 77-116, (2003).
  18. Le Thi Hoai An, Pham Dinh Tao, Dinh Nho Hao , D.C.(Difference of Convexe) Functions Programming for Solving an Inverse Problem or an Elliptic Equation. Journal of Global Optimization, 25(4), pp. 407-423 (2003).
  19. Le Thi Hoai An, Pham Dinh Tao, A new algorithm for solving large scale molecular distance geometry problems. Applied Optimization: Special Issue “High Performance Algorithms and Software for Nonlinear Optimization”, pp. 279-296, (2003), Kluwer Academic Publishers.
  20. Le Thi Hoai An, Solving large scale molecular distance geometry problems by a smoothing technique via the gaussian transform and d.c. programming, Journal of Global Optimization, Vol 27, No 4 (2003), pp. 375-397.
  21. F. Akoa, Le Thi Hoai An and Pham Dinh Tao : An Interior Point Algorithm with DC Regularization for Nonconvex Quadratic Programming. Modelling, Computation and Optimization in Information Systems and Management Sciences, Hermes Science Publishing, pp. 87-96 (2004) .
  22. F. Akoa, Approches de points intérieurs et de laprogrammation DC enOptimisationnonconvexe.Code et Simulation numériques industrielles. Thèse de Doctorat en Mathématiques Appliquées à l'INSA de Rouen 1-2005.
  23. M.T. Belghiti, Le Thi Hoai An, Pham Dinh Tao: Clustering via DC programming & DCA. Modelling, Computation and Optimization in Information Systems and Management Sciences, Hermes Science Publishing, pp. 499-507 (2004).
  24. A. Hachemi, Le Thi Hoai An, S. Mouhtamid, Pham Dinh Tao : Large-scale nonlinear programming and lower bound direct method in engineering applications. Modelling, Computation and Optimization in Information Systems and Management Sciences, Hermes Science Publishing, pp. 299-310 (2004).
  25. Nam Nguyen Canh, Pham Dinh Tao, and Le Thi Hoai An, DC Programming and DCA for Diversity Data Mining, Procceding des 13eme Rencontres de la Société Francophone de Classification 2006, pp. 63-167.
  26. Nguyen Canh Nam, Le Thi Hoai An, et Pham Dinh Tao, A Branch and Bound Algorithm based on DC Programming and DCA for Strategic Capacity Planning in Supply Chain Design for a New Market Opportunity, Operations Research Proceedings 2006 (Selected Papers of the International Conference on Operations Research 2006, Karlsruhe, September 6--8). LNCS, pp. 515-520, Springer Verlag 2006.
  27. Le Thi Hoai An, Nguyen Trong Phuc, Pham Dinh Tao, A Continuous DC Programming ApproachTo The Strategic Supply Chain Design Problem From Qualiffed Partner Set, European Journal of OperationalResearch (2007), 183: 1001-1012.
  28. Le Thi Hoai An, Le Hoai Minh, Pham DinhTao, Optimization based DC programming and DCA for Hierarchical Clustering, European Journal of Operational Research (2007) 183: 1067-1085
  29. Le Thi Hoai An, T. Belghiti and Pham Dinh Tao, A new eficient algorithm based on DC programming and DCA for Clustering, Journal of Global Optimization (2007), 37:593-608.
  30. F. Akoa, A.Hachemi, Le Thi H.A, S. Mouhtamid, Pham Dinh T., Application of lowerbound direct method to engineering structures, Journal of Global Optimization (2007) 37: 609-630.
  31. Le Thi Hoai An, Le Hoai Minh, Pham Dinh Tao, Fuzzy clustering based on nonconvex optimisation approaches using difference of convex (DC) functions algorithms, Journal of Advances in Data Analysis and Classification, Num 2 (2007), pp. 1-20.
  32. Le Thi Hoai An and Pham Dinh Tao, A continuous approach for the concave cost supply problem via DC Programming and DCA, Discrete Applied Mathematics, 156 (2008) 325 - 338.
  33. Le Hoai Minh, Le Thi Hoai An, Pham Dinh Tao, Pascal Bouvry, A deterministic Optimization approach for generating highly nonlinear balanced boolean functions in Cryptography, in Modeling, Simulation and Optimization of Complex Processes, Springer, 2008, pp. 381 - 392.
  34. Pham Dinh Tao, Le Thi Hoai An, François Akoa, Combining DCA and interior point techniques for large-scale nonconvex quadratic programming, Optimization, Methods and Softwares, 23:4, 609 – 629, 2008.
  35. Le Thi Hoai An, Pham Dinh Tao, Nguyen Van Thoai, Nguyen Canh Nam, D.C. Optimization Techniques for Solving a Class of  Nonlinear Bilevel Programs, Journal of Global Optimization, Vol 44, Num 3, pp 313-337, 2009.
  36. Le Thi Hoai An, Madhi Moeini, Pham Dinh Tao, DC Programming Approach for Portfolio Optimization under Step Increasing Transaction Costs, Optimization, Volume 58, Issue 3 2009, pp 267 – 289.
  37. Le Thi Hoai An, Le Hoai Minh, Nguyen Van Vinh, Pham Dinh Tao, A DC Programming approach for Feature Selection in Support Vector Machines learning, Journal of Advances in Data Analysis and Classification, Vol 2 Num 3 (2008), pp. 259-278.
  38. Le Thi Hoai An, Le Hoai Minh, Nguyen Trong Phuc, Pham Dinh Tao, Noisy image segmentation by a robust clustering algorithm based on DC programming and DCA, in "Advances in Data Mining", P. Perne (Edt) ICDM2008, Lecture Note in Intelligence Artificial, pp.72-86, Springer Verlag 2008.
  39. Le Thi Hoai An, Nguyen Quang Thuan, Phan Tran Khoa, Pham Dinh Tao, Energy Minimization-based Cross-layer Design in Wireless Networks, Proceedings of the 2008 High Performance Computing & Simulation Conference (HPCS 2008) Nicosia, Cyprus, June 3 - 6, 2008, pp 283 - 289.
  40. Le Thi Hoai An, Ndiaye Babacar Mbaye, Pham Dinh Tao, Solving a multimodal transport problem by DC, Proceedings of RIVF'08, IEEE International conference on Research, Innovation and Vision for the future in Computing & Communications Technologies, Ho Chi Minh city, July 13-17, pp. 49-56.
  41. Le Thi Hoai An, Nguyen Van Vinh, S. Ouchani, Gene selection for cancer classification using DCA, in Tang et al. Eds ADMA08, Lecture Notes in Artificial Intelligence (LNAI) 5139, Springer Verlag 2008, pp. 62-72.
  42. Babacar M. Ndiaye, Tao Pham Dinh and Hoai An Le Thi, DC programming and DCA for SSCRP, in Modelling, Computation and Optimization in Information Systems and Management Sciences, Communications in Computer and Information Science CCIS Volume 14, pp. 21-30, Springer Verlag 2008.
  43. Mamadou Thiao, Tao Pham Dinh, and Hoai An Le Thi, DC programming approach for a class of nonconvex programs involving l0 norm, in Modelling, Computation and Optimization in Information Systems and Management Sciences, Communications in Computer and Information Science CCIS Volume 14, pp. 358-367, Springer Verlag 2008.
  44. Sarra Bouallagui, Hoai An Le Thi, and Tao Pham Dinh, Design of highly nonlinear balanced Boolean functions using an hybridation of DCA and Simulated Annealing algorithm, in Modeling, Computation and Optimization in Information Systems and Management Sciences, Communications in Computer and Information Science CCIS Volume 14, pp. 583-592, Springer Verlag 2008.
  45. Le Thi Hoai An, Le Hoai Minh, Pham Dinh Tao and Pascal Bouvry, Solving the Perceptron Problem by deterministic optimization approach based on DC programming and DCA, Proceeding of the 7th IEEE International Conference on Industrial Informatics INDIN 2009, pp. 222-226.
  46. Le Thi Hoai An, Moulay Belghiti, Pham Dinh Tao, Multiple Alignment of Sequences by a Continuous Optimisation Approach Based on DC Programming and DCA, Proceedings of the 2009 International Conf. on Bioinformatics & Computational Biology, pp 109-115,  World Congress in Computer Science Computer Engineering, and Applied Computing, July 13-16, 2009, Las Vegas, USA.
  47. Le Thi Hoai An, Pham Dinh Tao,  Bouallagui Sarra, Cryptanalysis of an Identification Scheme Based on the Perceptron Problem using a hybridization of deterministic optimization and genetic algorithm, Proceedings of the 2009 International Conference on Security and Management, pp. 117-123, World Congress in Computer Science Computer Engineering, and Applied Computing, July 13-16, 2009, Las Vegas, USA.
  48. Le Thi Hoai An and Pham Dinh Tao, Minimum Sum-of-Squares Clustering by DC programming and DCA, in Advanced Intelligent Computing Technology & Applications,  Lecture Notes in Artificial Intelligence (LNAI), Springer Verlag 2009, 14 pages.
  49. Pham Dinh Tao, Nguyen Canh Nam and Le Thi Hoai An, DC Programming and DCA for Globally Solving the Value-At-Risk, Computational Management Science, Issue 4, 2009.
  50. Le Thi Hoai An, Madhi Moeini, Pham Dinh Tao, Portfolio Selection under Downside Risk Measures and Cardinality Constraints based on DC Programming and DCA, Computational Management Science, Issue 4, 2009.

WORKS OF OTHER AUTHORS USING DCA (partial list)

  1. P.Mahey, T.Q. Phong and H.P.L Luna , Separable convexification and DCA techniques for capacity and flow assignement problems, RAIRO-Recherche Opérationnelle 35 (2001), pp.269-281.
  2. J. Neumann, C. Schnörr, G. Steidl , SVM-based Feature Selection by Direct Objective Minimisation, Pattern Recognition, Proc. of 26th DAGM Symposium, LNCS, Springer, August 2004.
  3. J.E. Harrington, B.F. Hobbs, J.S. Pang, A. Liu, G. Roch , Collusive game solutions via optimisation, Math.
    Program. Ser. B(2005), 29 pages.
  4. J. Neumann, C. Schnörr, G. Steidl : Combined SVM-Based Feature Selection and Classification
    Machine Learning , in press, ( published online ).
  5. S. Weber, A. Nagy, T. Schüle, C. Schnörr and A.Kuba, A Benchmark Evaluation of Large-Scale Optimization Approaches to Binary Tomography In: Proc. 13th International Conference on Discrete Geometry on Computer Imagery ( DGCI '06 ). LNCS Vol.4245, Springer, Oct. 2006.
  6. Yufeng LIU, Xiaotong SHEN, and Hani DOSS , Multicategory ψ−Learning and Support Vector Machine: Computational Tools , Journal of Computational and Graphical Statistics, 14(1): 219-236.
  7. S. Weber, T. Schüle, A.Kuba and C. Schnörr . Binary Tomography with Deblurring . In: Proc. 11th International Workshop on Combinatorial Image Analysis ( IWCIA '06 ). LNCS Vol.4040, Springer, June 2006.
  8. T. Schüle, C. Schnörr, S. Weber, and J. Hornegger . Discrete tomography by convex-concave regularization and d.c. programming. Discr. Appl. Math., 151:229-243, Oct 2005.
  9. Schn¨orr, C., Sch¨ule, T., Weber, S. . Variational Reconstruction with DCProgramming. In Herman, G.T., Kuba, A., eds.: Advances in Discrete Tomography and Its Applications. Birkh¨auser, Boston (2006)
  10. T. Schüle, S. Weber, C. Schnörr , Adaptive Reconstruction of Discrete-Valued Objects from few Projections
    Electr. Notes in Discr. Math., 20:365-384, 2005.
  11. X. Shen , From large margin classification to ψ −learning, (28 pages), School of Statistics, University of
    Minnesota.
  12. S. Weber, T. Schüle, J. Hornegger, C. Schnörr , Binary Tomography by Iterating Linear Programs from Noisy Projections , Proceedings of International Workshop on Combinatorial Image Analysis (IWCIA), 2004.
    Auckland, New Zealand, Dec. 1.-3./2004, Lecture Notes in Computer Science, Springer Verlag .
  13. S. Weber, T. Schüle, C. Schnörr , Prior Learning and Convex-Concave Regularization of Binary Tomography. Electr. Notes in Discr. Math., 20:313-327, 2005.
  14. S. Weber, C. Schnörr, T. Schüle, J. Hornegger , Binary Tomography by Iterating Linear
    Programs, R. Klette, R. Kozera, L. Noakes and J. Weickert (Eds.), Computational Imaging and Vision -
    Geometric Properties from Incomplete Data, Kluwer Academic Press 2005.
  15. X. Shen, G.C. Tseng, X. Zhang, and W. H. Wong , On psi-Learning, Journal of American Statistical Association, 98, 724-734,(2003).
  16. Liu, Yufeng and Shen, Xiaotong, Multicategory psi-learning , Journal of the American Statistical Association/, 101, 474, 500-509 (2006).
  17. Ronan Collobert ronan, Fabian Sinz f Max Planck , L´eon Bottou , Trading Convexity for Scalability, Proceedingf of the International Conference on Machine Learning ICML 2006.
  18. Sijin Liu, M.S., Computational developments for psi-learning, PhD thesis Univ. Ohio 2006.
  19. Wang, J., Shen, Z., and Pan, W. , On transductive support vector machines Proceedingf of the International Conference on Machine Learning ICML 2007.
  20. Wang, J., and Shen, X , Large margin semi-supervised learning, JMLR 8 (2007), pp 1867-1891.
  21. Krause, N., & Singer , Leveraging the margin more carefully. International Conference on Machine Learning, ICML (2006).
  22. Andreas Argyriou, Raphael Hauser, Charles A. Micchelli, Massimiliano Pontil, A DC-Programming Algorithm for Kernel Selection, Proceedings of the 23 rd International Conference on Machine Learning, Pittsburgh, PA, 2006.
  23. Alberto Bemporad, Advanced control methodologies for hybrid dynamical systems , Research program, Università degli Studi di SIENA.
  24. Dinh Nho Hao, Nguyen Trung Thanh and H. Sahli , Numerical Solution to a Parabolic Boundary Control Problem.
  25. Kurt M. Anstreicher and Samuel Burer , D.C. Versus Copositive Bounds for Standard QP , Dept. of Management Sciences University of Iowa May 29, 2003.
  26. Le Dung Muu and Jianming SHI , D.C. Optimization Methods for Solving Minimum Maximal Network Flow Problem .
  27. C. Schnoerr, Signal And Image Approximation With Level-set Constraints, Computing 2007 Vol.81 (No.2-3).
  28. Yoshihiro Kanno, Makoto Ohsaki, Eigenvalue Optimization of Structures via Polynomial Semidefinite Programming
  29. Bharath K. Sriperumbudur David A. Torres Gert R. G. Lanckriet, Sparse Eigen Methods by D.C. Programming, Proceedings of the 25 th International Conference on Machine Learning 2007.
  30. David A. Torres, Douglas Turnbull, Bharath K. Sriperumbudur, Luke Barrington, Gert R. G. Lanckriet, Finding Musically Meaningful Words by Sparse CCA.
  31. Jörg Kappes and Christoph Schnörr, MAP-Inference for Highly-Connected Graphs with DC-Programming.
  32. Nikolaos Vasiloglou Alexander G. Gray David V. Andersony, Non-Negative Matrix Factorization, Convexity and Isometry, Proceedings of SIAM conference on Data Mining 2009, pp 673-684.
  33. F. Akoa, Combining DC Algorithms (DCAs) and Decomposition Techniques for the Training of Nonpositive–Semidefinite Kernels, IEEE Transactions on Neural Networks 2008 Vol. 19 (No.11).
  34. Peng Zhang, Yingjie Tian, Zhiwang Zhang, Aihua Li, Xingquan Zhu, Select Objective Functions for Multiple Criteria Programming Classification, wi-iat, vol. 3, pp.420-423, 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, 2008.
  35. Liang Fang, Li Sun, Guoping He, Fangying Zheng, A New Algorithm for Quadratic Programming with Interval-Valued Bound Constraints, International Conference on Natural Computation, vol. 6, pp. 433-437, 2008 Fourth International Conference on Natural Computation, 2008.
  36. D. Wozabal, A new method for Value-at-Risk constrained optimization using the Difference of Convex Algorithm (DCA), Optimization online 2008.
  37. Effrosyni Kokiopoulou, Pascal Frossard, Minimum Distance between Pattern Transformation Manifolds: Algorithm and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 7, pp. 1225-1238, June 2009.
  38. Antonio Fuduli, A. Astorino, Manlio Gaudioso, DC Programming and Spherical separation, EURO Conference 23, Bonn July 5-8, 2009.
  39. Chun-Nam John Yu Thorsten Joachims, Learning Structural SVMs with Latent Variables, Proceedings of the 26 th International Conference on Machine Learning, Montreal, Canada, 2009.
  40. Quoc V. Le Alex Smola, Olivier Chapelle, Choon Hui Te, Optimization of Ranking Measures.
  41. Yiqing Zhong, El-Houssaine Aghezzaf, A DC Programming Approach to solve the Single-Vehicle Inventory Routing Problem, in the Proceedings of the international conference CIE39, July 6-8, 2009.
  42. JunhuiWang, Xiaotong Shen, Wei Pan, On Efficient Large Margin Semisupervised Learning: Method and Theory, Journal of Machine Learning Research 10 (2009) 719-742.

  

  
 

  


  


SPECIAL SESSIONS IN INTERNATIONAL CONFERENCES 







    
  
  1. “DC Programming: Theory, Algorithms and Applications”: 18th International Symposium on Mathematical Programming (ISMP 1997) Lausanne, Switzerland, August 24-29, 1997. 
    2. 
  
  2. “DC Programming: Theory, Algorithms and Applications”: The First International Conference on Optimization Methods and Software, December 15-18, 2002, Hangzhou, China . 
    3. 
  
  3. “DC Programming: Theory, Algorithms and Applications”: 18th International Symposium on Mathematical Programming (ISMP 2003) Copenhagen, Denmark, August, 18-22, 2003. 
    4. 
  
  4. “DC Programming: Theory, Algorithms and Applications”: The Sixth International Conference on Optimization: Techniques and Applications (ICOTA6, 2004), Ballarat, Australia, 9-11 December 2004. 
    5. 
  
  5. “DC Programming: Theory, Algorithms and Applications”: SIAM Conference on Optimization, May 15-19, 2005, Stockholm, Sweden. 
    6. 
  
  6. “DC Programming: Theory, Algorithms and Applications”: 7ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Lille 2-2006 . 
    7. 
  
  7. “DC Programming: Theory, Algorithms and Applications ”: International Conference on Computational Management Science (CMS) , Amsterdam 17-18 May 2006 . 
    8. 
  
  8. “Programmation non convexe, Approches locales et globales, Théorie, Algorihmes et Applications ”: International Conference FRANCORO-ROADEF'07, Grenoble 20-23 February 2007 . 
    9. 
  
  9. “Mathematical programming”: International Conference on Computational Management Science (CMS) , Geneva 20-22 April 2007 . 
    10. 
  
  10. DC programming and DCA, INternational conference on Nonconvex programming: Local and Global approaches  NCP’07, Rouen 17-21 december 2007.
    11. 
  
  11. Stream: Nonconvex programming: Local and Global approaches, 23rd European Conference on Operational  Research, Bonn, July 5 - 8, 2009. 3 sessions: Recent developments from Nonconvex Programming, Novel opportunities of Nonconvex programming  for Industry and Finance, Novel opportunities of DC programming and DCA for Industry and  Finance,
    12. 
  



  

  

    	Aller en haut de page