Questions tagged [linear-programming]

Linear programming is the study of optimizing a linear function over a set of linear inequalities. The Simplex Method, Ellipsoid Method and Interior Point Method are popular algorithms to solve linear programs.

Filter by
Sorted by
Tagged with
1 vote
0 answers
81 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 ...
VS.'s user avatar
  • 1,816
1 vote
0 answers
69 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 ...
Marcelo Pedro's user avatar
0 votes
1 answer
133 views

Linear programming with exponential inequalities and rational variables

If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...
VS.'s user avatar
  • 1,816
2 votes
1 answer
498 views

Intersection of a vector subspace with a cone

Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating ...
Marcelo Pedro's user avatar
1 vote
0 answers
60 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 $$\...
Bob Mullins's user avatar
0 votes
1 answer
186 views

Fractional values in linear programming

Consider the linear programming problem \begin{align} f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1 \end{align}where $p$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
dineshdileep's user avatar
  • 1,371
0 votes
1 answer
295 views

Sub optimal algorithm for linear programming

Consider the linear programming problem \begin{align} f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1 \end{align}where $c$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
dineshdileep's user avatar
  • 1,371
2 votes
0 answers
64 views

Proving the existence of a dual for an infinite linear program

I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
teddy's user avatar
  • 121
0 votes
1 answer
126 views

Maximize function on rotation matrices [closed]

Let $A$ be a fixed 3-by-3 matrix and $Q$ be a rotation matrix whose yaw, pitch, and roll angles are $\phi\in[0,\pi]$, $\theta\in[0,\pi]$, and $\psi\in[0,\pi/2]$, respectively: \begin{equation} Q= \...
Benjamin Techer's user avatar
3 votes
0 answers
159 views

A new "adversarial" Wasserstein distance?

Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...
Gilles Mordant's user avatar
10 votes
2 answers
841 views

Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?

Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
VS.'s user avatar
  • 1,816
2 votes
1 answer
450 views

Odd cycle transversal

Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, ...
Mario Giambarioli's user avatar
1 vote
2 answers
786 views

Integer linear programming (ILP) formulation of connectivity of induced subgraph

Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...
Himanshu Khandelwal's user avatar
2 votes
1 answer
773 views

Interior point of a convex polytope

Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
Davide Papapicco's user avatar
2 votes
1 answer
217 views

Sampling algorithms on convex polytopes

Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
Davide Papapicco's user avatar
0 votes
0 answers
40 views

Minimizing along independent directions, nonlinear programming

Good afternoon, I am studying the book Nonlinear Programming: Theory and Algorithms (by Mokhtar S. Bazaraa, Hanif D. Sherali, C. M.) particularly the Theorem $7.3.5$. I'm not sure I understand this ...
Rusbert's user avatar
  • 173
2 votes
0 answers
47 views

A linear program where coordinate descent works pretty well

I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense: Select any coordinate $j$ and set $...
Sean M. Cook's user avatar
1 vote
1 answer
152 views

Perturbation of the value of a general-sum game at a equilibirium

Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...
Steve's user avatar
  • 1,117
1 vote
0 answers
254 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 ...
Ozzy's user avatar
  • 383
6 votes
1 answer
602 views

Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers

Let $a(n)$ be the Dirichlet inverse of the Euler totient function: $$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$ and let the matrix $T(n,k)$ be: $$T(n,k)=a(\gcd(n,k)) \tag{2}$$ It has been ...
Mats Granvik's user avatar
  • 1,133
1 vote
1 answer
130 views

find a PSD matrix that that verify matrices sum of equality

$A $, $ C$ $(n,n)$ are symmetric PSD matrices, $B$ is PD symmetric matrix, and $H_i$ $\; $ $(i=[1,m])$ represent $ m $ complex matrices. $H_i$ are all one rank matrix Our objectif is to find ...
hichem hb's user avatar
  • 367
2 votes
2 answers
378 views

Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$

I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...
diracdeltafunk's user avatar
0 votes
1 answer
354 views

Computing discrete optimal transport

I am trying to find a combinatorial approach to solve the following optimization problem. \begin{align} &\max_{x_{ij}} C_{ij} x_{ij}, \\ &\text{such that},\\ &\sum_{j} x_{ij} \leq r_i~\...
Soumya Basu's user avatar
4 votes
1 answer
202 views

Reference: Packing under translation is in NP

I am looking for a reference for a result that I am aware of. Let me describe the result. Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP time, if $p_1,\ldots,p_n$ can be ...
Till's user avatar
  • 469
6 votes
1 answer
648 views

If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?

I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
ArtificiallyIntelligent's user avatar
1 vote
0 answers
139 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\...
0xbadf00d's user avatar
  • 161
0 votes
1 answer
96 views

Finding dual of a scheduling LP formulation

Suppose I have an LP formulation as such: $\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$ $\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$ $\sum\limits_{j}x_{ijt}\leq ...
user_1_1_1's user avatar
0 votes
1 answer
103 views

How do I solve this integer programming problem with non convex constraints?

I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place. I have an optimization problem like this ...
Aaron_Geng's user avatar
0 votes
0 answers
84 views

How can we analytically solve this max-sum-min problem?

Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\...
0xbadf00d's user avatar
  • 161
