**14**

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

117 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

68 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

178 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

132 views

### Closed-form solution of a linear programming question

Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & ...

**4**

votes

**0**answers

47 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

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

**4**

votes

**0**answers

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

**3**

votes

**0**answers

113 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} + ...

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

191 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

325 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

35 views

### Existence of probability distribution satisfying upper/lower bounds on events

Suppose we have a finite sample space $S$ and some events $A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on $S$ so that no element has probability greater than a ...

**2**

votes

**0**answers

111 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

82 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

62 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

73 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

29 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

142 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

545 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

246 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

183 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

268 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

594 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

65 views

### Existence of Nonnegative Solutions of Linear Systems of Equations and Inequalities with particular constraints

Suppose we have an n by m nonnegative matrix A, where each row sums to 1. I wonder whether there exists an m by n nonnegative matrix X that satisfies the following constraints: each row of X sums to ...

**1**

vote

**0**answers

67 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

59 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

50 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

81 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

65 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

179 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

124 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

198 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

107 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

173 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

276 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

896 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

36 views

### Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ ...

**0**

votes

**0**answers

14 views

### Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...

**0**

votes

**0**answers

60 views

### Optimization with vectors

I am trying to solve the following optimization problem as a small part of a research project, and I do not know if there exists closed form solutions. My linear algebra is very rusty and I am looking ...

**0**

votes

**0**answers

47 views

### About identifying a few diagrams

Please have a look at these beautiful seminar slides,
https://math.berkeley.edu/~bernd/coimbra1.pdf
Can someone kindly identify the algebraic description of the spectrahedron that is drawn on slide ...

**0**

votes

**0**answers

28 views

### Maximisation of a discrete linear function

I am trying to maximise the function
$$
Q=\sum_i{\alpha _{i}x_{i}}
$$
subject to the constraint
$$
W<=\sum_i{\alpha _{i}w_{i}x_{i}}
$$
By changing $\alpha _{i}$ subject to $ 0<=\alpha ...

**0**

votes

**0**answers

26 views

### Equivalence between multiclass SVMs, power diagrams, and constrained $k$-means

Apologies in advance for the long post:
Suppose we have a collection of points $\mathbf{p}_1,\dots,\mathbf{p}_n$ in $\mathbb{R}^d$, and we consider the following three ways of partitioning these ...

**0**

votes

**0**answers

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