Questions tagged [optimization]
general questions about selecting a best element from some set of available alternatives.
-1
votes
0answers
33 views
How could the No Free Lunch Theorem be applied to complexity classes
I was reading a chapter from a book, which states: (section 11.3.4)
No Free Lunch (NFL) has not been proven to hold over the set of problems in the complexity class NP.
I was confused because NP ...
0
votes
0answers
106 views
Star seperators to explain computational complexity of algorithms on a class of graphs?
A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
0
votes
0answers
56 views
Coordinate descent in integer programing: when does it work?
Denote $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to minimize a function $f:N\rightarrow \mathbb{R}$. It is very easy to minimize $f$ coordinate by coordinate so ...
2
votes
1answer
83 views
Maximum-minimum satisfiability
In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\...
3
votes
2answers
101 views
Minimum relevant variables in linear system - additive approximation
In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.:
$$ A x = b $$
and the goal is to find a solution $x$ with as few nonzero variables as ...
0
votes
0answers
84 views
Maximum Weight Independent Set on a Changing Graph?
Suppose I have an optimal solution to the maximum weight independent/stable set problem on an arbitrary graph. If I were to induce a clique among a subset of its vertices (and perhaps add in some ...
1
vote
0answers
29 views
Pass ordering for greedy local search algorithms
Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for.
I have a problem with the following setup: I have a (finite) totally ...
1
vote
0answers
33 views
Back-propagation for computing derivative of certain line integral
Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
1
vote
0answers
34 views
Best approach for allocation problem
I am a bit rusty on optimization algorithms and need an advice. This is my problem:
I have n images (with width and ...
1
vote
1answer
128 views
Is this a knapsack problem?
I have a set of $K$ keywords. Each of this keywords can have a set of bids from $1\$,\ldots, N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and ...
0
votes
0answers
37 views
What is the right term/theory for prediction of Binary Variables based upon their continuous value?
I am working with a linear programming problem in which we have around 3500 binary variables.
Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
2
votes
1answer
93 views
Stochastic gradient methods and risk of neural nets
Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv....
2
votes
1answer
96 views
Minimization version of matrix p-norms?
I considered a minimization version of matrix p-norms, defined for a matrix $A$ by
$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$
Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
1
vote
1answer
43 views
Problem property name where an optimal solution in a graph can be used as a solution in any subgraph
Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal ...
9
votes
0answers
103 views
Shortest string in the intersection of regular languages
Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string
Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
3
votes
0answers
67 views
Linear optimization over intersection of totally unimodular matrices
I am currently dealing with a problem of the following form
\begin{alignat}{2}
&\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\
&\text{sub to} \hspace{0.05in}&&...
6
votes
0answers
136 views
Optimal set union tree
Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
1
vote
1answer
56 views
Reference request — minimizing a non-increasing submodular function with (upper bound) cardinality constraint
Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$.
I am wondering if there are ...
1
vote
1answer
60 views
Minimum graph cut with constraints
Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G_i, i=1,......
1
vote
0answers
26 views
Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent
I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so ...
1
vote
0answers
55 views
Minimization of the maximal adjacent integer sums on a circle
Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange....
3
votes
0answers
44 views
Primal/Dual of the Lasserre/ SOS SDP hierarchy
Sum of Squares proofs and the Lasserre hierarchy can both be stated as SDPs. It is often claimed without proof that these SDPs are dual to each other, although I do not see that this is obvious. I was ...
4
votes
1answer
323 views
Minimum Union-Sum Cost Path
I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
1
vote
0answers
49 views
maximization of non-negative monotone supermodular set function with cardinality constraints
the following link Maximizing a monotone supermodular function s.t. cardinality says no kind approximation possible for maximizing non negative supermodular function subject to maximum cardinality ...
1
vote
2answers
82 views
Partitioning a square for optimal queries
I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles:
$f(x, y, r)$ tells me how many ...
3
votes
1answer
46 views
Algorithm for finding smallest set and instanciation for a given constraint system
I have a system of constraints described by a set of clauses of the form
$x_1 \neq x_2 \lor \dots \lor x_{i-1} \neq x_i$, for instance:
...
0
votes
0answers
13 views
Modelling a fixed-size chromosome for a variable task number in a genetic algorithm
I'm trying to use GA to solve a fairly simple scheduling problem with a set of agents. Agents are just moving entities that have simple and predictable trajectories. They need to "capture" information ...
4
votes
0answers
83 views
Showing hardness of maximizing stochastic objective function over graph
Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$.
The challenge is to ...
0
votes
1answer
43 views
About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective
Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?
1
vote
0answers
32 views
Getting to local/global minima with (stochastic) gradient descent on non-convex objectives
Is there any class of non-convex objective functions for which (stochastic) gradient descent can provably get to a local or a global minima? (..maybe in the approximate sense like a point such that ...
0
votes
0answers
82 views
Find the maximum induced (weighted) subgraph with edge weights greater than some minimum
I have a (fully connected) weighted undirected graph.
I want to find a maximal induced subgraph whose edge weights are all above some minimum value.
Or, if not a maximal subgraph, then with some ...
0
votes
0answers
43 views
Problem: Scheduling diverse teams while minimizing frequency
I have the following problem which I have been asked to solve. I like to think that a few years ago, I'd be able to do it myself, but these days I must admit that help is good :)
Given $n$ employees $...
3
votes
1answer
214 views
Optimal partition according to partition cardinality
Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$.
We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements.
Can ...
0
votes
0answers
233 views
Complexity of Quadratic Programming
I'm trying to learn the complexity of a quadratic program in the form of:
minimize:
$f(x,y)=x^2-y^2-4xy$
given only $x*y$
s.t.
$x=a+b$
$y=a-b$
$x+y>3\,\sqrt{xy}$
$x,y,a,b >0$
What I ...
1
vote
1answer
105 views
Monotone supermodular function minimization under partition matroid constraints
Is there a known approximation algorithm for the problem of minimizing
a monotone (non increasing) supermodular function under partition matroid constraints ?
0
votes
0answers
184 views
Does binary search converge faster than gradient descent on 2 convex functions?
Here is the thing, I have two functions, lets call them $E_0$ and $E_1$. The functions are both convex, and they essentially look something like this:
Now I am looking to get an $\epsilon$ close to ...
2
votes
0answers
159 views
Is Non-linear Constrained Optimal Exact Cover NP-Hard?
Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard....
0
votes
1answer
37 views
How do minimally violated k-mod cuts work (intuitive explanation)?
As a background, I am not a specialist in theoretical computer science. But I have to take an exam with research-level optimization topics, and I have to learn it on my own, without lectures or tutors....
2
votes
1answer
360 views
Maximum difference between two shortest paths
My problem is the following maximization problem:
Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two ...
3
votes
2answers
278 views
NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
3
votes
0answers
118 views
Stacks serving interval storage requests
An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in ...
3
votes
0answers
65 views
Minimizing a sum of thresholded quadratics
Let $W_1, \ldots, W_k$ be positive semi-definite matrices, $b_1, \ldots, b_k$ be vectors, and $a_1, \ldots a_k$, $c_1, \ldots, c_k$ be scalars. How difficult is it to find an approximate minimum of
...
5
votes
0answers
170 views
Which well-known algorithmic problem is this an instance of?
Consider that you have n counters initialised with numbers $M_1 \dots M_n$. In each round you decrement exactly $k$ out of these counters. Keep doing this until at least $n-k+1$ counters are zero, so ...
4
votes
1answer
456 views
Understanding the No Free Lunch Theorem
I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out
to me. The first was that we can't define a uniform ...
0
votes
0answers
143 views
Data structure to search name of files and get its path
I will be inserting names of files in a dynamically way, approximately till 1 billion of names. Besides, I do also want to store the path where the files are located in order to do the following ...
1
vote
0answers
98 views
QUBO formulation of a discrete-variable optimization problem
I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes ...
1
vote
1answer
299 views
Common terminology used for lower/upper bounds
Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?...
3
votes
1answer
79 views
Centroid in $\ell_2$ distance
Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right)
$$
0
votes
0answers
46 views
Wavelet based Non linear optimization technique
I am outlining a method for solving Non Linear optimization problems.
Consider the system of equations:--------------------------------- 1
f1(a0, a1, a2, a3 ......... an) = 0
f2(a0, a1, a2, a3 ........
1
vote
0answers
155 views
Convergence of Q-learning with non-linear function approximation
Q-learning is a well-known algorithm in Reinforcement learning which enjoys great empirical success but with insufficient theoretical understanding. In the tabular setting, it is known that if each ...
