All Questions
1,234 questions
3
votes
1
answer
132
views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 41
1
vote
0
answers
29
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
-2
votes
0
answers
24
views
Conditions for a cubic function to be quasiconcave or quasiconvex [closed]
I would like to understand under what conditions a cubic function $f(x)=ax^3+bx^2+cx+d$ can be considered quasiconcave or quasiconvex. Specifically, I am interested in finding conditions on the ...
- 13
1
vote
1
answer
82
views
Solution to a quadratically constrained quadratic program with unit ball constraint
I am working on a quadratically constrained quadratic program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$
$$ \text{subject to} \qquad x^{T}x \leq 1 $$
where $P \in S^{++}_{...
- 13
0
votes
0
answers
37
views
Bounding the error of a truncated moment problem
Let $\{x_{i}\}_{i=1}^{\infty}$ be a non-increasing sequence of non-negative real numbers, and let $\{y_{j}\}_{j=1}^{B}$ be a non-increasing sequence of non-negative real numbers, where $B$ is a finite ...
- 433
0
votes
0
answers
39
views
Optimizing over convex polynomials
I have a minimization problem which reads $\min\limits_P J(P)$, where the minimum is over convex polynomials in $n$ variables, with degree at most $d$, and $J$ is a function taking polynomials as ...
- 101
2
votes
1
answer
91
views
Does approximately null gradient imply approximately global minimum for convex functions?
Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ be a non-negative and differentiable convex function which vanishes in a non-empty convex set $\Omega$ - possibly unbounded. Usually, when one ...
- 225
0
votes
0
answers
30
views
Question on the closed proper convex functions
I'm confused with the definition of the closed proper convex functions when reading the paper
https://people.orie.cornell.edu/aslewis/publications/00-dykstras.pdf
It appears that, when a function $f$ ...
- 1,389
1
vote
0
answers
48
views
What makes the generalized projection different than metric on a Banach space?
I have came across the notion of generalized projection in Banach spaces, introduced by Ya. Alber and has seen many iterative algorithms being solved by using this projection. It helps in finding the ...
- 85
0
votes
0
answers
35
views
Describing the boundary of the feasible direction cone to a convex open subset of $\mathbb{R}^n$ at a boundary point: connection via subdifferential?
Let $U\subset \mathbb{R}^n$ be a convex, open set with nonempty boundary. Let $x_0\in \partial{U}.$ We can describe $U$ locally near $x_0$ as a super level set of a suitable continuous concave ...
- 1,465
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
1
vote
0
answers
29
views
Change in active constraints when perturbing the objective of a QP
Suppose I have a quadratic program (with positive semidefinite cost matrix) with affine (polytopic) constraints. It is known that the solution to this is piecewise affine, with the ``pieces'' defined ...
- 11
4
votes
1
answer
171
views
Maximizing trace subject to two equality constraints
I am looking at the following optimization problem
$$\begin{align}
\underset{{\bf X}}{\text{maximize}} \qquad&\mathrm{tr}({\bf AX})\\
\text{subject to} \qquad& \mathrm{tr}({\bf X}) = 1,\\
&...
- 43
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
0
votes
1
answer
57
views
Self-concordant barrier for the epigraph of $f(x,y) = x^p y^{1-p}$?
The problem
Assume $p > 1$. Consider the function
$$f(x,y) = x^p y^{1-p}, \qquad x,y > 0.$$
Note that
$$
f'' = p(p-1)x^{p-2}y^{-1-p}
\begin{bmatrix}
y \\ & x
\end{bmatrix}
\begin{bmatrix}
1 &...
- 981
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
0
votes
1
answer
236
views
Solving a 0-1 quadratic matrix inequality
I am working on a binary optimization problem. So far I have derived the following constraint functions.
\begin{align}
\begin{bmatrix} \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^...
- 11
1
vote
0
answers
46
views
Intuition for proximal point method using L2 regularization
To minimize a function $f$, the proximal point method is defined as
$$x_{k+1} := \operatorname*{argmin}_x f(x) + \frac{1}{2\eta}\|x - x_k\|^2.$$
What's the intuition for why we want to use L2 ...
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
1
vote
1
answer
60
views
Optimal transport for sum of two costs
Let $X$ be a finite set and $\sigma_0$, $\sigma_1$ two fixed measures on $X$ with $\sigma_0(X)=\sigma_1(X)$. A transportation plan is a measure $\mu$ on $X\times X$ whose projections on the first and ...
- 1,074
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
0
votes
0
answers
69
views
Degree of reflectional symmetry of (unbounded) convex polyhedra in Euclidean spaces
Let $U \subset \mathbb{R}^m$ be an open domain. I'm trying to come up with a measure of its degree of reflectional symmetry and I have a question. The post in two-part, where in PART I I introduce the ...
- 1,465
7
votes
0
answers
249
views
Proving this function is convex
Let $C$ be a symmetric positive definite matrix such that $0\leq c_{ij} \leq 1$, $c_{ii}=1$, and define $f$ as $$f(x)=\sum_{i}x_{i}\log(\sum_{j}c_{ij}x_{j})$$ for positive vectors $x$ (in fact let's ...
- 4,049
1
vote
0
answers
39
views
In search for optimal solution for a minimization problem
I am trying to solve the following optimization problem:
$\begin{align}\min_{\mathbf{c}_{k}} \sum_{k=1}^{K}\frac{q_k}{c_k} \\
\text{s.t. } c_k &\geq t_k \quad \forall k \tag1\label1 \\
\sum_{k=1}^{...
1
vote
0
answers
143
views
Integer points inside the high-dimensional ball (asymptotics)
Let $N(\alpha, n)$ denote the number of integer points inside the origin-centered ball of radius $\alpha \sqrt n$ in $n$ dimensions, where $\alpha \in (0,\infty)$ is some fixed constant. Precisely:
$$...
- 435
0
votes
0
answers
52
views
What are the injective embeddings of R^d into the cone of (semi-) positive definite matrices of dimension d?
How can we characterize the set of all injective functions from $\mathbb{R}^d$ to the set of all symmetric positive definite matrices of dimension d?
- 109
1
vote
0
answers
73
views
Convexity and subdifferential monotonicity
Do you know any reference where I can find some results in this sense:
Consider $W:K\to [0,\infty)$ is a functional defined on a convex cone $K\subset X$, where $X$ is a Banach space. Then the ...
- 1,759
1
vote
0
answers
41
views
Is there any software package to find the vertices of convex polytope where the inequality constraints are bounded by variable?
I know of this package lcon2vert that computes vertices from given inequality and equality constraints describing a bounded polyhedron. Here the bounds of constraints only accept numerical values, i.e....
1
vote
1
answer
63
views
Question on the relation between the Lagrangian Multiplier $\mathcal{L}=r+\lambda g(r,\theta_1,\dotsc,\theta_{N-1})$ and the Hessian of $r$
I want to minimize the radius $r=\sqrt{x^2_1+x^2_2+\dotsb+x^2_N}$, with the constraint $g(r,\theta_1,\dotsc,\theta_{N-1})=0$. Here $g(r,\theta_1,\dotsc,\theta_{N-1})$ is a function defined in the $N$-...
- 375
13
votes
0
answers
710
views
Minimizing total variation under constraint
For $p\in[0,1]$, we write $\mathrm{Ber}(p)$
to denote the Bernoulli measure on $\{0,1\}$;
that is, $\mathrm{Ber}(p)(0)=1-p$,
$\mathrm{Ber}(p)(1)=p$.
For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]...
- 6,541
1
vote
0
answers
45
views
Inequality Involving Concave Monotonic Function
Assume that $ f: \mathbb{R} \to \mathbb{R}_+ $ is a concave, non-decreasing and positive function. Let $\mathbb{X}$ be a finite set consisting of $ 0\leq x_1 \leq x_2 \leq x_3 \leq \ldots \leq x_n$. ...
0
votes
0
answers
51
views
Minimizer of forward and reverse Kullback-Leibler divergence with sum constraints on marginals
Consider minimization of the Kullback Leibler divergence between two discrete distributions $p$ and $q$:
\begin{align*}
D_{KL} \left( p \parallel q \right) = \sum_i p_i \log \left( \frac{p_i}{q_i} \...
2
votes
0
answers
58
views
An s-convex function lying between two convex functions
Let $f: \mathbb R_{+} \to \mathbb R_{+}$ be an $s$-function in the second sense, i.e.,
$$ f(\lambda x +(1-\lambda)y) \leq \lambda^s f(x) +(1-\lambda)^s f(y)$$ for every $\lambda \in (0,1)$. Assume ...
- 55
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214
0
votes
0
answers
54
views
How to deal with minimizing a flat objective function
Problematic (Debiased Sinkhorn barycenter, proposed by H.Janti et al.): Let $\alpha_1, \ldots, \alpha_K \in \Delta_n$ and $\mathbf{K}=e^{-\frac{\mathrm{C}}{\varepsilon}}$. Let $\pi$ denote a sequence ...
- 121
1
vote
0
answers
99
views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved ...
- 990
0
votes
1
answer
150
views
When are infimal convolutions contractions?
Let $X$ be a separable Fréchet space and $\varphi,\psi:X\to \mathbb{R}$ be a lower semi-continuous and convex function with $\psi$ bounded below and coercive. Consider the infimal convolution
$$
\...
- 364
0
votes
0
answers
56
views
How explicit the optimiser of this optimisation problem can be?
Provided the given parameters as follows :
$\mu\in\mathbb R, \sigma\in\mathbb R_+$ are constant, $\kappa, r, \alpha, \beta: \mathbb R_+\to\mathbb R_+ $ are measurable functions such that $\kappa(y)\...
- 1,334
7
votes
2
answers
178
views
Separating domains in $\mathbb{R}^{2n}$ by a real algebraic variety
Suppose $\Omega_1$ and $\Omega_2$ are two disjoint unbounded domains in $\mathbb{R}^{2n}$, $n \in \mathbb{N}$. Can there be conditions on $\Omega_1$ and $\Omega_2$ so that these two domains can be ...
- 171
0
votes
0
answers
115
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
6
votes
1
answer
234
views
Stopping criteria for damped Newton iterations with backtracking line search
Are there better criteria than the Armijo criterion for damped Newton iteration with backtracking line search, when the objective is standard self-concordant? (See Boyd and Vandenberghe.)
Let $F(x)$ ...
- 981
1
vote
0
answers
79
views
Touring a sequence of convex polygons with minimal energy
There is a known problem of touring a sequence of $n$ polygons: given a starting point $s$, an ending point $t$ and a sequence of polygons $P_1,\dots,P_k$ with a total of $n$ vertices, find points $...
- 177
0
votes
0
answers
56
views
Convex optimization of the Lovász extension of a submodular function
I have a finite set of $n$ elements $A$, and a submodular function $f:2^A\rightarrow R$.
Let $g:[0,1]^n\rightarrow {R} $ be the Lovász extension of $f$.
I want to solve the following optimization ...
- 107
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 151
0
votes
0
answers
72
views
Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX
I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
- 43
6
votes
0
answers
48
views
Strengthening the Kovner-Besicovich theorem: Does every unit-area convex set in the plane contain a centrally symmetric hexagon of area $2/3$?
The Kovner-Besicovich theorem states that every convex set $S$ in the plane contains a centrally symmetric subset $C$ of at least $2/3$ the area of $S$, and that this bound is sharp for triangular $S$....
- 3,068
0
votes
0
answers
38
views
Approximate local minima for sum of inverse trigonometric functions
Let $\{a_1, a_2, ..., a_N\} \in [0, 1[^N$, I would like to approximate the minimum of the function
$$f(x) = x \sum_{i=1}^N \left(\sin(x)^2 - \sin(a_i x)^2 \right)^{-2} $$
in the domain $x \in {]0, \...
- 1
2
votes
1
answer
170
views
Equivalence of minimizing trace and determinant over matrix quadratic form in multivariate regression
Consider the multivariate regression model
$$Y = XB + E$$
where $Y$ is $n \times p$ and corresponds to the dependent variables, $X$ is $n \times k$ and corresponds to the independent variables, $B$ is ...
0
votes
0
answers
40
views
Iterating partially-unconstrained optimization with projection
Let $f:H\to \mathbb{R}$ be a strictly convex Fréchet differentiable, coercive function on a separable Hilbert space $H$ and let $C_1,C_2\subseteq H$ be closed and convex.
I want to optimize
$$
\tag{(A)...
- 5,405