All Questions
685 questions
14
votes
0
answers
4k
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?
- 1,015
7
votes
3
answers
913
views
Some questions about Invexity
Recently, I am looking into a non-convex optimization problem whose points satisfying KKT conditions can be obtained. Then the problem becomes how to decide whether the KKT conditions are sufficient ...
- 95
2
votes
1
answer
308
views
Can subgradient infer convexity?
It is known that
If $f:U→ R$ is a real-valued convex function defined on a convex open set in the Euclidean space $R^n$, a vector v in that space is called a subgradient at a point $x_0$ in $U$ if for ...
- 95
2
votes
1
answer
1k
views
Linear Programming Cost Function [closed]
I need to add the following to my LP problem:
If the amount of workers hired in period $t$ ($H_t$) is higher than 25, the hiring cost is only 1 instead of 1.2.
Example: if 30 workers are hired in ...
1
vote
4
answers
978
views
Maximum average value within a rectangular bounding box
The goal is to expedite detection using the sliding window approach. In other words, an object classifier is known and I need to find where the possible locations of this object are in an image. This ...
- 111
1
vote
2
answers
1k
views
Inequality-constrained linear-regression, what is the covariance of the estimator?
If you do a linear regression: $||Ax - e ||^2$, where e is iid Gaussian, mean 0 and variance 1, then your answer is $x_{hat} = (A' A)^{-1} (A' * e)$ and the covariance of $x_{hat}$ is $(A' A)^{-1}$
...
4
votes
1
answer
2k
views
How to find which subset of bitfields xor to another bitfield?
I have a somewhat coding-oriented problem. I have a bunch of bitfields and would like to calculate what subset of them to xor together to achieve a certain other bitfield, or if there isn't a way to ...
- 41
0
votes
1
answer
307
views
max length or size of a convex set
I want to maximize $||x-y||$ with $x$ and $y$ in $C$ where $C$ is the intersection of some discs. We assume the intersection is nonempty, and closed. I am thinking, how to formulate it as a ...
- 15
1
vote
1
answer
9k
views
what is the difference between the revised simplex method andthe full tableu?
No to sound naive but they look like they include the same steps to me, one's just the algorithmical representation of the other. Thanks in advance.
- 111
21
votes
1
answer
3k
views
A circle packing conjecture
Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and ...
- 1,085
2
votes
0
answers
281
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 ...
- 567
10
votes
5
answers
2k
views
Robust black box function minimization with extremely expensive cost function
There is an enormous amount of information about the common applied math problem of minimizing a function.. software packages, hundreds of books, research, etc.
But I still have not found a good ...
- 415
2
votes
2
answers
640
views
Sorting a binary matrix diagonal in polynomial time while preserving rows
Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?
For example given ...
- 121
0
votes
1
answer
1k
views
For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)?
Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I ...
- 135
5
votes
2
answers
3k
views
Continuous Linear Programming: Estimating a Solution
I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the ...
- 373
4
votes
1
answer
275
views
Symmetry of the integer gap
Are there results that bound the asymmetry of the duality gap of an integer program? That is to say, if the difference between the LP solution and the IP (primal) solution is $a$, is there a function ...
- 183
51
votes
7
answers
23k
views
Is all non-convex optimization heuristic?
Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic ...
- 2,383
5
votes
2
answers
1k
views
Applications of minmax theorem(s)
Intro We suppose $X$ and $Y$ are nonempty sets and f: $X\times Y \rightarrow \mathbb{R}$. A minimax theorem is a theorem that asserts that, under certain conditions,
$$ \inf_Y \sup_X f = \sup_X \...
1
vote
3
answers
2k
views
How to solve Linear Programming problem with tighter Integer Programming constraints
I want to learn a bit about Linear Programming.
After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...
9
votes
1
answer
6k
views
Proving that a binary matrix is totally unimodular
I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
- 213
10
votes
3
answers
6k
views
Solving a system of linear inequalities -- what is the dimension of the solution set?
It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...
- 7,857
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 1,182
5
votes
1
answer
271
views
Feasibility of linear programs
It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
- 201
2
votes
0
answers
5k
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 $\...
4
votes
0
answers
790
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 ...
- 41
6
votes
3
answers
2k
views
A simple infinite dimensional optimization problem
I'd be grateful for a reference for the following result, which I believe to be true, and
should be well-known.
Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
- 520
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
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 ...
- 111
0
votes
2
answers
4k
views
Linear programming piecewise linear objective
I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this:
max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$
$s.t. $
$|\...
- 3
10
votes
1
answer
2k
views
Sum of difference moduli vs. sum of modulus differences
This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself.
Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
- 33.8k
1
vote
2
answers
256
views
how to estimate a polyhedron(convex hull) classifier from data sample
Given a set of points $X\in\Re^D$, they have labels $Y\in${$-1,+1$}. I would like to separate the data labeled +1 and the data labeled -1 by a polyhedron.
$min_w \sum_i \xi_i + \frac{1}{2}\|w\|_2^2$
...
- 171
2
votes
0
answers
169
views
modification of singlestart in global optimization
When minimizing a nonconvex function $f : \Omega \rightarrow \mathbb{R}$ that may have multiple minima, there are some very simple strategies to improve the odds of finding the global minimum point. ...
- 4,485
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
9
votes
5
answers
646
views
Software for rigorous optimization of real polynomials
I am looking for software that can find a global minimum of a polynomial function over a polyhedral domain (given by, say, some linear inequalities) in $\mathbb R^n$. The number of variables, $n$, is ...
- 7,826