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

learn more… | top users | synonyms

0
votes
1answer
19 views

What modification is this of the notion of Renyi divergence?

Given two probability distributions $P$ and $Q$ over the same outcome and event space (assume finite if needed) one defines their Renyi divergence as $D_\alpha (P \vert \vert Q) = \frac{1}{\alpha -1} ...
-1
votes
0answers
34 views

Why is the affine hull of the unit circle $\mathbb{R}^2$?

My question is addressed in Why is the affine hull of the unit circle $\mathbb R^2$? However, I am still confused. I thought that the affine of C in this case would be the interior of the circle. I ...
-1
votes
1answer
25 views

Image restoration in matlab via PDE toolbox

I want to remove a noise for an image using matlab, when the observed image is $$f=u+v$$ where $u$ is the restored image (is the image i want recovered) and $v$ is the gaussian noise. To restore $u$, ...
0
votes
0answers
41 views

Concave optimization and corner solution

I have a optimization problem as follows: Assumptions: $f$ is an increasing and convex function on $R^+$ such that: $f(x): R^+\rightarrow R^+, \quad f(0)=0, \quad f'(x)\ge1,\quad f''(x)\ge 0 ...
0
votes
0answers
13 views

Should the object function value be decreasing during the iteration procedure in ADMM

I want to solve the following convex optimization problem: $$\operatorname{argmin}\limits_X\|Ax-b\|_2^2+\lambda\sum_{i=1}^3 \|X_i\|_{*}$$ where $X$ is a three order tensor, $X_{(i)}$ is a matrix ...
1
vote
1answer
34 views

How to resolve total variation $F(u)=f(u)+\lambda\sum_i^N\int_{\Omega}|\nabla u_i(x)|dx$

Given $u(x)=[u_1(x)..u_N(x)]$, $0 \le u_i(x) \le 1, \sum_i^N u_i(x)=1$ and the cost function is: $$F(u)=f(u(x))+\lambda\sum_i^N\int_{\Omega}|\nabla u_i(x)|dx$$ where $u_i(x)$ is a value that indicate ...
3
votes
3answers
72 views

How to show the convexity of this set

Is the set, $S=\{\bf x \in \mathbb{R}^n: \sum_{i=1}^{n} \frac{e^{x_i}}{1+e^{x_i}}=1 \}$, a convex set?
0
votes
1answer
15 views

Is it covex function?$J_{new}(u)=\int_{\Omega} \sum_{i=1}^{N} \lambda_if(x)u_i(x)dx$

I have a function such as $$J(u)=\int_{\Omega} \sum_{i=1}^{N} f(x)u_i(x)dx$$ where $f(x):\Omega \to R$, $0 \le u_i(x) \le 1,\sum_i u_i(x)=1$ Given that $J(u)$ is a convex function w.r.t $u$. Now I ...
0
votes
0answers
11 views

the convergence of ADMM [on hold]

I solve a convex optimization problem by ADMM, I calculate the value of object function in each step ans plot it, why isn't the value increase decreasing? I don't know whether value of object ...
2
votes
0answers
41 views

Least Squares Nuclear Norm Optimization

I have the following least squares nuclear norm problem, $$ \min_{\bf X} \frac{1}{2}{\left\lVert {\bf b} - {{\bf W}}vec({\bf X}) \right\rVert}^2_2 + {\lambda_*}\Arrowvert {\bf X} \Arrowvert_* $$ ...
1
vote
0answers
14 views

Convergence results for block coordinate descent methods

