**2**

votes

**0**answers

28 views

### In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...

**2**

votes

**0**answers

139 views

### existence of lattice point in polytope

This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...

**2**

votes

**1**answer

311 views

### Why does the LP Formulation of the MST Problem need Topology Constraints?

I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...

**0**

votes

**1**answer

393 views

### Nonconvex optimization problem

I have a nonconvex optimization problem. It is actually optimizing a linear objective function over a set of linear constraints and a set of nonlinear, non convex constraints.
Is this problem ...

**0**

votes

**2**answers

146 views

### Rewrite optimization objective

Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...

**1**

vote

**2**answers

177 views

### Name of operations on two vectors

Suppose we have two vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$.
I could define the mapping
$$
T: \mathbb{R}^n\times \mathbb{R}^m \rightarrow \mathbb{R}^{n\times m}
$$
as follows
$$
T(x,y) = ( ...

**0**

votes

**2**answers

187 views

### positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix

Given that $A$ is a positive semidefinite matrix, $x$ is a vector, $\lambda_0 \in [0, +\infty) $ is a real non-negative number. I want to know the answer to the following optimization problem.
$$
...

**2**

votes

**2**answers

99 views

### LP constraint enconding

I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...

**1**

vote

**1**answer

132 views

### Deducing Linear Inequalities

Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...

**2**

votes

**1**answer

170 views

### Arrangements of hyperplanes

Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form
$$
f(\bar{x})=a_1x_1+\ldots+a_nx_n+b
$$
for some $a_i,b\in\mathbb{R}$.
Suppose we ...

**0**

votes

**1**answer

1k views

### What does “Vertex Solution” mean?

Hello!
I come across the word "vertex solution" in the context
" We can also assume that x and y are vertex solutions,so that the sequence {x,y} remains in a finite set."
Could anybody know any ...

**0**

votes

**0**answers

77 views

### Big eigenvalues of a special stochastic matrix

Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq ...

**6**

votes

**1**answer

922 views

### Inverse of a totally unimodular matrix

A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...

**2**

votes

**1**answer

654 views

### Maximizing supermodular functions

I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...

**2**

votes

**0**answers

47 views

### Put positive polynomial in finite intersection of half-spaces

This is a cross-posting of a MSE question (which did not attract any attention there so far).
Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...

**2**

votes

**1**answer

101 views

### Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?

In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...

**1**

vote

**1**answer

400 views

### Reference Request for Integer factorization with LP/ILP

Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...

**1**

vote

**1**answer

470 views

### Finding a point farthest away from $k$ points in a polygon

There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...

**0**

votes

**2**answers

692 views

### Efficient algorithm finding 'a' solution of system of linear inequalities

I'm working on rational number field $\mathbb{Q}$.
Is there an efficient algorithm finding a solution of system of linear inequalities?
In many computer algebra systems like Sage or Maple,
there ...

**1**

vote

**2**answers

138 views

### complexity of finding optimal matchings of given fixed size

It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...

**1**

vote

**0**answers

796 views

### Robust optimization in matlab using fmincon [closed]

I am trying to implement the following optimization (from this paper) in Matlab using fmincon:
$\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$
where $\Sigma$ is a positive definite ...

**0**

votes

**1**answer

724 views

### Find edge weights that fit given node weights

Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...

**1**

vote

**1**answer

1k views

### Schur complement and negative definite matrices

Hello,
My question regards to the Schur complement lemma. Consider the matrix $M=\left( \begin{array}{cc}
A & B\\\
B^T & C \end{array}\right)
$.
According to the lemma $M\geq0$ iff $C>0$ ...

**11**

votes

**2**answers

863 views

### Is the tensor product of polyhedra a polyhedron?

Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...

**1**

vote

**0**answers

106 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

**1**answer

262 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

**1**answer

836 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

**2**answers

445 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

**2**answers

348 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

**2**answers

644 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

**2**answers

173 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

**1**answer

105 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

**0**answers

94 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

**1**answer

325 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 ...

**0**

votes

**1**answer

3k 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

**0**answers

180 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

**0**answers

72 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

**1**answer

109 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

**2**answers

704 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

**2**answers

483 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

**2**answers

114 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

**0**answers

235 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

**1**answer

289 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

**1**answer

143 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

**1**answer

314 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

**1**answer

1k 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

**2**answers

197 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

**2**answers

2k 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

**2**answers

339 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

**3**answers

940 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
\;\;
...