0 votes
1 answer
59 views

Variant of the linear programming problem

Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem: $$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$ $$s.a....
Rusbert's user avatar
  • 173
2 votes
0 answers
133 views

Generalization of Farkas' Lemma to Hermitian Matrices

I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...
Frederik vom Ende's user avatar
0 votes
0 answers
35 views

Converting a vector in a cone statement to inequality constraints

I would like to convert the following condition for $x$ \begin{align} x = N \lambda, \lambda \geq 0 \end{align} to a pure linear inequality form, i.e. find an $L$ and eliminate $\lambda$ \begin{...
Jacob Di's user avatar
1 vote
0 answers
24 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\...
Jonathan Lee's user avatar
6 votes
1 answer
661 views

Is Binary Integer Linear Programming solvable in polynomial time?

The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
aroyc's user avatar
  • 221
3 votes
1 answer
1k views

Finding the closest special orthogonal matrix in Frobenius norm sense

Given a $3\times3$ matrix $M$, if we would like to get the closest $\mathrm{SO}(3)$ matrix $R$ that minimizes \begin{equation} \|R-M\|_F \end{equation} then $R$ = $UV^{T}$ where $U$ and $V^{T}$ are ...
Karnik Ram's user avatar
1 vote
1 answer
418 views

Sufficient conditions for a system of linear inequalities to admit a solution

I am looking for sufficient conditions such that a system of linear inequalities of the type $A x >0$ admits a non-negative solution $x \in \mathbb{R}^n_+$. I know a few properties of the $m \times ...
Peter's user avatar
  • 355
3 votes
1 answer
269 views

Uniqueness of l1 minimization

Let $A \in \mathbb{R}^{m \times n}$. Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to $\...
love_backups's user avatar
1 vote
0 answers
167 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} &...
Mats Granvik's user avatar
  • 1,133
0 votes
0 answers
228 views

What do square roots as minimums have to do with Harmonic numbers?

In an earlier question where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at s=1 of a certain Dirichlet series: $$\Lambda(m)=\lim_{s\to 1+}\zeta(s)\sum_{d\mid ...
Mats Granvik's user avatar
  • 1,133
3 votes
0 answers
164 views

Uniqueness of projection under spectral norm

I am considering $$ \min_{M\in \mathcal{M}} \|X - M\|:=x \neq 0, $$ where $X$, $M$ are $m\times n$ matrices, $\|\cdot\|$ is spectral norm and $\mathcal{M}$ is a matrix subspace. I wonder to what ...
Doris's user avatar
  • 131
5 votes
1 answer
257 views

On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights

Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1), the minimum weight perfect matching problem on a complete graph $G$ with even number of vertices and weight $w:E(G)\to \...
Mikhail Ostrovskii's user avatar
3 votes
1 answer
211 views

What importance does the Hirsch conjecture have to Simplex Complexity?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$. After being open for decades, Francisco Santos has ...
VS.'s user avatar
  • 1,816
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$? ...
Basca's user avatar
  • 19
2 votes
1 answer
240 views

Does quantifier elimination help here?

Suppose we have a quantified linear program $$\exists z_1,\dots,z_{poly(n)}\in\mathbb R$$ $$\exists u_1,\dots,u_n\in\mathcal P\cap\mathbb R^m$$ $$\forall v_1,\dots,v_n\in\mathcal P\cap\mathbb R^m$$ $$...
VS.'s user avatar
  • 1,816
3 votes
1 answer
149 views

A question about polytopes related to linear programming

Given linear functions $f_1({\bf x}),\dots,f_n({\bf x})$ on ${\bf R}^m$, let $K = \{(a_1,\dots,a_n) \in {\bf R}^n:$ the $n$ halfspaces $\{{\bf x}: f_i({\bf x}) \leq a_i\} $ have nonempty intersection$\...
James Propp's user avatar
  • 19.4k
1 vote
0 answers
120 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 ...
VS.'s user avatar
  • 1,816
0 votes
1 answer
38 views

Gluing simplices through a common point/ realisation of a convex simplicial polytope

Given $m≥d+1$ a positive integer, is it always possible to find m d-dimensional simplices $\Delta_i=\mathrm{Conv}(M,V_{i,1},…,V_{i,d})$ such that 1) they all share the common vertex M 2) the ...
giulio bullsaver's user avatar
1 vote
1 answer
126 views

Quantifier elimination and where is this quantified convex program in the polynomial hierarchy?

I have a quantified convex program of the form that I need to solve $$\exists(x_{1,1},\dots,x_{1,n})\in\mathbb R^n\quad\forall(x_{2,1},\dots,x_{2,n})\in\mathbb R^n$$ $$\vdots$$ $$\exists(x_{2t-1,1},\...
VS.'s user avatar
  • 1,816
7 votes
2 answers
816 views

Formula for volume of a convex polytope

So I've been searching around the internet for some answers to this, but I currently have a set of linear constraints: $Ax = b, Cx \le d$ for matrices $A \in \mathbb{R}^{n \times m}$, $b\in \mathbb{R}^...
Erik's user avatar
  • 81
1 vote
0 answers
21 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 ...
Tom Solberg's user avatar
  • 3,910

1 2
3
4 5
10