An objective penalty function method for biconvex programming (Q2052381)

A function \(f(x_1,x_2)\) is biconvex when \(f(\cdot,x_2)\) and \(f(x_1,\cdot)\) are both convex for all \(x_1,x_2\). A point \((x_1^*,x_2^*)\) is said to be a partial minimiser if \(x_1^*\) is a minimiser of \(f(\cdot, x_2^*)\) and \(x_2^*\) is a minimiser of \(f(x_1^*,\cdot)\). Consider the constrained biconvex programming problem of minimising the function \(f\) subject to the constraint \(g(x_1,x_2)\leq 0\) where \(g\) is also biconvex. One can similarly define the notion of partial KKT solutions as points satisfying KKT conditions in each of its variables, when the other one is fixed (both subproblems are then convex). A penalisation of this problem consisting of minimising \(P(f(x_1,x_2)) + \rho Q(g(x_1,x_2))\) is a partially exact objective penalty function if it admits a partial optimum that coincides with the partial optimum of the original constrained problem for some \(\rho\). This paper presents algorithms based on properties of biconvex function relating to their partial properties. The first part establishes the equivalence between partial optimality and the satisfaction of partial KKT conditions, under reasonable conditions on \(P\) and \(Q\). This result opens the possibility for ADMM-like algorithms that converge to partial minimisers to constrained biconvex problems using a penalty approach. This is the focus of the second part of the paper.