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

learn more… | top users | synonyms

3
votes
0answers
930 views

Convex minimization over the Unit Simplex

I have a simple (few variables), continuous, twice differentiable convex function that I wish to minimize over the unit simplex. In other words, $\min. f(\mathbf{x})$, $\text{s.t. } \mathbf{0} \preceq ...
2
votes
2answers
491 views

Why the unit circle in $\mathbf{R^2}$ has one dimension?

When I was reading 'Convex Optimization, Stephen Boyd', I was wondering of following steps Consider the unit circle in $\mathbf{R^2}$, $i.e.$, $\{x\in\mathbf{R^2}|x^2_1+x^2_2=1\}$. Its affine hull ...
2
votes
2answers
73 views

Convexity of a trace of matrices with respect to diagonal elements

Can we prove that $\mbox{trace}({\bf A} ({\bf P}+{\bf Q})^{-1} {\bf A}^T)$ is a jointly convex function of positive variables $[q_1,q_i,...,q_N]$, where ${\bf Q}=\mbox{diag}(q_1,...,q_N)$, ...
2
votes
3answers
169 views

Is this set convex ?2

Is this set convex for every arbitrary $\alpha\in \mathbb R$? $$\Big\{(x_1,x_2)\in \mathbb R^2_{++} \,\Big|\, x_1x_2\geq \alpha\Big\}$$ Where $\mathbb R^2_{++}=[0,+\infty)\times [0,+\infty)$.
2
votes
3answers
291 views

What is the dual of this optimization problem?

Consider the points $x_1, \ldots, x_N \in \mathbb{R}^n$, and a (locally bounded, convex) function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. I am looking for the dual of the following optimization ...
2
votes
1answer
191 views

Is this necessarily true for a convex function?

$$\sum_{s \in V} \lambda_sf(s) \geq f(\sum_{s \in V} s\lambda_s)$$ $V$ is a set of points and corresponding to each point in $V$, there is a $\lambda_s$ which is a scalar so $\sum_{s \in V} ...
2
votes
2answers
109 views

Every concave function that is nonnegative on its domain is log-concave?

This is a statment from Wiki. I'm not sure why this is true: If: $f(\theta x+(1-\theta y) \geq \theta f( x) + (1-\theta)f(y)$ And $f(\cdot) \geq 0$ then: $$f(\theta x+(1-\theta y) \geq f( ...
2
votes
3answers
145 views

Is this optimization problem solvable?

I have the following optimization problem: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~ \|\mathbf{y+Ax}\|_\infty \leq \beta\|\mathbf{y}\|_\infty ~~,~~ \|\mathbf{x}\|^2 \leq \alpha^2$$ where ...
2
votes
2answers
68 views

Is this a polyhedron?

Is $S$ a polyhedron? $$S=\{x\in\mathbb{R}^n|\|x-x_0\|\le\|x-x_1\|\}$$ where $x_0, x_1$ are given. $S$ is the set of points that are closer to $x_0$ than to $x_1$. I was thinking the ...
2
votes
2answers
137 views

Verifying the convexity of some function

Convex function: We will say that $f:X\rightarrow R$ is convex function if for every $\lambda\in [0,1]$ and for every $x,y\in X$ ($X$ is convex space) $f(\lambda x+(1-\lambda)y)\leq\lambda ...
2
votes
2answers
6k 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 ...
2
votes
1answer
285 views

Is the following problem convex?

I think the following problem is convex (due to the results of some simulations), but I am not sure: $min_x||e^{(Ax)}-b||^2_2$ s.t. x>0 where $A$ is m x n, $x$ is n x 1, and b is m x 1. $A,x,b$ are ...
2
votes
1answer
331 views

Simple resource for Lagrangian constrained optimization?

Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that ...
2
votes
1answer
341 views

Maximizing the number of non-crossing lines between a number of points

Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross. Hoping for a polynomial time algorithm, I ...
2
votes
3answers
159 views

Proof of Convexity

Is the function $Trace(AX^TBX)$ a convex function in $X$ or not ? Here, $X$ is a rectangular matrix and $A,B$ are square, symmetric, p.s.d matrices. The entries in $X,A,B$ are real valued.
2
votes
2answers
43 views

