Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

learn more… | top users | synonyms

5
votes
1answer
202 views

optimization problem, any solution?

The objective is as follows: $\min_{\mathbf{F}} a Tr(\mathbf{F} \mathbf{F}^H) - Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\}$ $s.t.\ \ \ Tr(\Sigma \mathbf{F} \mathbf{F}^H)<p$ ...
5
votes
1answer
157 views

Reference request: Continuity of unique maximizer of linear functional on convex set

Does anyone know reference for a theorem of the following sort: Proposition: Let $K \subset\mathbb {R}^n$ be a compact convex set, and assume that $$f(w):=\operatorname{argmax}_{x\in K}w(x) $$ is ...
2
votes
1answer
254 views

Projection onto $\ell^{2,1}$ ball

Does anyone have an idea how to project onto the $\ell^{2,1}$ ball efficiently, i.e. how to solve $$ u = \arg \min_u \|u-f \|^2 \text{such that } \left(\sum_i \big(\sum_j |u_{i,j}|\big)^2 \right)^{...
1
vote
1answer
80 views

mixed semi definite and second order programming complexity order

Consider the following mixed semi definite and second order programming: $\begin{array}{l} \mathop {{\rm{min}}}\limits_{\bf{X}} \,{\rm{Tr}}\left( {{\bf{XA}}} \right)\\ {\rm{s}}{\rm{.t:}}\, & {\rm{...
1
vote
1answer
519 views

Convergence rate of stochastic gradient decent with projections

Given a strong (not only strict) convex function $f: \mathbb{R}^n\to\mathbb{R}$. On such problems, stochastic gradient decent (SGD) has a convergence rate of $O(1/T)$, where $T$ is the number of ...
3
votes
2answers
92 views

Is the prox-residual monotone?

$\newcommand{\scp}[2]{\langle #1,#2\rangle}\newcommand{\id}{\mathrm{Id}}$ Let $f$ and $g$ be two proper, convex and lower semi-continuous functions (on a Hilbert space $X$ or $X=\mathbb{R}^n$) and let ...
1
vote
0answers
123 views

dual problem of SDP [closed]

suppose we have the following optimization problem: \begin{array}{l} \mathop {\min }\limits_{{\bf{X}},{\bf{x}}} \,\,Tr\left( {{\bf{XA}}} \right) + 2{{\bf{a}}^H}{\bf{x}} + b\\ s.t:\,\,\,\,\left[ {\...
2
votes
0answers
193 views

proving quasi convexity of multivariable function

Given an arbitrary $(N \times N)$ square matrix ${\bf X}$ a positive definite $(M\times M)$ matrix ${\bf T}$ a $(Q\times MN), Q< MN$ matrix ${\bf Z}$ consisting of only 1s and 0s where there is ...
2
votes
0answers
263 views

Continuity of minimizers to distance function from point to convex set

Suppose I am minimizing the Euclidean distance in $\mathbb{R}^{n}$ between a point $y$ and compact convex set $U$ (where $y\notin U$): $\min_{x\in U}\|x-y\|$. I believe the minimizer $x_{U}^{*}$ is ...
4
votes
0answers
194 views

When is the sum of a weak-$*$ closed convex cone and a subspace also weak-$*$ closed?

Let $X$ be a Banach space. Suppose $C \subset X^*$ is a convex cone and $V \subset X^*$ is a subspace, and suppose both $C$ and $V$ are closed in the weak-$*$ topology. Are there any general ...
2
votes
0answers
154 views

Optimality condition for non-differentiable constrained convex optimization problem

(EDIT: see proof at the end) Consider the problem $$ \min f(x) \; \text{s.t.} \; x\in D $$ where $f(x)$ is convex but not differentiable, and $D$ is convex. For differentiable $f$, we know that $x$ ...
9
votes
3answers
871 views

Is group theory useful in any way to optimization?

For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it. Is group theory useful in any way to ...
2
votes
2answers
145 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 ...
1
vote
0answers
134 views

Diagonal entries of a Cholesky factorization

Let $I$ denote an identity matrix, $E$ denote the all-one matrix of dimension $k\times k$ and $c$ some positive real number. Define $X=B(I-cE)B^T$ where $B$ is given by $B:=\begin{pmatrix} 1 &\...
0
votes
0answers
75 views

Sufficient optimality condition for a non-smooth quasiconvex problem

The result of relaxing to an integer program is the following optimization problem: $$\min_{\textbf{x}} \sum_{i=1}^n \alpha_i h(x_i)\quad subject \; to \quad A\textbf{x} = \textbf{0}$$ where $\textbf{...
5
votes
1answer
301 views

What it is the volume of the unit ball section of the cone of positive definite matrices?

Let $PD_{n}$ be the cone of positive definite $n \times n$ real matrices and let $B$ be the unit sphere in $n \times n$ dimensions. What is the volume of $PD_{n} \cap B$? EDIT: Let's assume that $B$ ...
2
votes
1answer
87 views

Convex interaction energy

Does anybody know examples of absolutely continuous probability measures $\mu_0,\mu_1$ on $\mathbb{R}^n$ with finite 2nd moments such that $$ \frac{d^2}{dt^2}\left(\int_{\mathbb{R}^n\times \mathbb{R}^...
1
vote
1answer
250 views

Minimize a strictly convex quadratic function subject to linearly equality and nonnegativity constraints in finite time?

I am wondering if we can minimize a strictly convex quadratic function in finite time, subject to linearly equality and nonnegativity constraints. Thanks!
2
votes
5answers
339 views

Distance between two sets

Let $A, B$ be two convex and closed subsets of $\mathbb{R}^n$. We would like to the minimum distance between these two sets. i.e., we want to find a solution for the following problem. $$ \min \{||x-y|...
2
votes
1answer
493 views

optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint. $D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter. $x$ and $v$ are two known p-dimensional vectors. The ...
2
votes
2answers
276 views

How to minimize the Bregman divergence on a convex hull spanned from a set of vectors?

everyone. It has been well known that the following minimization problem of a Bregman divergence with linear inequality can be solved by successively projecting the current point to each constraint $\...
24
votes
2answers
992 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 ...
1
vote
0answers
35 views

Searching for the maximum of a (strictly convex) two-dimensional distribution via maximization over a series of arbitrarily specified 1D intervals

Let $f$ be a strictly convex two-dimensional distribution with a maximum $M$ at some unknown position $(x_m,y_m)$. Starting from the origin, $(x_0,y_0) = (0,0)$, we need to find $(x_m,y_m)$, however ...
2
votes
1answer
236 views

Homotopy with non piece-wise linear boundary

in the middle of a long proof I encounter the following problem. Let $E$ be a closed and convex set in $\mathbb R^n$ such that for all $\vec x\in E$ it holds that $\sum_ix_i=1$. (We can understand $E$...
4
votes
2answers
566 views

Gradient descent-like optimization on a convex landscape with noisy sampling

This is a rewrite of the original positing (below), and is crossposted to (http://cstheory.stackexchange.com/questions/21496/gradient-descent-like-optimization-on-a-convex-landscape-with-noisy-...
2
votes
1answer
553 views

Block Covariance Matrix - Positive Definite? (Quadratic Optimization) [closed]

I have a covariance matrix C. I have then formulated an quadratic optimization problem that involves the following matrix in the quadratic form: [ C C ] [ C C ] However, the quadratic solver ...
1
vote
0answers
183 views

Extreme points of a set related to semidefinite cone

Let $X \in \mathbb{R}^{n \times n}$ be symmetric matrix. Consider the following set $$ \mathcal{C} = \{ X: X \succeq 0, \quad 0 \le X_{ij} \le 1, \forall i,j\} $$ What are the extreme points of this ...
4
votes
1answer
605 views

SDP formulation of noisy low rank matrix completion

Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...
1
vote
1answer
192 views

No strong duality In spite of Slater's condition

I was reading some course notes here. On Page 8, it says: Note that strong duality holds here (Slater's condition), but the optimal value of the last problem is not necessarily the optimal ...
1
vote
1answer
465 views

Find the following transformation $G$

I asked this question 6 days ago on math.stackexchange.com (http://math.stackexchange.com/questions/656585/find-the-following-transformation-g). I didn't get any answers yet, so I'm posting here. I'm ...
2
votes
1answer
277 views

Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$). The cost to send $x$ unit of flow through edge $e_i$ is defined ...
4
votes
2answers
312 views

Minimax theorem on a non convex domain

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 \mathcal{...
-1
votes
1answer
337 views

Uniqueness of the solution to a quadratic problem [closed]

Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...
0
votes
1answer
134 views

Eigenvalues of a given parametrized matrix.

Let $\mathbf{A}$ and $\mathbf{B}$ be two complex rank-one $N\times N$ positive semi-definite matrices. Let the matrix $\mathbf{C}$ be defined as \begin{align} \mathbf{C}=\left(\mathbf{I}*\frac{1}{\...
2
votes
2answers
447 views

Interior of a dual cone

Let $K$ be a closed convex cone in $\mathbb{R}^n$. Its dual cone (which is also closed and convex) is defined by $K' = \{ \phi\ |\ \phi(x) \geq 0,\ \ \forall x \in K\}$. I know that the interior of $...
1
vote
1answer
289 views

Lagrange multiplier and semidefinite programming

suppose we have a primal semidefinite programming. for finding its dual we use Lagrange multiplier $w_i$ for each semidefinite constraint. If the Lagrange multiplier be zero for one constraint what we ...
1
vote
0answers
151 views

How to solve such an optimization problem efficiently?

Given a symmetric positive semi-definite matrix $\mathbf Y$ and a convex set $\mathcal M$ which is a subset of all symmetric positive semi-definite matrices (consider a simple case of $\mathcal M$: a ...
2
votes
2answers
119 views

Projection onto rotated box

Does anyone know if there is an efficient way to find the projection of an arbitrary point $z$ onto a rotated box, i.e. onto the set $\Omega=\{x \mid a \leq Ux \leq b\}$ where $U$ is a unitary matrix? ...
3
votes
1answer
178 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 |) ...
1
vote
0answers
123 views

Maximizing an integral over a convex region

Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...
1
vote
0answers
266 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 ...
2
votes
1answer
161 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 ...
-1
votes
1answer
55 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(...
3
votes
1answer
331 views

quadratic programming on hypercube

I want to maximize a quadratic form $\mathbf x^T\mathbf Q\mathbf x$ and also want to find out which vector $\mathbf x$ maximizes the quadratic form when $\mathbf Q$ is an $n\times n$ positive ...
1
vote
1answer
373 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 ...
2
votes
2answers
249 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. ...
2
votes
1answer
273 views

maximizing convex quadratic form over the intersection of unit sphere and positive orthant

For a positive semi-definite matrix $C$, I want to find the solution to the following problem: $\arg\max_{h\geq 0} h^T C h\quad$ s.t. $\quad h^T h\leq 1$ Any pointers are welcome.
3
votes
1answer
526 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
vote
0answers
93 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 ...
2
votes
1answer
230 views

optimize spectral radius

Hi I would like to solve the following optimization problem. Let $A$ be an $n \times n$ nonnegative real matrix where $A^{-1}$is an M-matrix. Let $D=\text{diag}\{d_{1}, \dots , d_{n}\}$ be a ...