Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
1answer
37 views

Making the Smallest Number of Mistakes Possible

I have the following problem. I have a set of $k$ labelled points, $\left\{\mathbf{x}_i, y_i\right\}_{i=1}^{k}$, where $\mathbf{x}_i\in \mathbb{R}^{2}$, and $y_i\in\left\{-1,1\right\}$. I want to ...
2
votes
0answers
55 views

Proving an optimization problem has a rational optimum.

Consider the function $$ J_\gamma(X) = \det\left( I - \tfrac{1}{\gamma^2} (A+BXC)^\mathsf{T}(A+BXC)\right) $$ where $A$, $B$, $C$, $X$ are matrices of real numbers. Further suppose that ...
1
vote
1answer
383 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
35 views

Convex optimization issues

I have to optimize a function $f(a,b,c_{ij})$ which consists of a terms like matrix $\mathrm{X = A + B + C}$ where $\mathrm{A}$ is a diagonal matrix with the diagonal elements equal to $a$. ...
0
votes
0answers
112 views

Issues in optimization with positive definite constraints

I have this function $f(\mathrm{X})$ such $\mathrm{X}$ is a positive definite matrix which is equal to $\mathrm{A+B+C}$. $\mathrm{A}$ is a diagonal matrix with variable $a$ on the diagonal elements. ...
0
votes
1answer
61 views

Minimization problem convex set

I'm trying to minimize the function: $$f(w)=w^T\mu+k\sqrt{w^T\Sigma w}$$ where $w$ is a vector in $W=\{x \in \mathbb{R}^n|x_1+...+x_n=1 , x_i \geq 0 \forall i\}$. The vector $\mu \in \mathbb{R}^n$, ...
1
vote
0answers
43 views

Permutating a matrix in a convex form

I am at the basis of convex optimization and I made a constraint written in the following form: $XAY\le M$ where: $A\in R^{3,4}$ given, $a_{ij} \in \{0,1\}\quad \forall i,j$ $X\in R^{3,3}$ ...
2
votes
1answer
310 views

Karush-Kuhn-Tucker (KKT) conditions

I am having difficulties understanding the graphical interpretation as well as why the two following KKT conditions is necessary for a point x* being a minimum. It is my understanding that the (d) ...
0
votes
0answers
48 views

proof of convexity 3

i have a function of 7 variables. Suppose I plot the function while varying any one variable at a time, the function is visually convex. Can I conclude that the function is convex for all possible ...
2
votes
5answers
286 views

Compressive sensing with non square matrices

I'm implementing the algorithm in the following paper: "Compressive sensing for wideband cognitive radios" http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361 However I've run into a ...
1
vote
1answer
58 views

Interpreting a theorem about convex sets

I'm studying about linear programming and I bumped into following theorem (I have added my questions into the image): So in 1st rectangle how did we obtain the resulting equation when $\alpha ...
2
votes
1answer
100 views

Help with a proof of a theorem about convex sets

I'm studying the following theorem: Theorem 1. Let $C$ be a convex set and let $\textbf{y}$ be a point exterior to the closure of $C$. Then there is a vector $\textbf{a}$ such that ...
0
votes
1answer
31 views

Confusion related to derivative

What is the gradient of $||x + b||_1$ with respect to $x$? Here $x$ is the variable and $b$ is the constant.
1
vote
0answers
16 views

Confusion about the implementation of thresholding operation

I was reading this paper. I didn't get the application of thresholding operator here I didn't get how the -c part came in the solution $\mu = -c + S(c-b/a, \lambda/a)$
1
vote
2answers
2k views

Derivation of soft thresholding operator

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg ...
1
vote
2answers
85 views

Optimal Configuration for a Set of Points

Consider a set of $n$ points on the plane with positions $\mathbf{p}_1,\dots,\mathbf{p}_n$, such that each point $i$ has at least one neighbor $j$ at a distance of no more than $\lambda$ away from it ...
1
vote
2answers
72 views

