All Questions
1,594 questions
1
vote
2
answers
416
views
Implicit derivative?
If we have function $y=L(x_1,x_2,x_3,...,x_n)$, and function $z=R(x_1,x_2,x_3,...,x_n)$. How to compute the derivative $\frac{dy}{dz}$?
Shall I do $\frac{dy}{dz} = \sup_{g\in \Re^n}\frac{\...
- 171
5
votes
1
answer
562
views
Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections?
We are interested in the following question (definitions and references are given below):
Main Question: Given an upper-semicontinuous polyhedral multifunction $F:R^n \rightarrow R^m$, is there ...
- 115
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
3
votes
1
answer
147
views
Optimizing finite-length approximations to space-filling loops
Take a loop in the unit disk D^2, with length l where length is defined as the supremum of the lengths of piecewise linear approximations. What is the smallest r such that every radius-r subdisk of D^...
- 3,612
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
0
votes
1
answer
225
views
Degree constrained edge partitioning (version 2)
Given a graph $G=(V,E)$ with real-valued (positive or negative) weights assigned to its edges, we want to remove a set of edges so that the sum of the remaining edges is minimized and the degree of ...
- 453
6
votes
1
answer
750
views
Degree constrained edge partitioning
I've come up with the following optimization problem in my research. Is this a known problem in graph-theory and/or combinatorial optimization? If not, which of the known problems are the most similar ...
- 453
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
2
votes
2
answers
5k
views
Best fit for multiple shapes inside an area
Is there a forumla to come up with the best fit for multiple shapes inside a rectangular area, so that none of the shapes are overlapping?
- 121
3
votes
1
answer
1k
views
Matrix approximation
Let A be an $m\times n$ matrix and $k$ be an integer. Assume that $A$ is non-negative. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$ (where $\...
- 145
10
votes
2
answers
7k
views
Is there an "adjacency matrix" for weighted directed graphs that captures the weights?
I am currently writing up some notes on the max-plus algebra $\mathbb{R}_{\max}$ (for those that have never seen the term "max-plus algebra", it is just $\mathbb{R}$ with addition replaced by $\max$ ...
- 363
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
0
votes
2
answers
2k
views
Finding the local/global minima of Shubert function
Consider the 2D Shubert function. As given in that page, the function has 18 global minima and several local minima. How can I find the (x,y) of all these minima? Any help appreciated. If it was a ...
- 121
2
votes
3
answers
421
views
Which method to apply to this problem?
I'm a programmer and I came a across an interesting problem. I'm sure there is a mathematical method or an algorithm to solve it, but I don't know where to start with the search nor which literature ...
- 125
6
votes
1
answer
424
views
How to optimize student happiness in group work?
There are $n$ students in a class, and they must be divided into, say, $k$ groups. Each student ranks the other students in order of preference of working together. Is there a way to generally ...
- 884
3
votes
2
answers
1k
views
Are Bregman divergences quasi-convex?
Given a convex set S ⊂ ℝd and an appropriately differentiable convex function f: S → ℝ, a Bregman divergence Bf(x, y) = f (x) - f (y) -⟨x- y , ∇f (y)⟩ for x, y &...
- 325
6
votes
2
answers
2k
views
Problem equivalent to "largest square in a cube"
The "largest square in a cube" problem, which asks for the largest square inside a cube, has a solution as can be seen on this page, which also says that the general problem in higher dimensions is ...
- 7,320
6
votes
2
answers
364
views
Algebraic characterization of transitive spaces of matrices
Fix an integer $d \ge 2$ and let $M_d$ be the space of real $d \times d$ matrices. Let $E$ be a vector subspace of $M_d$. We say that $E$ is transitive if $E \cdot \mathbb{R}^d_* = \mathbb{R}^d$, ...
- 2,479
4
votes
2
answers
4k
views
Minimizing a function containing an integral
I am trying to optimize a function of the following form:
$L = \int_{t=0}^{T}(AR-x)dt$, where A is a system parameter
i.e. I am trying to find the optimum x(t) that minimizes L over all admissible x(...
- 439
1
vote
2
answers
2k
views
Why is solving a MILP w/o an objective function so much faster?
When solving a MILP (mixed integer linear program) using a linear relaxation, the solver finds a feasible solution much faster if there is no objective function. The same problem with an objective ...
- 180
3
votes
1
answer
1k
views
Maximizing Sparsity in l1 Minimization?
Consider the optimization problem
$$\min_x ||Ax||_1 + \lambda||x-b||^2,$$
where $A \in \mathbb{R}^{n \times n}$, $x,b \in \mathbb{R}^n$ and $\lambda$ is strictly greater than 0. (This problem is ...
- 3,059
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
5
votes
2
answers
457
views
Heaviest Convex Polygon
Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
- 341
0
votes
2
answers
595
views
univariate prior corresponding to weighted sum of L1 and L2 penalties?
Is there a univariate probability distribution $p_{\lambda,\alpha}(\beta)$ over the reals, parameterized by $\lambda > 0$ and $1 >= \alpha >= 0$, such that $p_{\lambda,\alpha} \propto \exp(-\...
- 103
2
votes
1
answer
337
views
Switching function for Bang-Bang nagivation
I'm attempting to develop an equation to determine the "switching time" for a control system. I've managed to work out a specific solution for when starting and ending velocities are are the same, ...
- 248
5
votes
3
answers
522
views
Navigation solution for frictionless vehicles.
Looked around a bit and couldn't seem to find a similar question. (either that or it was worded with vocabulary above the multivariable calculus I've taken. :))
Roughly worded: I would like to ...
- 248
0
votes
3
answers
296
views
Uniformly distribute a population in a given search space
I am trying to uniformly distribute a finite number of particles into a 2D search space to get me started with an optimization problem, but I am having a hard time doing it. I am thinking that it ...
- 101
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
6
votes
3
answers
1k
views
How can I embed an N-points metric space to a hypercube with low distortion?
I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of ...
- 171
23
votes
2
answers
2k
views
Five Front Battle
Two generals are fighting a five front battle. Each general has 1 unit of army, which he divides into five separate armies that he sends to the five fronts. If one general sends more army to a front ...
- 8,688
29
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
- 2,383
1
vote
2
answers
6k
views
If a quadratic form is positive definite on a convex set, is it convex on that set?
Consider a real symmetric matrix $A\in\mathbb{R}^{n \times n}$. The associated quadratic form $x^T A x$ is a convex function on all of $\mathbb{R}^n$ iff $A$ is positive semidefinite, i.e., if $x^T A ...
- 3,059
1
vote
0
answers
142
views
Term to describe how much harder an optimization problem can become after constraining a small part of the domain?
This is a follow up to this question.
I'm interested in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form
$$\Phi = \max_{\mathbf{x} \in \left\{0,1\...
- 341
3
votes
2
answers
362
views
Hardness of combinatorial optimization after adding one constraint
I'm interested generally in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form
$$\Phi = \max_{\mathbf{x} \in \left\{0,1\right\} ^N} f(\mathbf{x})$$
...
- 341
5
votes
2
answers
4k
views
On Quadratic Integer Programming
I have the quadratic integer program over $\mathbb{Z}^n$
$\displaystyle\min_{z \in \mathbb{Z}^n} \Phi (z) = \frac{1}{2} z^T Q z - r^T z + s$
subject to $G z = h$, and $z_i \in \{0,1,2,\dots, b_i\}$ ...
- 430
0
votes
2
answers
207
views
What optimization criteris should be used for this problem?
The real world version:
I have a united value (e.i. 12in, 120V 1.414 kg*m/s) where the units are specified as the rational exponents of the 5 base units; m, s, kg, C and K. Additionally, I have a set ...
- 205
1
vote
3
answers
5k
views
how to get a feasible solution to dual program from a feasible solution to primal program?
If a feasible solution to a linear programming is known, and the corresponding value of the objective function is close to the optimum, can we get a feasible solution to the dual programming which ...
- 11
4
votes
1
answer
720
views
"Transient" of the discrete-time Riccati equation
It is a well-known result that, if the pair $(A,Q^{1/2})$ is stabilizable and the pair $(A, C)$ is detectable, the solution to the discrete-time Riccati recursion
$P(t+1) = A P(t) A^T - A P(t) C^T\ (...
- 141
0
votes
1
answer
280
views
Searching global minima fast?
I am minimizing a highly non-linear function. If I know the global minimum is at most some value, is this information helpful to design a faster algorithm than random restart?
If we know an upper ...
- 171
7
votes
4
answers
2k
views
Is there a name for the matrix equation A X B + B X A + C X C = D?
I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...
- 1,890
6
votes
5
answers
2k
views
Simplex method for SDP?
I know the interior point method works both for Linear Programming (LP) and semidefinite programming (SDP). My question is, can the other popular method for solving LP, namely the simplex method, be ...
- 105
0
votes
2
answers
313
views
scalable binary linear optimization
Has anyone encountered scalable solutions to a binary linear optimization problem of the form:
\min \sum_{i=1}^n x_i
s.t x_i \in {0,1}
Ax=b
where, x=(x_1,x_2,...,x_n)^t, b=(b_1, b_2,...,b_m)^t, ...
- 1
1
vote
2
answers
301
views
Mediated envy-free and efficient cake cutting with n=2?
Is there an algorithm in literature to compute an efficient (pareto optimal) and envy-free cake cutting when there are only $n=2$ players and a mediator?
- 31
3
votes
2
answers
384
views
High dimensional Steiner tree
Given n affinely independent points in n-1 dimensional Euclidean space, how is the minimum Steiner tree constructed? Or assuming that the topology of the Steiner tree is given, is there an easy way ...
- 31