Convert any convex optimization problem to a linear objective

Wikipedia claims that: Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. Is there a ...
2
votes
1answer
57 views

Consider $(f\Box g) (z)=\inf_{x+y=z}(f(x)+f(y))$

Consider $$(f\Box g) (z)=\inf_{x+y=z}(f(x)+g(y))$$ Find two convex functions $f$ and $g$ from $X$ to $\mathbb{R}$ such that the infimum given above is never a minimum. Can anyone help with finding ...
2
votes
1answer
92 views

Is the expectation of log-concave function still log-concave?

I know the expectation preserves the concavity (or convexity), but I was wondering is it still true that the expectation of log-concave function still log-concave; to be more precise, Let ...
2
votes
1answer
265 views

Regarding Nesterov's smooth minimization

I am currently studying this Nesterov's paper for project purposes, and I am trying to figure out how the smoothing and the minimization algorithm works I have tried looking at the example ...
2
votes
1answer
65 views

linear approximation with respect to L1 norm

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$ any hints how to proceed
2
votes
1answer
734 views

Proving convexity of a function whose Hessian is positive semidefinite over a convex set

C is a convex set in R^n and f:R^n --> R is twice continuously differentiable over C. The Hessian of f is positive semidefinite over C, and I want to show that f is therefore a convex function. I ...
2
votes
1answer
67 views

Origin of Slater's condition

I've been looking all over the internet to answer this question: Slater's condition is a commonly used to certify that strong duality holds in a convex optimization problem. Although used in many ...
2
votes
5answers
511 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 ...
2
votes
2answers
1k views

How can I solve Lagrange multiplier equation with multi constraints?

This site is really awesome. :) I hope that we can share our ideas through this site! I have an equation as below, $$ min \ \ w^HRw \ \ subject \ \ to \ \ w^HR_aw=J_a, \ w^HR_bw=J_b$$ If there is ...
2
votes
1answer
391 views

Sion's minimax theorem

Sion's minimax theorem is stated as: Let $X$ be a compact convex subset of a linear topological space and $Y$ a convex subset of a linear topological space. Let $f$ be a real-valued function on ...
2
votes
2answers
221 views

straightforward way to determine if this set is convex?

straightforward way to determine if this set is convex? $Z=\left\{x\in\mathbb{R}^2:3x_1^4-x_1x_2+x_2^4\le x_2,x_1>2,x_2>2\right\}$ I know I can try by manipulation of linear combination of two ...
2
votes
2answers
938 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
2
votes
1answer
91 views

Rewriting a matrix as a polynomial

If a finite dimensional matrix $A$ is positive semidefinite, how can we write $A$ as a polynomial in $A^{2}$? Thanks.
2
votes
2answers
973 views

time complexity of a convex quadratically constrained quadratic program (QCQP) problem

Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP) problem? And any references? Thank you very much.
2
votes
1answer
36 views

Are posynomial functions convex?

I know that you can transform a posynomial function into an exponential function, which is convex. Does this imply that all posynomial functions are convex?
2
votes
2answers
53 views

Convexity of variance

How can I prove the following function is convex? Is variance concave or convex? $$\psi (x)=\left(x_1-\frac{x_1+x_2+x_3}{3}\right)^2+ \left(x_2-\frac{x_1+x_2+x_3}{3}\right)^2+ ...
2
votes
1answer
51 views

How to replace piecewise objective function in convex optimization problem?

Suppose I have a minimization problem \begin{equation} \begin{aligned} & \min\limits_{x} & & g(x)+f(x) \end{aligned} \end{equation} \begin{equation} f(x)= \begin{cases} 1, ...
2
votes
1answer
82 views

Why the gradient of $\log{\det{X}}$ is $X^{-1}$, and where did trace tr() go??

I'm studying Boyd's "Convex Optimization" and encountered a problem in page 642. According to the definition, the derivative $Df(x)$ has the form: $$f(x)+Df(x)(z-x)$$ And when $f$ is ...
2
votes
1answer
149 views

Proof of convergence for the proximal point algorithm

