The tag has no wiki summary.

learn more… | top users | synonyms (1)

1
vote
0answers
101 views

Matrix Minimax problem

I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The ...
3
votes
1answer
212 views

How to implement linear constraints that include several absolute values

Dear all, I am trying to implement a linear constraint that includes several absolute values in the form: Abs(A) + Abs(B) + Abs(C) + Abs(D) + ... = 1 Since the minimization problem includes quite a ...
0
votes
1answer
706 views

Finding linearly independent columns of a large sparse rectangular matrix

I have a problem that necessitates solving a large non-negative least-squares problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols) and nearly binary. However, A is not ...
3
votes
2answers
356 views

Bounding the minimal maximum norm of a solution of a linear system.

I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...
5
votes
2answers
300 views

relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$ \max_j c' x_j $$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
1
vote
2answers
498 views

Nonstandard Hessian approximations in Gauss-Newton

The Gauss-Newton algorithm optimizes functions $$ E(x) = \sum f(x)^2 $$ by approximating f as (locally) linear, in which case the Hessian of $E$ is approximated as $$ H = 2 \sum {J_f}^T J_f $$ Now ...
1
vote
2answers
155 views

Levenberg-Marquadt near the minima for non-zero-residual problems

I'm using the LM algorithm to do gradient descent in a model fitting context. I'm minimizing: $$ c(x) = \sum ( f_i(x) - y_i )^2 $$ I'm noticing that after a few steps when I'm close to the minima, I ...
0
votes
1answer
80 views

Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?

I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise. The other variables in the linear ...
0
votes
0answers
93 views

Gauss-Newton for quotient functions

I'm optimizing a function of the form $$ \sum \frac{ \|\mathbf{f_i}(x)\|^2 }{ g_i(x)^2 + h_i(x)^2 } $$ where $x$ is a real vector, $\mathbf{f}(x)$ is a real vector, and $g(x)$ is a scalar. My first ...
1
vote
1answer
276 views

Results for minimizing the norm w.r.t a unitary matrix

Suppose $x \in \mathbb{R}^n$, $B,U \in \mathbb{R}^n\times\mathbb{R}^n$ and $U$ a unitary matrix. Define $g_{U}(x) = || BUx||$ where $||.||$ is some norm or norm-ish function on $\mathbb{R}^n$ (not ...
-1
votes
1answer
2k views

If then condition on mixed linear integer programming [closed]

Hi all. Let $a$ and $b$ be two real variables such that $0 \le a \le a_{max}$ and $0 \le b \le b_{max}$. I must write the following if-then-else condition with linear inequalities: if $a < ...
0
votes
0answers
179 views

A linear program related question

Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice. Let $\alpha^k \in (\alpha_1^k, ...
0
votes
0answers
71 views

Computing maximum point for minimal function of a family of linear functions

Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such ...
0
votes
1answer
107 views

Cascading minimization problems

Hi all. Suppose I have a linear programming problem on the vector variable $x$ that has many solutions and let $U$ be the set of these solutions. Suppose I have a second LP problem on $y \in U$. ...
0
votes
2answers
578 views

linear programming with OR restrictions

Hi all. I have a linear program with the restriction that every variable can be zero or greater than or equal to a positive constant. That is: minimize: $w^Tx$ subject to: $Ax=b$, $Cx \le d$ and for ...
0
votes
2answers
467 views

Find both maximum and minimum values in linear programming problem

Hi all. I have a linear programming problem where I need to find both maximum and minimum values of the objective function. The optimal points are not relevant. Is there an efficient way to do so?
1
vote
2answers
111 views

LP/QP with not-so-constant linear constaints

I have an otherwise standard LP or PSD QP problem as below: $\min\limits_x {c}' x$ subject to $Ax\leq b$ or $\min\limits_x \frac{1}{2}{x}' Qx + {c}' x$ subject to $Ax\leq b$ the only exception ...
0
votes
0answers
195 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
1
vote
1answer
275 views

Solving a system of linear inequalities

Consider the following system of inequalities: $Ax=b$; $x\geq 0$; A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. How this system can be solved without ...
0
votes
1answer
133 views

SDP Algorithms/ maximally complementary solutions

Hello, I was wondering if there are algorithms for (linear) Semidefinite Programs (SDP) out there, that converge towards a maximally complementary solution, even if strict complementary does not hold. ...
0
votes
1answer
208 views

$\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
2
votes
1answer
986 views

sum of maxima vs the maximum of the sum

Consider the following integer program $$ \begin{align} \max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\ \text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant ...
1
vote
2answers
189 views

what method can I employ to solve this optimization problem which involves \min?

The optimization problem is: maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N ...
2
votes
2answers
1k views

Dual Norm For Sum of 2-Norms

What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}_i \in \mathbb{R}^{m \times n}$ $\|\mathbf{x}\| = ...
1
vote
2answers
285 views

constructing a curve dividing two sets of points

Lets assume I have two sets of points, each characterized as being "A" or "B", respectively, that are in a Euclidean plane. Theoretically these two sets are samplings from a space that has ...
2
votes
3answers
697 views

Efficient Algorithm For Projection Onto A Convex Set

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem: $\underset{\mathbf{p}}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2 \;\; ...
1
vote
0answers
158 views

Consistency of a system of linear equations

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
1
vote
0answers
249 views

Totally Uni-modular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
3
votes
1answer
264 views

Grading a non-graded poset as squeezed as possible

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage). Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...
10
votes
1answer
273 views

Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$. Now add edge-pair ...
0
votes
1answer
126 views

