Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficiently Maximizing a Homogeneous Polynomial over Unit Sphere without Convex Relaxation
59
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This work studies the problem of maximizing a higher degree real homogeneous multivariate polynomial over the unit sphere. This problem is equivalent to finding the leading eigenvalue of the associated symmetric tensor of higher order, which is nonconvex and NP-hard. Recent advances show that semidefinite relaxation is quite effective to find a global solution. However, the solution methods involve full/partial eigenvalue decomposition during the iterates, which heavily limits its efficiency and scalability. On the other hand, for odd degree (odd order) cases, the order has to be increased to even, which potentially reduces the efficiency. To find the global solutions, instead of convexifying the problem, we equivalently reformulate the problem as a nonconvex matrix program based on an equivalence property between symmetric rank-1 tensors and matrices of any order, which is a generalization of the existing results. The program is directly solved by a vanilla alternating direction method, which only involves the computation of leading eigenvalue/singular value of certain matrices, benefiting from the special structure of the program. Although being nonconvex, under certain hypotheses, it is proved that the algorithm converges to a leading eigenvalue of the associated tensor. Numerical experiments on different classes of tensors demonstrate that the proposed approach has a significant improvement in efficiency and scalability, while it can keep the effectiveness of semidefinite relaxation as much as possible. For instance, the proposed method finds the leading eigenpair of a third-order 500 dimensional Hilbert tensor in a personal computer within 100 seconds.
rate research
Read More
A bilevel program is an optimization problem whose constraints involve another optimization problem. This paper studies bilevel polynomial programs (BPPs), i.e., all the functions are polynomials. We reformulate BPPs equivalently as semi-infinite polynomial programs (SIPPs), using Fritz John conditions and Jacobian representations. Combining the exchange technique and Lasserre type semidefinite relaxations, we propose numerical methods for solving both simple and general BPPs. For simple BPPs, we prove the convergence to global optimal solutions. Numerical experiments are presented to show the efficiency of proposed algorithms.
This paper studies convex Generalized Nash Equilibrium Problems (GNEPs) that are given by polynomials. We use rational and parametric expressions for Lagrange multipliers to formulate efficient polynomial optimization for computing Generalized Nash Equilibria (GNEs). The Moment-SOS hierarchy of semidefinite relaxations are used to solve the polynomial optimization. Under some general assumptions, we prove the method can find a GNE if there exists one, or detect nonexistence of GNEs. Numerical experiments are presented to show the efficiency of the method.
Optimized Pulse Patterns (OPPs) are gaining increasing popularity in the power electronics community over the well-studied pulse width modulation due to their inherent ability to provide the switching instances that optimize current harmonic distortions. In particular, the OPP problem minimizes current harmonic distortions under a cardinality constraint on the number of switching instances per fundamental wave period. The OPP problem is, however, non-convex involving both polynomials and trigonometric functions. In the existing literature, the OPP problem is solved using off-the-shelf solvers with local convergence guarantees. To obtain guarantees of global optimality, we employ and extend techniques from polynomial optimization literature and provide a solution with a global convergence guarantee. Specifically, we propose a polynomial approximation to the OPP problem to then utilize well-studied globally convergent convex relaxation hierarchies, namely, semi-definite programming and relative entropy relaxations. The resulting hierarchy is proven to converge to the global optimal solution. Our method exhibits a strong performance for OPP problems up to 50 switching instances per quarter wave.
Numerical tools for constraints solving are a cornerstone to control verification problems. This is evident by the plethora of research that uses tools like linear and convex programming for the design of control systems. Nevertheless, the capability of linear and convex programming is limited and is not adequate to reason about general nonlinear polynomials constraints that arise naturally in the design of nonlinear systems. This limitation calls for new solvers that are capable of utilizing the power of linear and convex programming to reason about general multivariate polynomials. In this paper, we propose PolyAR, a highly parallelizable solver for polynomial inequality constraints. PolyAR provides several key contributions. First, it uses convex relaxations of the problem to accelerate the process of finding a solution to the set of the non-convex multivariate polynomials. Second, it utilizes an iterative convex abstraction refinement process which aims to prune the search space and identify regions for which the convex relaxation fails to solve the problem. Third, it allows for a highly parallelizable usage of off-the-shelf solvers to analyze the regions in which the convex relaxation failed to provide solutions. We compared the scalability of PolyAR against Z3 8.9 and Yices 2.6 on control designing problems. Finally, we demonstrate the performance of PolyAR on designing switching signals for continuous-time linear switching systems.
We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x in mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in diverse contexts ranging from tensor and operator norms to graph expansion to quantum information theory. The homogeneous degree $2$ case is efficiently solvable as it corresponds to computing the spectral norm of an associated matrix, but the higher degree case is NP-hard. We give approximation algorithms for this problem that offer a trade-off between the approximation ratio and running time: in $n^{O(q)}$ time, we get an approximation within factor $O_d((n/q)^{d/2-1})$ for arbitrary polynomials, $O_d((n/q)^{d/4-1/2})$ for polynomials with non-negative coefficients, and $O_d(sqrt{m/q})$ for sparse polynomials with $m$ monomials. The approximation guarantees are with respect to the optimum of the level-$q$ sum-of-squares (SoS) SDP relaxation of the problem. Known polynomial time algorithms for this problem rely on decoupling lemmas. Such tools are not capable of offering a trade-off like our results as they blow up the number of variables by a factor equal to the degree. We develop new decoupling tools that are more efficient in the number of variables at the expense of less structure in the output polynomials. This enables us to harness the benefits of higher level SoS relaxations. We complement our algorithmic results with some polynomially large integrality gaps, albeit for a slightly weaker (but still very natural) relaxation. Toward this, we give a method to lift a level-$4$ solution matrix $M$ to a higher level solution, under a mild technical condition on $M$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
