Search

This paper studies tensor eigenvalue complementarity problems. Basic properties of standard and complementarity tensor eigenvalues are discussed. We formulate tensor eigenvalue complementarity problems as constrained polynomial optimization. When one tensor is strictly copositive, the complementarity eigenvalues can be computed by solving polynomial optimization with normalization by strict copositivity. When no tensor is strictly copositive, we formulate the tensor eigenvalue complementarity problem equivalently as polynomial optimization by a randomization process. The complementarity eigenvalues can be computed sequentially. The formulated polynomial optimization can be solved by Lasserre’s hierarchy of semidefinite relaxations. We show that it has finite convergence for generic tensors. Numerical experiments are presented to show the efficiency of proposed methods. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new class of nonsmooth convex functions called SOS-convex semialgebraic functions extending the recently proposed notion of SOS-convex polynomials. This class of nonsmooth convex functions covers many common nonsmooth functions arising in the applications such as the Euclidean norm, the maximum eigenvalue function and the least squares functions with ℓ1-regularization or elastic net regularization used in statistics and compressed sensing. We show that, under commonly used strict feasibility conditions, the optimal value and an optimal solution of SOS-convex semialgebraic programs can be found by solving a single semidefinite programming problem (SDP). We achieve the results by using tools from semialgebraic geometry, convex-concave minimax theorem and a recently established Jensen inequality type result for SOS-convex polynomials. As an application, we show that robust SOS-convex optimization proble ms under restricted spectrahedron data uncertainty enjoy exact SDP relaxations. This extends the existing exact SDP relaxation result for restricted ellipsoidal data uncertainty and answers an open question in the literature on how to recover a robust solution of uncertain SOS-convex polynomial programs from its semidefinite programming relaxation in this broader setting. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the CP-nuclear value of a completely positive (CP) tensor and study its properties. A semidefinite relaxation algorithm is proposed for solving the minimal CP-nuclear-value tensor recovery. If a partial tensor is CP-recoverable, the algorithm can give a CP tensor recovery with the minimal CP-nuclear value, as well as a CP-nuclear decomposition of the recovered CP tensor. If it is not CP-recoverable, the algorithm can always give a certificate for that, when it is regular. Some numerical experiments are also presented. [ABSTRACT FROM AUTHOR]

The uncertainties in renewable generators and load demand make it a challenge for system operators to execute the security-constrained unit commitment (SCUC) program in an ac-dc grid. The SCUC is a nonlinear mixed-integer optimization problem due to the power flow equations, constraints imposed by the ac-dc converters, and the binary variables associated with the generators’ on/off state. In this paper, we study the SCUC problem in ac-dc grids with generation and load uncertainty. We introduce the concept of conditional value-at-risk to limit the risk of deviations in the load demand and renewable generation. We relax the binary variables and introduce a $l_1$-norm regularization term to the objective function, and then use convex relaxation techniques to transform the problem into a semidefinite program (SDP). We develop an algorithm based on the iterative reweighted $l_1$ -norm approximation that involves solving a sequence of SDPs. Simulations are performed on an IEEE 30-bus test system. Results show that the proposed algorithm returns a solution within 2% gap from the global optimal solution for the underlying test system. When compared with the multi-stage algorithm in the literature, our algorithm has a lower running time and returns a solution with a smaller gap from the global optimal solution. [ABSTRACT FROM PUBLISHER]

This paper studies the tensor maximal correlation problem, which aims at optimizing correlations between sets of variables in many statistical applications. We reformulate the problem as an equivalent polynomial optimization problem, by adding the first order optimality condition to the constraints, then construct a hierarchy of semidefinite relaxations for solving it. The global maximizers of the problem can be detected by solving a finite number of such semidefinite relaxations. Numerical experiments show the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

The quantum measurement incompatibility is a distinctive feature of quantum mechanics. We investigate the incompatibility of a set of general measurements and classify the incompatibility by the hierarchy of compatibilities of its subsets. By using the approach of adding noises to measurement operators, we present a complete classification of the incompatibility of a given measurement assemblage with n members. Detailed examples are given for the incompatibility of unbiased qubit measurements based on a semidefinite program.

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W-tensors, which not only extends the well-studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H-eigenvalue of an even-order symmetric W-tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H-eigenvalue of W-tensors and is based on a new structured sums-of-squares decomposition result for a nonnegative polynomial induced by W-tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H-eigenvalue of W-tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H-eigenvalues of large-size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state-of-the-art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z-tensors, whose order may be even or odd. [ABSTRACT FROM AUTHOR]

