All Questions
783 questions
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.2k
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
1
vote
0
answers
79
views
Is there an efficient way to do semidefinite programming with a Lyapunov equation constraint?
I am trying to numerically solve semidefinite programs of the form
$$\begin{array}{ll} \underset{X,Y}{\text{minimize}} & \operatorname{tr}(AX)\\ \text{subject to} & BY + YB = X\\ & X, Y \...
- 31
1
vote
0
answers
81
views
Algorithm for deciding feasibility of linear programs [closed]
Suppose I have the simple linear program
$$Ax \geq 0, \quad x \geq 0$$
We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system?
$$Ax \geq 0, \quad ...
1
vote
0
answers
192
views
What is the solution of the matrix equation $A X + X A' + B X B' + C = 0$ for $X$?
I know that the matrix equation $A X + X A' + C = 0$ is in the form of the time-continuous Lyapunov equation, so solving for $X$ is pretty trivial since the solution already and numeric solvers ...
- 11
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
- 111
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
1
vote
0
answers
92
views
Approximating matrix multiplication with integer arithmetic
The following question is inspired with approximation of matrix multiplication computations occurring in numerical simulations and machine learning algorithms with a use of efficient integer ...
- 225
1
vote
0
answers
121
views
Algorithm for the nilpotence of matrix polynomials
Let $P$ be a multivariate polynomial of real-valued $N \times N$ matrices. Given $X_1, X_2, ..., X_M \in \mathcal{M}_N\{\mathbb{R}\}$, is there any optimal algorithm to determine whether the result of ...
- 19
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
- 13.9k
1
vote
0
answers
147
views
Convergence of infinite linear programming
Suppose we have the following linear program (LP1),
$$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...
- 53
1
vote
0
answers
82
views
What is the relation between different generalizations of linear programming?
Linear programming subsumed by each of
Semidefinite programming (SDP)
Convex programming (CXP)
SOS programming (SSP)
Is there any relation between each pair in the three?
Are all three equivalent in ...
- 1,826
1
vote
0
answers
78
views
Fast computation of linear equation with row and column removed
Given $A, x, b$ and a linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ is full rank. Denote $A_{\backslash i}$ as a $(n-1)\times(n-1)$ matrix where $A$ removes its $i^{th}$ column and row, ...
- 133
1
vote
0
answers
78
views
Reference for the algorithm to find the intersection between a subspace and positive orthant
I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ;
Is there any reference for the algorithm described in the ...
1
vote
0
answers
67
views
What are the corners of this polytope?
Let $f$ be a non-negative function on the positive integers such that $f(s+t)\geq f(s) + f(t)$ for all $s,t\in\mathbb{Z}^+$. Consider the polytope consisting of all $x\in \mathbb{R}^n$ such that $$\...
- 11
1
vote
0
answers
175
views
Compute Frobenius inner product of two tensor-trains in terms of tensor contractions
Let $p\in\mathbb N$, $n\in\mathbb N^p$ and identify the Hilbert space tensor $\bigotimes_{k=1}^p\mathbb R^{n_k}$ with $\mathbb R^{n_1\times\cdots\times n_p}$ (equipped with the Euclidean inner product)...
- 167
1
vote
0
answers
27
views
Show that a tensor-train is contained in a recursive sequence of subspaces
Let
$p\in\mathbb N$;
$n_k\in\mathbb N$ and $\left(e^{(k)}_1,\ldots,e^{(k)}_{n_k}\right)$ denote the standard basis of $\mathbb R^{n_k}$ for $k\in\{1,\ldots,p\}$;
$u\in\bigotimes_{k=1}^p\mathbb R^{n_k}...
- 167
1
vote
0
answers
34
views
One-sided Jacobi SVD and Divide&Conquer SVD stability and cost [closed]
I'm studying SVD, in particularly the Jacobi SVD and Divide&Conquer SVD algorithms. I can't find anything on the stability and error analysis on these methods. Also can someone show show me what's ...
- 139
1
vote
0
answers
283
views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
- 393
1
vote
0
answers
163
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 167
1
vote
0
answers
25
views
Weird subspace/equality-constrained LP problem/variant of change-making problem
Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...
- 11
1
vote
0
answers
214
views
Effective Jordan normal form
Given $A \in \mathrm{GL}_m(\mathbb{C})$, I can conjugate it by some $B \in \mathrm{GL}_m(\mathbb{C})$ into its Jordan normal form. That is, for some $n\le m$, there exists a $J \in \mathrm{GL}_n(\...
- 73
1
vote
0
answers
177
views
Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]
The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...
- 1,183
1
vote
0
answers
36
views
Linear programming with a convergent coefficient
The following linear programming problem
$x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$
has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? ...
- 19
1
vote
0
answers
126
views
Mixed integer formulation of union of polytopes?
Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
- 1,826
1
vote
0
answers
98
views
L1 Norm regression [closed]
First time poster...apologies for formatting.
I am trying to devise a solution to a familiar linear algebra equation, Ax=b, where all elements in A are non-negative and all the elements in b are ...
- 11
1
vote
0
answers
166
views
How to compress variables in a linear regression
I have a large linear regression where all the independent variables are logical (ie TRUE/FALSE) and sparse. The data has roughly 10,000 variables and 10 million observations, on average around 20 ...
- 687
1
vote
0
answers
225
views
Why de-blurring a blurred image is an ill-conditioned problem? [closed]
Why de-blurring a blurred image is an ill-conditioned problem? What's the intuitive explanation? How to show it using the condition number?
- 139
1
vote
0
answers
24
views
Simple monotonicity property for coordinate descent and linear objective functions
Let $S \subset \mathbb{R}^n$ satisfy $0\leq x_1\leq\dots\leq x_n$ for all $\mathbf{x}\in S$, among other (possibly nonconvex) constraints, and suppose in addition that $\sum_{i=1}^n x_i \geq 1$ for ...
- 4,049
1
vote
0
answers
37
views
Fast certficate of negativity for objective value of mixed-integer linear program
Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...
- 6,853
1
vote
0
answers
74
views
How to minimize n-polytope's bounding box with linear transformation?
I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...
- 11
1
vote
0
answers
85
views
"Barrier functions" in function spaces [closed]
In general the idea of a "barrier function" (as in the context of "interior point methods") can possibly be thought of as defining a function corresponding to an open subset of $\mathbb{R}^n$ such ...
- 2,246
1
vote
0
answers
66
views
On number of solutions by simplex and number of solutions in total in a linear optimization problem?
This is more of a clarification query.
Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem
$$\max c'x$$
$$Ax\leq b$$
where $A\in\...
- 13.9k
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
- 13.2k
1
vote
0
answers
60
views
On the defect of a flow network
This problem in graph theory was actually motivated by some problems in Theory of Fractals.
To formulate the problem I need to recall some definitions related to flow network.
A flow network is a ...
- 41.8k
1
vote
0
answers
86
views
Infinite system of equations with finitely many constraints
During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
- 1,151
1
vote
0
answers
246
views
How to solve a large linear programming problem? [closed]
I have the linear programming problem in $\mathbf x \in\mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \mathbf c^T\mathbf x\\ \text{subject to} & \mathbf A\mathbf x \leq \mathbf b\end{...
- 149
1
vote
0
answers
44
views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
- 19
1
vote
0
answers
19
views
Empirical approaches to validate observational bounds on minimum gap between least eigenvalues of $n \times n$ correlation matrix and its submatrices
Let
$\Sigma$ be an $n \times n$ correlation matrix whose least eigenvalue is denoted by $\lambda$.
$\Sigma_i'$ be an $(n-1) \times (n-1)$ submatrix of $\Sigma$ obtained by eliminating the $i$-th row ...
- 141
1
vote
0
answers
261
views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
- 31
1
vote
0
answers
125
views
smallest singular value over invertible sub-matrices
Consider the matrix $M = \begin{bmatrix} A & A B \end{bmatrix} \in R^{n \times (n+m)}$, with $A \in R^{n\times n}$, $B \in R^{n \times m}$, $m < n$, $m > 1$, $A$ symmetric positive definite.
...
- 303
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
- 13.2k
1
vote
0
answers
78
views
Family of functions which satisfies $f(\boldsymbol{x}) = 0$ if $\nabla f(\boldsymbol{x})=0$? [closed]
I have a Lagrangian of which I want to find the supremum in the primal variable $\boldsymbol{x}$:
$\mathscr{L}(\boldsymbol{x},\boldsymbol{\lambda})=f(\boldsymbol{x})^T\boldsymbol{a} + \boldsymbol{\...
1
vote
0
answers
47
views
Linear programs [closed]
Can the optimal value of the primal problem of a linear program ever be less then zero?
An example is: minimize $C=2x_1 +3x_2$ Subject to: $3x_1+4x_2 \leq 5$. Obviously, $x_1$ and $x_2$ are free ...
- 11
1
vote
0
answers
93
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
- 867
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
1
vote
1
answer
73
views
minimize number of unique elements in a vector
I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector). Note that I'm not asking for minimization of nonzero elements (rank ...
- 13
1
vote
0
answers
1k
views
Number of different combinations in a 0-1 knapsack problem with integer weights [closed]
My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
- 153