I'm trying to come up with a super simple proof of convergence on the proximal point algorithm, which uses the iteration scheme $x^{i+1} = \mathbf{prox}_{tf}(x^i)$ where $f$ is a closed, convex ...
2
votes
2answers
150 views

Why a convex cone cannot have more than one extreme point?

The way I define an extreme point is : A point which cannot be defined as a convex combination of two distinct points. I'm not able to extend this and show why a convex cone cannot have more than ...
2
votes
2answers
69 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
2
votes
2answers
529 views

How to maximize an entropy function?

I'm very novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
2
votes
1answer
588 views

Is there any method that convert a non-convex problem to a convex one?

I have an optimization problem of the form: minimize $\quad f_0(x)$ subject to $\;\;\;f_1(x)\leq0,\quad\quad\quad(C1)$ $\quad\;\quad\;\quad\quad\;f_2(x)\leq0,\quad\quad\quad(C2)$ where ...
2
votes
1answer
69 views

Got stuck with this $L^2(-1, 1)$ optimization problem. Any ideas where it comes from?

Statement Let $u(x) \in L^2(-1, 1)$. Solve the following optimization problem: $$ \begin{cases} J(u) = 4 \int_{-1}^{1} \sqrt{|x| (1 - |x|)} u(x) dx + \left(\int_{-1}^1 \sin(3\pi x) u(x) dx\right)^2 ...
2
votes
1answer
573 views

Solution to a Quadratic Minimization with Norm Constraint

How do I solve the optimization problem \begin{align} &\min_{\mathbf{x}\in\mathbb{C}^N}\mathbf{x}^H\mathbf{A}\mathbf{x}+2\Re\{\mathbf{b}^H\mathbf{x}\} \\ \mbox{subject to }\\ ...
2
votes
2answers
420 views

What change of variables, if any, transforms this nonconvex problem into a convex one?

I'm looking for a convex reformulation, if any exists, of the following minimisation problem: Let $A$ be a symmetric, positive definite $n \times n$ matrix, and $b \in \mathbb{R}^n$. Minimise ...
2
votes
1answer
54 views

What is the name of this object?

Suppose I have a convex set $K\subset X$, where $X$ is say a real Hilbert space (for simplicity). Then, given some $a\in \Bbb{R}$, let $$ \hat{K}=\{x:\langle x,y\rangle \leq a \;\forall y\in K\} $$ ...
2
votes
2answers
151 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 ...
2
votes
3answers
106 views

Convex set. Proof.

Prove that if A is convex set and $\alpha, \beta ≥ 0$ then $(\alpha + \beta)A = \alpha A + \beta A$ What came first on my mind is that I have to show that $(\alpha + \beta)A\subset \alpha A + \beta ...
2
votes
2answers
495 views

Finding convex conjugate of a bounded function

The convex conjugate of a function $f:\mathcal{X}\mapsto \mathbb{R}$ is formally defined as $$f^\star\left(y\right)=\sup_{x\in\mathcal{X}}\ \left\langle x,y\right\rangle-f\left(x\right).$$ In cases ...
2
votes
2answers
185 views

Analytical Solution to a simple l1 norm problem

Can we solve this simple optimization problem analytically? $ \min_{w}\dfrac{1}{2}\left(w-c\right)^{2}+\lambda\left|w\right| $ where c is a scalar and w is the scalar optimization variable.
2
votes
2answers
68 views

What are the relations between these two minimizations

What are the relations between the minimization problems $\arg\min_{\mathbf{y}=A\mathbf{x}}\left\Vert \mathbf{x}\right\Vert _{2}$ and $\arg\min_{\mathbf{x}}\left\Vert A\mathbf{x-y}\right\Vert _{2}$ ?
2
votes
2answers
129 views

Constrained maximization problem

I need help with the following optimization problem $$ \max\;\alpha\ln(x(1-y^2))+(1-\alpha)\ln(z) $$ where the maximization is with respect to $x,y,z$, subject to \begin{align} \alpha ...
2
votes
2answers
111 views

Geometric difference between $x^TAx$ and $x^TAx + b^Tx + c$

What is the difference between $x^TAx$ and $x^TAx + b^Tx + c$ geometrically? Some analogous examples from quadriatic equations would be great.
2
votes
2answers
2k views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...