Search

Among many approaches to increase the computational efficiency of semidefinite programming (SDP) relaxation for nonconvex quadratic constrained quadratic programming problems (QCQPs), exploiting the aggregate sparsity of the data matrices in the SDP by Fukuda et al. [Exploiting sparsity in semidefinite programming via matrix completion I: General framework, SIAM J. Optim. 11(3) (2001), pp. 647–674] and second-order cone programming (SOCP) relaxation have been popular. In this paper, we exploit the aggregate sparsity of SOCP relaxation of nonconvex QCQPs. Specifically, we prove that exploiting the aggregate sparsity reduces the number of second-order cones in the SOCP relaxation, and that we can simplify the matrix completion procedure by Fukuda et al. in both primal and dual of the SOCP relaxation problem without losing the max-determinant property. For numerical experiments, nonconvex QCQPs from the lattice graph and pooling problem are tested as their SOCP relaxations provide the same optimal value as the SDP relaxations. We demonstrate that exploiting the aggregate sparsity improves the computational efficiency of the SOCP relaxation for the same objective value as the SDP relaxation, thus much larger problems can be handled by the proposed SOCP relaxation than the SDP relaxation. [ABSTRACT FROM AUTHOR]

One important task in image segmentation is to find a region of interest, which is, in general, a solution of a nonlinear and nonconvex problem. The authors of Chan and Esedoglu (Aspects of total variation regularized L 1 function approximation. SIAM J. Appl. Math. 2005;65:1817–1837) proposed a convex T V − L 1 problem for finding such a region Σ and proved that when a binary input f is given, a solution u ∗ to the convex problem gives rise to other solutions 1 { u ∗ ≥ μ } for a.e. μ ∈ (0 , 1) from which they raised a question of whether or not u ∗ must be binary. The same is to ask if the two-phase Mumford–Shah model in image processing has a unique solution with a binary input. In this paper, we will discuss how to construct a non-binary solution that provides a negative answer to the question through a connection of two ideas, one from the two-phase Mumford–Shah model in image segmentation and the other from mean curvature motions discussed in some geometric problems (e.g. Alter, Caselles, Chambolle. A characterization of convex calibrable sets in R N . Math. Ann. 2005;322:329–366; Chambolle. An algorithm for mean curvature motion. Interfaces Free Boundaries 2004;6:195–218) revealing the nature of non-uniqueness in image segmentation. [ABSTRACT FROM AUTHOR]