8 votes
Accepted

Convex Optimization problem with sum of absolute value constraints

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} |...
user avatar
8 votes
Accepted

Can this simple quadratic optimization problem be turned into a simple eigenvalue problem?

At least for the second question the answer is yes. See for example Mattheij, Robert MM, and Gustaf Söderlind. "On inhomogeneous eigenvalue problems. I." Linear Algebra and its Applications ...
user avatar
  • 188
6 votes
Accepted

How to determine whether two cylinders intersect or not?

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 ...
user avatar
  • 331
5 votes
Accepted

Solve $AX = B$ where $X^T X = C$

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, ...
user avatar
5 votes
Accepted

0,1 binary polynomial programming

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 ...
user avatar
5 votes
Accepted

Converting convex quadratic constraint to linear matrix inequality (LMI)

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. ...
user avatar
5 votes

Minimize quadratic form with equality constraints

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, ...
user avatar
5 votes
Accepted

Quadratic programs with rank deficient positive semidefinite matrices

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 ...
user avatar
5 votes
Accepted

Checking positive definiteness on a hyperplane

Instead of e = eig(N'*A*N);, you can use [R,p]=chol(N'*A*N);, and test for p==0. Matlab ...
user avatar
  • 551
4 votes
Accepted

Minimize quadratic form with equality constraints

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}...
user avatar
  • 428
4 votes

Can Variance be replaced by absolute value in this optimization problem

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 ...
user avatar
  • 261
4 votes

Solving absolute value quadratic optimization problem

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 ...
user avatar
4 votes
Accepted

Algorithm for solving system of quadratic equations and linear equations

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. ...
user avatar
  • 56
4 votes

Discrete-time Algebraic Riccati Equation (DARE) solver in C++

If you want a ten-line solution that is decently fast and stable, you can implement yourself the structured doubling algorithm: set up the coupled iteration $A_0 = A, G_0 = G = BR^{-1}B^T, H_0 = Q$ ...
user avatar
3 votes

How to determine whether two cylinders intersect or not?

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 ...
user avatar
3 votes

Modeling a quadratic constraint with a linear expression

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) $$...
user avatar
3 votes

Solver for a MIQP with an indefinite coefficient matrix

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 ...
user avatar
3 votes

A separable nonnegative quadratic program

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 ...
user avatar
3 votes
Accepted

Sparse quadratic programming solver

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/...
user avatar
3 votes

Factoring a quadratic function

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 ...
user avatar
3 votes
Accepted

Approximating solutions to quadratic recurrence boundary value problem

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 ...
user avatar
  • 11.4k
3 votes
Accepted

Reformulate a strictly convex QP problem containing absolute value term

$$\begin{align} \text{Minimize}\quad&\frac{1}{2} x^T Q x + a^T x + c^T|x| \\ \text{subject to}\quad&Gx \leq b \end{align}$$ where $Q$ is positive definite matrix, $c^T \gt 0$ (element-wise) ...
user avatar
  • 151
3 votes
Accepted

What is the fastest way to solve Ax=b (subject to constraints and an absolute term)

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 \...
user avatar
3 votes

Complementary quadratic knapsack problem

Applying the transformation you suggested, we get: $$\min_{y \in\{0,1\}^n} (\mathbf{1}-y)^TP(\mathbf{1}-y)$$ $$\mathrm{s.t.}\;\;w^T(\mathbf{1}-y)\geq c\, ,$$ where $n$ is the dimension where $x$ ...
user avatar
  • 131
3 votes
Accepted

Which optimization method can be used to do the following?

Despite my comment, I think you can find $\tilde{D}$ that contains the noise term as well. You have this equation: $$-M^{T} \tilde{D} M \phi(t) = -M^{T} D M \phi(t) + W(t)$$ Where $W(t)$ is the ...
user avatar
3 votes
Accepted

Is solving QP easier than a QCQP with linear objective?

Quadratically constrained problems are fundamentally more complicated than linearly constrained problems because the feasible set is not necessarily convex (unless, of course, you are specific about ...
user avatar
3 votes

How to ensure the numeric value is always positive in Optimization Python?

Consider a variable transform. Assuming you care about the individual entries of $x$ and not something like its determinant, you can transform the $x_i$ such that the new variable $y_i$ is not bounded ...
user avatar
2 votes

Plane constraints in R3

It's a quadratic program with linear inequality constraints, which are efficiently solved by the active set method. I pose implementing this method as a homework in my optimization courses and it ...
user avatar
2 votes

rank-deficient NNLS

Others have already supplied the two most likely answers to this question, but I'll add a bit of comparison and a way to help decide between the two approaches. I'd suggest either A primal-dual ...
user avatar
2 votes
Accepted

Mixed-integer quadratic programming, state of art

For LPs, MILPs, and QPs, Gurobi and CPLEX are considered best-of-breed. They beat any open-source general-purpose solver by at least an order of magnitude. I see no reason why that would be different ...
user avatar

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