Absract convergence of a suboptimal version of steepest descent

I'm looking for a citable reference to fill in a gap in an intermediate step of a proof which requires convergence of a suboptimal version of steepest descent. The function $f:\bf{R}^n\to\bf{R}^n$ I ...
1
vote
1answer
117 views

Convex functions and Hahn-Banach application

Let $Z$ be a convex subset of a real vector space, and $f:Z \to \mathbb{R}^m$ be such that every component $f_i:Z \to \mathbb{R}$ is a convex function. Let $S:\mathbb{R}^m \to \mathbb{R}$ be defined ...
0
votes
2answers
254 views

when is the epigraph a convex cone?

The problem is from Stephen Boyd's textbook, which I couldn't solve. The question is "when is the epigraph of a function a convex cone?" The solution says that it is when the function is convex and ...
2
votes
0answers
27 views

Tractability of a cardinality problem

I have this confusion related to the convexity and tractability of a problem. The given problem is maximize $u^TSu$ subject to $||u||_2 = 1$ and card(u) <= r This is a NP hard problem because ...
2
votes
2answers
219 views

Is alpha divergence a convex divergence measure?

Alpha divergence is defined as following : $$ D_\alpha(p||q) = \frac{1}{\alpha (1-\alpha)} \left( 1- \int _x p(x)^{\alpha} q(x)^{(1-\alpha)} dx \right) $$ if the distributions are restricted to ...
1
vote
2answers
56 views

Minimize the function

Minimize the function $$f(x) = (ax+b)^2 \left(\frac{c}{x} + d\right),$$ where $a , b , c \text{ and } d$ are all positive constants and $x$ is the variable. Thanks and regards
0
votes
1answer
29 views

Minimization problem

