All Questions
1,019 questions
1
vote
1
answer
1k
views
Is minimum of convex envelope the same as minimum of the original function?
Hello everyone my question is:
$Question:$ Consider a function $f:X \rightarrow \mathbf R$ where $X$ is a convex subset of $\mathbf{R}^n$. The convex envelope of $f$ over $X$ is defined as the ...
- 11
0
votes
1
answer
2k
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 ...
- 103
5
votes
2
answers
2k
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 ...
- 191
5
votes
2
answers
888
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 ...
- 373
2
votes
0
answers
1k
views
Definition and Convergence of Iteratively Reweighted Least Squares
I've been using iteratively reweighted least squares (IRLS) to minimize functions of the following form,
$J(m) = \sum_{i=1}^{N} \rho \left(\left| x_i - m \right|\right)$
where $N$ is the number of ...
- 121
1
vote
2
answers
1k
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 ...
- 561
0
votes
1
answer
179
views
Is these two optimization problems share the same solution?
Hello all,
I am dealing with some SDP optimization, and I come across the following problem.
The optimization problem is given by
\begin{aligned}
&\operatorname*{min}_{t_1,\ldots,t_m,X}\ \sum ...
- 43
1
vote
2
answers
444
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 ...
- 561
1
vote
1
answer
2k
views
Question regard checking convexity by "restriction to any line that intersects the function domain"
Hello all,
I have a question (probably stupid one) about the fact that " A function is convex if and only if it is convex when restricted to any line that intersects its domain".
In Stephen Boyd and ...
- 43
2
votes
1
answer
126
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 program,...
- 121
0
votes
1
answer
4k
views
Is a jointly convex function of x and y convex as a function of x when y=z(x)?
Hi,
Suppose that $x \in R^m, y \in R^n, z(x) \in R^n$, and $f(x,y)$ is convex in $(x,y)$.
Is $f(x,z(x))$ a convex function in $x$ for arbitrary continuous functions $z(x)$?
Thanks!
- 13
0
votes
0
answers
103
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 ...
- 561
2
votes
1
answer
2k
views
Proving that a specific function is quasiconvex
Hello all,
Assume we have a sequence of quasiconcave functions (in $X$) denoted by $f_{i,j}(X)$ for $i,j = 1,\ldots,n$. Denote by $F(X)$ the $n\times n$ matrix whose $(i,j)$ entry is the function $f_{...
- 43
1
vote
1
answer
769
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 ...
- 322
0
votes
0
answers
194
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, \alpha_2^...
- 769
0
votes
0
answers
79
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 that:...
- 11
0
votes
1
answer
130
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$. ...
- 57
3
votes
2
answers
10k
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 ...
- 57
0
votes
2
answers
891
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?
- 57
1
vote
2
answers
134
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 ...
- 11
0
votes
0
answers
783
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 ...
3
votes
1
answer
533
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 ...
- 221
0
votes
1
answer
205
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.
...
- 1
0
votes
1
answer
504
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 ...
- 11
2
votes
1
answer
6k
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 c_j,&...
- 21
1
vote
2
answers
242
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 \log\left(a_{2,i}+\frac{b_{2,i}}{c_{2,i}+d_{2,i}x_i}\...
- 764
4
votes
2
answers
4k
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
660
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 ...
- 11
2
votes
3
answers
2k
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
\;\;
\...
2
votes
0
answers
230
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 ...
- 221
1
vote
0
answers
628
views
Totally unimodular 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 ...
- 11
12
votes
2
answers
752
views
Geometric applications of Ekeland's variational principle
I'm looking for geometric applications of Ekeland's variational principle in order to see it at work in a context I'm familiar with. Let me recall the principle itself:
Definition. Let $(X,d)$ be a ...
- 13.5k
3
votes
1
answer
347
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 ...
- 33.8k
10
votes
1
answer
411
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 ...
- 37.7k
30
votes
4
answers
4k
views
Elementary applications of Krein-Milman
This is a cross-post from MSE: Elementary applications of Krein-Milman. I'm starting to suspect that the question just doesn't really have a great answer, it's worth a try.
Recall that the Krein-...
0
votes
1
answer
226
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 ...
- 29
2
votes
1
answer
848
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 ...
- 85
1
vote
1
answer
241
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 ...
- 2,966
5
votes
2
answers
2k
views
Does the minima of a sequence of convex convergent functions converge?
Suppose $f_1,f_2,\ldots $ is a sequence of convex functions that converges to a continuous convex $f$. Let $x_1^*,x_2^*$ be their respective (not necessarily unique) minima, and let y be a minima of $...
- 323
3
votes
0
answers
254
views
Ways to establish equality of measures on locally compact spaces
Let $M$ be a locally compact space and $\mu$ be some probability measure on $M$. Let $y^\ast \in M$, $f(x,y)$ be a real continuous bounded function $M \times M \to \mathbb{R}$. Consider an equality
$$
...
- 1,329
0
votes
1
answer
456
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, ...
- 693
3
votes
2
answers
2k
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 ...
- 113
0
votes
0
answers
228
views
On the remarkable property of the concave function's level sets
Consider a smooth function $f(x) \colon \mathbb{R}^2_+ \to \mathbb{R}_+$ such that $f$ is concave and positively homogeneous of order one. Consider a linear transform $P$ given by matrix
$$
P = \...
- 1,329
6
votes
1
answer
761
views
Checking if one polytope is contained in another
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 ...
- 491
2
votes
1
answer
137
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 ...
- 30.1k
3
votes
2
answers
3k
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 (...
- 31
10
votes
2
answers
3k
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.
- 693
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
- 149
3
votes
0
answers
220
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 ...
- 131
2
votes
1
answer
3k
views
Sufficient conditions for gradient descent convergence
I have an unconstrained optimisation problem with convex objective function $f(x)$. Suppose I have access only to some function of the gradient $\hat{\nabla}= g(\nabla f)$, and I take gradient steps ...
- 561