9
votes
Small quadratic programming problem - a simple Fortran code needed
John Burkardt provides parallelepiped_point_dist_3d in his geometry library. The Fortran90 version: https://people.sc.fsu.edu/~...
- 716
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 ...
- 188
8
votes
Accepted
Small quadratic programming problem - a simple Fortran code needed
Your problem is a bounded variables least squares (BVLS) problem. For small instances, an active set method can quickly solve the problem. Lawson and Hanson have Fortran code for this in their book ...
- 18.9k
6
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) ...
- 191
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 ...
- 1,848
5
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$
...
- 11.8k
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 ...
- 571
4
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 ...
4
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 ...
- 56.2k
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 ...
- 2,332
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$ ...
- 131
3
votes
How to ensure the numeric value is always positive in Optimization Python?
$
\def\bbR#1{{\mathbb R}^{#1}}
\def\a{\alpha}\def\b{\beta}\def\l{\lambda}
\def\o{{\tt1}}\def\p{\partial}
\def\LR#1{\left(#1\right)}
\def\diag#1{\operatorname{diag}\LR{#1}}
\def\Diag#1{\operatorname{...
- 644
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 \...
- 18.9k
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 ...
- 11.5k
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 ...
- 56.2k
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) $$...
- 31
2
votes
What is the fastest method for solving a quadratic programm repeatedly,( warmstarted)?
You could try any iterative algorithm, such as gradient descent or L-BFGS. To speed up solving each instance after the first, use the solution to the prior instance as the initial value for solving ...
- 477
2
votes
Disjunctive programming software
I haven't used it, but Pyomo, a seemingly well-supported modeling software includes a module for generalized disjunctive programming.
One of the many examples they provide at the above link appears as ...
- 4,021
2
votes
Solving multiple least-square problems with the same constraints
Depends on dimensions, but for small problems you can compute an explicit piecewise affine representation of the solution, i.e., a function $x = f(t)$. This field is called multiparametric programming....
- 1,848
2
votes
Approximating solutions to quadratic recurrence boundary value problem
In addition to Kirill's excellent answer, one thing I think work mentioning is Smale's $\alpha$-theory. One of the hard parts about applying Newton's method is that, if you don't make a really good ...
- 10.4k
2
votes
Accepted
Improve optimization speed for a set of similar problems: Quadratic programming with a warm start
Here's an approach for dense $Q$ and $A$ that does some relatively expensive preliminary computations that make the individual solutions very fast. I doubt that any iterative approach would be faster ...
- 18.9k
2
votes
Reuse linear mapping that provides the solution to least squares problem using LAPACK
I think the equations might not match (min x^T Q x vs min |c-Q x|_2), but I still think i understood the core question; can one ...
- 996
2
votes
Overconstraining in SQP
That can't happen. You can have more constraints than variables, but the number of active constraints can not exceed the number of variables. (That's not quite true: Some constraints might be ...
- 56.2k
2
votes
Solving a parameter estimation problem using trajectory optimization
Your cost function can also be written as
$$
K = \int_0^{t_f} \left(\phi(t) - e^{-M^\top \tilde{D}\,M\,t} \hat{\phi}(0)\right)^\top \left(\phi(t) - e^{-M^\top \tilde{D}\,M\,t} \hat{\phi}(0)\right) dt....
- 470
2
votes
Solving a parameter estimation problem using trajectory optimization
I am a bit confused as to your characterization of constraints. Equation $(1)$ is not a constraint. It is the model that generated the time series data you are trying to fit. You then try to find the ...
- 2,926
2
votes
Accepted
Numerical Simulation of a Quadratic MIP with a highly rational term
Getting an exact solution via brute force
I'll try to circle back later to formulate this as a MIP, but your problem as stated is small enough that you can just brute force the solution.
For instance, ...
- 4,021
2
votes
Accepted
Can this problem be solved using convex optimization?
This is not a convex problem. In fact, I don't think it even has a problem. Think about the special case where $x\in{\mathbb R}^1$, then your problem has the form
$$\begin{align}
\max & \quad \...
- 56.2k
1
vote
Project to nearest point on convex polytope
Assume that $y$ is not in the polyhedron (it is easy to check whether it is, and we know that the distance is zero in that case). If $y$ is outside then the closest point will be on the surface of the ...
- 2,831
1
vote
Accepted
Why am I getting this DCPError?
cvxpy's rules for disciplined convex programming are listed here.
Notably, it states that:
The DCP rules require that the problem objective have one of two forms:
Minimize(convex)
...
- 4,021
1
vote
Accepted
Minimize squared error of linear function
Your problem is still a linear least squares problem. You can write $\Psi(x)$ as
$\Psi(x)=\| Hx - g \|_{2}^{2}$
where
$H=\left[
\begin{array}{c}
I \\
M
\end{array}
\right]
$
and
$g=\left[
\...
- 18.9k
Only top scored, non community-wiki answers of a minimum length are eligible