For Which positive value(s) of $x$ the following function is most minimum $f(x) = x^2 + ax +c$ [ where $a ,c > 0$ ] [note : I know there is no positive $x$ for which $f(x)$ is minimum but I ...
1
vote
1answer
183 views

Prove convexity of complicated rational function

Can anyone help me prove the convexity of this rational function? The man who proved the convexity of function used these facts. But I don't know this fact is correct or not. Here are the facts and ...
1
vote
0answers
54 views

Optimization problem in the Von Neumann Entropy

I have a constrainted optimization problem in the Von Neumann Entropy. In a CVX-like syntax the problem goes as follows: given variable $\mathtt{c(n)}$ $$\begin{align} \text{minimize} \qquad & ...
0
votes
1answer
47 views

Determine negligible coefficients in spectrum

Suppose I have some function $f$ that I have sampled at $N$ points and I preform a transform on it (this could be a Fourier transform, or perhaps a Hadamard, or really anything eles - I'm hoping for a ...
5
votes
3answers
422 views

Is inverse matrix convex?

I wonder a generalization of Jensen's inequality: let $\mathbf{X,Y}$ be two positive definite matrices, can we obtain the following Jensen like inequality ...
1
vote
1answer
66 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
1answer
48 views

A minimization problem [duplicate]

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$, ...
1
vote
1answer
102 views

Supporting hyperplanes Theorem in Boyd's Convex Optimization

On page 51, the authors applied the separating hyperplane theorem to the sets ${x_0}$ and the interior of $C$ to prove the supporting hyperplanes theorem (assuming the interior of $C$ is nonempty). ...
1
vote
1answer
55 views

Is this function convex or not?

Is this function convex ? $$ f(\mathbf y) = { \left| \sum_{i=1}^{K} y_i^2e^{-j\frac{2\pi}Np_il} \right| \over\sum_{i=1}^{K}y_i^2} $$ where : $ P = \{p_1,p_2,\cdots,p_K\} \subset\{1,2,\cdots,N\} $ I ...
1
vote
1answer
371 views

Convexity of the squared Frobenius norm of a matrix

I was reading this paper where the define an optimization problem as where K and L are kernel matrices and $\pi$ is the permutation matrix. They have explained that the function is convex because ...
0
votes
0answers
49 views

Confusion related to convexity of a quadratic function

Lets say I have the following function of X $f(X) = (AX^TBX)$ I didn't get why matrices A and B need to be psd to make f(X) convex. Clarifications guys
1
vote
0answers
59 views

Duality in Chebychev approximation

I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me. Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the ...
2
votes
1answer
34 views

Confusion related to explanation of convexity of a function

I was reading this paper where the define an optimization problem as where K and L are kernel matrices and $\pi$ is the permutation matrix. They have explained that the function is convex because ...
0
votes
1answer
796 views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
1
vote
0answers
41 views

Looking for a “Neat” Transform to Yield a Convex Set

Optimizing on a unit sphere $\mathbb{S}^n$ is almost a convex problem (if the function is convex in the new set) if we make our "new" set $\mathbb{R}^n$, via the stereographic projection. Clearly ...
2
votes
2answers
128 views

Prove Convexity of Recursively Defined Function

Let $\mathbf{x}=[x_1, x_2, \dots, x_K]\in\mathbb{R}^K_{++}$ and $E_1>E_2>\dots>E_K>0$ are positive constants. If $$f_i:\mathbb{R}^K_{++}\rightarrow\mathbb{R}_{++}\quad\forall1\leq i\leq ...
1
vote
0answers
132 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
3
votes
1answer
110 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
1
vote
1answer
47 views

suggest globally quasi-convex function

Can you suggest a function $f:R^2\to R, f\in C^2$, such that $f$ is globally quasi-convex (all its group sets are convex), but at no point convex?
1
vote
0answers
71 views

Maximum of the expectation of a concave function

Let's have a function $f(x, \theta)$, and some probability distribution on $x$. Let's say I have found $\theta^* = \operatorname{argmax}(f(E[x], \theta) $, and $f$ is concave in $x$. I would like to ...
1
vote
0answers
33 views

An Optimization problem related with $(-1)^{N-1}\sum_{i=1}^M\frac{\ln x_{i}}{x_{i}^N}\prod_{j\neq i}\frac{x_i}{x_i-x_j}$

I encountered an optimization problem \begin{align} f(x)=(-1)^{N-1}\sum_{i=1}^M\frac{\ln x_{i}}{x_{i}^N}\prod_{j\neq i}\frac{x_i}{x_i-x_j} \end{align} where $N$ is a positive integer, $x_i>0$ for ...
2
votes
0answers
89 views

are elementary symmetric polynomials concave on probability distributions?

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on ...
1
vote
2answers
67 views

When $\min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y)$?

When $$ \min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y) \qquad? $$ I mean when we are minimizing a function with respect to two variables, under what conditions we are allowed to ...
1
vote
1answer
69 views

Is this function involving matrices convex?

Let $X\in \mathbb{R}^{n \times n}$. Then, is the function $$ \text{Tr}\left( (X^T X )^{-1} \right)$$ convex in $X$? ($\text{Tr}$ denotes the trace operator)
2
votes
0answers
57 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
1
vote
1answer
70 views

Quadratic integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
1answer
158 views

Find conjugate indicator function

I'm doubt with this problem. Let $C=\left\{(x,y)\in \mathbb{R}^2|x+\frac{y^2}{2}\le 0\right\}$. I have to find $I_C^{*}(Y)$ defined by $I_C^{*}(Y)=\sup_{X \in \mathbb{R}^2} \left\{\langle ...
1
vote
1answer
131 views

Convex conjugate of absolute affine function?

Let $f:\mathbb{R}^n \rightarrow \mathbb{R} \cup \{ \infty \}$ be a convex function. The convex conjugate of $f$, which we call $f^*$ is defined as $f^*(y)=\sup \, \left \{ \langle y,x \rangle -f(x) ...