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

learn more… | top users | synonyms

1
vote
0answers
45 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
26 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
63 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
44 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
69 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
18 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
34 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
36 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
34 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
30 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
18 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
37 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
33 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
40 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
96 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
43 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
55 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
63 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
37 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
51 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
31 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 ...
1
vote
0answers
26 views

Question about sub differentiability of convex function

I am reading this book to study sub differentiability. On page 20 it says, as $V$ is a normed linear space for simplification, "a continuous affine function $l(v)$: $V\to \mathbb R$ everywhere less ...
1
vote
0answers
59 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in ...
1
vote
0answers
54 views

How to define the nuclear norm of a tensor

As we know,the nuclear norm of a matrix $X$ is defined as this: $$||X||_{*}=\sum{\sigma_{i}}$$ where $\sigma_{i}$ is the singular value of $X$. But how to define the nuclear norm of a tensor ...
1
vote
0answers
34 views

Is there any software to solve this large scale convex optimization problem?

I want to solve the following large scale convex problem: $min\ \ ||A$u-b$||_2^{2}+ ||$U$_{(1)}||_*+||$U$_{(2)}||_*+||$U$_{(3)}||_*$ where U is a three order tensor, U$_{(i)}$ is a matrix whose ...
1
vote
0answers
42 views

Intuition on primal convergence in dual subgradient method

It is well known that the subgradient method applied to the Lagrange dual of a convex problem may produce a sequence converging to the dual optimum, but the primal iterates produced by this sequence ...
1
vote
0answers
67 views

Quadratic optimization problem (inner products) with stochastic constraints

Let the set of feasible solution be the set of all row-stochastic $n \times k$ matrices $P = [p_{ij}]$, that is $\mathcal{P} := \{P \in \mathbb{R}^{n \times k} \ | \ P \mathbf{1} = \mathbf{1}, P \geq ...
1
vote
0answers
23 views

Solution to a nonlinear problem at an extreme point

I have a convex optimization problem of the form: $$ \begin{aligned} \operatorname*{minimize}_{\mathrm{x} = (\mathrm{x}_1, \dots, \mathrm{x}_m) \in \mathbb{R}^{nm}} &\quad f(\mathrm{x}) = ...
1
vote
0answers
46 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
1
vote
0answers
49 views

tangent cone to the set

I'm supposed to solve this problem: Let us consider the set $M=\{(x, \sin{x}):x\in\mathbb{R}\}\cup\{\big(\cos(x)-1,x\big):x\in\mathbb{R}\}$ The question is to find the tangent cone to the set $M$ in ...
1
vote
0answers
39 views

Optimization of sum of logs

I have an optimization problem of the form $$\operatorname*{argmax}_{\mathbf{w}} \sum_i \log(1 + \mathbf{w} \cdot \mathbf{k_i})$$ given some set of vectors, $\mathbf{ \{k_i\} }$. I have tried both ...
1
vote
0answers
39 views

Do quasi-Newton methods check the second-order optimality condition?

I have a practical question about quasi-Newton methods. In quasi-Newton methods, Hessian matrix is approximated. It seems to be impossible for them to check the second optimality condition. In ...
1
vote
0answers
79 views

Proximal operator of spectral norm of a matrix

How can I calculate the proximal operator of spectral norm for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_2 + \frac{1}{2\tau} ||X-Y||_F^2$ I understand that the proximal ...
1
vote
0answers
39 views

How to solve this entropy optimization problem with gradient projection method?

The problem is defined as $$ \min_{w} = \sum_{i=1}^{n} \sum_{j=1}^{n}\left\{ \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \log \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \right\} + \gamma \|w\|_2^2\\ $$ ...
1
vote
0answers
69 views

Proximal operator for the nuclear norm of Hankel (x)

I have a problem in hand for which I need to compute the proximal operator of the composite function $||Hankel(x)||_{nuc}$ where $x \in R^N$ and $||.||_{nuc}$ denotes the matrix nuclear norm. For a ...
1
vote
0answers
74 views

Tucker's theorem from Farkas lemma

I am trying to understand the proof of Tucker's theorem using Farkas lemma but there are some points that are not clear to me. The proof I am following is in this paper at page 16. What I do not ...
1
vote
0answers
86 views

Convex Optimization: Advantages of Symmetric Primal-Dual Algorithms?

This is a follow-up to an answer on a previous question on PD algorithms: http://math.stackexchange.com/a/1193928/36257 I have done some research learning the mechanics of how Infeasible PD ...
1
vote
0answers
48 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
35 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
32 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
94 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
57 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
65 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 ...