Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
839 questions
2
votes
0
answers
614
views
Lipschitz continuity of solution set mapping of a parametric convex optimization problem
I have a parametric convex optimization problem:
\begin{array}{cl}
\underset{x}{\text{minimize}} & f\left(x,z\right)\\
\text{subject to} & g\left(x\right)\leq0
\end{array}
where $x$ is the ...
- 21
2
votes
1
answer
250
views
Circumscribed ellipsoid of minimum Hilbert-Schmidt norm
Let $K\subseteq \mathbb{R}^n$ be a full-dumensional convex body. The Löwner ellipsoid of $K$ is the unique ellipsoid of smallest volume containing $K$. My question is about a related object: the ...
- 757
-1
votes
1
answer
73
views
Determining the sign of each element of the optimal of a strict convex function
The problem is:
Let $\vec{x}\in\mathbb{R}^d$ be the variable and $f(\vec{x})$ be a scalar function that is globally strictly convex in $\mathbb{R}^d$. We assume the unique optimum of $f$ to be finite(...
- 54.2k
1
vote
1
answer
1k
views
Question on convex optimization and dual norms [closed]
I have the following questions about dual norms :
How do you prove that the dual of the dual norm is in fact the original norm?
This is what I have so far:
If I have $||y||_* $ as the norm dual of ...
- 28.6k
2
votes
2
answers
799
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. ...
- 151k
3
votes
1
answer
2k
views
Fast algorithm for maximizing smallest eigenvalue of linear combination of hermitian matrices
I have an engineering back ground. Due to work, I came across this problem
\begin{align}
&\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\
s.t.~&\left(\mathbf{A}_0+\sum_{i=1}^{K}y_i\mathbf{A}_i\...
- 1,590
1
vote
0
answers
182
views
Checking feasibility with eigenvalue and linear constraints
Is there an efficient algorithm to check the simultaneous feasibility of linear and eigenvalue constraints? For example, given $ \lambda_1 \ge \lambda_2 \ge 0$, is the following problem efficiently ...
- 563
1
vote
0
answers
196
views
Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method
I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...
- 111
1
vote
0
answers
1k
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 ...
CommunityBot
- 1
3
votes
1
answer
1k
views
optimization over positive semidefinite matrices
I wonder what is the most explicit characterization that can be given for the solution to the ($N$-dimensional) problem of maximizing the criterion
$$
-\textrm{trace}[AS^{-1}] - b^\top Sb
$$
over ...
- 79.9k
1
vote
2
answers
229
views
Feasibility of a given set of homogenuous nonconvex quadratic inequality constraints
Let $C_1$,$C_2$,...$C_N$ be $M \times M$ indefinite hermitian matrices. What can we say about the following quadratic constriants
\begin{align}
w^{H}C_1w>0 \\\
w^{H}C_2w>0 \\\
...~~~~~~~~~~ \\\
....
CommunityBot
- 1
4
votes
2
answers
359
views
A certain type of constrained Rayleigh-Ritz ratio
Let $\mathbf{A_1}$ and $\mathbf{A_2}$ be two hermitian matrices. Consider the problem
\begin{align}
\max_{\mathbf{u}^H\mathbf{u}=1}~\mathbf{u}^H\mathbf{A}_1\mathbf{u} \\\
\mathbf{u}^H\mathbf{A}_2\...
- 27.5k
2
votes
2
answers
2k
views
convergence of the infima of convex functions
Can one give a reference to a result like this:
If a sequence of convex functions $f_{n}$ on $\mathbb{R}$ converges pointwise to a non-monotonic function $f$, then $\displaystyle\inf_{\mathbb{R}...
- 128k
1
vote
0
answers
436
views
Min of a real-valued Fourier transform
Let $P$ be a compact, convex, symmetric, $d$-dimensional body in $\mathbb R^d$, and let $\mu$ be a (necessarily) symmetric probability measure on $P$, so that
$\mu_P(x) = \mu_P(-x)$, for all $x \in \...
- 623
0
votes
2
answers
244
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 ...
- 3,934
2
votes
0
answers
168
views
Recovering a partition from spectral properties of the graph Laplacian
Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...
- 500
0
votes
0
answers
81
views
convexity of two linear spaces connected by convex nonlinear equality constraints
If there are two sets of linear constraints in different variables, Ax <= b with x_l <= x <= x_u and Cy <= d with y_l <= y <= y_u, and a set of equality constraints of a specific non-...
- 1
1
vote
1
answer
137
views
Constrained minimum maximal distance.
Let $C$ and $D$ be two convex sets. And suppose $C\cap D\neq \emptyset$. Let $x^*$ is the solution to the optimization problem:
$$\min_{x\in C} \max_{y \in D} |x-y|^2$$
Is it true that $x^* \in D$. ...
CommunityBot
- 1
0
votes
0
answers
52
views
Dense Matrix Estimation
I have a matrix $X \in \mathbb{R}^{m\times n}$ and I want to estimate it with a dense matrix $Y^{m\times n}$ such that $Y$ is still close to $X$ in some distance measure. Is this doable in a ...
- 137
2
votes
2
answers
315
views
On a version of gradient descent
I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has Lipschitz constant $M$ and considers the scheme
$$ x(t+1) = x(...
CommunityBot
- 1
0
votes
0
answers
104
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 |\lambda_2|(M)....
- 105
1
vote
1
answer
172
views
Regularizing a Convex function with itself
Hi,
This is a problem that has being bothering me the last few days.
Assume a convex function $f(x): {\mathbb R}^n \rightarrow {\mathbb R}$ with a unique minimizer $x^{\star}$. Now consider the ...
- 895
2
votes
0
answers
242
views
Quadratic optimization with parameter in constraint
Disclaimer: I posted the same question on math.stackexchange. However, the FAQ suggests to post research-level questions in this forum.
Question: Given a function $q: \mathbb R^{N\times N}\mapsto \...
CommunityBot
- 1
5
votes
1
answer
3k
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 ...
0
votes
0
answers
145
views
The role of subgradient in programming with nonsmooth functions
It is obvious that there is similarity between subgradient and gradient. The subgradient of smooth functions is reduced to gradient. I have two questions.
The first is does there exist subgradient ...
- 173
3
votes
1
answer
244
views
Is the Binomial Expectation of a Multivariate Convex Function Convex in the Vector p?
Let $\mathbf{p}=(p_1,\dots,p_m)$ be a vector in $[0,1]^m$ and let $\mathbf{X}=(X_1,\dots,X_m)$ be a vector of independently-distributed binomial random variables such that $X_i\sim \text{Binom}(n,p_i)$...
CommunityBot
- 1
0
votes
1
answer
654
views
minimization of a function when the feasible set is an unbounded cone
I have the following semi-infinite programming problem: I need to minimize a strictly convex real-valued function $f:\mathbb R^n\to\mathbb R$ subject to infinite linear constraints. I know in advance ...
- 3,934
1
vote
1
answer
113
views
Expected rank - computable approximations
I'm interested in finding the expected rank of some random matrix $A$ (I don't want to specify its distribution right now, since my question makes sense in general).
Computing $\mathbb{E} \ \mathrm{...
- 28.6k
4
votes
1
answer
2k
views
lipschitz constant of a multivariate function
I have a function $f:\mathbb{R}^{50} \rightarrow \mathbb{R}$ and I need to compute the Lipschitz constant of $f$ to solve an optimization problem using a specific algorithm. Does any one have ...
- 28.6k
9
votes
2
answers
768
views
On the convexity of element-wise norm 1 of the inverse
Question first asked on math.stackexchange here: https://math.stackexchange.com/questions/317209/on-the-convexity-of-element-wise-norm-1-of-the-inverse
On the convexity of element-wise norm 1 of the ...
CommunityBot
- 1
1
vote
1
answer
808
views
Is unconstrained integer convex optimization problem NP-hard?
Does anyone know a reference to the answer if unconstrained integer convex optimization problem (i.e. $\min_{x\in \mathbb{Z}^N} F(x)$, $F$ is convex and $N$ is NOT fixed) is NP-hard?
Thank you in ...
CommunityBot
- 1
2
votes
1
answer
512
views
How to Find a Matrix Closest to a Given One Under Certain Constraints
I was reading a paper about BFGS and met the following problem:
$\min_B \|B-B_k\|$, s.t. $B=B^{\top}, Bs_k=y_k, s_k^{\top}y_k>0$ and $B$ is positive definite. Here $B_k$ is a symmetric positive ...
CommunityBot
- 1
3
votes
1
answer
4k
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$ ...
- 155
1
vote
1
answer
141
views
Numerical optimisation for multivariate Gaussians
Hi,
I want to calculate
$
f_{\mathbf x}(x_1,\ldots,x_k)\, =
\frac{1}{(2\pi)^{k/2}|\boldsymbol\Sigma|^{1/2}}
\exp\left(-\frac{1}{2}({\mathbf x}-{\boldsymbol\mu})^T{\boldsymbol\Sigma}^{-1}({\mathbf x}...
- 28.6k
7
votes
0
answers
209
views
Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently
Hi,
my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$.
The matrix $C$ is huge ($n$ up to a ...
CommunityBot
- 1
0
votes
1
answer
222
views
Minimal point of the intersection of convex sets.
I am trying to find out if there is any known result in convex optimization that implies the following statement:
"A minimal point of the intersection of $N > 2$ convex sets in $\mathbb{R}^2$ is ...
- 73.2k
2
votes
2
answers
293
views
Convex optimization problem to QPP
Briefly, have the following problem:
\begin{equation}
\sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\
s.t.\\\\
A \bar x \leq b
\end{equation}
where $ F( \bar x ) $ is a ...
- 211
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 ...
CommunityBot
- 1
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 ...
- 30.1k