11

I wrote a full answer (below the line) before discovering CVXPY, which (like CVX for MATLAB) does all the hard stuff for you and has a very short example almost identical to yours here. You only need to replace the relevant line with p = program(minimize(norm2(A*x-b)),[equals(sum(x),1),geq(x,0)]) My old answer, doing it the harder way with CVXOPT: ...


6

A typical way to deal with this is to replace products $xy$ where $x$ is binary and $y$ continuous with a new variable $w$, and then add a constraint to ensure $w=0$ when $x=0$ and $w=y$ when $x=1$. This can be accomplished with $-M(1-x) \leq w-y \leq M(1-x)$, $-Mx \leq w \leq Mx$ where $M$ is a sufficiently large (but as small as possible) constant to ...


6

For problems of this form, you should solve the dual problem using MOSEK. In some cases this can provide several orders of magnitudes of speedup. MOSEK is tuned for the more common case \begin{align} \text{min }& 0.5 x^T Q x + c^T x \\ \text{s.t. }& A x = b \\ & x >= 0 \end{align} where there are many more variables than ...


6

Unfortunately, your problem isn't a convex optimization problem because the constraint $\Sigma_{i} | a_{i}|=4$ describes a non-convex feasible region. If you could change this to $\Sigma_{i} | a_{i} | \leq 4$, you'd have a convex constraint. If the constraint were $\Sigma_{i} | a_{i} | \leq 4$, then you can introduce auxiliary variables $t_{i}$, and add ...


6

David Eberly has a good description of the solution (with pseudocode) here: http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf The short summary: like most convex-convex collision detection algorithms, you search systematically for a separating axis between the cylinders. For future reference on similar problems, the authors of Real-...


5

If the $s_{i}$ are integers, there are reformulations of integer polynomial terms that result in mixed-integer (linear) programs, at the cost of introducing additional variables and constraints. Fred Glover has a sequence of papers to that effect in the mid-to-late 1970s, and subsequent work has built upon it. For example: Fred Glover, "Improved Linear ...


5

If your problems are small, you could try a simple solver with dense data structures and use stack allocation (old Fortran codes). IPOPT uses sparse data structures and indeed, it takes a relatively long time to initialize IPOPT if your problems are small. Old Fortran codes with stack allocation are surprisingly fast if you have small problems. If the ...


5

At first, I thought that Nicolas' answer was right, and then I looked at the question again. For a quadratic program (QP), $A$ is symmetric by convention, and it's possible to re-express it as such, so without loss of generality, suppose that $A$ is symmetric. If $A$ is also positive semidefinite, then a local optimum is a global optimum, and the KKT ...


5

One option here is to use the pseudoinverse of $\Sigma$ rather than the actual inverse. Appendix A of Boyd and Vandenberghe discusses a version of the Schur complement that includes this case. Another alternative is to find a factorization of $\Sigma$ as $\Sigma=M^{T}M$ (e.g. by eigenvalue decomposition), and then use the Schur theorem on $\left[ \...


5

Your problem is related to low rank approximation problems, about which there has been a lot of research in recent years. Are you looking for a solution in which $X$ has a specified number of rows, or are you trying to find the smallest number of rows possible? In most cases, users are interested in finding $X$ such that $X^{T}X$ is close to $C$ (in e.g....


5

Instead of e = eig(N'*A*N);, you can use [R,p]=chol(N'*A*N);, and test for p==0. Matlab function chol returns the cholesky factor R and a p which is zero if N'*A*N is positive definite. p is a positive integer if the matrix is not positive definite. Usually chol is much faster than eig. For example, with dimension n=2000, I found that chol(N'*A*N) is ...


4

I have used cvxopt to implement an SVM before, however in matlab not python. It will definitely serve your purpose, whether its efficient enough will depend on what you are using it for. The most efficient SVMs do not use a QP solver package, they take advantage of some optimizations unique to SVM. Many use an SMO style algorithm to solve it. LibSVM is ...


4

Instead of the problem you solved, solve \begin{alignat}{1} & \min_{x}\|Ax - b\|^{2}_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat} This problem is a differentiable, convex, nonlinear optimization problem that can be solved in CVXOPT, IPOPT, or any other convex optimization solver.


4

Writing the Lagrangian gives rise to the following optimality conditions $B x^* =0 $ and $A x^* + b +A^T\lambda^*=0 $. Rewritten in matrix-form we have \begin{align} \underbrace{\begin{bmatrix} A&B^T \\B &0 \end{bmatrix}}_{=:K}\begin{bmatrix} x \\ \lambda\end{bmatrix} =\begin{bmatrix} -b \\ 0\end{bmatrix}. \end{align} If $K$ is non singular ...


4