I am trying to solve the problem minimize $f(x)$ subject to $x_1 \in C_1, x_2\in C_2, ... x_m\in C_m$ where $x_1, ..., x_m$ are block subvectors of $x$, and $C_i$ are each closed convex sets (not ...
2
votes
0answers
12 views

Accelerated Gradient Descent V.S Nonlinear Conjugate Gradient Descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has ...
0
votes
1answer
33 views

Optimization Example with some constraints !? [on hold]

We want to optimize the following function: $$ f(x,y)=x^2+3y^2+2xy+2 $$ with constraints $-2 \leq x< 2$, $-2 <y<2$, and $3y^2+x \leq 10$. Who can help me for the above example from ...
0
votes
0answers
21 views

non-linearity and non-convexity

I am taking a course on linear regression online and it talks about the sum of square difference cost function and one of the points it makes is that the cost function is always convex i.e. it has ...
1
vote
1answer
29 views

Matrix norm in the objective of an optimization problem

I am stuck with the following optimization problem from research. The optimization problem have the following objective function: $\|Q-H\|_\infty$. Here $Q$ is a PSD matrix and $H$ is a symmetric ...
1
vote
0answers
17 views

Question about sub differentiability of convex function

I am reading this book to study sub differentiability. On page 20 it says, as $V$ is a normed linear space for simplification, "a continuous affine function $l(v)$: $V\to \mathbb R$ everywhere less ...
0
votes
0answers
27 views

Compressive sensing for complex matrix

I'm fairly new to compressive sensing, and I have been looking for a MATLAB implementation of the problem $$ A x = b $$ where $A$ is non square, $x$ is kind of sparse and all the numbers involved are ...
2
votes
0answers
41 views

How does one evaluate the derivative of a matrix with a tensor $\frac{\partial \operatorname{Tr}[A(\mathrm{Id}\otimes w)]}{\partial w}$?

I am stuck on the following: $$\frac{\partial \operatorname{Tr}[A(\mathrm{Id}\otimes w)]}{\partial w}=\text{ ?}$$ with $A$ a $d\times d^2$ matrix, $\mathrm{Id}$ the identity matrix of $d\times d$ ...
1
vote
1answer
42 views

Can I solve a problem like a combination of PCA and compressed sensing?

$$ \underset{A,x}{\text{minimize}} \quad \lambda \left\| x \right\|_{1} + \left\| A \right\|_{*} $$ $$ D = A + Mx $$ Where $M \in \mathbb{R}^{n \times m}$, $x \in \mathbb{R}^{m \times z}$, $E=Mx \in ...
0
votes
0answers
38 views

Minimizing a quadratic term

$\mathbf{x_1},\mathbf{x_2}$ are known and I need to solve the following objective wrt to one variable $\mathbf{y}$. The single constraint is $y(1,1)=1$. This is expressed as an inner product ...
3
votes
2answers
57 views

In linear programming, how to check whether a convex polyhedron is contained in another

Suppose we have two convex polyhedra $P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$ and $P_2=\{x\in \mathbb{R}^n \mid A_2 x \geq b_2 \}$ Is there a way to check whether $P_1 \subseteq P_2$? I was ...
0
votes
0answers
18 views

What's the difference between this proximal method and subgradient projection?

http://stanford.edu/~boyd/papers/pdf/prox_algs.pdf In the link above it is proposed that the nonsmooth separable resource allocation problem $$\min \sum f_i(x_i) \ \ \text{s.t.} \ \ \textbf{1}^Tx = ...
1
vote
1answer
18 views

Subgradient of the optimal value of a linear program with respect to its parameters

Consider the linear program $f(c)=\min\{c'x\mid x\in\mathbb{R}^n,Ax=b,x\geq0\}$. Are there any results on what is $\partial f/\partial b$?
1
vote
1answer
33 views

How to pivot to an adjacent vertex in simplex method

In the simplex method, we need to move from one vertex of the polyhedron to an adjacent one. Suppose the polyhedron is $P=\{x\in\mathbb{R}^n\mid Ax=b,x\geq0\}$ with rank$A=m<n$. For a ...
1
vote
0answers
20 views

Is $K =\{ S: \exists \text{ positive diagonal} D, D^TSD \;\text{diagonally dominant}\}$ convex?

I am doing some convex cone optimization and wonder whether the following set $K_1$ is convex or not. Assume the following matrices are all in $\mathbb{R}^{n\times n}$ and symmetric. Let the set of ...
1
vote
1answer
33 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 ...
0
votes
0answers
6 views

Gomory's cut typical running time until the constraint is fractional

I was considering the following problem. Say we are given an linear programming problem $$ \max c^Tx $$ $$ Ax \le b $$ $$ x \ge 0$$ Where instead I consider $i^{th}$ the optimal solution $X_i$ of ...
2
votes
0answers
32 views

how to find the edges emanating from a given vertex in a polyhedron

Suppose my polyhedron $P$ is defined as $P={ x\in \mathbb{R}^n \mid Ax=b, x\geq0 }$ I have $x_0$, which is a vertex of $P$. How to find the edges emanating from $x_0$? In other words, I want to find ...
0
votes
2answers
33 views

Minimum quadratic form value within a line?

If I have $x\in R^n , C\in R^{m\times n}, d\in R^m$, $m<n$, then $Cx=d$ is a linear manifold. And $P\in R^{n\times n}$, $P>0$, the quadratic form is $y=x^TPx$ Is there an analytical expression ...
0
votes
1answer
26 views

How do I prove that objective function is not convex

Here is my objective function. \begin{equation} \begin{array}{c} \underset{\mathbf{x},\mathbf{y}}{\text{minimize}}\hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + ...
0
votes
0answers
13 views

Convex signal reconstruction for convex generator function?

Let $f : \mathbb{R} \mapsto \mathbb{R}$ be a convex (not affine) function and suppose that $y = f(x)$. We want to reconstruct the input $x$ for a given $y$, and the standard approach would be to ...
0
votes
0answers
13 views

how do I enter this objective function in cvx [closed]

Following is my expression.$\mathbf{z}$ is a vector and $\mathbf{P_i}$ is a matrix. Also $i>0$ and is not fixed. I am not sure how to I enter this objective function in cvx? ...
0
votes
1answer
31 views

The Legendre-Fenchel transform of $BV$ semi-norm

I am reading a numerical paper in which it calls some "easy" facts from convex analysis but I can't justify it... Let $\Omega\subset \mathbb R^2$ be open. Define for a function $u\in L^1(\Omega)$ and ...
0
votes
0answers
26 views

Convex envelopes of bivariate functions

In order to convexify my nonlinear non-convex program I need convex envelopes for the function $(x/y)^2$, both x,y are positive. I am only aware of the convex envelopes of the type $xy$ from here ...
0
votes
0answers
14 views

Rewriting a strictly convex quadratic equality constraint

I have the following constraint $$ x^TAx+b^Tx=c $$ where $A$ is a positive definite matrix. Is there any way to take advantage of the strict convexity of this expression to reformulate the constraint ...
2
votes
1answer
123 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 ...
0
votes
0answers
12 views

Find the nearest point of $y$ from a probability simplex. [duplicate]

I need to compute the nearest point of $x$ from a probability simplex. Formally, I want to ask if there is a close form for the solution to the following optimization problem: for $y\in \mathbb{R}^k$, ...
0
votes
1answer
23 views

Functional Lifting in Optimisation - Reference Request

I'm looking to learn about the use of (functional) lifting applied to a non-convex optimisation problem to give a (larger) convex problem. Unfortunately, I'm having a great deal of trouble finding ...
1
vote
0answers
46 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in ...
0
votes
0answers
17 views

Find $U \subset D $ with $|U|$ minimal s.t $v = (1/2,1/2,1/2)$ belongs to the convex hull of $U$.

Consider the convex hull $\text {conv} \{e_1,e_2,e_3,(1,1/2,1/2),(1/2,1,1/2), (1/2,1/2,1)\}$ in $\mathbb R^3$ and the vector $v = (1/2,1/2,1/2)$. I want to compute $U \subset ...
0
votes
0answers
20 views

strengths and weaknesses of analytical method

I was wondering if anyone could suggest any books or paper that explain/discuss the advantages and drawbacks of analytical methods for optimization. Also, if we have a convex objective function ...
0
votes
0answers
20 views

Invex function? How can I show?

Let $\mathbb{S}^m_+$ and $\mathbb{M}^{(m,n)}$, respectively, be the closed cone of positive semidefinite matrices and space of $m\times n$-dimensional matrices. Define function $F$ as ...
1
vote
0answers
19 views

How to define the nuclear norm of a tensor

As we know,the nuclear norm of a matrix $X$ is defined as this: $$||X||_{*}=\sum{\sigma_{i}}$$ where $\sigma_{i}$ is the singular value of $X$. But how to define the nuclear norm of a tensor ...
0
votes
2answers
116 views

Prove a closed ball in $\mathbb R^3$ has an infinite number of extreme points.

How do I show that a closed ball in $\mathbb R^3$ has an infinite number of extreme points ? (Closed ball is written as $S = \{(x,y,z) \in \mathbb R^3 | \sqrt {x^2 + y^2 + z^2} \le R \}$) I know ...
0
votes
1answer
47 views

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove $(1-\lambda)x + \lambda y \in S$ for $x=\lambda'y$, $\lambda' < 0$.

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. I've verified that $x,y \in S$ implies $(1-\lambda)x + \lambda y \in S$ when $x,y$ are linearly independent using Pythagoras and when ...
0
votes
1answer
18 views

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these. I want to compute all the extreme points of the set $P$ (polyhedron) in $\mathbb R^3$ ...
3
votes
2answers
45 views

Can $\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$ be reduced to a convex hull of a subset of these?

How do I see whether $$\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$$ can be reduced to a convex hull of a subset of these vectors? That is, if $D = \{ e_1,e_2,e_3, ...
0
votes
1answer
25 views

How do I show that the set $S$ in $\mathbb R^3$ defined by linear inequalities is a $3$-simplex?

Consider the set $S$ in $\mathbb R^3$ defined by the inequalities: $x+y+z \ge 1$ $-x+y+z \le 1$ $x-y+z \le 1$ $x+y-z \le 1$ How can I show that $S$ is a $3$-simplex ? (Convex hull of $3 + 1$ ...
0
votes
1answer
25 views

How to introduce auxiliary variables to make the objective function separable?

$$\min_{X}\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*}+\lambda\|Ax-b\|_2^2$$ where $X$ is a three order tensor, $X_{(i)}$ is a matrix whose column are the mode-$i$ fibers of $X$(i=1,2,3),$x$ is ...
0
votes
5answers
86 views

Let $B=\{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove existence of a unique point $v_0 \in B$ that is closest to $v \notin B$?

Suppose $B=\{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Consider a point $v \notin B$. How do I prove that there exist a unique point $v_0 \in B$ that is closest to $v$. Also, how do I ...