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

learn more… | top users | synonyms

1
vote
1answer
9 views

Fenchel duality in conic program

The question is from the textbook Convex Optimization Algorithms, prof. Bertsekas, p.511 A special case of Fenchel duality is the following: \begin{equation} ...
0
votes
0answers
5 views

Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix ...
0
votes
0answers
8 views

The Dual of a Dual problem for Convex Optimization Problem [on hold]

Assume we have a convex optimization problem, and its dual, and there is strong duality between the primal and the dual problem. My question is if we take the dual of the dual problem, how the dual ...
0
votes
0answers
12 views

The Dual Problem

I have a question related to the dual problem of a maximization primal problem with norm inequalities constraints. I want to find the dual problem for the following primal optimization problem: ...
0
votes
0answers
13 views

Augmented Lagrangian method for nonsmooth problem

Given the problem $\min \sum_i f_i(x_i) \ \ ; \ Ax = b, x_i \in [\ell_i,u_i] $, we can construct the augmented Lagrangian as $$L_\rho(x,\lambda) = \sum_i f_i(x_i) + \lambda'(Ax-b) + ...
0
votes
0answers
10 views

Monotropic polyhedrally constrained programming, implementations

I'm looking for algorithm implementations that can solve problems of the type $$\min \sum_i f_i(x_i) \\ s.t. Ax \leq b \\ Cx = d \\ x_i \in [\ell_i,u_i]$$ I.e. polyhedrally constrained optimization ...
0
votes
0answers
20 views

KKT system with rank-deficient constraints

I have an optimization problem of the following form: $$ \begin{aligned} \operatorname*{minimize}_x & \quad \frac{1}{2}||x - a||^2 \\ \operatorname{subject~to} & \quad ...
2
votes
1answer
31 views

How to solve the convex combination problem of matrix?

Let $A \succeq B$ denote matrix $A-B$ is positive semidefinite, and here is the definition of redundant(all the matrix dimensions are $N\times N$ ): Given a set of matrix $\{B_i\}_{i=1}^{l}$, if ...
1
vote
2answers
42 views

Gradient mapping minimization problem

I am trying to solve this particular problem which can be found in this paper: $$\underset{y\in\Delta_n}{\text{argmin}}\{\langle\nabla f(x),y-x\rangle+\dfrac{1}{2}L\|y-x\|_1^2\}$$ I tried formulating ...
0
votes
1answer
25 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
56 views

If this problem is not unbounded, what's wrong in this dual derivation?

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 proposed: \begin{align} \min_{0\leq ...
0
votes
1answer
14 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
43 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
28 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
9 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
34 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
22 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
22 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
44 views
+50

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
24 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
26 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
41 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 ...
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
28 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
19 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
20 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
16 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
59 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 ...