Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

general questions about selecting a best element from some set of available alternatives.

1
vote
0answers
13 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....
-3
votes
0answers
50 views

How to compute Girth of a graph using Integer Programming?

I am fairly new to linear and integer programming. I am trying to solve a problem which requires me to obtain the Girth of a graph using integer programming. The problem formulation becomes ...
2
votes
1answer
90 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
41 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 ...
8
votes
0answers
93 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
58 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
132 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
52 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
55 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
25 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
54 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
41 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
296 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
42 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
42 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
12 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
80 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
42 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
31 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
53 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
213 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
231 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 ...
0
votes
1answer
97 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
149 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
158 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
35 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....
0
votes
0answers
60 views

How does an NP-complete continuous optimization problem map to Boolean SAT?

I looking at this paper where the authors mention that the following problem: "Given a neural network and a set of training examples, does there exist a set of edge weights for the network so that ...
2
votes
1answer
348 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 ...
0
votes
0answers
30 views

Lower bound on the complexity of projection onto simplex?

The projection onto the simplex problem is the following optimization problem: $\mathbf{x} = \text{argmin } ||\mathbf{x} - \mathbf{y}||_2$ subject to $\mathbf{x} \geq 0$, $\mathbf{1}^{\text{T}} \...
3
votes
2answers
273 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
117 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
64 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
435 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
141 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 ...
0
votes
0answers
59 views

Flow Optimization: minimum cost matching of demands from multiple sinks

The Graph I've been looking into a flow optimization problem (please follow the above link to view the directed acyclic graph with the source and multiple sinks) We have a single source 1 and ...
1
vote
0answers
89 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
247 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
45 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
143 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 ...
7
votes
0answers
152 views

A class of functions on a lattice that are easy to optimize

Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there ...
1
vote
1answer
104 views

Solving linear program with 1 quadratic constraint complexity

Consider the following linear program, $$\min y \\ xc_1 \leq c_2 + yz,\\ x = x_1 + \dots + x_n,\\ z \leq x_1 + x_2, \\ z \leq x_2 + x_3, \\ \vdots\\ z \leq x_{n-1} + x_n, \\ x,x_1, \dots, x_n,y,z \...
-1
votes
2answers
118 views

How to continue this algorithm? [closed]

I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º). I have thought about ...
0
votes
0answers
457 views

What is the difference between NSGA-II and NSGA-III?

Can someone please explain the difference between the two versions of Non-dominated Sorting Genetic Algorithm NSGA-II and NSGA-III?
4
votes
0answers
446 views

Optimizing Maximum Weighted Matching (Edmonds Blossom)

Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation ...
1
vote
0answers
43 views

Average case or beyond worse case analysis for non-convex optimization procedures?

I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature. It is known that global optimization of non-convex functions is NP-...
1
vote
0answers
46 views

Parametrically-relaxed Kolmogorov complexity

Consider the following problem: Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation. Output: The encoding of some kind of automaton (say, a Turing machine) which ...