Beyond canonical DC-Optimization: the single reverse polar problem
Giancarlo Bigi, Antonio Frangioni and Qinghua Zhang
Summary
DC optimization problems are those nonconvex extremum problems in which the objective function is the difference of two convex functions and the constraint is given by the set difference of two convex sets. It is well-known that all of them can be transformed into the so-called Canonical DC problem (CDC, shortly). Since a large number of nonconvex optimization problems can be reduced to DC problems, has a wide set of applications.
In this paper, we introduce the Single Reverse Polar problem (SRP, shortly) as a generalization of CDC. In effect, SRP makes it possible to directly address a host of different problems of practical interest other than all the applications that can be formulated as DC optimization problems. Among them, Separable Linear Complementarity Problems (SLCP, shortly) have many practical applications. For instance, the l-zero-norm could be easily reformulated as a linear complementarity form, thus convex optimization problems with an additional l-zero constraint, such as compressed sensing problems, can be easily formulated as SLCPs. Many other structures, such as value-at-risk minimization problem in portfolio selection, also admit a linear complementarity reformulation. Furthermore, separable bilevel problems, where leader and follower variables are only "tied" in the objective function, are also easily reduced to SLCPs; in turn, these can be used to reformulate several families of Mixed-Integer (Non)Linear Problems.
We extend the outer approximation algorithms for CDC of to the new class of problems, as this approach should have similar cost per iteration for SRP and CDC. In fact, these algorithms are based on an approximated oracle for checking the global optimality conditions, which is the most computationally demanding part of the approach. As shown in Section 2, the optimality conditions for SRP are a minimal modification of those for CDC. Both entail the solution of an optimization problem with a non-convex objective function and a convex feasible region.The "difficult" part (the objective function) of both is the same, while the "easy" part (the feasible set) is very similar; hence, it is likely that the difference does not substantially impact the practical cost of solving the problems. Furthermore, allowing not to solve them up to proven global optimality can substantially improve the efficiency of the overall cutting-plane method. Yet, this also requires to properly characterize the impact of approximations in the oracle on the quality of the obtained solution. After that is done, one can devise different ways to exploit the information produced by the oracle to construct globally convergent algorithms. This analysis gives rise to three different implementable algorithms for SRP. Our analysis shows that, despite the similarities, SRP have markedly different properties than CDC, which substantially impact on the way in which algorithms can be constructed, thereby shedding some new light on the algorithms for the original problem too.
The paper is organized as follows. In Section 2, we describe and analyze the main properties of SRP and contrast them with those of CDC.
Then, in Section 3, we extend the approximate optimality conditions for CDC to the new problem. In Section 4, we develop a hierarchy of conditions that guarantee the convergence of cutting plane algorithms; in Section 5, relying on these conditions, we build three cutting plane algorithms for solving SRP, and we discuss possible strategies to enhance their effectiveness in practice. Finally, Section 6 draws some conclusions.
The original paper is available at http://dx.doi.org/10.1007/s10957-012-0069-7.
A Technical Report version is available
here.
My Home Page