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

learn more… | top users | synonyms

1
vote
0answers
42 views

Optimization problem: $\min \limits_{\mathbf{q}} \sum_{n=1}^N q_n$, s.t. $\frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a$

\begin{array}{rl} \min \limits_{\mathbf{q}} & \sum_{n=1}^N q_n \\ \mbox{s.t.} & \frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a, \forall n \in \{1,\ldots,N\} \end{array} For this ...
1
vote
0answers
36 views

Good text book recomendation

I would like to do some reading about a technique called sequential convex programming. There is a lot of material about sequential quadratic programming out there, including books (Nocedal & ...
1
vote
0answers
24 views

A question on Edgeworth Expansion

I'm working Edgeworth Expansion. I couldn't understand one thing . Can you help me about that please. $$Z= \frac{\sqrt {n} (\bar {x} -\mu)}{\sigma}$$ converges in distribution to N(0,1) I have ...
1
vote
0answers
36 views

maximum of a concave function in a minkowski sum

Let: $f(x,y)$ - a strictly-concave function, monotonically increasing in $x$ and $y$; $A,B$ - two compact and convex sets in the positive quadrant; $C$ - their Minkowski sum, $A+B$; $(x_A,y_A)$ - ...
1
vote
0answers
35 views

Proving function is convex argmin

How can I show that the following function is convex in which Z is a random variable? $$\rho(Z)=\frac{2}{3}argmin_{t}\{t+10\mathbf{E}[Z-t]_{+}\}+\frac{1}{3}argmin_{t}\{t+5\mathbf{E}[Z-t]_{+}\}$$ I ...
1
vote
0answers
10 views

Why this problem is unbounded, even though it's dual is feasible?

In this paper, An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming,page 2, there is a problem called, (P): \begin{align} P: &\min_{X,s} && ‎ \frac{1}{2} ‎\Vert ...
1
vote
0answers
27 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
22 views

Can a linear program be optimal if its basis is infeasible?

I want to know thanks to the dual theorem wether the following basis is or isn't optimal. That is to say looking for the slack variables. As far as the third line doesn't respect the constraints: ...
1
vote
0answers
58 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
83 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
29 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
22 views

Expressing $\forall$ in linear programing

I'm doing a linear program to a game and I don't know how to express $\forall$ in linear programing (or if I had the right intuition to do it). Here is the problem: I have several vessels that are ...
1
vote
0answers
21 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
45 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
38 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
27 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
35 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
48 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
29 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
49 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
29 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
41 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
35 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
44 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
25 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
63 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
47 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
79 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
51 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
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
58 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
47 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
53 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
37 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
49 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
45 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
55 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
13 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
134 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 ...