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

learn more… | top users | synonyms

1
vote
0answers
21 views

Variational inequality and saddle point problem

I refer to the following paper: (fix the wrong link) https://papers.nips.cc/paper/5723-adaptive-primal-dual-splitting-methods-for-statistical-learning-and-image-processing.pdf In that paper, we ...
1
vote
0answers
57 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 ...
1
vote
0answers
12 views

Variant of conjugate function: $V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$

Consider one variant of conjugate function: $$V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$$ You can think $s$ as a linear functional. If I do the following steps: ...
1
vote
0answers
24 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
1
vote
0answers
76 views

Some intuition on the support function of a convex set

I have some doubts on the interpretation and properties of the support function of a convex subset of $\mathbb{R}^d$. (1)Let $K$ be a convex set in $\mathbb{R}^d$. (2) The support function of $K$ is ...
1
vote
0answers
24 views

Why the trace norm of a tensor is a good approximation to its rank?

In many literature, they use the trace norm of a tensor to approximate its rank, which is defined as follows: $$\|\mathcal{X}\|_{\ast}:=\sum_{i=1}^{n}\alpha_i\|X_{(i)}\|_{\ast}$$ where ${\alpha_i}'s$ ...
1
vote
0answers
20 views

How to perform a quasiconvex optimization

I have a quasiconvex objective function $f:\mathbf{R}^n\rightarrow \mathbf{R}$ which I would like to minimize over a simplex $S\subseteq \mathbf{R}^n$. I have looked pretty hard but have been unable ...
1
vote
0answers
42 views

Can we use simple alternating optimization for minimax (saddle point) problems?

Consider a function $f(x,y)$, convex in $x$ and concave in $y$. we are interested in the following optimization problem, \begin{align} \min_{x \in D_x} \max_{y \in D_y} f(x,y) \end{align} Because of ...
1
vote
0answers
35 views

Generalizations of Positive Definiteness

What, if any, notions of positive definiteness can be extended to 3rd order tensors (and beyond)? The reason I ask is because the Hessian matrix of a convex function is positive semi-definite, but ...
1
vote
0answers
22 views

Converting a norm-computation SemiDefinite program to standard SDP form.

I'm trying to express this norm-computation semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$ $$\gamma_{2}^{\epsilon}(A):= \min\,t\,\, subject\, to\, \left( ...
1
vote
0answers
20 views

Boyd & Vandenberghe's proof that all simplexes are polyhedra.

On page 33 of B&V's convex optimization book, during the proof that any simplex can be represented as a polyhedron, they discuss a $n \times k$ matrix $B$ with full column rank and conclude that: ...
1
vote
0answers
33 views

Logarithmic Function Behaivour

I have read about Logarithmic function. We can use the second-order condition to show that the $f(x)=\log_2(1+x), x \geq 0$ is a concave function. Now, is $g(x)$ a concave function? How can I prove ...
1
vote
0answers
44 views

Convex Conjugate of Log Sum Exp Function

