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

learn more… | top users | synonyms

1
vote
0answers
36 views

Transform a nonconvex constraint into a convex one

I am solving an optimization problem and I need to formulate it as a convex optimization problem. Is there any way to write the constraint $$ 1 - e^{z} - \frac{e^{-r}}{1+r} \leq 0 $$ as a convex ...
1
vote
0answers
28 views

Practical exercise in SVM

Suppose we have four positive points $\{0,1,2,3\}$ and three negative points $\{-3,-2,-1\}$. We want to learn soft-margin linear SVM $\min_{w}0.5 \left \| w \right \| +C \sum \epsilon_i$ the ...
1
vote
0answers
29 views

Estimating parameters of a stochastic matrix

I am stuck with the following problem in research. Let $A_{1}$, $A_{2}$ and $B$ be stochastic matrices. Let $B = f(A_{1},A_{2})$. Let $\pi =[\pi_{1},\pi_{2},\pi_{3}]$ be a vector such that $\sum_{i} ...
1
vote
0answers
65 views

Why use two slack variables in the support vector regression formulation?

I am learning support vector regression but cannot fully understand the rational of the slack variable tricks in its formulation. The original optimization problem for SVR is as follows: ...
1
vote
0answers
36 views

Strictly Concave Function over non-convex set

I have to optimize a function $f$ over a set $S \subset X$. We know that $f$ is non-negative, continuos and strictly concave over $X$. We have that $S$ is compact but not convex. By Extreme Value ...
1
vote
0answers
44 views

Basis pursuit denoising

The Lagrangian form of basis pursuit denoising $\min_{w} ||w||_{\ell_{1}} + \lambda ||Aw-x||_{\ell_{2}}^{2}$ can be solved using proximal gradient descent. Proximal methods also can be used to ...
1
vote
0answers
31 views

sup is bounded or not?

The sup is as following: $c_f = sup_{x,s\in D} \ f(y) - f(x) - (y-x)^Tb$ where $y=x+\alpha(s-x)$, $\alpha \in (0,1 )$ is constant and $b$ is a constant vector. $D$ is a convex compact set and ...
1
vote
0answers
125 views

Linear programming optimization problem formulation

I need help in formulating an optimization problem. I have a system of equations as follows: $c_1x_1+c_2x_2+c_3x_3=1$ $b_1x_1+b_2x_2+b_3x_3=1$ $a_1x_1+a_2x_2+a_3x_3=1$ In my case the ...
1
vote
0answers
25 views

Subspace of tangent feasible directions

If $h: \mathbb{R}^3 \to \mathbb{R}^3$ defined by $h(x_1,x_2,x_3) = (x_1^3 - x_2 + x_3^2, x_2,x_1+x_2+x_3)$ I define $V(x)$ as a subspace formed by all directions tangent to some constrained set at ...
1
vote
0answers
41 views

Subdifferential of a convex function

How would I find a convex function $f: \mathbb{R} \to \mathbb{R}$ such that $\partial f(0) = [0,1]$ A subdifferential is just the collection of vectors $w \in \mathbb{R}^n$ such that $f(y) \geq ...
1
vote
0answers
24 views

Why is this set a subset of its polyhedral approximation - contradicting the gradient inequality?

