The convex-optimization tag has no wiki summary.
0
votes
0answers
38 views
A minimization problem [migrated]
Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \|\frac{w}{x}\|,~w,u\in R^n$$
where $$\frac{w}{x}=(\frac{w_1}{x_1},\dots, \frac{w_n}{x_n})$$
$$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$
Given $u$, $x$ and $\beta$, ...
4
votes
2answers
48 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} \\\
...
-1
votes
0answers
50 views
Minimizing sum( max(|x - xi|, |y - yi|) for i = 1 to n) [closed]
Suppose there are n points (xi, yi) for i = 1 to n, how find another point (x, y) to minimize function: sum( max(|x - xi|, |y -yi|) for i = 1 to n)
1
vote
0answers
49 views
Coordinate mirror descent
Let $f$ be a jointly convex function of 2 variables say $x,y$. I am interested in solving the optimization problem $$\min_{x,y\in\Delta} f(x,y)$$ where $\Delta$ is a $d$ dimensional simplex. An ...
0
votes
0answers
123 views
NP-Completeness
Consider the following optimization problem:
\begin{align}
\text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-x_sx_t\|\\
s.t.: && Ax=b\\
&&x\geq 0
\end{align}
where $I$ is a ...
2
votes
2answers
108 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 ...
0
votes
0answers
39 views
Can a solution of SDP be proven optimal by estimating the perturbation of each variable individually?
More precisely, I'm considering the special case for vector programming, which is an equivalent form to semidefinite programming:
$$
\min \sum_{i,j} c_{i,j} (x_i \cdot x_j) \\
\textbf{subject to: ...
0
votes
0answers
70 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 ...
0
votes
1answer
51 views
Nonconvex optimization problem
I have a nonconvex optimization problem. It is actually optimizing a linear objective function over a set of linear constraints and a set of nonlinear, non convex constraints.
Is this problem ...
0
votes
2answers
93 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 ...
1
vote
1answer
148 views
Hessian of function of covariance matrices
Suppose we have a typical logdet function $\mathcal{L}$ with respect to a covariance matrix $\mathbf{A}$,
$$
\mathcal{L}(\mathbf{A}) = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - ...
1
vote
0answers
104 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 ...
0
votes
0answers
70 views
Regularized Gradient with respect to a matrix (with a specific structure)
Suppose we have a typical logdet function $\mathcal{L}$
$$
\mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - \mathbf{q}^T(\mathbf{A}^{-1} + \mathbf{S})^{-1} \mathbf{q},
$$
where ...
0
votes
0answers
34 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 ...
0
votes
0answers
43 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 ...
0
votes
1answer
98 views
solve non-convex quadratic constrained quadratic programming
$\min_{\beta}\beta^{T} A \beta$
$s.t. \ \beta^{T} C \beta=1\ and\ \beta\geqslant 0$
Here $A,C\in \mathbb{R}^{M\times M}$, $\beta \in \mathbb{R}^{M}$
I saw in one paper saying that it could be ...
0
votes
0answers
49 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 ...
1
vote
2answers
175 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) = ...
1
vote
1answer
63 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$. ...
1
vote
1answer
130 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 ...
2
votes
0answers
92 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 ...
0
votes
1answer
131 views
Minimum conditional expectation of complement of event given conditional expectation of event?
Suppose $X$ is a pdf over $[0,m]$ and $Y$ is a binary experiment on $X$ such that $P(Y=1|X)$ is continuous, and we have that $\mathbb{E}[X|Y=1] = \mu_y$ and $\mathbb{E}[X] < \mu_y$. Is it always ...
1
vote
0answers
55 views
optimization function: sum of root squares of sum of two quadratic
Full question (same question in jpg, pdf and doc\docx):
https://drive.google.com/folderview?id=0BxFEf1J4iYVeX2l2NlVjUldEUlE&usp=sharing
Hello
I am a graduate student in computer science, making ...
0
votes
2answers
65 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 \\\
...~~~~~~~~~~ \\\
...
2
votes
1answer
122 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
0answers
55 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 ...
0
votes
1answer
58 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 ...
1
vote
1answer
69 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} \ ...
1
vote
1answer
121 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 ...
1
vote
2answers
126 views
What is the dual of an semidefinitely representable (SDR) cone?
The Question
Let $V\simeq \mathbb{R}^r$ be an $r$-dimensional vector space with the usual Euclidean inner product.
Let $\mathcal K\subset V$ be a cone defined as
$$
\mathcal K=\Big\{x\in ...
5
votes
2answers
93 views
On the convexity of element-wise norm 1 of the inverse
Question first asked on math.stackexchange here: http://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 ...
1
vote
0answers
52 views
Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?
In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...
3
votes
1answer
137 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 ...
1
vote
1answer
238 views
Robust optimization in matlab using fmincon
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 ...
1
vote
0answers
63 views
Subgradient of Minimum Eigenvalue
Consider three $N \times N$ hermitian matrices $A_0,A_1,A_2$. Consider the function
\begin{align}
f(t_1,t_2)=\lambda_{min}(A_0+t_1A_1+t_2A_2)
\end{align}
where $\lambda_{min}$ denotes the minimum ...
0
votes
0answers
60 views
Minimize the spectral radius of a perturbed matrix
Given a matrix $M$, and it is perturbed by a matrix $E$.
Denote the new perturbed matrix by $M'=M+\epsilon E$. I wish to find out the optimal $\epsilon^*$ that minimizes the spectral radius of $M'$. ...
0
votes
0answers
143 views
Properties of the subgradient method
The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule
$$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and
$\alpha(t)$ is a ...
0
votes
0answers
46 views
Optimization with parameters
I'm trying to formulate a game so that at Nash equilibrium I achieve supply equales demand. Then I ran into this problem.
For all $i,$ $v_{i}\left(x_{i}\right)$ is concave
in $x_{i}$. The value ...
1
vote
1answer
277 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$ ...
1
vote
1answer
62 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 ...
5
votes
0answers
116 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 ...
0
votes
1answer
91 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 ...
1
vote
2answers
148 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 ...
2
votes
2answers
166 views
A certain type of Quadratic Constrained Quadratic Programming Problem (QCQP)
Let $P_1$, $P_2$ be two hermitian matrices. Can anyone comment about the following (QCQP)
\begin{equation}
\min_{z}~z^{H}z \\\
~~subject~to ~z^{H}P_1z+1\leq 0,~z^{H}P_2z+1\leq 0
\end{equation}
I am ...
0
votes
1answer
156 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 ...
0
votes
2answers
145 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 ...
0
votes
1answer
231 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 ...
2
votes
1answer
193 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 ...
0
votes
0answers
96 views
Non-linear optimzation with multipe objectives and multiple inequality constraints
I posted an earlier version of this question on math.stackexchange almost a week ago but have not had any replies. I'm recasting the problem in light of new understanding. I'd like to know if the the ...
