general questions about selecting a best element from some set of available alternatives.
1
vote
0answers
17 views
Confusion related to minimization of a gaussian likelihood function
I have this confusion related to minimization of gaussian likelihood function. The negative of the log likelihood of gaussian distribution is
$-logdet(Q) + tr(SQ) + \lambda||Q||_{1}$ where Q is the ...
3
votes
0answers
43 views
Closest Vector Problem with sparse basis and target vector
The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety ...
-1
votes
0answers
39 views
Is there a general way to convert a critical section to one or more semaphores? [migrated]
Is there a general way to convert a critical section to one or more semaphores? That is, is there some sort of straightforward transformation of the code that can be done to convert them?
For ...
8
votes
0answers
115 views
Expected length of a self-avoiding random walk
We're given an arbitrary graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists.
...
1
vote
0answers
40 views
confusion related to the dual of svm
I have a confusion related to the dual of svm
In the main objective function I have
Now to solve the dual of this objective function, I will minimize with respect to the primal variables first to ...
2
votes
0answers
155 views
Confusion related to L1 and L2 svm
I have this confusion related to L1 and L2 svm. It is given in this paper that
The dual problem is given by
$$
min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha
$$
subject to
$$
0 <= \alpha_i ...
-1
votes
0answers
58 views
Some confusion related to dual coordinate descent in SVM [duplicate]
I have this confusion related to L1 and L2 svm. I was reading this paper
I am attaching the screenshot and the part I didn't understand
The part that I didn't understand how it was derived
I ...
1
vote
0answers
68 views
Poly-time Algorithm for Non-Linear Optimization
As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this ...
2
votes
2answers
203 views
Undecidability of program optimization
A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that:
On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is ...
3
votes
1answer
153 views
A weighted sorting problem
Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized.
It can be formulated as ...
1
vote
0answers
100 views
What does “no integrality gap” implies?
I'm currently working on a linear time heuristic for the rectangle decomposition of binary matrix. This problem has a polynomial time solution, which in our case it too slow for large scale ...
-2
votes
2answers
142 views
how do you turn an algorithm for a decision problem into an algorithm for an optimization problem?
It is well-known, I believe, that theoretically, in quite a few cases, an algorithm that solves a decision problem can be turned into an algorithm that solves the corresponding optimization problem.
...
2
votes
0answers
61 views
Small area containing large amount of patterns
The problem:
I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
3
votes
0answers
99 views
Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables
Integer programing is one of the most narutal optimization tools.
As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.
$x_{1}x_{2}x_{3}+$ ...
1
vote
0answers
81 views
What is the shape of cost function of weighted graph matching problem?
According to Umeyama, the weighted graph matching problem can be formulated as
$min_P || PA_GP^T - A_H ||$
s.t. $P$ is a permutation matrix.
where $A_G$ and $A_H$ are n-by-n matrices
If we relax ...
3
votes
0answers
94 views
Existence of complete “asymptotic” optimization problems
Define a function $u:\lbrace 0,1 \rbrace^* \rightarrow \mathbb{R}$ to be an asymptotic optimization problem when the following conditions hold:
There is an algorithm $U$ which computes the first $n$ ...
5
votes
0answers
94 views
Generating interesting combinatorial optimization problems
I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension ...
0
votes
0answers
46 views
Nonmetric TSP and Functional Compleixty Classes
Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method.
Is this general TSP a complete problem in some functional complexity classes ?
...
-1
votes
1answer
129 views
Integer compression
I'm looking to devise a scheme for compressing integers which have a known sampled distribution (they might be clustered around a value, say, or have several areas of differing density). So far, I've ...
2
votes
0answers
68 views
Benchmarks for approximation algorithms
I'm working on a Haskell library for approximation algorithms. In particular, I'm working on Partition, Knapsack, Vertex Cover, and possibly a few others. Of course, I'd like to benchmark my library ...
1
vote
0answers
117 views
Properties of the subgradient method
The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule
$$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and
$\alpha(t)$ is a ...
4
votes
1answer
116 views
Splitting line segments with a line
Given is a finite set $S$ of line segments in the plane.
I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$.
Here ...
5
votes
1answer
124 views
Effective algorithm of searching the “nearest” doubly stochastic matrix
Given a data matrix $D$, is there any effective algorithm to solve the optimization problem
$\min_Q || D - Q ||_F$
such that
$Qe=e$,
$e^TQ=e^T$, and
$Q_{i,j} \geq 0 $ $\forall i,j$,
where ...
6
votes
0answers
110 views
Numerical stability of Simplex method
The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.
...
2
votes
1answer
52 views
Covering only one of two types of objects in a cartesian space using minimum number of rectangles
There is a side problem in my research that I believe should be a known problem. I do not want to spend lots of time on a problem that already has been studied, but I do not have a name for the ...
2
votes
1answer
107 views
NP-complete problems related to Minimizing Variance
I am interested in references to NP-complete problems that involve some non-linear terms (e.g. quadratic terms). So far I am aware of the "Quadratic Assignment problem" and "Quadratic Programming". ...
0
votes
0answers
35 views
Effective algorithm to search for closest vector set under certain constraints
The problem is given a set of data vectors $D = [d_1,d_2,...,d_N]$ and an diagonal weighting matrix $W$, search for vectors $Q = [q_1,q_2,...,q_N]$ that are closest to $[d_1,d_2,...,d_N]$ and at the ...
9
votes
1answer
383 views
Minimum spanning tree over all vertex matchings
I ran into this matching problem for which I am unable to write down a polynomial time algorithm.
Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| ...
4
votes
1answer
104 views
Nearly-Eulerian Tours
The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more ...
-6
votes
1answer
104 views
Minimizing edges of an FSM [closed]
There are various well-understood, efficient, and theoretically interesting algorithms to minimize a DFA in terms of states.
Is there research into minimizing based on edges of the FSM?
edit: ...
1
vote
0answers
58 views
Can I apply the constraint while constructing the Lagrangian?
Consider the problem:
$\min_X ||XAX^T||_F$
s.t. $X^TX=I$
If A and X are real matrices, the lagrangian will be $tr(XAX^TXA^TX^T)+\sum_i\alpha_i(x_i^Tx_i-1)+\sum_i\sum_{j\neq i}\beta_{ij} q_i^Tq_j$ ...
3
votes
1answer
200 views
Stochastic version of a strongly NP-Complete problem
Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ?
The problem Tree CVRP(Capacitated Vehicle ...
6
votes
1answer
222 views
NP-hardness of an optimization problem
While studying a problem in algorithmic game theory I got interested
in the complexity of the following optimization question:
Problem
Given:
ground set $U = [n] = \{1,\ldots,n\}$ given by $n$,
...
10
votes
1answer
217 views
Exact algorithms for non-convex quadratic programming
This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form
minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T ...
13
votes
3answers
489 views
0-1 Linear Programming: computing the Optimal Formulation
Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
5
votes
0answers
225 views
Which problems in graph theory can be stated as quadratic programs?
There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency ${\bf A}$ or the Laplacian matrix ...
5
votes
1answer
136 views
Splitting a graph into minimum number of subpaths
I have an ordinary weighted graph. I need to traverse every edge in the graph at least once. BUT I must do it in subpaths of maximum length L. Those subpaths need not be connected to each other. There ...
1
vote
0answers
95 views
Trace minimization with an orthogonality constraint
For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint:
that $X$ is orthogonal.
All the matrices have real entries and $A,B$ are ...
1
vote
1answer
203 views
Difference between weak duality and strong duality?
For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:
Weak duality:
If $\bar{x}$ ...
0
votes
1answer
275 views
Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?
Forgive me wise men for my simple words, for I am but a noob.
There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum ...
1
vote
1answer
198 views
What are some good references for mathematical optimization for the layman?
I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
5
votes
2answers
325 views
How/Why are linear systems so crucial to computer science?
I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
3
votes
1answer
186 views
Is this multiprocessor scheduling problem with overlaps NP-Hard?
The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the ...
8
votes
1answer
208 views
Maximizing a submodular function of two sets with different size constraints
I have two totally distinct domains (apples and oranges) and I have a function $f$ that takes a set of objects from the first domain and a set of objects from the second domain and returns a real ...
2
votes
0answers
153 views
Maximizing a convex function where the objective function is separable but the search space is not
The problem statement is
Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$
Does this kind of problem structure allow one to use specific strategies to solve the ...
1
vote
1answer
283 views
Vehicle routing problem over Manhattan distances
I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot.
Is the following ...
5
votes
1answer
331 views
Implementation that solves minimum set cover
Does anyone know of any tools that solve the approximate minimum set cover problem?
I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about ...
1
vote
0answers
229 views
Optimizing along a cube $s=\{0,1\}^n$
I am doing an optimization on a n-dimensional cube. That means that every solution is a set of $0$ and $1$, hence $s=\{0,1\}^n$. Most optimization algorithms though need a differential to work. E.g. ...
4
votes
0answers
370 views
Can the Hungarian method be used with real edge weights?
I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
0
votes
1answer
237 views
To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient?
I recently watched this video on youtube. It featured someone explaining how he used genetic algorithms to improve the efficiency of wind mill turbines by finding the optimal shape for the blades. ...
