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

learn more… | top users | synonyms

0
votes
1answer
22 views

how to calculate the projection of a vector onto a closed convex set? [duplicate]

suppose we have a vector $x \in \mathbb{R}^{n}$, and a closed convex set $C \in \mathbb{R}^{n}$. $C =\{x|Ax=b\}$ how to calculate the vector $y \in \mathbb{R}^{n}$, which is the projection of $x$ ...
2
votes
0answers
31 views

Is this optimization problem feasible and bounded?

A long question with a short answer. In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm ...
0
votes
1answer
9 views

Linear objective with quadratic constraints

I have the problem $$ \text{maximize } f= c^Tx \\ \text{subject to } x^T Q x \leq 1 \\ x,c \in \mathbb{R}^n \text{ , } Q \in \mathbb{R}^{n \times n} $$ and $ Q $ is additionally symmetric positive ...
1
vote
0answers
22 views

Regression linearization to apply Gauss-Newton

I want to try and use Gauss-Newton in order to estimate a solution to the regression problem with normalizing factor $$\min_{x \in \mathbb{R}^n}: \|y - Ax\|_2^2 + \lambda\|x\|_1.$$ To do this, I have ...
0
votes
2answers
40 views

Is the projection function convex?

Define the following function $f:\mathbb{R}^n\rightarrow \mathbb{R}^n$ to be the projection function onto a convex and a closed set C $f(x)=\arg\min_{y\in C} ||x-y||_2^2 $ Denote $f_i(x)$ ...
0
votes
1answer
28 views

A small but quite general question about the optimization

If I have a minimization problem in which both the objective function and constraint are nonconvex. I use gradient projection method to solve the problem iteratively. If we relax the constraint and ...
1
vote
1answer
27 views

Is this function composition convex?

Say we have two functions $f:R^n\rightarrow R$ , $g:R^m\rightarrow R^n$. Given that $f$ is convex, under what conditions on $f$ and $g$ we will be able to say that the composition function ...
1
vote
1answer
8 views

Interior of polar cone and self-concordant function

Suppose $f$ is a self-concordant(see 9.6.2) barrier of a proper cone $K$ ( solid,convex, closed and pointed) in $\mathbb{R}^n$. It looks like the value of all $\nabla f$ is just the interior of the ...
0
votes
1answer
27 views

Failing To Frame Convex Non-Linear Problem as SOCP

I'm trying to reproduce an equation from equation 5 in the paper here: https://web.stanford.edu/~boyd/papers/pdf/rob_downlink_bf.pdf The equation is an SOCP of the form: ...
0
votes
1answer
25 views

Prove if C is midpoint convex and closed then its a convex set [duplicate]

Midpoint convexity. A set C is midpoint convex if whenever two points a,b are in C, the average or midpoint (a + b)/2 is in C.Prove that if C is closed and midpoint convex, then C is convex. ...
1
vote
0answers
33 views

Unique solution of LP

Hi I am working on the following question: If $c \in int(N_P(x))$, then $x$ is a unique solution. I have proven that this is true if $x$ is a vertex. Well I am wondering if the following is a ...
0
votes
0answers
21 views

Multivariable gradient descent with approximation of gradinet

This is not a statistics problem I have a vector $$X=[x_1,...,x_{10}]$$ and a cost function $$y=F(X)$$ and my aim in to find the best $X$ to minimize the cost function. It is impossible to ...
1
vote
1answer
18 views

Can I write $\mathbb{S}_+^3$ as a norm cone?

Let $\mathbb{S}^3_+$ be the set of $3\times 3$ symmetric semi-definite positive matrix. I wonder whether I can write $\mathbb{S}^3_+$ as a norm cone, i.e., $$\exists A\in \mathbb{R}^{m\times 9}, C, ...
1
vote
1answer
21 views

Can I write $\mathbb{R}^n_+$ as a norm cone?

Let $\mathbb{R}^n_+=\{x=(x_1,\dots,x_n):x_i\geq 0,\forall i \},n\geq 2$. I wonder whether I can write $\mathbb{R}^n_+$ as a norm cone, i.e., $$\exists A, c, \|\cdot\|, s.t. x \in \mathbb{R}^n_+ \iff ...
0
votes
0answers
21 views

What is the right isomorphism for convex set in $\mathbb{R}^n$

Like we have linear transformation for vector space, I wonder what kind of 'transformation' or 'homomorphism' or 'isomorphism'( when the map is bijective) to look at for convex set in $\mathbb{R}^n$. ...
0
votes
1answer
40 views

