Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Equivalence of SDP Feasibility and a Convex Hull Relaxation for System of Quadratic Equations
77
0
0.0
(
0
)
Added by
Bahman Kalantari
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Bahman Kalantari
Ask ChatGPT about the research
No Arabic abstract
We show {it semidefinite programming} (SDP) feasibility problem is equivalent to solving a {it convex hull relaxation} (CHR) for a finite system of quadratic equations. On the one hand, this offers a simple description of SDP. On the other hand, this equivalence makes it possible to describe a version of the {it Triangle Algorithm} for SDP feasibility based on solving CHR. Specifically, the Triangle Algorithm either computes an approximation to the least-norm feasible solution of SDP, or using its {it distance duality}, provides a separation when no solution within a prescribed norm exists. The worst-case complexity of each iteration is computing the largest eigenvalue of a symmetric matrix arising in that iteration. Alternate complexity bounds on the total number of iterations can be derived. The Triangle Algorithm thus provides an alternative to the existing interior-point algorithms for SDP feasibility and SDP optimization. In particular, based on a preliminary computational result, we can efficiently solve SDP relaxation of {it binary quadratic} feasibility via the Triangle Algorithm. This finds application in solving SDP relaxation of MAX-CUT. We also show in the case of testing the feasibility of a system of convex quadratic inequalities, the problem is reducible to a corresponding CHR, where the worst-case complexity of each iteration via the Triangle Algorithm is solving a {it trust region subproblem}. Gaining from these results, we discuss potential extension of CHR and the Triangle Algorithm to solving general system of polynomial equations.
rate research
Read More
Given a subset $mathbf{S}={A_1, dots, A_m}$ of $mathbb{S}^n$, the set of $n times n$ real symmetric matrices, we define its {it spectrahull} as the set $SH(mathbf{S}) = {p(X) equiv (Tr(A_1 X), dots, Tr(A_m X))^T : X in mathbf{Delta}_n}$, where ${bf Delta}_n$ is the {it spectraplex}, ${ X in mathbb{S}^n : Tr(X)=1, X succeq 0 }$. We let {it spectrahull membership} (SHM) to be the problem of testing if a given $b in mathbb{R}^m$ lies in $SH(mathbf{S})$. On the one hand when $A_i$s are diagonal matrices, SHM reduces to the {it convex hull membership} (CHM), a fundamental problem in LP. On the other hand, a bounded SDP feasibility is reducible to SHM. By building on the {it Triangle Algorithm} (TA) cite{kalchar,kalsep}, developed for CHM and its generalization, we design a TA for SHM, where given $varepsilon$, in $O(1/varepsilon^2)$ iterations it either computes a hyperplane separating $b$ from $SH(mathbf{S})$, or $X_varepsilon in mathbf{Delta}_n$ such that $Vert p(X_varepsilon) - b Vert leq varepsilon R$, $R$ maximum error over $mathbf{Delta}_n$. Under certain conditions iteration complexity improves to $O(1/varepsilon)$ or even $O(ln 1/varepsilon)$. The worst-case complexity of each iteration is $O(mn^2)$, plus testing the existence of a pivot, shown to be equivalent to estimating the least eigenvalue of a symmetric matrix. This together with a semidefinite version of Caratheodory theorem allow implementing TA as if solving a CHM, resorting to the {it power method} only as needed, thereby improving the complexity of iterations. The proposed Triangle Algorithm for SHM is simple, practical and applicable to general SDP feasibility and optimization. Also, it extends to a spectral analogue of SVM for separation of two spectrahulls.
We revisit the so-called sampling and discarding approach used to quantify the probability of violation of a scenario solution when some of the original samples are allowed to be discarded. We propose a scheme that consists of a cascade of optimization problems, where at each step we remove a superset of the active constraints. By relying on results from compression learning theory, we produce a tighter bound for the probability of violation of the obtained solution than existing state-of-the-art one. Besides, we show that the proposed bound is tight by exhibiting a class of optimization problems that achieves the given upper bound. The improvement of the proposed methodology with respect to a scenario discarding scheme based on a greedy removal strategy is shown by means of an analytic example and a resource sharing linear program.
Mean field games with a major player were introduced in (Huang, 2010) within a linear-quadratic (LQ) modeling framework. Due to the rich structure of major-minor player models, the past ten years have seen significant research efforts for different solution notions and analytical techniques. For LQ models, we address the relation between three solution frameworks: the Nash certainty equivalence (NCE) approach in (Huang, 2010), master equations, and asymptotic solvability, which have been developed starting with different ideas. We establish their equivalence relationships.
Distributed operation of integrated electricity and gas systems (IEGS) receives much attention since it respects data security and privacy between different agencies. This paper proposes an extended convex hull (ECH) based method to address the distributed optimal energy flow (OEF) problem in the IEGS. First, a multi-block IEGS model is obtained by dividing it into N blocks according to physical and regional differences. This multi-block model is then convexified by replacing the nonconvex gas transmission equation with its ECH-based constraints. The Jacobi-Proximal alternating direction method of multipliers (J-ADMM) algorithm is adopted to solve the convexified model and minimize its operation cost. Finally, the feasibility of the optimal solution for the convexified problem is checked, and a sufficient condition is developed. The optimal solution for the original nonconvex problem is recovered from that for the convexified problem if the sufficient condition is satisfied. Test results reveal that this method is tractable and effective in obtaining the feasible optimal solution for radial gas networks.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
