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

learn more… | top users | synonyms

1
vote
1answer
46 views

Dual formulation of an SDP problem

Could you help me formulate the dual problem to this SDP? maximize $\frac{1}{2} Tr(GW)$, subject to $ G \ge 0$ (and G symmetric), and $ \forall i$, $ G_{ii} = G_{1i} = G_{i1} $ Note that $G$ and ...
1
vote
0answers
20 views

restricted set of a convex set

Let $S \subset \mathbb R^n$, $S$ is convex and let $||.||$ be a norm on $\mathbb R^n.$ For $a \ge 0$ we define $S_{-a} =\{ x | B(x,a) \in S\}$, where $B(x,a)$ is the ball (in the norm $||.||)$, ...
1
vote
0answers
57 views

Reference table of “tricks” for converting problems to standard LP, QP, SOCP, etc. form?

Where can I find a decent source/reference that which I can use to look up the various standard "tricks" for converting typical problems to standard form in LP, QP, SOCP, etc.? The Charnes-Cooper ...
1
vote
1answer
181 views

Proof of the Moreau decomposition property of proximal operators?

Given the prox operator i.e. $ prox_h (x) = arg min_u (h(u) + 1/2 ||u-x||^2_2) $ the Moreau decomposition property says that $ x = prox_h (x) + prox_{h^*} (x) $ where $h^*$ is the conjugate of ...
1
vote
1answer
54 views

Examples of affine functions and convex sets

I'm just learning about convexity and affineness, and I've read over some similar questions asked here, but those were more about general properties. I need some help applying those properties to a ...
1
vote
1answer
109 views

Confusion related to augmented lagrangian multiplier method

I have this confusion related to the augmented lagrangian multiplier method from this tutorial How come the gradient wrt y is equal to $\rho(Ax^{k+1}-b)$
1
vote
1answer
93 views

Tangent Cone is a cone?

