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

learn more… | top users | synonyms

0
votes
0answers
3 views

Prove convexity of function over space of positive definite matrices

I want to show that the function $f(X) = -log \ det(X)$ is convex on the space $S$ of positive definite matrices. What I have done: It seems like this problem could be tackled by considering the ...
0
votes
0answers
9 views

Feasible solutions in semidefinite programming - beyond Slater's theorem

Suppose a semidefinite program is given by: \begin{align} \text{Maximize:}&\quad \text{Tr}\left[AX\right],\\ \text{subject to:}&\quad \Phi\left(X\right)=B,\\ &\quad X\geq 0. \end{align} ...
0
votes
1answer
40 views

Type of convex function?

I want a convex function $f:\mathbb{R} \to \mathbb{R}$ with the following property: given points $x,d \in \mathbb{R}$, and $\alpha \in (0,1)$, we have $$f(x + \alpha d) \geq \alpha f(x + d).$$ Is ...
0
votes
0answers
23 views

Distributed Newton methods for large scale problems

I am keen to know about the literature landscape for distributed convex optimization methods which use second order information like the Newton step. This is as such a less evolved area compared to ...
1
vote
1answer
26 views

Analytical solution to the first PCA direction

It is known that the first PCA direction for a dataset of $n$ points is the unit vector with max variance after projecting the points onto this vector. I wonder whether there are some analytical ...
0
votes
2answers
23 views

convexity of piece wise function

I have a piece-wise function defined on the real line. The pieces are connected continuously, and the second derivative of each piece is strictly positive. Does this means that the function is convex? ...
1
vote
1answer
12 views

Weighted Norm Minimization

I have a minimization problem of the form $min (w_1 \|x\|+w_2\|y\|)$ subject to constraints $A_1x=b_1$, $A_2y=b_2$, $0< l_1 \leq x \leq u_1$ and $0< l_2 \leq y \leq u_2$ where ...
0
votes
2answers
48 views

Looking for numerical methods for finding roots of convex vector function ${\bf f}({\bf x})={\bf 0}$