In this paper, we study a modified version of the conic trust region subproblem which arises within a class of nonlinear programming algorithms. First using a variant of S-Lemma, we give an SOCP/SDP formulation which gives its optimal objective value. Then using the parametrization approach of Dinkelbach and the known exact SOCP/SDP relaxation of the extended trust region subproblem, we find its optimal solution. Finally, some preliminary numerical results are given. [ABSTRACT FROM AUTHOR]

The emission function associated with the economic-emission dispatch prob- lem contains exponential functions that model the emission pollutants. This paper presents a strategy of solving the economic-emission dispatch problem whereby the ex- ponential function is approximated by a rational function that permits reduction to a standard polynomial optimization problem. This is reformulated as a hierarchy of semidefinite relaxation problems using the moment theory and the resulting SDP prob- lem is solved. Different degrees of rational functional approximation were considered. The approach was tested on the IEEE 30-bus test systems to investigate its effectiveness. Solutions obtained were compared with those from some of the well known evolutionary methods. Results showed that SDP has inherently good convergence property and a lower but comparable diversity property. [ABSTRACT FROM AUTHOR]

We consider in this paper a class of semicontinuous quadratic programming problems, which arises in many real-world applications such as production planning, portfolio selection, and subset selection in regression. We build upon the idea of the quadratic convex reformulation approach, i.e., adding to the original objective function an additional convex term that is zero at all points of the feasible region. Exploiting the structure of semicontinuous variables, we derive the most general set of quadratic functions that can be added. We also incorporate the state-of-the-art perspective reformulation into our new framework. Within this framework, the set of optimal reformulations with the tightest continuous relaxation can be found by solving a semidefinite programming problem. We also explore the relationship among different reformulations within our framework and simplify the search for optimal ones in certain cases with the help of second-order cone programming. Among the proposed set of optimal reformulations, we can choose one with or without the perspective component. If the perspective component is present, the new reformulation can be solved by the perspective cut algorithm in the literature. If the perspective component is not present, the new reformulation is a standard mixed-integer quadratic programming (MIQP) problem and can be plugged into and solved by any MIQP solvers. Our preliminary numerical tests in both portfolio selection and subset selection problems have demonstrated the effectiveness of our new reformulations, and the comparison results indicate that the performance of the new reformulation without the perspective component, when solved in general MIQP solvers, is competitive to the perspective cut approach. [ABSTRACT FROM AUTHOR]

This paper studies a bilevel polynomial program involving box data uncertainties in both its linear constraint set and its lower-level optimization problem. We show that the robust global optimal value of the uncertain bilevel polynomial program is the limit of a sequence of values of Lasserre-type hierarchy of semidefinite linear programming relaxations. This is done by first transforming the uncertain bilevel polynomial program into a single-level non-convex polynomial program using a dual characterization of the solution of the lower-level program and then employing the powerful Putinar's Positivstellensatz of semi-algebraic geometry. We provide a numerical example to show how the robust global optimal value of the uncertain bilevel polynomial program can be calculated by solving a semidefinite programming problem using the MATLAB toolbox YALMIP. [ABSTRACT FROM AUTHOR]

This paper concentrates on a robust transmit optimization problem for the multiuser multi-input single-output (MISO) downlink scenario and under inaccurate channel state information (CSI). This robust problem deals with a general-rank transmit covariance design and follows a safe rate-constrained formulation under spherically bounded CSI uncertainties. Curiously, simulation results in previous works suggested that the robust problem admits rank-one optimal transmit covariances in most cases. Such a numerical finding is appealing because transmission with rank-one covariances can be easily realized by single-stream transmit beamforming. This gives rise to a fundamentally important question, namely, whether we can theoretically identify conditions under which the robust problem admits a rank-one solution. In this paper, we identify one such condition. Simply speaking, we show that the robust problem is guaranteed to admit a rank-one solution if the CSI uncertainties are not too large and the multiuser channel is not too poorly conditioned. To establish the aforementioned condition, we develop a novel duality framework, through which an intimate relationship between the robust problem and a related maximin problem is revealed. Our condition involves only a simple expression with respect to the multiuser channel and other system parameters. In particular, unlike other sufficient rank-one conditions that have appeared in the literature, ours is verifiable. The application of our analysis framework to several other CSI uncertainty models is also discussed. [ABSTRACT FROM PUBLISHER]

A symmetric tensor, which has a symmetric nonnegative decomposition, is called a completely positive tensor. In this paper, we characterize the completely positive tensor as a truncated moment sequence, and transform the problem of checking whether a tensor is completely positive to checking whether its corresponding truncated moment sequence admits a representing measure, then present a semidefinite algorithm to solve it. If a tensor is not completely positive, a certificate for it can be obtained; if it is completely positive, a nonnegative decomposition can be obtained. [ABSTRACT FROM AUTHOR]