Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2017-002 (August 29, 2017)

Sub-Homogeneous Optimization
by Shota Yamanaka and Nobuo Yamashita

pdf File

We consider an optimization problem with sub-homogeneous functions in its objective and constraint functions. Examples of such sub-homogeneous functions include the absolute value function and the $p$-norm function, where $p$ is a positive real number. The problem, which is not necessarily convex, extends the absolute value optimization proposed in [O.L. Mangasarian, Absolute value programming, Computational Optimization and Applications 36 (2007) pp. 43--53]. In this work, we propose a dual formulation that, differently from the Lagrangian dual approach, has a closed-form and some interesting properties. In particular, we discuss the relation between the Lagrangian duality and the one proposed here, and give some sufficient conditions under which these dual problems coincide. Finally, we show that some well- known problems, e.g., sum of norms optimization and the group Lasso-type optimization problems, can be reformulated as sub-homogeneous optimization problems.