Mark L. Stone
  • Member for 6 years, 7 months
  • Last seen this week
Good examples of "two is easy, three is hard" in computational sciences
33 votes

In one and two dimensions, all roads lead to Rome, but not in three dimensions. Specifically, given a random walk (equally likely to move in any direction) on the integers in one or two dimensions, ...

View answer
Matrix multiplication accuracy Matlab vs Python
14 votes

Here is R1, as computed in MATLAB: 1.0e+07 * -7.382605957465515 -9.599867106092937 -2.830412177259742 -0.000000000002830 -0.000000000002830 -1.230434326244253 -1.599977851015490 -0....

View answer
Imposing special structure on Positive Semi-Definite matrix
Accepted answer
7 votes

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 ...

View answer
Reformulating a convex optimization problem with $x \mapsto \max(x,0)$ in the constraint
5 votes

Because you say the losses are convex, I will presume that all $c_i \ge 0$, which means that max is used in a convex fashion. Given that, this problem can be formulated as a Linear Programming problem ...

View answer
Why am I getting this DCPError when my matrix is PSD?
Accepted answer
5 votes

Because the matrix KK is not PSD. It has minimum eigenvalue of -1. It is indefinite. Perhaps you are under the misapprehension that a symmetric matrix with all elements positive is PSD. As this ...

View answer
How to find closed form $C$ such that $CC^T = AA^T + BB^T$
5 votes

If A and B are known, then the right hand side is known, and must of necessity be symmetric positive semi-definite. Therefore, there is a solution C to the stated equation, and this is the (lower ...

View answer
Best platform for complex SDPs with n and m around 5-15K?
4 votes

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. ...

View answer
SCP (Sequential Convex Programming) vs SQP (Sequential Quadratic Programming)
Accepted answer
4 votes

In SCP (a.k.a. SCA), at each outer iteration: Objective function is replaced by a convex approximation, not necessarily quadratic. Nonlinear inequality constraints are replaced by convex ...

View answer
How to optimize nuclear norm subject to positive semidefinite constraints?
Accepted answer
4 votes

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 ...

View answer
QR decomposition
4 votes

Look at section 5 of http://web.stanford.edu/group/SOL/papers/ggms74.pdf to see how to update QR decomposition when a row is added to the matrix you wish to factorize. You may find it not so easy to ...

View answer
Changing min function to max function for optimization
4 votes

If you want to maximize f(X) subject to specified constraints (if any), then minimize -f(X) subject to those same constraints. Your optimal objective function will be the negative of -f(X_optimal), ...

View answer
Frobenius norm of a binary matrix
Accepted answer
3 votes

The Frobenius norm of a binary matrix is the square root of the number of non-zero elements. Let the point (0.,...0) be the origin, and let's say the vec'd binary matrix elements are the coordinates ...

View answer
Solving a linear program with an active set method
Accepted answer
3 votes

Yes, it would be called the Simplex algorithm. An active set method for solving Quadratic Programming problems is often called a "Simplex algorithm" (which is as opposed to an Interior Point method).

View answer
Is there any other sparse matrix data in matlab built-in file?
Accepted answer
3 votes

There are many sparse matrices in Matrix Market A visual repository of test data for use in comparative studies of algorithms for numerical linear algebra, featuring nearly 500 sparse matrices ...

View answer
Term for an small optimisation algorithm used as a subroutine
3 votes

Lower level optimization problems being solved within a top or higher level algorithm are called subproblems. So the algorithm or routine to solve subproblems could be called a "subproblem solver". ...

View answer
How to efficiently solve a QCQP with "dynamic" constraints in Python?
Accepted answer
3 votes

In order for a QCQP to be convex, the quadratic terms needs be be convex. Linear terms are always convex. With regard to your specific problem, the objective function is convex because it is linear. ...

View answer
Optimization with matrix determinant as constraint
3 votes

The constraint $\det(A) > 0$ is very unstable and absolutely horrible. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can ...

View answer
Non-linear optimization package that allows an user-defined Hessian
3 votes

You are looking for a Newton's method, as opposed to Quasi-Newton used by SNOPT. You can consider using KNITRO, which can handle any optimization problem type that SNOPT can, but has a greater number ...

View answer
Checking singularity of a matrix
2 votes

@Federico Poloni 's fine answer states the impossibility of getting an exact yes/no answer using IEEE arithmetic. However, using interval arithmetic with outward rounding, it is possible to get a &...

View answer
what is non-asymptotic convergence?
2 votes

The authors provide bounds on various things as an explicit function of the iterate $n$, for a generic, but finite, $n$. These bounds apply for finite $n$, not only in the limit as $n \rightarrow \...

View answer
log(det(X)) in Semidefinite Programming
Accepted answer
2 votes

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 ...

View answer
Two variables integration matlab
Accepted answer
2 votes

The error message is because you forgot the . before * before exp in psi2. Once you fix that, MATLAB will be none too happy about the singularity you get dividing by abs(r1-r2) in I and J. If (1./abs(...

View answer
FMINCON Step Size Tolerance
Accepted answer
2 votes

FMINCON is not able to find a feasible point starting at what I think is the default value provided by YALMIP of all variables being zero vectors. Local solvers, such as FMINCON, may have trouble ...

View answer
Making difference of log constraints convex
2 votes

The constraints are not convex. Consider the example below in which x1 and x2 are each vectors of 3 elements which satisfy the inequality in question, as shown. 0.5(x1 + x2) does not satisfy the ...

View answer
Is there a high quality nonlinear programming solver for Python?
2 votes

KNITRO has Python and MATLAB interfaces, among others. Think of it as an FMINCON replacement, but much better performing, and more expensive. https://www.artelys.com/en/optimization-tools/knitro#doc-...

View answer
Computing Eigenvectors in MATLAB
Accepted answer
2 votes

Eigenvectors are only unique to within a scale factor (can be + or - scale factor). If $x$ satisfies $Ax=\lambda x$, and hence is an eigenvector of $A$ corresponding to eigenvalue $\lambda$, then any ...

View answer
Enforcing bounds and equality constraints for convex optimization
2 votes

This is just a standard convex Quadratic Programming (QP) problem, which quadprog, or any number of other QP solvers, can solve. There are a variety of algorithms for solving QPs, and I think you ...

View answer
Solving a singular system of linear equations with smallest solution?
2 votes

If you are willing to minimize the 2-norm of the solution rather than minimizing the number of non-zeros, you can use the pseudo-inverse. To solve A*x = b in MATLAB, that would be pinv(A)*b. In your ...

View answer
Fast algorithms for computing only the generalized singular values (but not the vectors)
Accepted answer
2 votes

Per http://www.nag.com/numeric/fl/manual/pdf/F08/f08msf.pdf , regarding the LAPACK routine in the NAG Library for complex singular values/singular vectors. (Not generalized, but I think the idea is ...

View answer
Exact analytical matrix inversion of sparse 100x100 matrices in C++
Accepted answer
2 votes

This may be more of a comment than an answer, but I can't comment. Yes on arbitrary precision. No on symbolic inverse, because at some point, you have to numerically evaluate it, and it is likely to ...

View answer