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

3
votes
1answer
108 views

A difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
1
vote
2answers
127 views

The set of matrices with same spectral radius

I am working on an optimization problem over the set of positive matrices (that is, matrices where all entries are positive numbers) that have the same spectral radius. My main problem is how to ...
3
votes
1answer
192 views

Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ...
0
votes
0answers
54 views

Convergence of Coordinate Descent / Alternating directions

My question regards this method http://en.wikipedia.org/wiki/Coordinate_descent, where at each step a function $f$ is minimized along one coordinate axis (or block of coordinates). Assume that $f: ...
0
votes
0answers
64 views

numerical and functional mixed optimization problem $\max f - \min f +\int_{-1}^1 (f'(x)-x)^2dx$

Given a function $g(x)$ and its domain, we want to get another function $f(x)$ whose derivative is approximately $g(x)$, but so that $f(x)$ itself has small variation. For example, for ...
3
votes
1answer
169 views

Linear dependency of real numbers with integer coefficients adding up to zero [closed]

Let $x = (x_1, \dots, x_n)$ be a vector of real number. I was asking myself if there was an efficient way of telling whether there exists a non-zero vector of integers $z \in \mathbb Z$ such that both ...
1
vote
0answers
84 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 ...
2
votes
0answers
326 views

On increasing the penalty term in convex optimization with regularization

Given the two strictly convex (unique solution) optimization problems as: $$Problem\:1:\min_{X} f(X)+\|X\|_{F}^2 \hspace{2cm}Problem \:2:\min_{X}f(X)+n\|X\|_2^2$$ where $X\in\mathbf{S}_{++}^{n}$ ...
2
votes
0answers
49 views

Reference request: Edmond's Algorithm for integer hull

I'm looking for a good reference for the algorithm (supposedly by Edmonds) to compute the integer hull of a polytope, not by cutting plane methods but by starting with a set of integer points and then ...
1
vote
0answers
37 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 ...
2
votes
1answer
83 views

Is first term of my cost function convex?

I have an optimization problem in the form of [\begin{array}{l} \mathop {{\rm{Minimize}}}\limits_{\bf{X}} \,\,\,2\left| \delta \right|\sqrt {{\rm{Tr}}\left( {{\bf{A}}{{\bf{X}}^2}} \right)} {\rm{ - ...
0
votes
0answers
54 views

Finding gradient of an optimization

I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me? Assume that we have an optimization ...
1
vote
0answers
44 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, ...
4
votes
1answer
183 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
121 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 ...
0
votes
0answers
190 views

Proximal operator of modified L1 matrix norm

In literature proximal operator $prox_{\lambda f} : R^n \rightarrow R^n$ of $f$ is defined as: $prox_{\lambda f}(V) = argmin(X) (f(X) + (1/2 \lambda)||X-V||^2_2)$ Consider now $g(X) = ...
2
votes
1answer
131 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 ...
1
vote
1answer
73 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:}}\, & ...
1
vote
1answer
108 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
75 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
74 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
134 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
175 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
166 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
97 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$ ...
8
votes
3answers
711 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
112 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
105 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
58 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 ...
5
votes
1answer
262 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
86 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 ...
1
vote
1answer
182 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
252 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 ...
1
vote
1answer
217 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
160 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 ...
23
votes
2answers
882 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
33 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 ...
1
vote
1answer
183 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 ...
4
votes
2answers
395 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 ...
2
votes
1answer
265 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
144 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 ...
3
votes
1answer
267 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
154 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 ...
0
votes
1answer
288 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 ...
0
votes
1answer
185 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
206 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 ...
-1
votes
1answer
119 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
116 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} ...
1
vote
1answer
260 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
165 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 ...