Continuity of Lexicographic Minimum Solution of a parametrized LP problem

Given a parametrized LP problem find x, that minimizes F*x such that Ax <=Bt+D where t is a parameter. And suppose C(t) is a set of all optimal solutions of LP with parameter t. Let x_L(t) be ...
2
votes
1answer
393 views

Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$. In ...
1
vote
1answer
176 views

Covering max flow arcs by arc disjoint paths

Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...
0
votes
1answer
191 views

Is the Simplex Method still polynomial when all inequalities are through the origin?

Hello, I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
1
vote
2answers
451 views

Sherali-Adams relaxation

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...
4
votes
1answer
223 views

Checking if one polytope is contained in another

Hi, I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other. At the moment I am ...
2
votes
1answer
106 views

Design constraint systems over the reals

This question is inspired by the discussion at this problem. Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
2
votes
2answers
699 views

how to model a linear program with step-like cost function in the objective

I have a large linear program with the following details. d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form d1 < d3 < d7 < d23 ...
7
votes
2answers
1k views

How do you tell if a system of linear inequalities has a solution?

A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
3
votes
0answers
828 views

0,1 solution to system of linear integer equations.

I have the following problem: $A x = b$ where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly). $x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
2
votes
0answers
174 views

Could SVD be used to optimize the partial inner-products?

Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with $m-$dimensional coordinates in ...
7
votes
1answer
275 views

Does the Hirsch conjecture hold for $n < 2d$?

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 ...
2
votes
2answers
1k views

Solving a system of equations/inequalities that have trigonometric functions on the left-hand side

Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system? Ex) Find $x,y,\theta \in \mathbb{R}$ that ...
4
votes
1answer
937 views

Closest 3D rotation matrix in the Frobenius norm sense

Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm: \begin{equation} \|R-M\|_F \end{equation} Is there a closed form solution for $R$, or is it ...
1
vote
1answer
182 views

Conditions for differentiability of minima and minimizers of linear functionals?

Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$. For every continuous linear functional $F$ on $B$, define $V(F)=min_{c\epsilon C} F(c)$ and $S(F)= { \lbrace c \epsilon C ...
3
votes
1answer
377 views

Solving for Hamiltonian path with constraints on allowable routes through vertices

Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...
0
votes
1answer
350 views

Minimum distance between two data sets

Suppose we have two sets of data, $X$ and $Y$, each of which contains $10$ positive numbers. Now let us order the data sets $X=\left\{ x_{1},\cdots,x_{10}\right\}$, $x_{1}\ge\cdots\ge x_{10}>0$ and ...
1
vote
0answers
688 views

How to solve simple bilinear equations under extra linear constraints

Hello, This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy: $\lambda_i^T ...
1
vote
1answer
548 views

Can one efficiently optimize over the inverse of matrix?

Hello, I have the following problem: Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...
0
votes
0answers
110 views

sparsest cut always has solution

Hi! How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset. Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...