This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest \mathbf {x}^{atural}\in\mathbb {R}^{n} from \mathbf {x}^{atural}\in\mathbb {R}^{n} quadratic equations/samples \mathbf {x}^{atural}\in\mathbb {R}^{n} , \mathbf {x}^{atural}\in\mathbb {R}^{n} . This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning.

The trust-region problem,which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.

In Nash bargaining problem, due to fairness concerns of players, instead of maximizing the sum of utilities of all players, an implementable solution should satisfy some axioms or characterizations. Such a solution can result in the so-called price of fairness, because of the reduction in the sum of utilities of all players. An important issue is to quantify the system efficiency loss under axiomatic solutions through the price of fairness. Based on Perles–Maschler solution of two-player Nash bargaining problem, this paper deals with the extended Perles–Maschler solution of multi-player Nash bargaining problem.We give lower bounds of threemeasures of the system efficiency for this solution, and show that the lower bounds are asymptotically tight.

No abstract uploaded!

Multi-way data arises in many applications such as electroencephalography classification, face recognition, text mining and hyperspectral data analysis. Tensor decomposition has been commonly used to find the hidden factors and elicit the intrinsic structures of the multi-way data. This paper considers sparse nonnegative Tucker decomposition (NTD), which is to decompose a given tensor into the product of a core tensor and several factor matrices with sparsity and nonnegativity constraints. An alternating proximal gradient method is applied to solve the problem. The algorithm is then modified to sparse NTD with missing values. Per-iteration cost of the algorithm is estimated scalable about the data size, and global convergence is established under fairly loose conditions. Numerical experiments on both synthetic and real world data demonstrate its superiority over a few state-of-the-art methods for (sparse