Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
36 views

Matrix equation

Let $A$ be $k\times n$ matrix i.e., $A=(a_{1},\ldots, a_{n})$ where $a_{j} \in \mathbb{R}^{k}$, $rank(A)=k$ and $1\leq k \leq n$. Let $q=(q_{1},\ldots, q_{n})\in\mathbb{R}^{n}$ be such that ...
2
votes
1answer
82 views

Necessary conditions for optimality in Banach spaces

Let $X$ denote the non-negative "orthant" of the Banach space $L^2$ (or whatever you call the set of functions in $L^2$ that are non-negative), and let $C$ be a closed, convex subset of $X$. Let $f$ ...
7
votes
2answers
146 views

Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...
1
vote
0answers
30 views

What is the purpose of the definition of “metric regularity”/“regularity modulus”?

A set mapping $F:X \rightrightarrows Y$ is said to be metrically regular for $\overline{x}\in X$ and $\overline{y} \in Y$ if there exists a $\kappa\in(0,\infty)$ for which $$ d(x,F^{-1}(y))\leq ...
3
votes
0answers
78 views

This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by ...
1
vote
0answers
39 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 ...
-3
votes
1answer
30 views

Convert constraint to do convex optimization or use Lagrange multiplier method [closed]

$w_1, w_2, w_3 ... w_n$ are the weights I need to find I have the following constraint: $|w_1| + |w_2| + .. |w_n| <= 5$ That is the sum of the absolute values of the weights has to be less than ...
2
votes
1answer
79 views

Linearly constrained eigenvalue problem

Suppose I'd like to: \begin{align} \mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\ \text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\ && ...
4
votes
2answers
235 views

Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that ...
3
votes
1answer
65 views

Can one always find sparse solutions to an $\ell^1$-minimization problem?

Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem $$\min \|x\|_1 \quad s.t. \;\; A x = b,$$ admits an $m$-sparse solution in ...
7
votes
3answers
320 views

The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small? More ...
1
vote
2answers
119 views

investigating positivity/negativity of a function [closed]

I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function ...
2
votes
1answer
78 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
111 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 ...
2
votes
1answer
114 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
29 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
58 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
162 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
73 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
vote
0answers
292 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
37 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
27 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
71 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
48 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
29 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
173 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
109 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
40 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
119 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
63 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
43 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
73 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
63 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
90 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 ...
1
vote
0answers
141 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
156 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
74 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
655 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
102 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
89 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
50 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
251 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$ ...
1
vote
0answers
65 views

Constrained optimization problem with system of differential equations [closed]

Thanks in advance for any help. My question relates to a homework problem. I have been given a system of generalized differential equations with the goal of creating an algorithm that will solve ...
2
votes
1answer
85 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
113 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!
0
votes
0answers
29 views

Maximizing the product of projections of a vector on another vectors

I want to get the $N\times1$ complex vector $\mathbf{x}$ which maximizes this real valued function $f=\mathbf{x}^{H}\left (\mathbf{a}_{1} \mathbf{a}_{1}^{H}\mathbf{x}\mathbf{x}^{H}\mathbf{a}_{2} ...
2
votes
5answers
228 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 ...
2
votes
1answer
91 views

optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint. D and T are symmetric matrice, where T is known and D is the unknown parameter. x and v are two known p-dimensional vectors. The objective ...
2
votes
2answers
119 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 ...
22
votes
2answers
832 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 ...