# Tag Info

8

From my own limited experience in the power industry, no one is solving SDPs at that sort of scale. I have some limited knowledge of what the New England ISO is doing, and I think they are more interested in incorporating stochasticity into their existing MILP models. From friends who have worked on power systems at governmental research labs in the USA, ...

7

Semidefinite programming and second order cone programming have not been adopted as rapidly in practice as many of us hoped. I've been involved in this for the last 20 years, and it has been very disappointing to see slow progress. Let me point out some of the challenges: Although we have polynomial time algorithms for SDP and SOCP, the widely used primal-...

7

The whole point is that you do NOT include the constraint $U = uu^T$ . That constraint is non-convex. Instead you include the constraint that $Z_j$ is (positive) semi-definite. This constraint is a convex relaxation of $U = uu^T$, obtained by Schur complement. I.e., the relaxed constraint, which is convex, is used instead of the original non-convex ...

6

You can obtain a semidefinite relaxation of your problem that will provide a bound on the optimal value of your problem, but it will not be an exact semidefinite formulation of your problem. Start with the constraints $aP_{i}a^{T} \geq z_{i}$, $i=1, 2, \ldots, n$ You can use the cyclic permutation property of the trace of a product to write this as $\... 6 In double precision, a system of 20,000 equations in 20,000 variables will require 3.2 gigabytes of RAM to store the matrix. This isn't "big" by contemporary standards, and is reasonably easy to solve in practice. To make this run fast, you'll want to use of a well tuned linear algebra library. The standard for this kind of work would be to use LAPACK ... 6 There's no need to use the Schur complement here because$A$and$S$are already symmetric. The conventional formulation of this problem as an SDP is $$\min t \quad\text{ subject to}\\ A-S+tI \succeq 0 \\ A-S - tI \preceq 0$$ results in an SDP of the form (I'm specific here because there are so many different "standard forms" for SDP) $$\min c^{T}x\\ ... 5 Most of the work I'm aware of at labs for power flow problems is on stochastic optimization also, focusing mostly on MILPs. In chemical engineering, they are interested in MINLPs, and the classic example is a mixing problem (specifically, the prototypical Haverly pooling problem), so bilinear terms come up a lot. Trilinear terms occasionally pop up, ... 5 The constraint \mbox{rank}(X) <= d is in general a non-convex constraint. Sorry. A commonly used approach is to minimize the Schatten 1-norm of X (the sum of singular values of X) as a surrogate for minimizing the rank. This works similarly to minimizing the 1-norm of a vector x as a way of minimizing the number of nonzero entries in x. 4 It's not too difficult to formulate a problem like this in CVX, but unfortunately your instances are too large to be solved in practice by the primal-dual interior point solvers used by CVX. The problem here is in the minimax objective function, which CVX will convert into \min t subject to | P_{d}(\theta,\phi)-\mbox{stuff} | \leq t for each \... 4 First, a standard semidefinite program (in primal form) would be$$\underset{X}{\text{min }} \langle W, X \rangle, \\ X\succeq 0,~\mathbf{A}(X) = b$$where \mathbf{A}(X) = b denotes the primal equalities (the model you have written is either trivially solved by X=0 or is unbounded) In reality one would never work with such a limited form, so you can at ... 4 This is easy to formulate in CVX, under MATLAB. A CVXPY solution, under Python, is similar. CVX code: cvx_begin sdp variable X(n,n) hermitian semidefinite minimize(norm_nuc(X-A)) X <= B cvx_end or alternatively cvx_begin variable X(n,n) hermitian semidefinite minimize(norm_nuc(X-A)) B - X == semidefinite(n) cvx_end Edit 2: CVX is very fussy about ... 3 The determinant is the product of all eigenvalues \lambda_i(A), so its logarithm is the sum of the logarithms of the eigenvalues. As a consequence, you can write the objective function as follows:$$ \min_A \quad-\sum_i \log\lambda_i(A). $$Now, assume you had an eigenvalue that tried to go to zero, then its logarithm would go to negative infinity and so ... 3 This problem can be formulated as a standard positive semidefinite QP with bounded variables. First, deal with the absolute value terms in the objective by letting x=u-v, where u\geq 0 and v \geq 0. Then write the problem as \min \;\; (A(u-v)-b)^{T}(A(u-v)-b)+c^{T}u+c^{T}v subject to B(u-v)=d (equality constraints) Upper ... 3 Quoting Michael Grant [MG'14]: The nuclear norm inequality \|X\|_*\leq y is satisfied if and only if there exist symmetric matrices W_1, W_2 satisfying$$\begin{bmatrix} W_1 & X \\ X^T & W_2 \end{bmatrix} \succeq 0, ~ \mathop{\textrm{Tr}}W_1 + \mathop{\textrm{Tr}}W_2 \leq 2 y$$Here, \succeq 0 should be interpreted to mean that the 2\times ... 3 Apply a Schur complement on the constraint \begin{pmatrix} M & \eta\\\eta^T & 1\end{pmatrix} \succeq 0 3 No, your understanding is not correct. By introducing a slack s\in R^{m}_+ you can write the constraints in the form \operatorname{tr}(B_iX) + s_i = b_i. You now have a standard semidefinite program, in primal form, over the product of a semidefinite cone of size n, and an LP cone of size m. The linear system will be a linear system of size m \times ... 3 You can try using SCS, either the direct or indirect solver. SCS uses first order methods, and hence may be able to solve larger problems than second order solvers such as SDPT3, SeDuMi, MOSEK, etc. On the downside, given that it is a first order solver, it can be very slow - but very slow may be better than not at all. Paper: http://web.stanford.edu/~... 3 According to the paper Nicholas J. Higham, MR 943997 Computing a nearest symmetric positive semidefinite matrix, Linear Algebra Appl. 103 (1988), 103--118, one of the solution is in the following form,$$A_{opt} = S + |\lambda| I$$where I is the identity matrix, \lambda is the smallest negative eigenvalue of S 2 YALMIP derives the model you do (except adding a dummy variable leading to ||X||_F\leq z, z\leq 1 and adding some redundant constraints). However, YALMIP works in the dual space, i.e., X is parameterized by variables, so to understand the model, it only makes sense to it interpret it as such. For instance, if you look at the data in representing the ... 2 Since A is symmetric, you can diagonalize it with A=XDX^t, and S=XWX^t, to get the equivalent formulation$$ \text{minimize}\quad\|D-W\|_2, \qquad \text{s.to }W\geq0. $$So for any positive eigenvalue d_i of A, you can use W_{ii}=d_i to subtract it off. I suspect that the answer might be the absolute value |\lambda_-| of the largest negative ... 2 You can potentially save some effort in the eigenvalue decomposition by finding only those eigenvalues (and the corresponding eigenvectors) that are greater than 0. If most eigenvalues are non-negative, then you can find the negative eigenvalues and subtract off that part of the eigenvalue decomposition to compute the projection. The LAPACK routine ... 2 A common definition of "positive semidefinite" is: A real symmetric n by n matrix S is positive semidefinite if and only if z^{T}Sz \geq 0 for all z \in R^{n}. Another equivalent definition is that a real symmetric n by n matrix S is positive semidefinite if and only if all of its eigenvalues are non-negative. I won't go through the ... 2 Inequality constraints in an SDP can be turned into equality constraints by introducing non-negative slack variables. If your original problem is \max \Sigma_{i=1}^{n} z_{i} subject to \mbox{tr}(P_{i}X) \geq z_{i}\;\; i=1, 2, \ldots, n X \succeq 0 You can rewrite the constraints as \mbox{tr}(P_{i}X) - z_{i} \geq 0\;\; i=1, 2, \ldots, n.... 2 It's possible I'm misunderstanding something (and please let me know if I am), but here's another approach: Based on your formulation, it looks like your first group of inequality constraints will always be tight. And since Q_i \succeq 0, there's no need for the w_i \geq 0 constraint. That would allow you to rewrite the problem as$$ \max_{\pmb a} \... 2 In order to do this, you'll need to convert inequalities to equality constraints by introducing slack variables and then add these slack variables to your matrix variable as an additional LP block. Let$ X=\left[ \begin{array}{ccc} W_{1} & B & 0 \\ B^{T} & W_{2} & 0 \\ 0 & 0 & \mbox{diag}(v) \\ \end{array} \right] $... 2 You simply put zeros on the required positions, i.e. parameterize$Z$using the required triangular basis. You never explicitly work with any factorization, that's just for proving that the optimization model yields the desired result at optimality. Here implemented with YALMIP interfacing Mosek % Random example (fixed A) A = randn(5);A = A'*A; % Define a ... 2 First of all, move the objective to the constraints by using the epigraph formulation max t subject to log_det(A)$\ge$t plus your other constraints. Section 6.2.3 of the Mosek Modeling Cookbook https://docs.mosek.com/modeling-cookbook/sdo.html#semidefinite-modeling shows how to formulate log_det(A)$\ge$t in terms of a combination of SDP and ... 1 You don't need SDP for an easy task like this.$X$are your points. Do a PCA on$Y Y', Y = X - \operatorname{mean}(X)$, reduce dimension to 2-dimensions (others dimensions are zeros). 3 points on the canonical plane, axis of ellipse are 1st and 2nd Principal Components. 1 That you get really big numbers is no accident. Consider $$C = \left(\begin{array}{ccc} 2 & 1 & \epsilon\\ 1 & 2 & 1\\ \epsilon & 1 & 2 \end{array}\right)$$ and $$X = \left(\begin{array}{ccc} -1 & -1 & 1\\ -1 & 1 & 1\\ 1 & 1 & 1\\ \end{array}\right).$$ Note that$X$has eigenvalues$\{1, \pm 2\}$and$C$... 1 Provided the matrix is symmetric and positive-definite, the conjugate gradient method is the provably fastest iterative method, requiring$O(\sqrt\kappa)\$ iterations to converge. Depending on how badly-conditioned your matrix is, that may be more favorable than using a direct method like the Cholesky decomposition to solve your system. It is likely that you'...

Only top voted, non community-wiki answers of a minimum length are eligible