Convex Optimization Snippet In showing the convex conjugate of log-sum-exp function, $f(x) = \log(\sum_{i=1}^n e^{x_i})$, Boyd argues that the domain of the convex conjugate, $$f^*(y) = \sup_{x \in ...
1
vote
0answers
14 views

Condition on linearly separable datasets

I am trying to understand linear classification with hyperplanes. So far I understood that for a binary classifier with labels $y_i \in \lbrace -1, 1\rbrace$ points $(x_i, y_i)$ are separable if ...
1
vote
0answers
27 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
1
vote
0answers
39 views

How to prove that unnormalized neg entropy is strongly convex with respect to 1-norm?

the unnormalized negative entropy of $\mathbf{x} \in \mathbb{R}^n_+$ is $$ g(\mathbf{x}) = \sum_i (x_i \log(x_i) - x_i) $$ it is stated that $g(\mathbf{x})$ is strongly convex with respect to 1-norm, ...
1
vote
0answers
27 views

Moreau Decomposition with Bregman Distance

I am working with a non-Euclidean proximity operator defined by a Bregman distance function $D(\cdot, \cdot)$: $$ \operatorname{prox}_f(x) = \operatorname*{argmin}_u \{ f(u) + D(u, x) \} $$ Is ...
1
vote
0answers
39 views

Scaled proximal operator for proximal Newton method

The scaled proximal operator was introduced as an extension of the (regular) proximal operator: $prox^H_h(x) = \arg\min_y h(y) + \frac{1}{2}\|y-x\|^2_H$. (See ...
1
vote
0answers
33 views

KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & ...
1
vote
0answers
27 views

What is the Computational Complexity of Minimising a Linear Function over a General Convex Set?

Is the computational complexity of finding or approximating $\inf\{c^Tx:x\in X\}$ (where $X$ is a compact convex given explicitly or by some reasonable oracle) known? EDIT: Suppose we had an ...
1
vote
0answers
41 views

Quasiconcavity of a product of ratios

Given $f(x_1\ldots x_k) = \dfrac{x_1x_2\cdots x_k}{(x_0+c_1)(x_0+c_2)\cdots(x_0+c_k)}$ where $x_i > 0$, the $c_i > 0$ are constants, and $$x_0 = \sum_{i=1}^k x_i$$ is it true that $f$ is ...
1
vote
0answers
24 views

Analytical algorithm to obtain solution to convex optimization problem.

Assume a vector $\vec{P}$ with N elements $\in \mathbb{R}^+$ and constants $T_P$ and $\epsilon$. The vector $\vec{P}$ is arranged in a column $(N\times 1)$. Consider the problem: $$ \begin{aligned} ...
1
vote
0answers
60 views

How to find the tangent cone to a set in a point?

Let $S\in R^{n}$ is a set and $x\in S$. We define tangent cone of $S$ in $x$ as: $$T_{S}(x)=\{z\in R^{n}:\exists (x_{k}), x_{k}\in S, x_{k}\rightarrow x, \exists (y_{k}), y_{k}>0, ...
1
vote
0answers
45 views

How to use Farkas' lemma?

How can I prove, that the set $$P = \{(x, y) \in \mathbb{R}^{n+m} : Ax + By \geq c, \: x \geq 0^n, \: y\geq 0^m \}, $$ where $B \in \mathbb{R}^{m \times m} \;$ is positive semidefinite matrix, $A ...
1
vote
0answers
73 views

Shadow prices in assignment problems (and their relationship to Lagrange multipliers of LP-relaxation)

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given ...
1
vote
0answers
47 views

Maximum over Probabilistic Distribution Functions Space

Suppose $P$ is the set of functions where $p\in P: R^{+2}\to R^+$ and $p(t,s)$ is differentiable in $t$. $\forall t, p(t,\cdot)$ is a probability distribution on the positive axis $s\in [0,\infty)$, ...
1
vote
0answers
70 views

How to write lagrangian terms related to only one variable in a semidefinite constraint?

I have a semidefinite problem as follows(which is nonconvex) \begin{alignat}{3} &\min_{x_{un}} \min_{t,H,w} &&t+f( w)\cr &\text{s.t. } &&\begin{bmatrix} K\odot H ...
1
vote
0answers
20 views

How to deal with a convex constraint

I want to deal with a convex constraint \begin{align} F(P)=P^{H}AP_{0}+P_{0}^{H}AP-P_{0}^{H}AP_{0}\succeq 0 \end{align} where $(\cdot)^{H}$ represents Hermitian transpose, $A$ is a positive definite ...
1
vote
0answers
36 views

A nonlinear optimization problem with difficult Kuhn-Tucker system of equations

I know about the sufficient optimality theorem Kuhn-Tucker, and this problem can use the Kuhn-Tucker theorem directly, but ridiculously, I got stuck on the system of equations to find one root for ...
1
vote
0answers
52 views

Convexity of the log barrier function

Let's consider the following convex optimization problem of minimizing the log barrier function: $$\min_{\textbf{x}\in \Re^n}f(\textbf{x})=\min_{\textbf{x}\in ...
1
vote
0answers
35 views

What does the above simplify into when $f_1$ and $f_2$ are indicator functions of convex subsets $C$ and $D$ of $X$, respectively?

Consider the expression $$\partial (f_1\Box f_2)(\bar{x})=\partial f_1(\bar{x_1})\cap\partial f_2(\bar{x_2}).$$ What does the above simplify into when $f_1$ and $f_2$ are indicator functions of ...
1
vote
0answers
46 views

min-max optimization problem

how do you solve the following optimization problem to find the global solution? $~~~~~\underset{y}{min} ~ \underset{x}{max} f(x,y)$ subject to $~~~~~g(x)<0$ with knowing that both g(x) and ...
1
vote
0answers
24 views

Determine $C^{\circ}$ explicity in terms of $A$ and $b$

If $C \subseteq E$ is a closed convex set define $$C^{\circ}=\bigcap_{x\in C}\{u \in E: \langle u,x\rangle\leq 1\}$$ Determine $C^{o}$ if $C= \{x: Ax \leq b\}$ Solution so far: $C^{o}=\bigcap_{x\in ...
1
vote
0answers
52 views

Proof of Stiemke's Theorem via Dubovitskii–Milyutin

Prove that the system $$\sum_{i=1}^{m} x_i a_i = 0, x_i > 0, i = 1, . . . , m,$$ has no solution if and only if the system $$<a_i , y> ≤ 0, i = 1, . . . , m,$$ not all zero has a solution. ...
1
vote
0answers
19 views

Quasiconvexity analog for function with an integer domain.

Suppose I have a function that is not quasiconvex, as in the graph below, but would be quasiconvex if we cared only about integer points. That is, $f:X \subset \mathbb{Z}\rightarrow \mathbb{R}$ ...
1
vote
0answers
36 views

Closed formula for unconstrained (matrix) optimization problem

Let $M$ be a square matrix of size $n$, $(a_i)_{i\in[1,n]},(b_i)_{i\in[1,n]},y$ vectors of size $n$ and $\lambda$ a real. Is there a closed form for the following problem: $$\arg\min_M ...
1
vote
0answers
46 views

Newton Raphson convergence: a convex function over a convex cone

Similar to the Newton Raphson algorithm that has a (global) convergence property when we minimize a (strictly) convex function over Euclidean space (based on the second order Taylor serise expansion ...
1
vote
0answers
42 views

Division of linear functions in convex polytope

I am a computer scientist, and find myself needing the following lemma: If f(x)=(g(x))/(h(x)), where g and h are linear and positive with domain the convex polytope d, then extrema of f occur at ...
1
vote
0answers
52 views

Definition of a Convex Cone

In the definition of a convex cone, given that x,y belong to the convex cone C,then theta1*x+theta2*y must also belong to C, where theta1 and theta2 are both >=0. What I don't understand is why there ...
1
vote
0answers
12 views

Regularity for the Feasible region

I have this problem $min -x +y $ $x-y^2\leq0 $ $\frac {(x-1)^2}{4} +y^2 \leq 1$ $y \geq -1/2$ Say if the feasible region is regular or not, analitically. I know that to check the KKT ...
1
vote
0answers
37 views

A question about minimizing the $\lambda_{max}$ over a set of diagonal perturbations

Say I have an off-diagonal symmetric $0,1,-1$ entry matrix $B$ and a set of $2k$ diagonal matrices, $D_{11}, D_{12}, D_{21}, D_{22},..,D_{k1},D_{k2}$. (if it helps you can assume that $(1)$ all the ...
1
vote
0answers
127 views

Convex optimization when Hessian is non-invertible

1) Are there any extensions to Newton's method for finding minimum of a convex function when the Hessian is singular ? (I have all positive eigenvalues in the Hessian except one which is zero) I ...
1
vote
0answers
32 views

how to get orthogonal rank 1 approximations?

The situation: I have $k$ matrices $A_i$, which are all real and of size $m\times n$. Now I would like to find the matrices $\tilde{A}_i$ of $A_i$ so that 1) $\tilde{A}_i$ is of rank 1 (thus a rank 1 ...
1
vote
0answers
41 views

Finding a polynomial approximation of a PDF

I would like to find a polynomial $P(x)=\sum_{d=1}^D P_dx^d$ of degree $D$, where its derivative is larger than or equal to a given pdf $f(x)$ in $[0,1-\epsilon]$, for any $\epsilon>0$. Note that ...
1
vote
0answers
49 views

Condition for product of increasing and decreasing functions to be quasiconcave?

Is there any condition for product of increasing and decreasing functions to be quasiconcave? More specifically, I am having in mind a condition for $F(x)\cdot(1-G(x))$ to be quasi concave where $F$ ...
1
vote
0answers
57 views

Can this be expressed in terms of linear constraints?

I'm attempting to find a matrix $X$ that minimizes some function $f(X)$ subject to the constraint that $$ X=W A Z $$ where $A$ is a given non-negative matrix with rows that sum to 1, and $W$ and $Z$ ...
1
vote
0answers
79 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 ...
1
vote
0answers
39 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 ...
1
vote
0answers
52 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 ...
1
vote
0answers
44 views

Convergence results for block coordinate descent methods

I am trying to solve the problem minimize $f(x)$ subject to $x_1 \in C_1, x_2\in C_2, ... x_m\in C_m$ where $x_1, ..., x_m$ are block subvectors of $x$, and $C_i$ are each closed convex sets (not ...