**13**

votes

**0**answers

2k views

### Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?

**6**

votes

**0**answers

110 views

### A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...

**5**

votes

**0**answers

66 views

### Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where ...

**5**

votes

**0**answers

176 views

### A linear optimization problem on a graph

Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...

**5**

votes

**0**answers

184 views

### A polytope associated with the Hadamard Transform

In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in ...

**4**

votes

**0**answers

41 views

### How does one go from convexity to submodularity?

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?
It would be helpful is someone can share some specific ...

**4**

votes

**0**answers

153 views

### Variant of orthogonal Procrustes problem

The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...

**3**

votes

**0**answers

1k views

### 0,1 solution to system of linear integer equations.

I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...

**3**

votes

**0**answers

189 views

### Could SVD be used to optimize the partial inner-products?

Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...

**3**

votes

**0**answers

604 views

### Infinite Linear Programming

I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...

**2**

votes

**0**answers

106 views

### Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...

**2**

votes

**0**answers

72 views

### Testing if a point is inside a convex polytope formed by halfspaces in n-dimension

Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.
$$
a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0
$$
$$
a_{1,0}x^{n-1} + ...

**2**

votes

**0**answers

75 views

### Listing all Lattice Points in a Box

Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...

**2**

votes

**0**answers

58 views

### Derivation of gradient of SSE in Geodesic Regression

On page 79 (or page 5) of this this paper the gradient of the SSE of the Geodesic model is described explicitly. My question is how are these equitations derived in detail; where can I find the ...

**2**

votes

**0**answers

66 views

### Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M

this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)
Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...

**2**

votes

**0**answers

71 views

### Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings

In one paper from 1980 I found a note that there are no known algorithms for solving
homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring.
(The ...

**2**

votes

**0**answers

28 views

### In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...

**2**

votes

**0**answers

139 views

### existence of lattice point in polytope

This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...

**2**

votes

**0**answers

47 views

### Put positive polynomial in finite intersection of half-spaces

This is a cross-posting of a MSE question (which did not attract any attention there so far).
Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...

**2**

votes

**0**answers

473 views

### Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...

**2**

votes

**0**answers

245 views

### Linear complementarity problem: principal pivoting algorithm

I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book ...

**2**

votes

**0**answers

180 views

### Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as
$$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),
$$
where all $c_{ij}<0$ (so that ...

**2**

votes

**0**answers

297 views

### When is polytope compatible with network flow?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...

**2**

votes

**0**answers

267 views

### Recovering a piecewise affine function

Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible:
Computing $f(x_1,x_2)$.
Computing a subgradient to $f$ at $(x_1,x_2)$
Computing all ...

**2**

votes

**0**answers

577 views

### Is it possible to use linear programming to solve this problem?

I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group.
Could someone comment on whether this is ...

**1**

vote

**0**answers

63 views

### Finding all feasible solutions

Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, ...

**1**

vote

**0**answers

54 views

### Finding optimal linear transformation for intersection of convex polytopes

I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in ...

**1**

vote

**0**answers

41 views

### The column generation technique on a Train Unit Assignment Problem [Linear Programming]

I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...

**1**

vote

**0**answers

131 views

### Reduce a Combinatorial problem

It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...

**1**

vote

**0**answers

73 views

### integrality of a linear program — binary equality constaints

Consider the following linear program:
$\left\{
\begin{array}{l}
\underset{x}{max} \;\;c^Tx\\
[I, \;B]x = \mathbf{1}\\
x\geq 0
\end{array}
\right.$
where $c$ is a vector ...

**1**

vote

**0**answers

64 views

### Are there any known bounds on the value of solutions of linear integer programming?

Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints?
...

**1**

vote

**0**answers

170 views

### Complexity of Nested Linear Optimization

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
...

**1**

vote

**0**answers

120 views

### Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method

I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...

**1**

vote

**0**answers

188 views

### Equal maximum and minimum in a large-scale linear programming

For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...

**1**

vote

**0**answers

106 views

### Matrix Minimax problem

I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The ...

**1**

vote

**0**answers

170 views

### Consistency of a system of linear equations

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...

**1**

vote

**0**answers

269 views

### Totally Uni-modular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...

**1**

vote

**0**answers

845 views

### How to solve simple bilinear equations under extra linear constraints

Hello,
This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:
$\lambda_i^T ...

**1**

vote

**0**answers

3k views

### A system of linear equations with linear constraints

Mathematical problem.
Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of ...

**1**

vote

**0**answers

1k views

### Covariance matrix formula interpretation - what am I missing?

I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...

**0**

votes

**0**answers

20 views

### Linear Program for Single Source Shortest Paths Tree

This question originates in quick, however wrong, idea to calculate a shortest paths tree in the presence of negative cycles. The essential motivation was that a linear program would determine binary ...

**0**

votes

**0**answers

18 views

### Is there a standard technique for overdetermined homogeneous integer programming?

Given $M\in\Bbb Z^{n\times n}$ of $\mathsf{rank}(M)=r\leq n$ consider $MX=\mathsf0_n$ where $X\in\Bbb Z^{n\times 1}$ holds. We also have a $\mathsf{rank}(N)=m\leq n$ matrix $N\in\Bbb R^{m\times n}$ ...

**0**

votes

**0**answers

70 views

### Is there a space in which the $\vec a$ in $\sin(a_1\cdot x)+\sin(a_2\cdot x)$ is linear?

Suppose one has equations of the form $\sin(a_1\cdot x_i)+\sin(a_2\cdot x_i)=y_i$ for $i = 1, \dots, n$ (there are also amplitudes and phase shifts, but let's ignore these for now). I want to solve ...

**0**

votes

**0**answers

47 views

### Finding a movement taking out of a convex set

There is a convex set $S$ as the hull of M points in an D-dimensional Euclidean space and a point $\vec P$ in the set. Then, there is a set of vectors $\vec W$ taking the form $\vec W=\sum_{i=1}^N ...

**0**

votes

**0**answers

146 views

### Inverse problem with a rank-1 update

I hope you can help me out with this. I have to find the solution x to an inverse system
$$
x=A^{-1}b
$$
This inverse problem is basically a least square problem with a rank-1 update.
$$
...

**0**

votes

**0**answers

77 views

### Big eigenvalues of a special stochastic matrix

Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq ...

**0**

votes

**0**answers

94 views

### Gauss-Newton for quotient functions

I'm optimizing a function of the form
$$
\sum \frac{ \|\mathbf{f_i}(x)\|^2 }{ g_i(x)^2 + h_i(x)^2 }
$$
where $x$ is a real vector, $\mathbf{f}(x)$ is a real vector, and $g(x)$ is a scalar. My first ...

**0**

votes

**0**answers

180 views

### A linear program related question

Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice.
Let $\alpha^k \in (\alpha_1^k, ...

**0**

votes

**0**answers

72 views

### Computing maximum point for minimal function of a family of linear functions

Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such ...

**0**

votes

**0**answers

235 views

### LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...