A nonconvex approach to low‐rank matrix completion using convex optimization

This paper deals with the problem of recovering an unknown low‐rank matrix from a sampling of its entries. For its solution, we consider a nonconvex approach based on the minimization of a nonconvex functional that is the sum of a convex fidelity term and a nonconvex, nonsmooth relaxation of the rank function. We show that by a suitable choice of this nonconvex penalty, it is possible, under mild assumptions, to use also in this matrix setting the iterative forward–backward splitting method. Specifically, we propose the use of certain parameter dependent nonconvex penalties that with a good choice of the parameter value allow us to solve in the backward step a convex minimization problem, and we exploit this result to prove the convergence of the iterative forward–backward splitting algorithm. Based on the theoretical results, we develop for the solution of the matrix completion problem the efficient iterative improved matrix completion forward–backward algorithm, which exhibits lower computing times and improved recovery performance when compared with the best state‐of‐the‐art algorithms for matrix completion. Copyright © 2016 John Wiley & Sons, Ltd.     

A fast interface solver for the biharmonic Dirichlet problem on polygonal domains

Summary. In this paper we propose and analyze an efficient discretization scheme for the boundary reduction of the biharmonic Dirichlet problem on convex polygonal domains. We show that the biharmonic Dirichlet problem can be reduced to the solution of a harmonic Dirichlet problem and of an equation with a Poincaré-Steklov operator acting between subspaces of the trace spaces. We then propose a mixed FE discretization (by linear elements) of this equation which admits efficient preconditioning and matrix compression resulting in the complexity . Here is the number of degrees of freedom on the underlying boundary, is an error reduction factor, or for rectangular or polygonal boundaries, respectively. As a consequence an asymptotically optimal iterative interface solver for boundary reductions of the biharmonic Dirichlet problem on convex polygonal domains is derived. A numerical example confirms the theory. Received September 1, 1995 / Revised version received February 12, 1996     

Support vector machine classifiers with uncertain knowledge sets via robust optimization

In this article we study support vector machine (SVM) classifiers in the face of uncertain knowledge sets and show how data uncertainty in knowledge sets can be treated in SVM classification by employing robust optimization. We present knowledge-based SVM classifiers with uncertain knowledge sets using convex quadratic optimization duality. We show that the knowledge-based SVM, where prior knowledge is in the form of uncertain linear constraints, results in an uncertain convex optimization problem with a set containment constraint. Using a new extension of Farkas' lemma, we reformulate the robust counterpart of the uncertain convex optimization problem in the case of interval uncertainty as a convex quadratic optimization problem. We then reformulate the resulting convex optimization problems as a simple quadratic optimization problem with non-negativity constraints using the Lagrange duality. We obtain the solution of the converted problem by a fixed point iterative algorithm and establish the convergence of the algorithm. We finally present some preliminary results of our computational experiments of the method.     

Some iterative methods for finding fixed points and for solving constrained convex minimization problems

The present paper is divided into two parts. In the first part, we introduce implicit and explicit iterative schemes for finding the fixed point of a nonexpansive mapping defined on the closed convex subset of a real Hilbert space. We establish results on the strong convergence of the sequences generated by the proposed schemes to a fixed point of a nonexpansive mapping. Such a fixed point is also a solution of a variational inequality defined on the set of fixed points. In the second part, we propose implicit and explicit iterative schemes for finding the approximate minimizer of a constrained convex minimization problem and prove that the sequences generated by our schemes converge strongly to a solution of the constrained convex minimization problem. Such a solution is also a solution of a variational inequality defined over the set of fixed points of a nonexpansive mapping. The results of this paper extend and improve several results presented in the literature in the recent past.     

Convergence analysis of an optimally accurate frozen multi-level projected steepest descent iteration for solving inverse problems

