The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
93 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$ ...
2
votes
1answer
98 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 ...
0
votes
1answer
120 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 ...
0
votes
1answer
228 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
130 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 ...
-1
votes
1answer
133 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 ...
5
votes
0answers
143 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 ...
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 ...
3
votes
0answers
84 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 ...
3
votes
0answers
284 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 ...
2
votes
0answers
28 views

Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?" More formally and generally, what I'm looking for ...
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 ...
2
votes
0answers
100 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
77 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$ ...
2
votes
0answers
145 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
0answers
167 views

An intuition for three different types of subgradients (proximal, regular, limiting)

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking. These subgradients are (assume $x \in$ ...
2
votes
0answers
141 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 ...
2
votes
0answers
70 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 ...
1
vote
0answers
33 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 ...
1
vote
0answers
43 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 ...
1
vote
0answers
75 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
305 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}$ ...
1
vote
0answers
29 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 ...
1
vote
0answers
33 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, ...
1
vote
0answers
148 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 ...
1
vote
0answers
90 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 ...
1
vote
0answers
31 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
0answers
121 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 ...
1
vote
0answers
139 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 ...
1
vote
0answers
103 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
65 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 ...
1
vote
0answers
84 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 ...
1
vote
0answers
125 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 ...
1
vote
0answers
92 views

minimizing the sum of euclidean norms

minimizing the sum of euclidean norms with box constraints I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
0
votes
0answers
11 views

Restricted strong convexity for biconvex functions

Recently, it has been shown (arxiv paper) that non-convex functions with the restricted strong convexity (RSC) property has the interesting property that their local minima lie within a small ball of ...
0
votes
0answers
57 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 ...
0
votes
0answers
33 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
59 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 ...
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 ...
0
votes
0answers
59 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) = ...
0
votes
0answers
52 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 ...
0
votes
0answers
31 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} ...
0
votes
0answers
75 views

An attempt to solve “Maximization of a total variation distance subject to another total variation distance in Markov chain”

I have been trying to solve Maximization of a total variation distance subject to another total variation distance in Markov chain. As a recall, suppose we have a pair of correlated random variables ...
0
votes
0answers
96 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
0answers
102 views

Modifying a QP to incorporate more constraints

Consider the following problem: $$\min \sum_{i=1}^n (Y_i - Z^{(i)})^2 \\ \text{subjected to}~ \epsilon_k^{\top}(X_j-X_k) \leq Z^{(j)}-Z^{(k)} ~ \forall k,j = 1 \ldots n. $$ where $\epsilon_1, ...
0
votes
0answers
104 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
0answers
52 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
46 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
0answers
67 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 ...
0
votes
0answers
82 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 ...