I first give two definitions. Def1: A set $S$ is a cone if $x \in S, \lambda \geq 0 \implies \lambda x \in S$. Def2: Let $S$ be any set (we may assume $\mathbb{R}^n$ with the usual Euclidean ...
1
vote
0answers
122 views

Until now, what is the fastest optimization algorithm of non-smooth convex functions

I am wondering if I minimize a non-smooth convex function, which solver should I choose. I think I should choose a fastest one with a big convergence rate. Subgradient descent is always on the ...
1
vote
0answers
29 views

Dual of the mixed $\ell_1/\ell_2$ norm?

The mixed $\ell_1/\ell_2$ norm $\Omega_{12} $ is defined as $\Omega_{12}(x) = \sum_g ||x_g||_2$ where $x_g$ are disjoint subsets of the elements of the vector $x$. This is used in machine learning ...
1
vote
0answers
27 views

can we prove that a certain supremum of affine functions is frechet differentiable or at least continuous?

Let $X$ be a Hilbert space. Let $A\colon \operatorname{dom} A\to X$ be linear operator with closed graph (not necessarily bounded). Define $$ g\colon \operatorname{dom}A\to \mathbb{R}:x\mapsto ...
1
vote
1answer
33 views

Approximate an exponential function

I have an optimization problem, where I would like to minimize $$F=\exp(\mathrm{trace}(A)+\frac{1}{2}\mathrm{trace}(A^2)-\lambda)$$ where $A$ is a non-negative matrix. Is it possible to replace $F$ ...
1
vote
0answers
17 views

Uniqueness of the solution to a quadratic opt problem

Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...
1
vote
1answer
97 views

The convex conjugate of a quadratic form with positive semi definite matrix

I want to find the convex conjugate (Legendre transform) of a quadratic for $1/2x^{t}Qx$ when $Q$ is positive semi-definite. If Q is non-singular, the solution is easy - the gradient is $y-Qx=0$ so ...
1
vote
0answers
195 views

Minimum L1 norm may not obtain the sparsest solution?

Here is a paper called For Most Large Underdetermined Systems of Equations, the Minimal L1-norm Near-Solution Approximates the Sparsest Near-Solution. However, I did not quite get its definition of ...
1
vote
0answers
65 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book ...
1
vote
1answer
43 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
1
vote
1answer
68 views

Convexity of a region on probability simplex

Exercise 2.15 g of Boyd et al Convex Optimization book : On the probability simplex in $\mathbb{R}^n$ where each point $p = (p_1,p_2,p_3,\ldots,p_n)$ corresponds to a distribution for random variable ...
1
vote
1answer
186 views

Sum of euclidean norms with box constraints

minimizing the sum of euclidean norms with box constraints I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
1
vote
0answers
34 views

Is $A^TP+PA<0$, $P>0$ and $A^TP+PA\leq-I$, $P\geq I$ equivalent?

Consider the LMI, where $A$ is a Hurwitz matrix: $A^TP+PA<0$, $P>0$, minimize trace(P) According to Stephen Boyd's book, the inequalities are homogeneous in P and hence can by replaced with ...
1
vote
1answer
41 views

Is $|| AXB-C ||_F$ convex?

Let $A \in \mathbb R^{n\times n}$, $B \in \mathbb R^{n\times n}$, $C \in \mathbb R^{n\times n}$ be constant matrices. Is the following convex? minimize $|| AXB-C ||_F$ for $X>0$, where $|| \dots ...
1
vote
0answers
60 views

Cauchy point,derivation: whe the constrianed optimizitaion is not used

Sorry for the slightly longer question. Consider the following definition of the Cauchy point $h_{i}^{C}=\alpha_{i}^{C}h_{i}.$ It can be found minimizing a quadratic form ...
1
vote
0answers
59 views

Some problems with a proof of the Farkas Lemma

The following is a proof of the Farkas Lemma that is creating me quite some problems. [I presented the all proof simply to point out the notation used by the author.] My problem is with the last part ...
1
vote
0answers
40 views

Differentiability of the Value (Support) Function

Consider the following problem, \begin{align} c(y,\mathbf{w})=\inf_{\substack{\mathbf{x} \in \mathbb{R}^n_{+} \\ \text{s.t. }f(\mathbf{x}) \geq y }} \mathbf{w} \cdot \mathbf{x} \end{align} where ...
1
vote
0answers
106 views

Whitening matrix for Fast ICA

I have a matrix $X $ with dimension say $ m \times n $ with $ m> n $. I am trying to whiten this matrix in matlab by first taking the $C= \operatorname{covariance}(X)$ followed by eigenvalue ...
1
vote
1answer
40 views

Motivation : min cut and max flow

Can someone explain the motivation behind the min cut and max flow problem?
1
vote
0answers
64 views

Joint cost function with Lagrangian

How can I formulate joint cost functions if Lagrangians are involved? For example, if I have $J_1 = \|\mathbf{Ax} - \mathbf{b}\|^2_2 + \lambda f$ and $J_2 = \|\mathbf{Cx} - \mathbf{d}\|^2_2$, ...
1
vote
0answers
39 views

Is there a textbook treatment of Ky Fan's minimax theorem and its generalizations?

Theorem 2 in Ky Fan(1952) is a powerful tool in zero-sum games, which states: Let $X$ be a compact Hausdorff space and $Y$ an arbitary set (not topologized). Let $f$ be a real-valued function on ...
1
vote
1answer
24 views

References or texts for learning about the augmented lagrangian?

I am reading a paper about a convex model for non-negative matrix factorization. In the paper it describes how to do such a technique and it says that it uses the augmented Lagrangian. I can't find ...
1
vote
0answers
44 views

Issues with quasi Newton method convergence

I have this issue with the convergence of the quasi newton method. I have a convex objective function which I need to minimize wrt some parameters. I generated some synthetic data using a defined ...
1
vote
0answers
64 views

Strong Duality and Duals of linear programming problem

I have the following problem: $ max_{x,y} \ x + y $ subject to $ 2x + y \leq 1 $ $ x + 3y \leq 3 $ $ x,y \geq 0 $ How to find the dual of this problem using the Lagrangian? I have done the ...
1
vote
0answers
23 views

Issues related to positive definiteness in a convex optimization problem

I have some issues in a convex optimization problem. My f(X) is a convex function of X where X is a positive definite matrix. X is very sparse and has a handful of non zeros values. Now I only need to ...
1
vote
0answers
21 views

Confusion related to interior point method

I was reading this wiki article related to interior point method. I didn't get when they say that it applied Newton's method to get an update for $(x,\lambda)$. How the expression at the end ...
1
vote
0answers
58 views

Confusion related to fmincon function in matlab

I was reading this help section of matlab's fmincon function that uses interior point algorithm for solving an optimization problem. It says the following optimization problem is replaced by To ...
1
vote
0answers
52 views

Is the following problem convex , quasiconvex, or nonconvex?

I want to get the optimal matrix $W$. But I am not sure whether it can be resolved. Note that $W,\mu,\lambda_{1},\ldots,\lambda_{K} $ are variables, others are fixed. Is it convex or quasiconvex or ...
1
vote
1answer
330 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
1
vote
0answers
33 views

Is the optimizer of a strongly-convex cost function bounded?

Let f(x) be strongly-convex. Can its minimizer be unbounded? I suspect not. Can we obtain a bound on it in relation to the strong-convexity constant? I believe an equivalent formulation of this ...
1
vote
1answer
102 views

Minimize Trace for non-symmetric matrix

Let $A$ be a given matrix and $X$ a symmetric positive definite matrix which shall be optimized: min $tr (AX)$ subject to $X>0$ This optimization problem is convex if $A$ is symmetric as it is ...
1
vote
0answers
23 views

Is $Q(b)=a^Hb+b^Ha$ ,where $a,b \in \mathbb{C}^{N\times1},b^Hb\leq\epsilon^2$convex or concave?

We assume that $a,b \in \mathbb{C}^{N\times1},b^Hb\leq\epsilon^2$. Is the function $Q(b)=a^Hb+b^Ha$ convex,concave? In other words, which of the following problems is feasible? $\min\ \ ...
1
vote
0answers
24 views

The timestep of Forward–backward algorithm

Recently, I try to learn Forward backward splitting algorithm. I find it was proposed in 1988 'Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational ...
1
vote
1answer
107 views

Relaxation of of sum of logarithms of affine function

As a constraint in an optimization program I have a sum of logarithm, $$\sum_{i=1}^{K}\log(1+c_ix_i)\le e,$$ where $\mathbf{c} = (c_1,c_2,\cdots,c_K)$ is a constant positive vector and ...
1
vote
0answers
57 views

Confusion related to k neighborly polytope

I was reading this paper related to neighborly polytope where they mentioned: Consider a $d \times n$ matrix $A$, with $d < n$. The problem of solving for $x$ in $y = Ax$ is underdetermined, ...
1
vote
2answers
72 views

Analytically solving simple quadratic problem in single variable with boundary constraints

I want to solve the following optimization problem where $x$ is scalar variable. $$ \min_x \dfrac12ax^2 + bx \\ subject\ to:\ l\le x \le u $$ $ a > 0 $ therefore, this is a convex optimization ...
1
vote
1answer
76 views

Linear System with constrained solutions

After a model my problem I found a rectangular linear system : $$Ax=b$$ I can easely solve it with a least square with QR/SVD... But the model include constrains for each solution $x_i$, the $\vec{x}$ ...
1
vote
0answers
36 views

Least square with constraints

I want to solve the least squares problem $(Ax-b)^2$ with no intercept term for linear regression with the constraint that the sum of the params/weights is equal to 1. I am trying to get the closed ...
1
vote
0answers
39 views

Issues with CVX package for optimization

I am trying to use the cvx package for optimization. However, I am having some issues with it. I have a variable X which is a matrix but I cannot add $X^{-1}$ in the objective function. What should I ...
1
vote
1answer
326 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 ...
1
vote
0answers
41 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}$ ...
1
vote
0answers
15 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
1answer
157 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
49 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 & ...