In this paper, we introduce a novel projected steepest descent iterative method with frozen derivative. The classical projected steepest descent iterative method involves the computation of derivative of the nonlinear operator at each iterate. The method of this paper requires the computation of derivative of the nonlinear operator only at an initial point. We exhibit the convergence analysis of our method by assuming the conditional stability of the inverse problem on a convex and compact set. Further, by assuming the conditional stability on a nested family of convex and compact subsets, we develop a multi-level method. In order to enhance the accuracy of approximation between neighboring levels, we couple it with the growth of stability constants. This along with a suitable discrepancy criterion ensures that the algorithm proceeds from level to level and terminates within finite steps. Finally, we discuss an inverse problem on which our methods are applicable.     

Iterative Regularization Methods for the Multiple-Sets Split Feasibility Problem in Hilbert Spaces

In this paper, we introduce iterative regularization methods for solving the multiple-sets split feasibility problem, that is to find a point closest to a family of closed convex subsets in one space such that its image under a bounded linear mapping will be closest to another family of closed convex subsets in the image space. We consider the cases, when the families are either finite or infinite. We also give two numerical examples for illustrating our main method.

     

Fixed point optimization algorithm and its application to network bandwidth allocation

A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness.     

Iterative algorithms for the multiple-sets split feasibility problem in Hilbert spaces

In this paper, for the multiple-sets split feasibility problem, that is to find a point closest to a family of closed convex subsets in one space such that its image under a linear bounded mapping will be closest to another family of closed convex subsets in the image space, we study several iterative methods for finding a solution, which solves a certain variational inequality. We show that particular cases of our algorithms are some improvements for existing ones in literature. We also give two numerical examples for illustrating our algorithms.     

On the extremal solutions for capacitated network problems

In this note we give a unifying approach to the problem of characterizing the extreme points of those convex matrix sets which correspond to the domains of various types of capacitated network problems. It is shown that we can determine whether a matrix is an extreme point of the sets by examining the pattern of a certain graph associated with it. We also study the extreme points of the convex matrix sets which are related to network problems free from capacity constraints by linking them up with certain capacitated network problem.     

Penalized Covariance Matrix Estimation Using a Matrix-Logarithm Transformation

For statistical inferences that involve covariance matrices, it is desirable to obtain an accurate covariance matrix estimate with a well-structured eigen-system. We propose to estimate the covariance matrix through its matrix logarithm based on an approximate log-likelihood function. We develop a generalization of the Leonard and Hsu log-likelihood approximation that no longer requires a nonsingular sample covariance matrix. The matrix log-transformation provides the ability to impose a convex penalty on the transformed likelihood such that the largest and smallest eigenvalues of the covariance matrix estimate can be regularized simultaneously. The proposed method transforms the problem of estimating the covariance matrix into the problem of estimating a symmetric matrix, which can be solved efficiently by an iterative quadratic programming algorithm. The merits of the proposed method are illustrated by a simulation study and two real applications in classification and portfolio optimization. Supplementary materials for this article are available online.     

Approximating a Zero of Sum of Two Monotone Operators Which Solves a Fixed Point Problem in Reflexive Banach Spaces

Abstract

The purpose of this paper is to introduce an iterative method for approximating a point in the set of zeros of the sum of two monotone mappings, which is also a solution of a fixed point problem for a Bregman strongly nonexpansive mapping in a real reflexive Banach space. With our iterative technique, we state and prove a strong convergence theorem for approximating an element in the intersection of the set of solutions of a variational inclusion problem for sum of two monotone mappings and the set of solutions of a fixed point problem for Bregman strongly nonexpansive mapping. We give applications of our result to convex minimization problem, convex feasibility problem, variational inequality problem, and equilibrium problem. Our result complements and extends some recent results in literature.     

A new simultaneous iterative method with a parameter for solving the extended split equality problem and the extended split equality fixed point problem