What's wrong in this dual derivation?

I have a function in the form \begin{align} f(q,M)=\sup_{0\leq \alpha \leq 1} -\alpha^T (R\odot M)\alpha+\alpha^Tq \end{align} which is a dual of a minimization problem, where $R$ and $M$ are ...
-2
votes
0answers
23 views

This fractional quadratic optimization problem is non-Convex, why?

Why is the following function $f(x)$ non-convex? $$ f(x)=\min\frac{x^TQx}{x^TPx+1} $$ where $Q$ and $P$ are positive semi-definite matrices.
0
votes
1answer
43 views

What is a proximity operator? why do we need it?

I am going to deal with convex optimization problems and I am not a math student so I may have some problems in understanding some topics. As you know, many of the optimization problems lead to a cost ...
0
votes
0answers
25 views

Strong convexity of quadratic function

Assume that $Q$ is a positive definite matrix, is it true to say that the function $f(v)=v^TQv$ is strongly convex with respect to the norm $||u||=\sqrt{u^TQu}$? Thanks
0
votes
2answers
40 views

Calculation of minimum infinity norm subject to L1 norm

Can somebody tell me how to evaluate the following in MATLAB or any other programming language? \begin{equation} \min_{x \in \partial \|w\|_1} \| x+y\|_\infty \end{equation} $x,w,y \in R^n$. $w,y$ ...
0
votes
0answers
17 views

Notion of outer normal cone and supporting cone if $x \in$ relint($C$)

In my lecture we defined the outer normal cone $ N_c(x^*)= \{ c\ \in \mathbb{R^n} : \max\limits_{x \in C} \ \ c^Tx = c^Tx^* \}$ and the supporting cone $S_C(x^*)= \bigcap\limits_{c \in N_c(x^*)} ...
0
votes
0answers
40 views

On a modified least square.

Given a vector $y \in \mathbb R^n$ and real constants $x_{ij}$ ($i=1,\dots,n$, $j=1,\dots,p$), we consider a vector $\beta = (\beta_0,\dots,\beta_p)$ which minimize ...
-1
votes
0answers
26 views

How to solve following optimization problem for a classifier using Lagrangian relaxation and subgradient? [closed]

\begin{align} \min &\quad H\\ \mathrm{s.t.} &\quad H \geqslant y_i(Wx_i+b)\\ &\quad y_i(Wx_i+b) \geqslant 1 \end{align} I am unable to get how to solve this optimization problem without ...
-1
votes
0answers
25 views

How doI solve given linear optimization equation by subgradient method? [closed]

Given the linear program \begin{align} \min &\quad cx\\ \mathrm{s.t.} &\quad Ax\geqslant b\\ &\quad Bx\geqslant d \end{align} The Lagrangian lower bound program would be reduced to: ...
0
votes
0answers
44 views

Computational complexity of the following quadratic program (QP)

Let $A^TA$ be a $n \times n$ matrix. I have the following quadratic program to solve: \begin{array}{rl} \min \limits_{x} & x^T A^T A x \\ \mbox{subject to} & \sum_{i=1}^{r} x_i =1, ...
0
votes
0answers
21 views

How to judge the convexity of this function?

$ f(X) = -\log \det(X^TX+I)$, $X \in \mathbb{R}^{n \times n}$, is this function convex or not? Does anybody have an idea about this problem? Thanks.
0
votes
0answers
20 views

Indicator function to zero-set of a function

Given the indicator function $I_{C}: \mathbb{R} \rightarrow \mathbb{R}$ to a convex set $C \subset \mathbb{R}$ and a function $g(x): \mathbb{R}^n \rightarrow \mathbb{R}$ $$ I_{C}(g(x)) = ...
0
votes
0answers
10 views

Can Somebody Help Me Find A Certain Paper about Hybrid Proximal Extragradient method for Bregman Functions?

