The tag has no usage guidance.

68 questions
Filter by
Sorted by
Tagged with
6k views

### Solving a least squares problem with linear constraints in Python

I need to 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} I think it is a ...
4k views

### Calculating Lagrange coefficients for SVM in Python

I'm trying to write a full SVM implementation in Python and I have a few issues computing the Lagrange coefficients. First let me rephrase what I understand from the algorithm to make sure I'm on the ...
274 views

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

I'm interested in a type of problem on this form $$\min_{x} x^{T}Ax+x^{T}b \quad \text{s.t} \quad x^{T}x=1$$ where $A$ is positive definite. As you can see, if it weren't for the $x^{T}b$ term in the ...
1k views

### Algorithm for solving system of quadratic equations and linear equations

Let $x \in R^N$. From a Spectral Chebyshev collocation method, I have a system of quadratic and linear equations. Denote them, $$x^T Q_i x + L_i^T x = 0$$ and $$A x = 0$$ Furthermore, I know ...
3k views

### How to determine whether two cylinders intersect or not?

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
4k views

154 views

### Multi-matrix orthogonal basis problem

Suppose we are given a set of symmetric, positive definite matrices $A_1,A_2,\ldots,A_k\in\mathbb{R}^{n\times n}$. Is there any numerical method or reduction to a known problem (e.g. eigenvalue ...
2k views

### Why does MATLAB's quadprog outperform MOSEK for my problem?

For a problem I am trying to solve it appears MOSEK's Quadratic Program solver is 100 times slower than MATLAB's Interior Point solver. Has anyone encountered this behavior in the past, or maybe ...
972 views

### Quadratic programs with rank deficient positive semidefinite matrices

Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...
1k views

### Converting convex quadratic constraint to linear matrix inequality (LMI)

I have the quadratic programming problem in $x$ $$\text{Minimize}\;\; x^T\Sigma x$$ $$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ $$\hspace{25mm}\boldsymbol{1}^Tx=1$$ ...
1k views

### Solver suggestion for many small quadratic problem in C++

I have a C++ program/model that in some parts already use IPOPT (with ADOL-C and ColPack) to solve some pretty large non linear problems. Now in an other part of the program I need to solve a large ...
213 views

### Which optimization method can be used to do the following?

I've the following system of equations for studying information flow in the below graph, $$\frac{d \phi}{dt} = -M^TDM\phi + \text{noise effects} \hspace{1cm} (1)$$ Here, M is the incidence ...
171 views

### Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
163 views

### Eigenvalue-style optimization with quadratic constraints

Suppose $A\in\mathbb{R}^{n\times n}$ is symmetric and positive definite and that we have several symmetric matrices $B_i\in\mathbb{R}^{n\times n}$ that are low-rank and indefinite. I need an ...
657 views

### Solver for a MIQP with an indefinite coefficient matrix

Do CPLEX or Gurobi handle MIQPs with indefinite coefficient matrices? The problem I am dealing with has quadratic terms in which one variable is binary and the other variable is continuous. The ...
1k views

### Minimizing a negative definite quadratic function with specified bounds

I have the following quadratic program $$\begin{array}{ll} \text{minimize} & f(x) = \frac{1}{2} x^T D x + c^T x\\ \text{subject to} & x_{\text{lower}} < x < x_{\text{upper}}\end{array}$$...
114 views

### Approximating solutions to quadratic recurrence boundary value problem

Cross-posted from Math Stackexchange: https://math.stackexchange.com/questions/2421964/approximating-solutions-to-quadratic-recurrence I have a branching process problem that has been reduced to ...
455 views

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = ||S w||^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
335 views

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

I am trying to solve/optimize $Ax=b$ in the least squares sense subject to box constraints; a few (less than 5) equality/inequality constraints; and an absolute function penalty (or some other ...
143 views

### A separable nonnegative quadratic program

I have spent quite some time trying to solve the following quadratic program: $$\min \sum_{i=1}^n (\frac{1}{2}x_i^TQx_i+c_i^Tx_i), \quad \mathrm{s.t. } \quad x_i\ge 0 \quad \forall i,$$ where $n$ is ...
1k views

For a hobby project I need to solve a series of quadratic programming problems each with about 500 variables about 1000 constraints, each of the form $x_i-x_j\le c_{ij}$ the objective function is the ...
73 views

### Improve optimization speed for a set of similar problems: Quadratic programming with a warm start

I am repeatedly solving quadratic program, $x^T Q x$ with time dependent linear constraints $Ax=b_t$. Dimension of $x$ is around 10000 and there are around 50 constraints. I want to solve the ...
76 views

### Solving multiple least-square problems with the same constraints

The following least-square problem can be solved efficiently (e.g. using matlab's lsqlin): $$\vec{x}^*=\arg\min_\vec{x} ||C\vec{x}-\vec{t}||^2\,\ s.t.\ Ax \le \vec{b}$$ where the parameters of the ...
156 views

### Automatically generate constraints for trajectory optimization

This is a follow up to my previous post here I'm interested in performing trajectory optimization from the problem mentioned in abov link. I want to supply the following as dynamical constraints to ...
1k views

### Modeling a quadratic constraint with a linear expression

In a problem I am trying to model with a MIP program, the following scenario occurs: I am given binary variables $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ which can really be regarded as $n$-vectors. ...
86 views

### Checking positive definiteness on a hyperplane

Is there a faster way to check whether $A\in\mathbb{R}^{n\times n}$ is positive definite on $b^{\bot}:=\{x\in \mathbb{R}^{n}: x\cdot b=0\}$ than ...
145 views

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

Is there a natural way to find the solution to $$AX = B, X^TX = C \enspace \text{?}$$ $X$ is a matrix and has a small number of rows, and $A$ is sparse. An approximate solution would be fine.
471 views

24 views

### Barrier algorithm Gurobi and interior-point quadprog; what kind of matrices can it handle the best (sparse or dense, large or small problems)?

I am trying to solve a QP problem. Does anybody know the differences between the interior-point-convex algorithm of quadprog and the barrier method of Gurobi in terms which kind of matrices can the ...
67 views

500 views

### Mixed-integer quadratic programming, state of art [closed]

I used Gurobi with a MIQP with 26 binary variables and 26*4 interaction term without any other constraint. The speed is very slow already.... I want to ask what is the state of art of MIQP solvers. ...