Consider the function ${\bf f}:\mathbb{R}^n\to\mathbb{R}^m$ defined as ${\bf f} = (f_1,f_2,\ldots,f_m)$ where each $f_i:\mathbb{R}^n\to\mathbb{R}$ is twice-continuously differentiable convex in ${\bf ...
0
votes
1answer
20 views

Properties of functions having the form $g(x,t) = t f(\frac{x}{t})$

I have been frequently coming across the function $g(x,t) = t f(\frac{x}{t})$ in my course on convex optimization. A friend of mine mentioned that it is the perspective function, but the book on ...
0
votes
0answers
20 views

low rank approximation using CVX

I try to use CVX toolbox to do "low rank approximation" work. The code is as follows: ...
0
votes
1answer
35 views

Does every strongly convex function has a stationary point?

Say does every differentiable $\mu$-strongly convex function $f:\mathbb{R}^n\mapsto\mathbb{R}$, with $\mu>0$ have a point where its gradient is $0$? If not so which is the minimum you can impose ...
0
votes
0answers
19 views

SOCP or SDP optimization problem

I am studying an optimization problem \begin{equation} \mathbf{w}^* = \text{argmax} \sum_{d=1}^D \log \bigg( \frac{|\mathbf{f}_d^H\mathbf{w}|^2+c_1}{|\mathbf{f}_d^H\mathbf{w}|^2+c_2} \bigg)\\ \\ ...
2
votes
0answers
27 views

proving that the ewma is convex

Hi: I know it's true but I don't know how to prove that exponentially weighted moving average when view ed as a function of $\lambda$, is strictly convex. The exponentially weighted moving average ...
0
votes
0answers
16 views

Using Taylor's theorem and Lagrange form of the reminder to prove the second order condition for convexity

I try to prove the second order condition for convexity. So far' I've done the following: First, I prove second order => convexity: Let $f$ be a function with positive semi-definite Hessian. Using ...
0
votes
1answer
23 views

Geometric interpretation of duality and Slater's condition

I am trying to study about optimization problems, Lagrange duality and related topics. I came across some presentation on the net, which claims to show the geometric interpretation of the duality and ...
0
votes
0answers
47 views

Which is the better way to optimize a function with 3 variables

I have an optimization function depends on 3 parameters a, b, and c. Which is the better way to optimize it? ...
1
vote
0answers
22 views

Property of Newton step for self-concordant convex functions

Suppose $f(x)$ is a convex and self-concordant function minimized at $x^*$. I have two starting points $\tilde{x}_0$ and $\hat{x}_0$ such that $|\hat{x}_0-x^*| \le |\tilde{x}_0 - x^*|$. We also know ...
1
vote
0answers
45 views
+50

Optimization of competitive scenario

Suppose we have a function $f(x_1,x_2)$ with the following properties: Let $x^*=\arg \max_{x_1} f(x_1,x_2=x^*)$ and $x^*=\arg \min_{x_2}f(x_1=x^*,x_2)$. $f(x_1,x_2)$ is concave in $x_1$. ...
2
votes
2answers
30 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( ...
0
votes
0answers
13 views

slaters condition - Duality - KKT condition [closed]

Can someone give a more intuitive idea to Slater's conditions and how it is related to KKT condition and duality ?
0
votes
1answer
18 views

Huber penalty function in Linear programming form.

I am trying to solve problem 6.3(b) of Convex optimization by stephen boyd and Vandenberghe. The problem is this Express the following minimization as a QP,LP,SOCP or SDP $$ ...
0
votes
0answers
17 views

What's wrong with the following trace optimization?

I'm reading a paper that has used the augmented Lagrange function for optimization. I've tried to derive one subproblem but got a different answer from that in the paper. Could you help check it ...
0
votes
1answer
23 views

Optimization problem $L(R, PQ) \rightarrow \min$

Suppose we have some $n \times m$ matrix $R$ and we want to find non-negative decomposition on matrices $P$ of dimension $n \times d$ and $d \times m$-matrix $Q$. But since exact decomposition usually ...
3
votes
1answer
38 views

Upper bound on maximum absolute value of all subdeterminants of a matrix

Let $A \in \mathbb{R}^{m \times n}$ and let $\Delta(A)$ be the maximal absolute value of the determinants of the square submatrices of $A$. A simple lower bound would be $$ \Delta(A) \geq ...
2
votes
1answer
36 views

Faster gradient descent convergence by transforming the gradient?

If we modify the gradient descent update for a convex objective function $f(\boldsymbol{\theta})$ from $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \nabla f(\boldsymbol{\theta}_t)$ to ...
1
vote
1answer
17 views

Is it right for chain rule in trace function?

The objective function is $$ f(X)=\min_X trace(B^TX^TCXBD) $$ we know the following derivatives from Matrix Cookbook, $$ \frac{\delta{trace(B^TX^TCXB)}}{\delta X}=C^TXBB^T+CXBB^T \\ \frac{\delta ...
1
vote
1answer
21 views

What is affine hull of conv(A)

Consider the set $A = \{(1,0),(0,1),(-1,0),(0,-1)\}$. The convex hull of $A$, i.e. $conv(A)$, should look like the following: (This is also a $l_1$-norm unit ball.) My question is what is the ...
0
votes
0answers
30 views

Uniform Sampling over Convex Polytope (not full-dimensional)

I want to simulate a uniform distribution on a convex polytope that is not full-dimensional for optimization purposes (to generate random points on the set I want to minimize over). The polytope is ...
0
votes
0answers
28 views

Relative interior

I'm having trouble solving the following equivalence. Let $A \in K^{m,n}, b \in K^{m}$ and $P := \{x \in K^m | Ax \le b\}$ Show that: a) There exists $x^1, ..., x^m \in P$ such that $A_{j*}x^j < ...
1
vote
1answer
28 views

About the slack variable for hinge-loss SVM

The hinge-loss SVM is defined $$ \min_{w,b} \frac{1}{2}w^T w+\sum_{i=1}^{N}\max\{0,1-y_i(w^Tx_i +b)\} $$ By introducing a slack variable $\xi_i$, the optimization problem is changed to $$ ...
5
votes
1answer
64 views

Constrained Optimizatoin: The Frank-Wolfe Method

A general convex optimization problem is framed as such: $$\min f(x) : x \in \Omega$$ where $\Omega$ is convex. The Frank-Wolfe method seeks a feasible descent direction $d_k$ (i.e. $x_k + d_k \in ...
1
vote
2answers
31 views

Solve matrix equation with some known values, assuming answer is symmetric positive definite

I'd like to solve $\boldsymbol{[K][U]=[F]}$ for $\boldsymbol{[K]}$ assuming that the answer is symmetric positive definite and contains some known values and that $\boldsymbol{[U]}$ and ...
0
votes
0answers
38 views

Can a positive definite kernel produce a kernel matrix which has negative eigenvalues?

(1) I've read that a symmetric matrix is positive definite when its associated eigenvalues are all positive. I am learning SVM lately, and have come to know a $d$th-degree polynomial kernel ...
0
votes
1answer
37 views

What is the correct change of variables to yield convexity in this nonlinear optimization problem?

$$ \text{min. } x/y \\ \text{s.t. } 2\leq x \leq 3 \\ x^2+y/z\leq \sqrt{y} \\ x/y=z^2 \\ x,y,z\geq 0 $$ To transform this problem into a nonlinear convex optimization problem, both the objective ...
1
vote
0answers
41 views

Distributed convex optimization problem

Consider the optimization problem $$ \min_{ x_1, \ldots, x_N } \sum_{i=1}^{N} f_i( x_i ) \\ \text{s.t.: } \sum_{i=1}^{N} x_i \in X, \ x_i \in X_i \ \forall i \in \{1, \ldots, N\} $$ where $f_1, ...
1
vote
1answer
34 views

Why test problems in convex optimization are mostly random?

Very often people who compare performance of different algorithms in convex optimization use randomly generated data. For instance, this often happens in compressed sensing and signal processing. Is ...
0
votes
0answers
30 views

About Intersection of two convex polytope?

the intersection of two convex hull of two polytope P and Q , is it the convex hull of the intersection of P&Q ? Conv(P) ∩ Conv(Q) = conv(P∩Q) ???.
0
votes
0answers
33 views

Learning pipeline for developing own optical flow algorithms

I am really sorry if this question is outside of this resource or too silly I am bachelor of computer science and a programmer in small company. And i am faced with the task of developing own custom ...
0
votes
1answer
25 views

Proof that the intersection of any finite number of convex sets is a convex set

How to prove that the intersection of any finite number of convex sets is a convex set? I have no idea.
0
votes
1answer
37 views

Minimizing a function of a complex variable

Given complex numbers $z_1,z_2,z_3,\ldots,z_n \in \mathbb{C}.$ Does there exist a $z \in \mathbb{C}$, for which the function $$f(z) = \sum_{j=1}^n |z-z_j|$$ achieves a global minimum? If yes, ...
1
vote
1answer
32 views

Toeplitz equality constrained least-square optimization

What is the fastest known algorithm for least-square optimization problem with a linear equality constrain \begin{align*} &\min \|K x - y\|^2 + \mu \|x\|^2\\ \text{s. t. }& Q x = v ...
0
votes
1answer
40 views

Is the optimization problem right?

If we want optimize the following problem $$ \min_x \{a(x)+c(x)\} $$ and we have $$ a = \min_y b(y) $$ then, could we directly optimize the following problem? $$ \min_x \{b(x)+c(x)\} $$
0
votes
1answer
29 views

quadratic constraints

Is it possible to reformulate the following quadratic constraints to conic constraints so that I use an SOCP solver $$ ( x_1^2 + x_2^2 ) - ( y_1^2 + y_2^2 ) \leqslant c $$ ...
1
vote
1answer
35 views

Proving that the solution of a norm constrained optimization is on the boundary of the set

I am trying to solve the following maximization problem $$\max_{||x|| \leq c} x^H A x,$$ where matrix $A$ is hermitian symmetric. I have been told that the argument of the maximum is on the ...
0
votes
0answers
17 views

Is there a unique tilted measure with specified marginals?

Suppose $\mathcal{A},\mathcal{B}$ are finite sets and $\mu_{A,B}(a,b)$ is a probability measure on the product set $\mathcal{A}\times \mathcal{B}$ so that $\mu_{A,B}(a,b)>0$ for each $a\in ...
4
votes
0answers
33 views

How to find accuracy of Matlab's quadprog solver?

I have solved with quadprog from Matlab a strong convex quadratic problem given as $$ f(x) = x^TQx + c^Tx$$ with constrains $$ Cx \leq b.$$ Now the output of quadprog is: Minimum found that ...
0
votes
1answer
25 views

unnecessary constraint in optimization problem

I have some optimization problem (optimizing parameter $\alpha$)with those constraints: $$\alpha_i\ge0$$ $$\sum\limits_i \alpha_i y_i =0$$ and a third constraints: $$w-\sum\limits_i \alpha_i y_i x_i = ...
1
vote
0answers
41 views

Is there any way to transform a non-convex optimization problem into a convex one?

I have an optimization problem which is described as $$\begin{array}{ll} \text{minimize}_x & c^{T}x\\ \text{subject to} & Gx \preceq h\\ & -x^{T}Px - qx - r \leq 0 \end{array} $$ where ...
2
votes
0answers
32 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
1
vote
0answers
15 views

Is there a good textbook/book out there that explains sub gradients thoroughly?

I was interested in learning and understanding sub gradients as much as I could from some good resource. I know what the definition is, but I seem unable to apply the definition to prove basic facts ...