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

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

Zbl 0626.00020