In content-based image retrieval (CBIR) and image screening, it is often desirable to automatically locate the regions of interest (ROI) in the images. This can be accomplished with multi-instance learning techniques by treating each image as a bag of instances (regions). Many SVM-based methods are successful in predicting the bag label. However, very few of them can locate the ROIs and often they are based on either the local search or an EM-type strategy, which may get stuck in local minima. To address this problem, we propose in this paper two convex optimization methods which maximize the margin of concepts via key instance generation in the instance-level and bag-level, respectively. Moreover, this can be efficiently solved with a cutting plane algorithm. Experiments show that the proposed methods can effectively locate ROIs. Moreover, on the benchmark data sets, they achieve performance that are competitive with state-of-the-art algorithms.