You do realize that there are at least two problems with your goal: This is, in general, a problem that can have $2^N$ solutions where $N$ is the number of variables. An example is if you tried to find the solution of $$ \min_{x\in {\mathbb R}^N} \sum_{1\le i\le N} -x_i^2 \\ \text{subject to} \quad -1 \le x_i \le 1. $$ For this problem, every ...


4

You can reformulate this as $x^{*}=\arg \min x^{T}Lx+ t $ subject to $t \geq P^{T}x $ $t \geq -P^{T}x $ $x \in \left\{ 0, 1 \right\}^{n}$ This is a 0-1 mixed integer quadratic programming problem (MIQP) The case where $L$ is positive definite is well handled by solvers like CPLEX.


4

Without knowing much about your question it is hard to answer more specifically. So first and foremost - no. These are not equivalent. Minimizing variangce will generally make you converge to some kind of sample mean, whereas minimizing absolute deviation would (generally) make you find some kind of sample median. A generally favourable property of sample ...


4

Quadratically constrained quadratic programming (QCQP) focuses on convex inequalities because those preserve the convexity of the problem. Quadratic equalities do not, so this problem is much harder. Any polynomial equation can be re-written as a system of quadratic equations. (For example: $x^3 = 1$ is equivalent to $\{xy = 1,\, x^2 - y = 0\}$.) So solving ...


4

To ensure this does not drown in the comments, I make it an answer. The solver used is not SeDuMi, as claimed in the question. The solver used is quadprog, and that solver (or more specifically, a severely outdated version of it), apparently had numerical issues on this particular instance. A recent version of quadprog, or any reasonably robust solver, ...


3

With $d=16$, the $Q$ matrix is just 256 by 256. Thus the individual subproblems are quite small. Your $Q$ matrices are singular, so the optimal solution to each of the subproblems is likely to be nonunique. Do you care which solutions you end up with? For example, are minimum norm solutions required? You write that "since n is very large, it is ...


3

cvxopt (for python) does QP, and can take advantage of sparsity (you can provide a custom KKT solver specific to your problem). An example of a custom solver is https://groups.google.com/forum/#!topic/cvxopt/W8kd3LHPwwA


3

For a symmetric and positive definite matrix $A$, the problem $\min Tr~X^TAX$ subject to $Tr~X^TC=b [\in R_+]$ can be solved by introducing a Lagrange multipliers and setting the gradient of the Lagrangian to zero. The result is $X=\lambda Z$, where $Z=A^{-1}C$. Inserting this into the constraints gives the multiplier $\lambda=b/Tr~C^TA^{-1}C$. As $C$ has ...


3

Suppose $$z_{i} = x_{i} \times y_{i}$$ The constraint $$ \sum_{i=1}^{n} x_{i}y_{i}\le 1 $$ can be reformulated as linear constraints: 1) $$ \sum_{i=1}^{n} z_{i}\le 1 $$ 2) $$ z_{i}\le x_{i} $$ 3) $$ z_{i}\le y_{i} $$ 4) $$ z_{i}\ge x_{i} + y_{i} -1 $$


3

Intropduce a new variable $z_i$ to represent $x_iy_i$ (logical and). Your constraint is $\sum_{i=1}^n z_i \leq 1$, and the product is modelled by $x_i + y_i -1 \leq z_i$.


3

To transform your original program into the form you specified, use the following mappings: First, $D = 2S'S$, and $D$ is positive semidefinite. $b = w$, as you pointed out $d = 0$, as Nico notes $A$ takes the following form: \begin{align} A = \left[\begin{array}{c} I \\ e^{T} \\ -e^{T}\end{array}\right] \end{align} $b_0$ takes the following form: \begin{...


3

Note that CPLEX 12.6 and later includes functionality to solve general nonconvex QPs and MIQPs. However, for the special case of the product of a binary and continuous variables, the reformulation in the previous answer is likely to run faster. But, for nonconvex QPs with products of continuous variables in the objective, this type of reformulation no ...


3

Hint: If the two cylinders are parallel, the problem is easy. Otherwise, if the perpendicular distance between the axis exceeds the sum of the radii, there is no intersection. Otherwise, there is an intersection curve between the two lateral surfaces. It can be expressed analytically: without loss of generality, the second cylinder is vertical with a base ...


3

Your conjecture can not be correct, for two purely formal reasons: In $x^T Q x$, if you multiplied this out as a sum $\sum_i \sum_j Q_{ij}x_ix_j$, every term in the sum is the product of two entries of the vector $x$. On the other hand, in your conjecture the formula (1) contains terms that are linear in the components of $x$. This can only be correct if ...


3

Newton-type methods are standard methods for solving system of nonlinear equations numerically. To make sure they can handle this, I tried solving your problem with NLsolve.jl in julia, and it seems to work just fine: using NLsolve using LineSearches using ForwardDiff function solve(d::Real, μ::Real, β::Real, T::Integer) @assert 0 < d < 1 @...


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


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