I have read these two papers by Svaiter and Solodov. The first one, published in 1999 (http://pages.cs.wisc.edu/~solodov/solsva99Teps.pdf) presents an error criterion for the hybrid proximal ...
3
votes
0answers
37 views

Is minmax equivalent to maxmin?

More precisely, problem $1$ is as follows: \begin{eqnarray} &\max_{1{\le}i{\le}N}\min_{[\gamma_m^i]}\left[\lambda_i - \sum_{m=1}^M\phi_m\gamma_m^iF_m^i\right] \\ &\mbox{subject to} ...
0
votes
1answer
26 views

Matrix equation from optimization problem

I am having a problem to find the solution to the following equation which has arisen as part of the solution of a (convex) optimization problem I am considering. $$\left(\frac{a}{n ...
0
votes
1answer
21 views

Strong convexity, non-smoothness, and directional derivative

I have a function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ that is (strongly) convex (say in $\mathbb{R}^n$), but not necessarily differentiable. It attains its minimum at $\mathbf{q}$. Given two ...
0
votes
1answer
5 views

concavity of functions of many variables

I have a function in many variables, the function is concave and non-increasing in each one of the variables, is the entire function concave?
0
votes
0answers
18 views

Newton-Raphson convergence for function $f(\gamma)$ with $\gamma \geq0$ constraint.

I am reading an (engineering) paper that in the part of their solution, They propose a 2-step iterative solution based on Newton-Raphson method for concave function $f$ as below : ...
0
votes
1answer
14 views

Gauss-Newton convergence for constant Hessian

If I use Gauss-Newton to solve a least square optimization problem and $\mathbf{J}^H\mathbf{J}$ is constant does it imply that I will reach the solution in one iteration?
0
votes
1answer
33 views

Non-vanishing of sub gradient near optimal solution

Consider the non-smooth optimization problem \begin{equation} \min_{x \in \mathbb{R}^n} f(x). \end{equation} To solve the above problem, I am suing subgradient descent \begin{equation} ...
-1
votes
0answers
19 views

How to transform this problem to a matrix optimization problem?

I wonder how can I loose the following set of equations to an optimization problem ? Suppose given three real vectors $w_0$, $f$ and $\delta$, and a positive entry vector $c$, such that for every ...
0
votes
1answer
15 views

Partitioning in convex problem (variables in two subsets)

Consider the following problem from textbook Convex Optimization Algorithm p.10: \begin{equation} \begin{aligned} &{\text{min}} & & F(x)+G(y)\\ ...
4
votes
1answer
34 views

Why lower semicontinuity?

I'm reading a proof on the existence of a solution to a minimisation problem, but I'm stuck. I give a brief summary of the arguments up to the point at which I'm stuck(at the yellow box). ...
0
votes
1answer
17 views

Proving convergence of projected subgradient descent

Any idea how to sum the series $\sum_{t=1}^T \frac{1}{\sqrt{t}} (\|x_t -a\|^2 -\|x_{t+1}-a\|^2) $, where $a$ is any constant and you can assume $\|x_{T+1}-a\|=0$. This sum occured in proving ...
0
votes
1answer
29 views

Gradient descent with linear perturbation

Given a convex, differentiable function $f$ (from a Hilbert space to $\mathbb{R}$) with a minimum (say $x^*$), I know you can find $x^*$ using gradient descent. Suppose now that you apply gradient ...
0
votes
0answers
18 views

Existence of lagrange multipliers with polyhedral constraints

I am working with a paper (Exact regularization of polyhedral norms, Schöpfer 2012) which states as a well-known fact that, if $f$ is a polyhedral norm, then for some $\mu^* > 0$ \begin{equation} ...
0
votes
0answers
30 views

optimization of a function with inequality constraint

I have a function to be maximized subject to constraints. I can write the primal Lagrange function as the following: (objective function WITH two constraints in the last two terms) $$L_P = ...
1
vote
1answer
57 views

Arc length function of a helix/spiral is convex?

Given the arc-length of a parametric curve, $\int_a^b\|\gamma'(t)\|$ if the parametric curve was non-convex, can the arc length be a convex function?If the parametric curve was convex, will the arc ...
0
votes
1answer
42 views

How to computer the proximal operator of a indicator function?

For $G_{1}(x) = I_{c}(x), c =\{x|Ax=b\}$, the Proximal operator is: $Prox_{\gamma G_{1}}(x) = Proj_{c}(x) = x + A^{T}(AA^{T})^{-1}(y-Ax)$ I hope to know, how to derivative this result. And, for ...
0
votes
1answer
33 views

Is this function convex or non-convex? How do you decide?

The problem is: find $$\min⁡ \mathrm{P}\left[{\log(1+p||H^H \mathbf{w}||^2)\over 1+p||G^H \mathbf{w}||^2}<R\right]$$ constraint to: $||\mathbf{w}||^2=1$ where $H$ and $G$ are matrices of ...
0
votes
1answer
45 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
45 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
39 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
46 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
16 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 ...