Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Triangle Algorithm for Semidefinite Version of Convex Hull Membership Problem
83
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
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.
rate research
Read More
The it Convex Hull Membership(CHM) problem is: Given a point $p$ and a subset $S$ of $n$ points in $mathbb{R}^m$, is $p in conv(S)$? CHM is not only a fundamental problem in Linear Programming, Computational Geometry, Machine Learning and Statistics, it also serves as a query problem in many applications e.g. Topic Modeling, LP Feasibility, Data Reduction. The {it Triangle Algorithm} (TA) cite{kalantari2015characterization} either computes an approximate solution in the convex hull, or a separating hyperplane. The {it Spherical}-CHM is a CHM, where $p=0$ and each point in $S$ has unit norm. First, we prove the equivalence of exact and approxima
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.
We propose an algorithm for solving nonlinear convex programs defined in terms of a symmetric positive semidefinite matrix variable $X$. This algorithm rests on the factorization $X=Y Y^T$, where the number of columns of Y fixes the rank of $X$. It is thus very effective for solving programs that have a low rank solution. The factorization $X=Y Y^T$ evokes a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second order optimization method. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. The efficiency of the proposed algorithm is illustrated on two applications: the maximal cut of a graph and the sparse principal component analysis problem.
We consider the problem of the semidefinite representation of a class of non-compact basic semialgebraic sets. We introduce the conditions of pointedness and closedness at infinity of a semialgebraic set and show that under these conditions our modified hierarchies of nested theta bodies and Lasserres relaxations converge to the closure of the convex hull of $S$. Moreover, if the PP-BDR property is satisfied, our theta body and Lasserres relaxation are exact when the order is large enough; if the PP-BDR property does not hold, our hierarchies convergent uniformly to the closure of the convex hull of $S$ restricted to every fixed ball centered at the origin. We illustrate through a set of examples that the conditions of pointedness and closedness are essential to ensure the convergence. Finally, we provide some strategies to deal with cases where the conditions of pointedness and closedness are violated.
We investigate a class of constrained sparse regression problem with cardinality penalty, where the feasible set is defined by box constraint, and the loss function is convex, but not necessarily smooth. First, we put forward a smoothing fast iterative hard thresholding (SFIHT) algorithm for solving such optimization problems, which combines smoothing approximations, extrapolation techniques and iterative hard thresholding methods. The extrapolation coefficients can be chosen to satisfy $sup_k beta_k=1$ in the proposed algorithm. We discuss the convergence behavior of the algorithm with different extrapolation coefficients, and give sufficient conditions to ensure that any accumulation point of the iterates is a local minimizer of the original cardinality penalized problem. In particular, for a class of fixed extrapolation coefficients, we discuss several different update rules of the smoothing parameter and obtain the convergence rate of $O(ln k/k)$ on the loss and objective function values. Second, we consider the case in which the loss function is Lipschitz continuously differentiable, and develop a fast iterative hard thresholding (FIHT) algorithm to solve it. We prove that the iterates of FIHT converge to a local minimizer of the problem that satisfies a desirable lower bound property. Moreover, we show that the convergence rate of loss and objective function values are $o(k^{-2})$. Finally, some numerical examples are presented to illustrate the theoretical results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