Say we have a set $C:= \{y\in \mathbb{R}^n : g_i(y) \leq 0, \space i=1,...,m\}$ where $g_i : \mathbb{R}^n \to \mathbb{R}$ are convex and differentiable functions, then we have $\tilde C : = \{y: ...
1
vote
0answers
27 views

Convexity Proof with constraints on the gradient

Consider a minimization problem $(P)$ : minimize $f(x)$ subject to $\delta_C(x) \leq 0$ Now assume that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and let $f: \mathbb{R}^n \to \mathbb{R}$ be ...
1
vote
0answers
89 views

Is the function $f(A)=-\log(tr(A^{-1}))-\log(\det(A))$ convex?

I am trying to show the following function is convex or not $$f(A)=-\log(\text{trace}(A^{-1}))-\log(\det(A)),$$ where $ A$ is positive definite. I know $\text{trace}(A^{-1}), -\log(\cdot)$ and ...
1
vote
0answers
55 views

Proximal Mapping of Composition with Linear Operator

I've posted this question on math overflow but got no answer, so I think it might not be a research level question so I decided to post it here too. Let $A$ be an orthogonal matrix. It is well known ...
1
vote
0answers
96 views

Conversion into linear program

I have an optimisation problem with decision variables that are multiplied with another (a weighted average is calculated). I'd like to convert it into a linear program. I found this link that ...
1
vote
0answers
47 views

Difficulty in understanding a solution: Constraint minimization of sum of Non-symmetric matrices

I am trying to understand why there is significance difference in the performance of two proposed solutions. Original question (Constraint minimization of sum of Non-symmetric matrices) ...
1
vote
0answers
47 views

Fenchel Conjugate of a norm squared

I was wondering if the fenchel conjugate of the $\frac{1}{2}||u||^2$, is the $\frac{1}{2}||u||_*^2$, where $||.||_*$ is the dual norm of $||.||$. This seems to be true for the $\ell_2$ norm. However, ...
1
vote
0answers
34 views

How to find a hyperplane

Let $A, B ⊂ \mathbb{R}^n$ be two nonempty sets such that $A ∩ B = ∅$. $H(A, B) := \{(w, d) ∈ \mathbb{R}^{n+1} : \sup_{x\in A} \langle w,x\rangle ≤ d ≤ \inf_{y \in B} \langle w, y\rangle \}$ How do I ...
1
vote
0answers
102 views

Showing convexity of a function with the restriction over an arbitrary line

Let $f : \mathbb{R}^n → \mathbb{R}_∞$ be a function and let $C ⊂ dom f$ be a convex set. $$**Part I**$$ Prove that $f$ is a convex function if and only if $f$ is convex over every line $L_{v,x_0}$ ...
1
vote
0answers
146 views

Any example of strongly convex functions whose gradients are Lipschitz continuous in $\mathbb{R}^N$

Let $f:\mathbb{R}^N\to\mathbb{R}$ be strongly convex and its gradient is Lipschitz continuous, i.e., for some $l>0$ and $L>0$ we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{l}{2}||y-x||^2,$$ ...
1
vote
0answers
18 views

Is epi(max(f,g)) the intersection of epi(f) and epi(g)?

On an exam, I found the question "is max($f(x),g(x))$" convex if $f,g$ are convex? This lead me to the question in the topic. Is the intersection of epi$(f)$ and epi$(g)$ = epi($\max(f,g)$)? If so, ...
1
vote
0answers
42 views

saddle point versus local extermum

Suppose a function $f$ from $\mathbb{R}^n \to \mathbb{R}$, is differentiable. We know that $c$ is a critical point of $f$, i.e. $\nabla f(c) = 0$. Our goal is to find out if $c$ is a local extremum, ...
1
vote
0answers
26 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...
1
vote
0answers
51 views

Compressed sensing: converse of a theorem

Theorem: Suppose that the signal length $N$ is a prime integer. Let $\Omega$ be a subset of $\{ 0, \ldots , N-1 \}$ and let $f$ be a vector supported on $T$ such that $|T| < \dfrac{1}{2}|\Omega|$ ...
1
vote
0answers
128 views

Dynamic programming problem for discrete linear time varying system

I'm working on a linear time varying discrete(LTV) multi input multi output(mimo) system. I formulate the problem description in the following way $$x_i(k+1) = x_i(k)\cdot A_i(k) + B_i(k)\cdot ...
1
vote
0answers
53 views

How nuclear norm is convex whereas weighted nuclaer norm is not?

In (http://nuit-blanche.blogspot.in/2014/05/wnnm-weighted-nuclear-norm-minimization.html), it is stated that nuclear norm of a matrix $\mathbf{X}$, given as $||\mathbf{X}||_{*}=\sum_{i} ...
1
vote
0answers
34 views

Entropy proerty

Let $a,b,c>0$ be distinct postive reals. Define four different probability distributions: $$\mathcal{P}_{ab}:P_{a,ab}=\frac{a}{a+b}=1-P_{b,ab}$$ ...
1
vote
0answers
34 views

The optimization problem of soft margin Support Vector Machine: How to interpret?

I try to understand what exactly we are trying to optimize in the case of Support Vector Machine problem, which supports soft margins. The original problem is posed first as, without soft margins ...
1
vote
0answers
43 views

Minimization using logarithmic barrier function

I'm thinking of the quadratic problem(QP) \begin{align} &\underset{x\in \mathrm{R}^n}{\mathrm{Minimize}}\ \ \ \frac{1}{2}x^\top{}Qx + f^\top{}x\\ &\mathrm{subject\ to}\ \ \ \ a_ix \leq b_i\ ...
1
vote
0answers
79 views

Conic hull of outer products

Consider the set of rank-k outer products, defined as $\{XX^T | X \in R^{n\times k}, rankX = k \}$. Describe its connic hull in simple terms. I have found the solution of this exercise but I have ...
1
vote
0answers
73 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 ...
1
vote
0answers
39 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
48 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
0answers
136 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) ???.
1
vote
0answers
57 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 ...
1
vote
0answers
30 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 ...
1
vote
0answers
32 views

Partial concave maximization of subset of variables

Let $f(x_1, \dots, x_N)$ be a concave function in $x_1, \dots, x_N$. For arbitray $n>1$, prove that the (constrained) truncated function defined by $$g(x_1, \dots, x_{n-1}) = \max_{x_n, \dots, x_N ...
1
vote
0answers
73 views

What is the left derivative of the hinge loss function in the context of subgradients?

Let: $$|a|_+ = max\{0,a\}$$ Then the Hinge loss function (in the context of classification in Machine Learning) is: $$V(-yf(x)) = |1 - yf(x)|_+$$ Note that $y \in \{-1,1\}$ Let $f(x) = \langle w, ...
1
vote
0answers
82 views

Proving/deciding concavity of a function of two variables

I would like to formally prove that the function $f(x,y) = \frac{(c+1)e^{-x}(xe^{x+y}+y)}{(c+2)(e^{x+y}-1)+e^y} $ is concave ($ c>2$ is a constant, and both $x,\, y \in \mathbf{R_+}$). Plots of ...
1
vote
0answers
39 views

When result of max of min problem is equal to min of max problem

Let's assume there are two functions $f(x)$ and $g(x)$. I want to know when the optimal $x$ of max of min of $f(x)$ and $g(x)$ is not equal to optimal $x$ of min of max of $\frac{1}{f(x)}$ and ...
1
vote
0answers
164 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
1
vote
0answers
27 views

Extra information needed to distinguish combinatorially isomorphic polytopes

The title pretty much sums up my question: what extra information do we need (or what is an example of sufficient information) on top of the face lattice in order to completely characterize a convex ...
1
vote
0answers
89 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
1
vote
0answers
54 views

Lagrange multipliers for minimax optimization

Does the equally constrained minimax optimization can be solved by using Lagrange multiplier method? Thanks in advance.
1
vote
0answers
52 views

Farthest point on a parallelotope from the origin

I have two related questions. First, consider a maximal independent set of vectors $\{v_1,\cdots,v_k\}$ in $k$ dimensional space. The rows of a square matrix $A$ are from those vectors. The origin is ...
1
vote
0answers
68 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where ...
1
vote
0answers
34 views

How to convexify (relax) this L0 eigenvalue optimization problem?

Let $C_1,\dots,C_L$ be $N\times N$ hermitian matrices. Let $d<0$ be a given negative constant. Then consider the optimization problem \begin{align} \max_{r\in \mathcal{R}^{L\times 1}} &\mid\mid ...
1
vote
0answers
123 views

Alternating Direction Method of Multipliers (ADMM) application

$\newcommand{\argmin}{\operatorname{argmin}}$ Recall, that ADMM algorithm solves the problem of the form: $\min \text{ } f(X) + g(Z)$ $\text{s.t. } AX + BZ = C$ where $X$, $Z$ and $C$ are real ...
1
vote
0answers
25 views

Can this type of constraint be recasted to a convex constraint?

I have an optimization problem where all the constraints are linear but some of the type: $$ y_i = \frac{x_i}{\sum_k x_k} $$ It seems that the equality can be relaxed to an inequality adding the ...
1
vote
0answers
49 views

When does l1 regularisation give a sparse solution?

I was maximising a likelihood function, which is convex. I know that the system has a K-sparse solution. I wanted to know the conditions (or some sufficient conditions) on the likelihood function ...