# Tagged Questions

The tag has no wiki summary.

811 views

### An Interesting Optimization Problem

You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
1k views

### Why are optimization problems called “programming”?

Why are optimization problems often called programs? linear programming geometric programming convex programming Integer programming ...
986 views

### The cone of positive semidefinite matrices is self-dual? (reference needed)

I'm seeking a reference for the following fact. The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar). This result is relatively easy to prove, has been known for a long ...
750 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 ...
1k views

### Sum of difference moduli vs. sum of modulus differences

This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself. Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
241 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 ...
466 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 ...
1k views

### Random Sampling a linearly constrained region in n-dimensions…

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
165 views

### A linear optimization problem on a graph

Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...
771 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: $$\|R-M\|_F$$ Is there a closed form solution for $R$, or is it ...
134 views

A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$: $$\inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in ... 2answers 482 views ### Algorithm for the intersection of a vector subspace with a cone of non-negative vectors Hi, I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of \mathbb{R}^{n} with a cone of vectors with non-negative entries than the ... 2answers 367 views ### Simplified knapsack problem There is a problem that I can not solve. Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ... 2answers 412 views ### Continuous Transportation Problem Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ... 0answers 108 views ### Variant of orthogonal Procrustes problem The orthogonal Procrustes problem seeks a matrix M that minimizes ||AM-B||_F subject to M^TM=I, where M is d\times d and both A and B are n\times d. Geometrically, M rotates a set of ... 4answers 529 views ### efficient way to compute the inversion of the following matrix Hi, there I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an n \times n matrix requires O(n^3). However, for the following special ... 1answer 2k views ### Linear program to maximize the minimum absolute value of linear functions ? I'd like to compute \max_{x,t} t such that \forall i, t < a_i + |x - b_i|. where a_i,\ldots, a_n and b_1,\ldots,b_n are fixed and x \in [0,1]. Can this be solved with a linear ... 2answers 241 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 ... 1answer 98 views ### submatrix of a given size with maximum frobenius norm Let I\subset \{1,2,\ldots,n\}, and let |I| denote its cardinality. Now given a Hermitian matrix \mathbf{A}\in\mathbf{C}^{n\times n}. I am interested in finding the subset I that maximizes the ... 1answer 142 views ### Equivalent method for maximum likelihood estimation of covariance parameters My goal is to estimate the parameters of a covariance matrix \Omega, by maximizing the following log-likelihood function:$$\log L(\vec\tau, \rho, \sigma \mid W, X) = -m\ln(\left | \Omega \right |) ...
256 views

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 ...
479 views

### Infinite Linear Programming

I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
839 views

### Circumference of convex shapes

Here is a puzzle I found in "Mitteilungen der DMV" (roughly "Letters of the German Society of Mathematicians") issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
443 views

### A simple infinite dimensional optimization problem

I'd be grateful for a reference for the following result, which I believe to be true, and should be well-known. Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
433 views

### Sorting a binary matrix diagonal in polynomial time while preserving rows

Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column? For example given ...
354 views

### Efficient algorithm for finding the minima of a piecewise linear function

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by $f(x) = \max_i ( a_i + b_i x )$ We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two ...
80 views

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ...
143 views

### For interior point methods of linear programming, what is the “L” in the computational complexity $\mathcal{O}(n^3 L)$?

My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior ...
534 views

99 views

### sensitivity analysis in conic optimization

I have a conic optimization of the form: $\min_x \langle c, x \rangle$, s.t. $Ax = b$, $x \in K$. Where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a self ...
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}\| = ... 2answers 202 views ### Maximization of a matrix product by iterative methods This might not be very difficult, but I think I may have gotten a little confused. Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ... 1answer 53 views ### Integer point in a non-empty polytope I have a high-dimensional, non-empty polytope$Ax\geq b$sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ... 2answers 118 views ### Survey on Compared Running Time: Ellipsoid Method vs. Simplex Method If you look through papers on the Ellipsoid Method, there is a large agreement, that the Ellipsoid Method, although theoretically polynomial, is in practice way slower than the Simplex Method. ... 1answer 153 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 ... 1answer 574 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 ... 1answer 316 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 ... 0answers 168 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 ... 0answers 223 views ### Linear complementarity problem: principal pivoting algorithm I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book ... 0answers 152 views ### Number of breakpoints in parametric maximum flow problems The parametric maximum flow problem can be formulated asf(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right), $$where all c_{ij}<0 (so that ... 0answers 262 views ### Recovering a piecewise affine function Lets say I have an piecewise affine convex function f(x_1,x_2), on which the following operations are possible: Computing f(x_1,x_2). Computing a subgradient to f at (x_1,x_2) Computing all ... 2answers 181 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 ... 1answer 212 views ### Maximizing linear objective function with absolute values This has be asked on other forums, though couldn't find authoritative answer. I have a linear program over the reals and don't want to introduce integer or binary variables. The objective function ... 2answers 140 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 ... 2answers 252 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 ... 2answers 352 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 ... 1answer 85 views ### a closed form lower bound solution for linear programming Given a linear objective function and a system of linear constraints, is there any known closed form lower bounds for it? to clearly express the problem assume that$z(\mathbf{a,B,c})=\mathop {\inf} ... 1answer 102 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< ...
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$ ...