All Questions
480 questions with no upvoted or accepted answers
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
1
vote
0
answers
88
views
On convex quadratic programming clarification
We know convex quadratic programming is in $P$.
Is it also in $P$ if the function of interest is only convex in the domain of interest?
- 13.9k
1
vote
0
answers
149
views
Coordinate descent conditions
The following is quoted from "Bertsekas, D. P. (1999). Nonlinear programming (p. 794). Belmont: Athena scientific".
Convergence of Coordinate Descent: Suppose a function $f$ is continuously ...
- 133
1
vote
0
answers
89
views
Optimization problem with non linear objective and non linear constraint (or upper bounding)
I am tackling the following optimization problem where ideally I would like to maximize (analytically, over $\alpha$) these sorts of quantities, where $n \ll d$ and $d \in \mathbb{N}, \epsilon \in \...
- 141
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
- 13.2k
1
vote
0
answers
806
views
Strong smoothness of Lp norm
I asked this question in math.stackexchange but got no answers (link: https://math.stackexchange.com/questions/2323520/strong-smoothness-of-lp-norm). So I decided to ask this question here. Hope I ...
- 373
1
vote
0
answers
93
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
- 867
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
1
vote
0
answers
49
views
Minimization of convex functions on dense subspaces
I want to consider the Moreau envelope $\psi_j$ of a proper, convex, lower semicontinuous function $\psi$ over a Banach space $V$ on dense (finite dimensional) monotonically increasing subspaces $V_m$,...
- 187
1
vote
0
answers
69
views
Soft: Lagrange Multiplier and Intersection of Thickened Sets
Suppose I have an optimization problem of the form
$$
\inf_{\{x \in \mathbb{R}^d: g(x)=0\}} f(x),
$$
for some convex function $f$ and non-convex l.s.c. function $g$.
Can we reinterpret the ...
- 5,405
1
vote
0
answers
96
views
Infimum of equivalent measures
Suppose I have a functional of the form
$$
F(\mathbb{P})\triangleq \int_{\mathbb{R}^d} \int_{\Omega}f(x,\omega)\mathbb{P}(d\omega)m(dx),
$$
where $m$ is the Lebesgue measure and $\mathbb{P}$ is a ...
- 173
1
vote
0
answers
672
views
Why are SDP generally slow?
This is more of a conceptual question. Don't expect a highly mathematical question. Nonetheless, the questions I pose here often arise in my field (not mathematics).
Usually Semidefinite Programs (...
- 345
1
vote
0
answers
483
views
minimize norm of matrix product
I have the matrix Product $PAP^H$ and I need to minimize $\|(PAP^H)^{-1}\|^2$ (over $P$ and Frobenius norm).
$A$ is a positive definite Hermitian matrix and $P$ has the structure
$$P=\left[\begin{...
- 129
1
vote
0
answers
72
views
Determining when specific gradient descent converges to singular or critical points
In my research on neural networks and learning theory I have recently come across the following problem dealing with gradient descent:
We consider a given column vector $ x=[x_1,x_2,...,x_{d}]^T \...
- 620
1
vote
0
answers
135
views
Intuition for analysis of basic gradient descent variants
I'm currently learning the basic variants of gradient descent for minimizing convex functions under various assumptions, such as Lipschitz, smooth, strongly-convex, ... .
I've found various sources ...
- 997
1
vote
0
answers
123
views
Generalization of concave envelope
Let $g:\mathbb R_+\to\mathbb R$ be a measurable function (which could be supposed to be bounded and Lipschitz if required). Let $\mathcal P$ be the collection of probability measures $\mu$ on $\mathbb ...
- 1,835
1
vote
0
answers
58
views
A possible extension of the information bottleneck principle with added equality constraint on the conditional probability
This question is related to research on Tishby's information bottleneck principle as seen here, the problem at hand is inherently an optimization problem as seen directly on page 7 section 3.2, my ...
- 620
1
vote
0
answers
383
views
(Quasi) convexity of separately convex homogeneous functions
Consider a function $f:\mathbb{R}^n_{\geq 0}\rightarrow \mathbb{R}$ that is separately convex, i.e. such that $\frac{d^2f}{dx_i^2}\geq 0$ for all $i\in \{1,\dots n\}$. Assume also that $f$ is ...
- 379
1
vote
0
answers
481
views
psd condition for matrix completion
The nuclear norm minimization for the matrix completion problem is given by
\begin{align}
\textrm{minimize } \quad &\|X\|_{*}\\
\textrm{subject to } \quad & X_{ij}=M_{ij} \quad \forall (i,j)...
- 221
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
0
answers
46
views
How to regularize to get appropriate sparse solution
I am working on an inverse problem of the form $Ax=b$ where $A$ and $b$ are known and I want to find $x$. I understand $L_1$ regularization and I have applied it to my work. But in addition to $L_1$ I ...
- 495
1
vote
0
answers
354
views
Solution to a system of nonlinear equations using convex conjugate of log sum exp
I need to prove the following result:
There exists a unique solution to the system of equations
$$\alpha = \frac{I^T(\gamma e^{I\beta})}{\sum_{i=1}^{n}\gamma_ie^{(I\beta)_i}}$$
if and only if $\...
- 11
1
vote
0
answers
187
views
Strong Duality of Mixed Integer Linear Program
The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
- 11
1
vote
0
answers
232
views
Semi-convex problem and almost convex problem
I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the ...
- 355
1
vote
0
answers
94
views
About a particular definition of a Hessian of a function of tuples of matrices
Say I have a function $L : (W_1,..,W_{H+1}) \rightarrow \mathbb{R}$ i.e it takes a tuple of $n$ matrices of different dimensions and computes a number from them.
Then I see being defined a ...
- 2,246
1
vote
0
answers
260
views
Nesterov's Methods for minimizing composite functions
There are some methods originally from Nesterov, which accelerates optimization methods, e.g. Nesterov 1983, Nesterov 2003, Nesterov 2005 ( smooth minimization of non-smooth functions), Nesterov 2013 (...
- 121
1
vote
0
answers
64
views
Maximize discrete harmonic function at given point
Let $n>0$, and let $S_n$ denote the discrete square
$S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
- 621
1
vote
0
answers
61
views
Can the extragradient method be computed only based on proximal steps?
As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method converges Structured Prediction via the ...
- 121
1
vote
0
answers
55
views
Separation on discrete set
Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...
- 61
1
vote
0
answers
60
views
Optimizing sum of approximate and exact functions
This is a research question that I had asked in Math.SE about a month ago, but even after putting a bounty on it, I did not get any answers.
I have two real values functions, where one ($g(w;x):\...
- 189
1
vote
0
answers
52
views
Which algorithm is most efficient for a specific QP problem
I have a QP problem of the following kind:
$\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$
s.t. $l\leq \alpha \leq u$
The matrix $M$ is symmetric and positive definite and of ...
- 11
1
vote
0
answers
227
views
Find optimal value for a regularization parameter in generalized eigenvalue problem
Consider the generalized eigenvalue problem :
$ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $
where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices $X$...
- 45
1
vote
0
answers
421
views
Is this QCQP convex or nonconvex?
\begin{equation}
\begin{split}
\min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x
\end{split}
\end{equation}
s.t.
$$
g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\}
$$
$$
g_i(x)=\frac{...
- 11
1
vote
0
answers
168
views
Projecting on a a special polyhedron
Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron
$$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$
Notice that $\mathcal P_X$ is symmetric about the origin.
...
- 6,853
1
vote
0
answers
77
views
Projecting on a convex compact polytope with special form
Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
- 6,853
1
vote
0
answers
115
views
convergence of unconstrained convex optimization
I encounter an optimization problem. The simplified version is like following:
Denote function $F(x):\mathbf{R}^n\rightarrow\mathbf{R}$, where $F(x)$ is a smooth lower bounded convex function (i.e. $...
- 11
1
vote
0
answers
152
views
Well-posedness of gradient flows
For a convex lower-semicontinuous functional on a Hilbert space $I\colon H\rightarrow\mathbb{R}$, it is shown in Evans' PDE that the Hilbert-space-valued ODE
$$\begin{cases}\mathbf{u}'(t)\in-\partial ...
- 123
1
vote
0
answers
82
views
Log convexity for the norm of a vector-valued function
Log convexity of various functions defined on the space of Hermitian matrices plays an important role in matrix analysis and probability theory.
Given $v \in \mathbb{C}^n$, $D$ a diagonal matrix with ...
- 31
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
1
vote
0
answers
120
views
The column generation technique on a Train Unit Assignment Problem [Linear Programming]
I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
- 111
1
vote
0
answers
52
views
Condition for maximizer of convex combination to be expansion mapping
I have $\Pi_n:\mathbb R^{n+1}\rightarrow \mathbb R$ and $F_n:\mathbb R^2\rightarrow \mathbb R$ with $$F_n(x,a)=\Pi_n(x,...,x,a)$$
$$f_n(x)=\operatorname{ArgMax}_{a\in\mathbb R}\{F_n(x,a)\} $$
such ...
- 43
1
vote
0
answers
87
views
Characterization of the maximizer of a function based on a parameter's value
Consider a smooth, continuously differentiable, and jointly concave function $f(x,y,z;a)$, where $x,y$ and $z$ are decision variables and $a$ is a problem parameter.
I have two optimization problems. ...
- 11
1
vote
0
answers
80
views
A version of isotone projection cones
We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...
- 773
1
vote
0
answers
684
views
Proximal mapping of composition with linear operator
Let $A$ be an orthogonal matrix. Then the proximal mapping $prox_{f \circ A}(x)$ can be evaluated efficiently by
$$
(I + \partial (f \circ A))^{-1}(x) = prox_{f \circ A}(x) = A^T prox_{f}(A x),
$$
as ...
- 303
1
vote
0
answers
81
views
Is there a unique tilted measure with specified marginals?
Suppose $\mathcal{A},\mathcal{B}$ are finite sets and $\mu_{A,B}(a,b)$ is a probability measure on the product set $\mathcal{A}\times \mathcal{B}$ so that $\mu_{A,B}(a,b)>0$ for each $a\in \mathcal{...
- 1,269
1
vote
0
answers
126
views
Convex Optimization related problem
Suppose two non-negative convex functions $f$ and $g$ be given.
We want to solve the following optimization
$$\max_{g\leq\epsilon}f.$$
Now suppose that both $f$ and $g$ can be upper-bounded by a ...
- 1,109
1
vote
0
answers
100
views
Changing a nonlinear equality constraint into some conic inequality plus rank constraint
If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
- 33
1
vote
0
answers
110
views
Characterization of the optimal solution in relative entropy minimization
The following optimization problem is related to relative entropy and to the limit of the iterative proportional fitting procedure.
For $1 \leq i,j \leq n$ and fixed $w_{ij} \geq 0$, and fixed $a_i, ...
- 340
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11