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

learn more… | top users | synonyms

2
votes
0answers
371 views

A convex programming problem involving sum of logarithms of linear functions

Here is a convex programming problem I encountered while working on an estimation problem for a mixture of multinomial distributions. We have a matrix $A_{m \times n}$ containing non-negative real ...
2
votes
0answers
417 views

real-time linear programming

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...
1
vote
0answers
49 views

Feasible Region of QCQP and Semidefinite Programs

I am trying to visualize the feasible region of a Quadratically Constrained Quadratic Program (QCQP) which is expected to be non convex (actually is a set of ellipses in $\mathbb{R}^2$) and the ...
1
vote
0answers
16 views

Benders decomposition Master Problem

I am currently working on implementation of Bender's Decomposition for MIP. I am looking at the simplest model \begin{equation} \begin{split} \min_{x,y} &\; c^Tx + f(y)\\ s.t. & \; Ax + Dy \ge ...
1
vote
0answers
20 views

Interpolating polynomial such that it is convex in specified region

The problem I have is that I have data at two points $x_1,x_2$ and $x_2>x_1>0$. At these two points, I know that the function $f$ has values $f(x_1)$ and $f(x_2)$ respectively. It is also ...
1
vote
0answers
15 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...
1
vote
0answers
23 views

Gradient Descent and Scale of Data and Objective Function

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
1
vote
0answers
14 views

Demonstrating convexity of a convex optimization problem

I am working on the following problem. Consider the following function $\textit{f}: \mathbb{R^n}$ × $\mathbb{R^n}$ → $\mathbb{R}$. $$f(\vec{z},\vec{d}) := \min_{t \in \mathbb{R},\vec{v} \in \mathbb{...
1
vote
0answers
43 views

How to solve a binary generalized assignment problem

I have the following generalized assignment problem: Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ such that $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\...
1
vote
0answers
51 views

What are some applications of vertex separators?

What are applications of finding a vertex separator that minimizes a cut in a graph. To clarify the problem I am talking about is is given a graph of n vertices and a partition $m_1,m_2,..,m_k $of ...
1
vote
0answers
40 views

Help needed to define a constraint in an optimization problem?

Given objective function is \begin{align} \underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t \hspace{4mm}\mathbf{p^Te_p}-1=0\\\...
1
vote
0answers
26 views

How to minimize objective function involving convolution?

My objective function is \begin{align} \underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t \hspace{4mm}\mathbf{p^Te_p}-1=0\\\mathbf{...
1
vote
0answers
39 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
39 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
39 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 X-G\...
1
vote
0answers
28 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 \end{...
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: \begin{...
1
vote
0answers
25 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
86 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
31 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
23 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
25 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
50 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
40 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
30 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
21 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
37 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
57 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
30 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
52 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
30 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
42 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 http://papers.nips.cc/paper/4740-...
1
vote
0answers
37 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} & \underset{n_{ij}}{\text{...
1
vote
0answers
28 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
26 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
65 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, y_{k}(x_{k}-x)\...
1
vote
0answers
49 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
82 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
53 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)$, i....
1
vote
0answers
40 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 \Re^n}\bigg\{\textbf{c}^T\textbf{x}-\sum\...
1
vote
0answers
37 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
49 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 f(x,...
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 ...