In this article, we first propose an extended split equality problem which is an extension of the convex feasibility problem, and then introduce a parameter w to establish the fixed point equation system. We show the equivalence of the extended split equality problem and the fixed point equation system. Based on the fixed point equation system, we present a simultaneous iterative algorithm and obtain the weak convergence of the proposed algorithm. Further, by introducing the concept of a G-mapping of a finite family of strictly pseudononspreading mappings \(\{T_{i}\}_{i = 1}^{N}\), we consider an extended split equality fixed point problem for G-mappings and give a simultaneous iterative algorithm with a way of selecting the stepsizes which do not need any prior information about the operator norms, and the weak convergence of the proposed algorithm is obtained. We apply our iterative algorithms to some convex and nonlinear problems. Finally, several numerical results are shown to confirm the feasibility and efficiency of the proposed algorithms.     

与渐近非扩张半群不动点问题相关的分裂等式混合均衡问题及其应用

研究了与渐近非扩张半群不动点问题相关的分裂等式混合均衡问题.在等式约束下,为同时逼近两个空间中混合均衡问题和渐近非扩张半群不动点问题的公共解,借助收缩投影方法引出了一种迭代程序.在适当条件下,该迭代算法的强收敛性被证明.文末还把所得结果应用于分裂等式混合变分不等式问题和分裂等式凸极小化问题.     

A new iterative algorithm for the variational inequality problem over the fixed point set of a firmly nonexpansive mapping

Many problems to appear in signal processing have been formulated as the variational inequality problem over the fixed point set of a nonexpansive mapping. In particular, convex optimization problems over the fixed point set are discussed, and operators which are considered to the problems satisfy the monotonicity. Hence, the uniqueness of the solution of the problem is not always guaranteed. In this article, we present the variational inequality problem for a monotone, hemicontinuous operator over the fixed point set of a firmly nonexpansive mapping. The main aim of the article is to solve the proposed problem by using an iterative algorithm. To this goal, we present a new iterative algorithm for the proposed problem and its convergence analysis. Numerical examples for the proposed algorithm for convex optimization problems over the fixed point set are provided in the final section.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming

ABSTRACT

In this note, we consider three types of problems, H-weighted nearest correlation matrix problem and two types of important doubly non-negative semidefinite programming, derived from the binary integer quadratic programming and maximum cut problem. The dual of these three types of problems is a 3-block separable convex optimization problem with a coupling linear equation constraint. It is known that, the directly extended 3-block alternating direction method of multipliers (ADMM3d) is more efficient than many of its variants for solving these convex optimization, but its convergence is not guaranteed. By choosing initial points properly, we obtain the convergence of ADMM3d for solving the dual of these three types of problems. Furthermore, we simplify the iterative scheme of ADMM3d and show the equivalence of ADMM3d to the 2-block semi-proximal ADMM for solving the dual's reformulation, under these initial conditions.     

A splitting method for quadratic programming problem

1. IntroductionThe quadratic programming (QP) problem is the most simple one in nonlinear pro-gramming and plays a very important role in optimization theory and applications.It is well known that matriX splitting teChniques are widely used for solving large-scalelinear system of equations very successfully. These algorithms generate an infinite sequence,in contrast to the direct algorithms which terminate in a finite number of steps. However,iterative algorithms are considerable simpler tha…     

A new iterative scheme for a countable family of relatively nonexpansive mappings and an equilibrium problem in Banach spaces

In this paper, we construct a new iterative scheme and prove strong convergence theorem for approximation of a common fixed point of a countable family of relatively nonexpansive mappings, which is also a solution to an equilibrium problem in a uniformly convex and uniformly smooth real Banach space. We apply our results to approximate fixed point of a nonexpansive mapping, which is also solution to an equilibrium problem in a real Hilbert space and prove strong convergence of general H-monotone mappings in a uniformly convex and uniformly smooth real Banach space. Our results extend many known recent results in the literature.     

Sylvester矩阵方程极小范数最小二乘解的迭代解法

研究了Sylvester矩阵方程最小二乘解以及极小范数最小二乘解的迭代解法,首先利用递阶辨识原理,得到了求解矩阵方程AX+YB=C的极小范数最小二乘解的一种迭代算法,进而,将这种算法推广到一般线性矩阵方程A_iX_iB_i=C的情形,最后,数值例子验证了算法的有效性.