Keywords

Introduction

Convexity is a central concept in optimization. Solving optimization problems somehow leads to separate the constraint set and the set of points no worse than a given candidate. In the convex optimization case, both sets are convex which makes the separation affordable by a hyperplane. However, when one deals with nonconvex optimization problems, one needs more appropriate tools because both sets or at least one of them can be nonconvex. A decade-long effort for finding such tools is presented briefly in the beginning of the chapter. The second part of the chapter is mainly devoted towards the ways of use spherical sets for the separation in nonconvex optimization instead of hyperplanes used in convex optimization.

We consider a nonconvex nonsmooth optimization problem:

$$\displaystyle{ \left \{\begin{array}{lc} \text{ maximize } & F(x)\\ \text{subject to }&x \in D,\end{array} \right. }$$
(PCMP)

where D is a nonempty compact in \(\mathcal{R}^{n}\) and \(F: \mathcal{R}^{n} \rightarrow \mathcal{R}\) is a piecewise convex function.

Definition 1.

A function F is called a piecewise convex function iff it can be decomposed into the pointwise minimum of convex functions, namely:

$$\displaystyle{F(x) = min\{f_{j}(x)\mid j \in M\},}$$

where all functions \(f_{j}: \mathcal{R}^{n} \rightarrow \mathcal{R}\) are convex j ∈ M: = { 1, 2. . . , m}.

Convex functions, concave functions are particular cases of piecewise convex functions, since clearly F is a convex when m = 1 and a concave whenever all functions f j are affine.

For any real number α ∈ R the Lebesgue set of a function f is defined like

$$\displaystyle{\mathcal{L}_{f}(\alpha ) =\{ x\mid f(x) \leq \alpha \}.}$$

A quasiconvex (in particular convex f j ) function has the property that its Lebesgue set (in particular \(\mathcal{L}_{f_{j}}(\alpha )\) ) is a convex set. Piecewise convex functions have a nice geometrical interpretation that the Lebesgue set of such function is the union of a finite number of convex sets

$$\displaystyle{\mathcal{L}_{F}(\alpha ) =\bigcup _{ j=1}^{m}\mathcal{L}_{ f_{j}}(\alpha ).}$$

For a given \(y \in \mathcal{R}^{n}\) the Lebesgue set \(\mathcal{L}_{F}(F(y))\) defines also, in the sense of maximization, the set of points no better than y. The Lebesgue sets of piecewise convex function \(\mathcal{L}_{F}(F(y))\) are generally nonconvex and can be disconnected or even discrete sets. As a result, the nonconvexity of the objective function F(⋅ ) poses the major difficulty for solving piecewise convex maximization problems since they generally have a large number of local optima which are not global optima.

Before solving an optimization problem it is useful to investigate the information about where global optima are attained? At some extreme points, on the boundary, or in the interior of the feasible set, etc. With this respect, it is well known [10, 11, 17, 22] that the global maximum occurs at an extreme point for convex maximization over a convex set while a solution to DC (difference of convex) optimization lies on the boundary of the feasible set. As regards (PCMP), in general, its large number of local optima including the global maximum can lie anywhere in D. As such, it is computationally very difficult to solve, especially if one wishes to find the global optimum.

The space of piecewise convex functions has been studied in [8]; any continuous nonconvex function can be approximated by piecewise convex one. In addition virtually many optimization problems can, theoretically, be approximated by (PCMP). Indeed, the latter justifies the importance of this class of optimization problems as a powerful tool in nonconvex optimization.

The reader is referred to [2, 11, 13, 15, 17, 18, 22, 26] for finding out the close relationship between (PCMP) and the other nonconvex optimization problems like convex maximization, reverse convex minimization, DC, Lipschitz optimization, etc.

Despite the concerns mentioned above, (PCMP) does not seem to have been extensively studied.

The purpose of this chapter is twofold:

  • to present a brief survey of some useful results, optimality conditions, methods, ideas for (PCMP);

  • to propose a novel approach of solving (PCMP) based on nonlinear separation and consider piecewise convex maximization problems over spherical sets (balls, spheres) which play the key role for this new research direction.

A Survey of Studies on PCMP

During the last decade we have been focusing on tools for solving (PCMP). This section provides a brief survey of optimality conditions, methods, and some useful ideas for (PCMP).

Global Optimality Conditions

Let us quote the article [20] for the global optimality conditions. First, we define an active index set at any z by

$$\displaystyle{I(z) =\{ i \in M\mid f_{i}(z) = F(z)\}}$$

and at given k ∈ M, z ∈ D a special subset of D by

$$\displaystyle{D_{k}(z) =\{ x \in D\mid f_{j}(x) > F(z)\text{ for all }j \in M\setminus \{k\}\}.}$$

The following results summarize our findings on optimality conditions so far:

Proposition 1 ([20]).

If z ∈ D is a global maximum of (PCMP) then for all k ∈ I(z)

$$\displaystyle{\partial f_{k}(y)\bigcap N(D_{k}(z),y)\neq \emptyset \text{ for all }y\text{ such that }f_{k}(y) = F(z)}$$

Theorem 1 ([20]).

Let z ∈ D and assume there exist k ∈ I(z) and \(v \in \mathcal{R}^{n}\) such that f k (v) < f k (z). Then a sufficient condition for z to be the global maximum for (PCMP) is

$$\displaystyle{\partial f_{k}(y)\bigcap N(clco(D_{k}(z)),y)\neq \emptyset \forall y\text{ such that }f_{k}(y) = F(z).}$$

Here cl, co stand for a closure and a convex hull of a set, respectively.

These necessary and sufficient conditions show that solving (PCMP) leads to choose one function f k and to maximize it over D k (⋅ ) or over clco(D k (⋅ )). This is the well known convex maximization problem

$$\displaystyle{ \left \{\begin{array}{lc} \text{ maximize } & f(x)\\ \text{subject to }&x \in D,\end{array} \right. }$$
(CM)

its optimality conditions have been obtained in [19]

$$\displaystyle{\partial f(y)\bigcap N(D,y)\neq \emptyset \text{ such that }y\text{ such that }f(y) = f(z).}$$

In [20], one can find geometric interpretation of the optimality conditions along with their illustrations in some examples.

Methods

Linearization Oriented Algorithm

To our knowledge, the first algorithm for solving (PCMP) has been presented in [4]. The article provides an algorithm based on optimality conditions (Proposition 1 and Theorem 1.) presented in the previous subsection. For the sake of simplicity of presentation it is assumed that functions f j (⋅ ), j ∈ M are strongly convex quadratic, the domain D a full dimensional polytope.

Quadratic convex maximization problems (the particular case of (PCMP) when m = 1) are normally classified as NP-hard. Furthermore, just finding a local maximum of a nonconvex quadratic programming problems is NP-hard too. Thus, even the local solution search for (PCMP) is not trivial. At the same time an efficient algorithm for finding local maxima may be the crucial factor in design of the global maximum search stage. Therefore, in [4] a local search algorithm for (PCMP) has attracted considerable attention. For this important issue of the local search, an algorithm derived from linearization of convex functions is proposed, and its convergence is examined carefully.

Assume that we are given a local solution y ∈ D. In order to improve the best known local solution, according to the optimality conditions, one should look for a point in D k (y). Then a practical global search algorithm is provided which combines the local search algorithm with successive inner and outer approximations to D k (⋅ ).

Computational experiments on small examples in \(\mathcal{R}^{2},\mathcal{R}^{3}\) are reported, which show the efficiency of the approach. One can find also therein some details of implementation as well as new notions like an intersection graph on the Lebesgue sets \(\mathcal{L}_{f_{j}}(F(\cdot ))\), the relationship of the optima of (PCMP) with Helly’s theorem from discrete geometry.

Piece Adding TeCHnique (PATCH for Short)

For nonconvex optimization problems, many standard techniques rely on local search and the challenge still remains to escape from a local maximum area.

Among other things the question about how to escape from a local maximum area was investigated in article [8]. The authors first studied the space of piecewise convex functions and showed that this class is closed under operations like addition, positive scalar multiplication, operations “min”, \(F^{+},F^{-}\). One can add missing operation “max” into the above list of operations, which has been observed recently.

The following one dimensional example given in [7] well illustrates the idea behind, so-called, the piece adding technique.

$$\displaystyle{\left \{\begin{array}{l} \text{ maximize }x^{2} - 2x, \\ \text{ subject to }0 \leq x \leq 3.\end{array} \right.}$$

Obviously, x = 0 is a local maximum, (but not the global !), an accumulation point of local search algorithms with a starting point x 0 ∈ [0, 1] and there is no clear way to escape from its region, once one is therein. The main idea for escaping is, it makes sense first to add into the objective function a convex piece x 2 − 4 issued from the local solution x = 0, then solve the following problem

$$\displaystyle{\left \{\begin{array}{ll} \text{ maximize } &min\{x^{2} - 2x,x^{2} - 4\}, \\ \text{ subject to }&0 \leq x \leq 3. \end{array} \right.}$$

Notice that the previous local solution x = 0 is a minimum of the new convex piece x 2 − 4. Now it is clear (Fig. 1) that any local search will not get back to x = 0 and easily finds the global solution x = 3 from any starting point.

Fig. 1
figure 1

Piecewise Adding Technique (PATCH) idea

Full size image

Similarly for escaping from a local solution y of (PCMP), it is proposed to solve the following problem

$$\displaystyle{ \text{ maximize }\;min\{F(x) - F(y),p(x)\},\text{ subject to }x \in D }$$
(PP)

where p(x) is a convex function, that will be specified hereafter.

Remark 1.

Here we underline that by adding a convex piece into objective function

  • one cuts off virtually from D a subset of points no better than y; (“virtual cut” in the sense that we add a convex piece in objectives rather than a reverse convex constraint p(x) ≥ 0)

  • the objective function remains piecewise convex;

  • the space of the problem is unchanged.

The function p(⋅ ) may be defined in different ways among which we select two.

Definition 2.

Let z be the global solution to (PCMP). A strictly convex function \(p_{y}: \mathcal{R}^{n} \rightarrow \mathcal{R}\) is called a patch around a local solution y of the problem (PCMP) iff

  • p y (y) < 0;

  • p y (x) ≥ 0 for all x ∈ D such that F(x) > F(y);

  • moreover p y (z) > 0

We notice that the conditions for patches are not easy to verify with respect to unknown global solution z, therefore we weaken those conditions and introduce a relaxed function with almost the same features.

Definition 3.

A strictly convex function \(p_{v}: \mathcal{R}^{n} \rightarrow \mathcal{R}\) is called a pseudopatch at v ∈ D iff

  • p v (v) < 0 and

  • there is u ∈ D such that F(u) > F(v) and p v (u) ≥ 0.

Unlike the patch, the virtual cutting p v (x) ≥ 0 defined by the pseudopatch could cut a feasible point v together with some better points (even the global solution!) but it should leave at least one better point. For practical purposes, pseudopatches are added in the objective function temporarily then, after they are dropped at each improvement since the global solution z can be incidentally cut off by a pseudopatch.

Outline of algorithm

  1. 1.

    Compute a local solution y k (\(k = 1,2,\ldots\)) obtained from a feasible point u ∈ D;

  2. 2.

    Construct a strictly convex function p k (⋅ ) as a pseudopatch or a patch around y k;

  3. 3.

    Solve

    where

    $$\displaystyle{\varPhi _{k}(x):=\min \{ F(x) - F(y^{k}),p_{ 1}(x),p_{2}(x),\ldots,p_{k}(x)\}.}$$

    Let u be an optimal solution to (P k );

  4. 4.

    If p k (⋅ ) is a pseudopatch then drop it from Φ k (x);

  5. 5.

    Repeat the sequence with \(k = k + 1\)

In a like manner, after one iteration we either obtain a better point due to pseudopatch or reduce virtually the domain by new patch p k (⋅ ) around y k.

For ease of presenting the main result, let consider two problems for a given local solution y:

$$\displaystyle{ \text{ maximize }\;F(x) - F(y),\text{ subject to }x \in D, }$$
(PCMP)

and

$$\displaystyle{ \text{ maximize }\;\varPhi (x)\text{ subject to }x \in D, }$$
(PP)

where \(\varPhi (x):=\min \{ F(x) - F(y),p_{y}(x)\}\), p y (⋅ ) is a patch around y.

Assumption 1.

Let us assume that p y (z) ≥ F(z) − F(y) at the global solution z.

Proposition 2.

If z is a global solution to (PP) and p y (⋅) is a patch satisfying Assumption  1 then z solves globally (PCMP) too.

This technique aims also at carrying piecewise affine approximation from convex optimization to piecewise convex approximation for the nonconvex case; since among others DC and Lipschitz functions have locally tight piecewise convex majorants, it shows the potential strength of this approach.

The key tool lies behind the virtual cutting function; we call it either a patch to avoid cycling through the same local solutions or a pseudo patch to early detect a better point.

Attractive Force Search Algorithm

Newton’s law of universal gravitation states that any two bodies in the universe attract each other with a force that is directly proportional to the product of their masses and inversely proportional to the square of the distance between them.

$$\displaystyle{\mathcal{F} = \mathcal{G}\frac{m_{1} \times m_{2}} {r^{2}} }$$

defines the attractive force between two bodies that possess masses m 1, m 2, respectively.

Inspired by the well known law, the authors provided an algorithm in article [9] that calculates an improvement from a current local solution y of (PCMP) by using some analogy of Newton’s attractive force.

How does one search for an improvement from a feasible solution x? Up until now, there have been used a local solution search algorithm to find a local solution y with subsequent checking the inclusion \(D \subset \mathcal{L}_{F}(F(y))\) for a possible further improvement. Of course, one can check also the inclusion \(D \subset \mathcal{L}_{F}(F(x))\) directly at x ∈ D. On the other hand, since

$$\displaystyle{\mathcal{L}_{F}(F(\cdot )) =\bigcup _{ i=1}^{m}\mathcal{L}_{ f_{i}}(F(\cdot ))}$$

an improvement can occur when

$$\displaystyle{D\not\subset \bigcup _{i=1}^{m}\mathcal{L}_{ f_{i}}(F(\cdot )).}$$

Anyway, for an improvement we seek a point in D, but outside of all the Lebesgue sets \(\mathcal{L}_{f_{i}}(F(\cdot ))\).

If we imagine each of these nonempty Lebesgue sets \(\mathcal{L}_{f_{i}}(F(y))\) as a convex body that possesses mass, then a direction of improvement at a current point y could be calculated by analogy to Newton’s attractive force.

In [9] a feasible set is assumed to be a full dimensional polytope defined by linear constraints

$$\displaystyle{D ={\bigl \{ x \in \mathcal{R}^{n}\mid Ax \leq b\} =\{ x \in \mathcal{R}^{n}\mid \langle a^{j},x\rangle \leq b_{ j},j = 1,2,\ldots,k\bigr \}}.}$$

To deal with the polyhedral domain we consider implicitly convex functions that approximate linear functions: \(f_{j}(x) \approx b_{j} -\langle a^{j},x\rangle\). The linear constraints \(b_{j} -\langle a^{j},x\rangle \geq 0\) in the domain, may be seen as the linearization of reverse convex constraints f j (x) ≥ 0 for some strictly convex quadratic functions f j (⋅ ); (a huge flat ellipsoid). This viewpoint looks strange at first sight, however, it turns all the Lebesgue sets of constraints, objective functions into convex bodies. The interaction between these convex bodies seems to be related to Newton’s law, which gives the main idea of our algorithm. At a given point y, two kind of forces can be involved from each body (the Lebesgue set): attracting and repelling forces.

An example, given in Fig. 2, shows for y

  • a repelling force from \(\mathcal{L}_{f_{i}}(\ell)\) body,

  • an attracting force from \(\mathcal{L}_{f_{k}}(\ell)\) body

Fig. 2
figure 2

Newton’s gravitational force

Full size image

since f i (y) < ℓ and f k (y) > ℓ, and in addition, a repelling force from the constraint. More precisely, we select respectively

  • the gradient of the function at y multiplied by a positive (resp. negative) scalar in repelling (resp. attracting) case as an analogy for the direction of Newton’s force;

  • the distance from y to \(\mathcal{L}_{f_{i}}(\ell)\) as an analogy for the distance between the masses.

Now at y, we are able to compute a gravitational force as the weighted sum of all attracting/repelling forces from each body similarly with Newton’s attractive force model:

$$\displaystyle{G(y) =\sum _{i\in M}\frac{F(\text{Pr}_{f_{i}}(y)) - F(y)} {\parallel \text{Pr}_{f_{i}}(y) - y \parallel ^{2}} \frac{\nabla f_{i}(y)} {\parallel \nabla f_{i}(y) \parallel },}$$

where \(\text{Pr}_{f_{i}}(y)\) stands for projection of y on the Lebesgue set \(\text{Pr}_{\mathcal{L}_{f_{ i}}(\ell)}(y)\) with ℓ, the best known level set value.

Remark 2.

When i is active i ∈ I(y), in other words f i (y) = ℓ the projection is replaced by c i the center of \(\mathcal{L}_{f_{i}}(\ell)\) which is a minimum of f i (⋅ ) and the gradient by the direction x − c i (the mass of the convex body is supposed at center). For active linear constraints, the center is assumed at infinity so that no attracting/repelling force contributes to G(x).

Before describing the algorithm, let us introduce a set which appears very convenient in data structure.

Definition 4.

The resolving border of F(⋅ ) at level set value ℓ is defined like the set of points:

$$\displaystyle{\text{rb}(F,\ell) ={\bigl \{ x \in \mathcal{R}^{n}\mid \exists i,f_{ i}(x) =\ell,F(x) \leq \ell\bigr \}}.}$$

For each i, we may distinguish three parts:

  1. 1.

    f i (x) = ℓ, f j (x) > ℓ for all j ≠ i

  2. 2.

    f i (x) = ℓ, f j (x) ≥ ℓ for all j ≠ i

  3. 3.

    f i (x) = ℓ, f j (x) > ℓ for some j ≠ i.

We notice that cases (1. ) and (2. ) easily lead to a better point.

A resolving border data structure stores points according to active functions ordered by decreasing values of F(⋅ ).

For sake of consistency with previous versions of global search algorithm [4, 8] we still refer to Newton’s Attractive force Search Algorithm as a local search, but it clearly outperforms a strict local searching since it cruises in the surroundings of the resolving border.

PCMP local Search (Newton’s Attractive force Search Algorithm)

  • (D, M, w j ∈ D)

  • Initialize RB=(key,sortedset) associating map

  • y 1=setAndBetter(w j,RB)

  • if y 1 not null then return y 1

  • dir = G(w j); Newton attraction at w j

  • \(u = w^{j} +\alpha \text{ dir }\); α > 0 gives the nearest intersection with the resolving border

  • y 2=setAndBetter(u,RB)

  • if y 2 not null then return y 2

  • else return findBetter(RB)

Relationship with Other Optimization Problems

  • Combinatorial Optimization Many practical problems give rise to combinatorial optimization problems can be formulated by the binary constraint x ∈ { 0, 1}n, by the permutation constraint like the assignment problems. The following two articles [5, 6] are devoted to continuous approaches for combinatorial optimization problems. The hardness of these problems consists in nonconvex domains. The current subsection highlights a couple of ideas about how to solve some combinatorial optimization problems using (PCMP).

    We consider the multiknapsack problem [5]

    $$\displaystyle{ \left \{\begin{array}{ll} \max &\langle c,x\rangle \\ \text{s.t.}&Ax \leq b \\ &x \in \{ 0,1\}^{n}\end{array} \right. }$$
    (MKP)

    Since the binary constraint x i  ∈ { 0, 1} can be written like

    $$\displaystyle{x_{i}(x_{i} - 1) \geq 0,0 \leq x_{i} \leq 1,}$$

    (MKP) has an equivalent continuous formulation

    $$\displaystyle{\left \{\begin{array}{ll} \max &\langle c,x\rangle \\ \text{s.t.}&Ax \leq b \\ &x \in [0,e] \\ &x_{i}(x_{i} - 1) \geq 0,\forall i = 1,\ldots,n,\end{array} \right.}$$

    where \(e = (1,\ldots,1)^{\top }\in \mathcal{R}^{n}\). Introducing a function

    $$\displaystyle{\varphi (x) = min\{x_{i}(x_{i} - 1)\mid i = 1,2,\ldots,n\},}$$

    we replace n constraints \(x_{i}(x_{i} - 1) \geq 0,\;i = 1,\ldots,n\) with a constraint \(\varphi (x) \geq 0\) and obtain an equivalent to (MKP) problem

    $$\displaystyle{\left \{\begin{array}{ll} \max &\varphi (x) \\ \text{s.t.}&Ax \leq b \\ &x \in [0,e] \\ &\langle c,x - y\rangle \geq 0.\end{array} \right.}$$

    for an admissible point y of (MKP). The latter is the piecewise convex maximization problem with n pieces.

    Let assume that there is suitable index set’s division \(J_{1},\ldots,J_{m}\) such that \(\bigcup _{i=1}^{m}J_{i} =\{ 1\ldots n\}\) and \(J_{i} \cap J_{j} =\emptyset,\;\forall i\neq j\). Then it holds also

    $$\displaystyle\begin{array}{rcl} x \in \{ 0,1\}^{n} \Leftrightarrow f_{ 1}(x) \geq 0,\ldots,f_{m}(x) \geq 0,0 \leq x \leq e,& & {}\\ \end{array}$$

    where f i (x) denotes \(f_{J_{i}}(x)\) defined like

    $$\displaystyle{f_{J}(x) =\varSigma _{i\in J}\left (x_{i} -\frac{1} {2}\right )^{2} -\frac{\vert J\vert } {4} }$$

    for any \(J \subseteq \{ 1\ldots n\}\) of | J | elements. In this way we obtain (PCMP) where number of pieces m much less than the dimension of the problem (m < n)

    $$\displaystyle{\left \{\begin{array}{ll} \max &min\{f_{i}(x)\mid i = 1\ldots m\} \\ \text{s.t.}&Ax \leq b \\ &x \in [0,e] \\ &\langle c,x - y\rangle \geq 0.\end{array} \right.}$$

    But, in practice, the nature of pieces as well as a number of pieces are crucial for solving (PCMP). One can find in [5] a practical algorithm with m = 2 of this approach along with computational results in contrast with the best known solutions found by heuristics from combinatorial optimization.

    What concerns the permutation constrained problems investigated in [6], in order to retain our focus on common features of continuous optimization, first, we study shortly relationship between (PCMP) and DC optimization, then as a result (PCMP) formulation for the well known quadratic assignment problems (QAP) is given. We consider a problem of maximization of a difference of two convex functions f, g over a convex compact \(D \subset \mathcal{R}^{n}\)

    $$\displaystyle{\begin{array}{ll} \text{ max}&f(x) - g(x)\\ \text{ s.t.} &x \in D.\end{array} }$$

    It is straightforward to turn it into (PCMP) of dimension n + 1 by introducing another variable t = g(x) and splitting the equality constraint into a convex constraint g(x) − t ≤ 0 while the converse inequality is dualized to add a new piece as \(F(x,t) =\min {\bigl \{ f(x) - t,g(x) - t\bigr \}}\). Then, it is equivalent to solving the following problem

    $$\displaystyle{\begin{array}{ll} \max \ &F(x,t) \\ \text{ s.t.}&x \in D,t \in \mathcal{R} \\ &g(x) - t \leq 0.\end{array} }$$

  • Multicriteria Optimization

    We consider multicriteria optimization problem

    $$\displaystyle{ \left \{\begin{array}{l} \text{ minimize }\;\varOmega (x),\\ \text{ subject to } x \in D\end{array} \right. }$$
    (MOP)

    where Ω(⋅ ) is a vector valued function from \(\mathcal{R}^{n}\) to \(\mathcal{R}^{m}\) whose components are the convex functions \(f_{i}(\cdot ),i \in M =\{ 1,2,\ldots,m\}\) namely:

    $$\displaystyle{\varOmega (x) = (f_{1}(x),\ldots,f_{m}(x))^{\top }\in \mathcal{R}^{m}.}$$

    Let us formally recall the definition of Pareto optimal solutions.

Definition 5.

A solution y ∈ D is called Pareto optimal, if there is no x ∈ D such that \(f_{i}(x) \leq f_{i}(y),i = 1,\ldots,m\) and f j (x) < f j (y) for some j ∈ M.

An interesting relationship between (PCMP) and multicriteria optimization is presented [21] and afterwards in [9].

We recall also some basic definitions and results from multicriteria optimization.

Definition 6.

 

  • y ∈ D is called weakly Pareto optimal if there is no x ∈ D such that

    $$\displaystyle{f_{i}(x) < f_{i}(y),\;\forall i = 1,\ldots,m}$$

  • y ∈ D is called strictly Pareto optimal if there is no x ∈ D, x ≠ y such that

    $$\displaystyle{f_{i}(x) \leq f_{i}(y),\;\forall i = 1,\ldots,m\text{ and }f_{j}(x) < f_{j}(y)\text{ for some }j \in M.}$$

We define also so called the level curve, the strict level set of f(⋅ ) at α respectively

$$\displaystyle{\mathcal{L}_{f}^{=}(\alpha ) =\{ x\mid f(x) =\alpha \},\;\;\mathcal{L}_{ f}^{<}(\alpha ) =\{ x\mid f(x) <\alpha \}}$$

Theorem 2 ([1], Chap. 2).

Let y ∈ D then

  1. 1.

    y is strictly Pareto optimal if and only if

    $$\displaystyle{\bigcap _{i=1}^{m}\mathcal{L}_{ f_{i}}(f_{i}(y)) =\{ y\}.}$$
  2. 2.

    y is Pareto optimal if and only if

    $$\displaystyle{\bigcap _{i=1}^{m}\mathcal{L}_{ f_{i}}(f_{i}(y)) =\bigcap _{ i=1}^{m}\mathcal{L}_{ f_{i}}^{=}(f_{ i}(y)).}$$
  3. 3.

    y is weakly Pareto optimal if and only if

    $$\displaystyle{\bigcap _{i=1}^{m}\mathcal{L}_{ f_{i}}^{<}(f_{ i}(y)) =\emptyset.}$$

The following results summarize our findings so far:

Proposition 3.

If y is local maximum to (PCMP) such that y ∈ int(D) then for some ε > 0

$$\displaystyle{F(y) =\min _{x\in B(y,\varepsilon )}max\{f_{i}(x)\mid i \in I(y)\},}$$

where \(B(y,\varepsilon )\) stands for the ball of radius \(\varepsilon\) , centered at y.

Let us denote \(\varOmega _{N}(\cdot ) \in \mathcal{R}^{\vert N\vert }\) with corresponding components f i (⋅ ) for \(i \in N \subset M\). Proposition 3 together with Theorem 2 provide the following relationship.

Theorem 3.

If y is local maximum to (PCMP) such that y ∈ int(D) then y is strictly Pareto optimal to the following multicriteria optimization problem:

$$\displaystyle{\left \{\begin{array}{l} \text{ minimize }\;\varOmega _{I(y)}(x), \\ \text{ subject to }x \in D\end{array} \right.}$$

Remark 3.

Weakly Pareto optimality of y is implied by Proposition 6.5 from [1].

Abstract Nonlinear Covering Method

The remainder of the chapter is devoted to new approach of solving (PCMP).

For all maximization problems, in particular for (PCMP), clearly, z is the global maximum iff all points of the domain are no better than z, in other words:

$$\displaystyle{D \subset \mathcal{L}_{F}(F(z)).}$$

Since as we observed early \(\mathcal{L}_{F}(F(y)) =\bigcup _{ i=1}^{m}\mathcal{L}_{f_{i}}(F(y)).\) the above inclusion means that

  • for all x no better than z (i.e. F(x) ≤ F(z)) there exists j ∈ M such that

    $$\displaystyle{x \in \mathcal{L}_{f_{j}}(F(z)),}$$

  • if there is u ∈ D better than z (i.e. F(z) < F(u)) then u does not belong to any Lebesgue set:

    $$\displaystyle{u\notin \mathcal{L}_{f_{i}}(F(z))\text{ for all }i \in M.}$$

In order to present the main idea of a new approach for solving (PCMP), we give a definition along with an abstract result on an equivalence of problems.

Definition 7.

An open subset C satisfying conditions

$$\displaystyle{C \subset \mathcal{L}_{F}(F(y))\mbox{ and }C\neq int(\mathcal{L}_{F}(F(y)))}$$

is called a covering set at level F(y).

Proposition 4.

Let y be a feasible point for (PCMP) such that

$$\displaystyle{F(y) = max\{F(x)\mid x \in D\}-\delta }$$

for some δ > 0. Let also C be a covering set at level F(y). Then the following problem is equivalent to (PCMP):

$$\displaystyle{ \left \{\begin{array}{ll} \text{ maximize }&F(x)\\ \text{subject to }&x \in D\setminus C.\end{array} \right. }$$
(CC)

The main algorithmic feature now looks like

  • to cover the feasible set (the domain) by a union of covering sets.

  • if the domain is covered by C totally, then stop and the global optimum is found.

  • otherwise, solve problem (CC) for an improvement.

In other words, one have to construct an “(union of covering sets)” such that

$$\displaystyle{D \subset \text{ (union of covering sets)} \subset \mathcal{L}_{F}(F(z)).}$$

Starting with an initial guess of covering sets, a method bootstraps its way up to ever more accurate “sandwich” approximations to answer “the global optimum” or “improvement”. What concerns the covering set, the first that comes to mind, is use balls (spherical set) as a simpler nonlinear shape.

(PCMP) over Spherical Sets

Let S(c; ρ) and B(c; ρ) be respectively a sphere and a ball of center c and radius ρ. This section is devoted to the following two (PCMP), solutions of them are going to be key tools in nonlinear separation as stated in previous section.

$$\displaystyle{\left \{\begin{array}{l} \text{ maximize }F(x),\\ \text{ subject to } x \in S(c;\rho ), \end{array} \right.\left \{\begin{array}{l} \text{ maximize }F(x),\\ \text{ subject to } x \in B(c;\rho ). \end{array} \right.}$$

We turn our attention to the problem over a sphere, that is a problem of piecewise maximization over a nonconvex feasible set with an empty interior. Since all feasible points are degenerated even the local search for this problem is worth-while to study. We consider a convex function f and notice that the KKT optimality condition for an optimizer of f (either \(\min\) or \(\max\)) over S(c, ρ) implies collinearity of gradient ∇f(u) and u − c. It is well known that the projected gradient method, from a reasonably good starting point, quickly converges to the optimal solution. If no meaningful guess is known, the gradient ∇f(c) is a good ray direction to find a starting point for maximizing f over the sphere; for minimizing we start from the antigradient −∇f(c).

Since \(F(x) =\min \{ f_{1}(x),\ldots,f_{m}(x)\}\) a piecewise convex function; using 2 × m times the above optimization paradigm (for both \(l^{j} =\arg \min _{S}f_{j}(x)\) and \(u^{j} =\arg \max _{S}f_{j}(x)\)) yields a sparse set of points which the actual values F(l j) and F(u j) may be computed for all \(j = 1,\ldots,m\). We call for the best value of \(\max \{F(l^{i}),F(u^{j})\mid i,j = 1,\ldots,m\}\) as sparse piecewise convex maximization value over a sphere and denote by z the point of this value.

Now we borrow from [9] the resolving border heuristic that focuses on points on the level set in the vicinity of D k (⋅ ) for some k that are likely to improve the easy sparse optimizers.

Algorithm 1 PCMP-over-sphere: Resolving border for arglocmax x ∈ S F(x)

We use the following two examples as the main lead to illustrate the different steps in Piecewise Convex Maximizing:

$$\displaystyle{\begin{array}{ll} F_{1}^{2D} =\min \bigl \{&x_{1}^{2} + (x_{2} + 4)^{2} - 36, \\ &(x_{1} + 8)^{2} + (x_{2} - 3)^{2} - 36, \\ &x_{1}^{2} + (x_{2} - 8)^{2} - 16, \\ &(x_{1} - 8)^{2} + (x_{2} - 3)^{2} - 53, \\ &(x_{1} - 10)^{2} + (x_{2} + 10)^{2} - 4\bigr \}, \\ F_{2}^{2D} =\min \bigl \{&x_{1}^{2} + (x_{2} + 2)^{2} - 9, \\ &9(x_{1} + 3)^{2} + 4x_{2}^{2} - 36, \\ &(x_{1} + 1)^{2} + (x_{2} - 4)^{2} - 4, \\ &\frac{1} {9}(x_{1} - 3)^{2} + \frac{1} {36}(x_{2} - 4)^{2} - 1, \\ &(x_{1} - 5)^{2} + (x_{2} + 5)^{2} - 1\bigr \}\end{array} }$$

respectively in spherical domain (spheres/balls) with (c, ρ) = ([0, 0], 4).

Despite there is no proof of global optimality, we experimented an effective behavior to find points on the sphere well ordered by the priority queue and likely to lay close to \(\cap D_{j}(z)\) (the best z found is drawn as a blue dot on Fig. 3).

Fig. 3
figure 3

Maximize F i 2D over a sphere, i = 1, 2 (left, right)

Full size image

In the remainder we concentrate on elementary coding steps, starting on optimization over a sphere towards more involved recursive calls of (PCMP) over a ball.

There is a subtlety when v = c for defining w; we choose \(w = \frac{z+c} {2}\) betting on a point in \(\cap D_{k}(z)\) (early detection of a better point). In both cases Figs. 3 and 4 blue points were found quickly which localize the global solution areas.

Fig. 4
figure 4

Maximize F i 2D over a ball, i = 1, 2 (left, right)

Full size image

Algorithm 2 PCMP-over-ball: Recursive radius search for arglocmax x ∈ B F(x)

Concluding Remarks

In this chapter we have presented an overview of studies on piecewise convex maximization problems: necessary and sufficient global optimality conditions, methods including linearization oriented algorithm, piece adding technique (patch for short), and Newton’s attractive force search algorithm (nasa for short). A novel approach of solving (PCMP) based on a nonlinear separation (instead of the traditional affine separation) has been proposed. We call it a nonlinear covering method. As a rule the approach opens up a field which should be investigated more thoroughly: a choice of the covering sets, algorithms of solving subproblems over them, etc.

Our aim is now to construct an “(union of covering sets)” such that

$$\displaystyle{D \subset \text{ (union of covering sets)} \subset \mathcal{L}_{F}(F(z))}$$

to check the global optimality of z for (PCMP).

As a preliminary we have considered piecewise convex maximization problems over spherical sets (balls, spheres) which play the key role for this new research direction. Algorithms along with some computational results with simple, but illustrative, examples have been reported.