Duality in d. c. (difference of convex functions) optimization. Subgradient methods. (English) Zbl 0634.49009

Pham Dinh Tao; El Bernoussi, Souad

Trends in mathematical optimization, 4th French-German Conf., Irsee/FRG 1986, ISNM 84, 277-293 (1988).

[For the entire collection see Zbl 0626.00020.]
For the d.c. optimization problem \[ (P)\quad \inf \{g(x)-h(x):x\in R^ n\}, \] where g and h are proper convex lower semicontinuous functions, it is shown that any optimal solution \(x^*\) must satisfy the necessary condition \[ (1)\quad \partial h(x^*)\subset \partial g(x^*). \] This condition, in turn, is equivalent to the existence of a solution \(y^*\) to the problem \(\inf \{<x^*,y>-g^*(y): y\in \partial h^*(x^*)\}\) such that \(x^*\in \partial g^*(y^*).\) Similar results are established for the dual problem to (P): \[ (Q)\quad \inf \{h^*(y)- g^*(y): y\in R^ n\}. \] Based on these results, a subgradient algorithm is proposed for finding a point x * satisfying the necessary condition (1). The algorithm constructs a sequence x k, y k, starting from an arbitrary x 0, such that \(y^ k\in \arg \min \{<x^ k,y>- g^*(y): y\in \partial h^*(x^ k)\}\), \(x^{k+1}\in \arg \min \{<x,y^ k> -h(x): x\in \partial g^*(y^ k)\}\).

Reviewer: H.Tuy

MSC:

49N15	Duality theory (optimization)
90C52	Methods of reduced gradient type
90C30	Nonlinear programming

Keywords:

d.c. optimization; dual problem; subgradient algorithm

Citations:

Zbl 0626.00020