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

learn more… | top users | synonyms

1
vote
0answers
24 views

Issues related to positive definiteness in a convex optimization problem

I have some issues in a convex optimization problem. My f(X) is a convex function of X where X is a positive definite matrix. X is very sparse and has a handful of non zeros values. Now I only need to ...
1
vote
0answers
21 views

Confusion related to interior point method

I was reading this wiki article related to interior point method. I didn't get when they say that it applied Newton's method to get an update for $(x,\lambda)$. How the expression at the end ...
1
vote
0answers
65 views

Confusion related to fmincon function in matlab

I was reading this help section of matlab's fmincon function that uses interior point algorithm for solving an optimization problem. It says the following optimization problem is replaced by To ...
1
vote
0answers
56 views

Is the following problem convex , quasiconvex, or nonconvex?

I want to get the optimal matrix $W$. But I am not sure whether it can be resolved. Note that $W,\mu,\lambda_{1},\ldots,\lambda_{K} $ are variables, others are fixed. Is it convex or quasiconvex or ...
1
vote
0answers
33 views

Is the optimizer of a strongly-convex cost function bounded?

Let f(x) be strongly-convex. Can its minimizer be unbounded? I suspect not. Can we obtain a bound on it in relation to the strong-convexity constant? I believe an equivalent formulation of this ...
1
vote
0answers
23 views

Is $Q(b)=a^Hb+b^Ha$ ,where $a,b \in \mathbb{C}^{N\times1},b^Hb\leq\epsilon^2$convex or concave?

We assume that $a,b \in \mathbb{C}^{N\times1},b^Hb\leq\epsilon^2$. Is the function $Q(b)=a^Hb+b^Ha$ convex,concave? In other words, which of the following problems is feasible? $\min\ \ ...
1
vote
0answers
26 views

The timestep of Forward–backward algorithm

Recently, I try to learn Forward backward splitting algorithm. I find it was proposed in 1988 'Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational ...
1
vote
0answers
64 views

Confusion related to k neighborly polytope

I was reading this paper related to neighborly polytope where they mentioned: Consider a $d \times n$ matrix $A$, with $d < n$. The problem of solving for $x$ in $y = Ax$ is underdetermined, ...
1
vote
0answers
38 views

Least square with constraints

I want to solve the least squares problem $(Ax-b)^2$ with no intercept term for linear regression with the constraint that the sum of the params/weights is equal to 1. I am trying to get the closed ...
1
vote
0answers
41 views

Issues with CVX package for optimization

I am trying to use the cvx package for optimization. However, I am having some issues with it. I have a variable X which is a matrix but I cannot add $X^{-1}$ in the objective function. What should I ...
1
vote
0answers
42 views

Permutating a matrix in a convex form

I am at the basis of convex optimization and I made a constraint written in the following form: $XAY\le M$ where: $A\in R^{3,4}$ given, $a_{ij} \in \{0,1\}\quad \forall i,j$ $X\in R^{3,3}$ ...
1
vote
0answers
15 views

Confusion about the implementation of thresholding operation

I was reading this paper. I didn't get the application of thresholding operator here I didn't get how the -c part came in the solution $\mu = -c + S(c-b/a, \lambda/a)$
1
vote
0answers
51 views

Optimization problem in the Von Neumann Entropy

I have a constrainted optimization problem in the Von Neumann Entropy. In a CVX-like syntax the problem goes as follows: given variable $\mathtt{c(n)}$ $$\begin{align} \text{minimize} \qquad & ...
1
vote
0answers
57 views

Duality in Chebychev approximation

I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me. Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the ...
1
vote
0answers
40 views

Looking for a “Neat” Transform to Yield a Convex Set

Optimizing on a unit sphere $\mathbb{S}^n$ is almost a convex problem (if the function is convex in the new set) if we make our "new" set $\mathbb{R}^n$, via the stereographic projection. Clearly ...
1
vote
0answers
132 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
1
vote
0answers
69 views

Maximum of the expectation of a concave function

Let's have a function $f(x, \theta)$, and some probability distribution on $x$. Let's say I have found $\theta^* = \operatorname{argmax}(f(E[x], \theta) $, and $f$ is concave in $x$. I would like to ...
1
vote
0answers
31 views

An Optimization problem related with $(-1)^{N-1}\sum_{i=1}^M\frac{\ln x_{i}}{x_{i}^N}\prod_{j\neq i}\frac{x_i}{x_i-x_j}$

I encountered an optimization problem \begin{align} f(x)=(-1)^{N-1}\sum_{i=1}^M\frac{\ln x_{i}}{x_{i}^N}\prod_{j\neq i}\frac{x_i}{x_i-x_j} \end{align} where $N$ is a positive integer, $x_i>0$ for ...
1
vote
0answers
240 views

Error on optimization problem, maximize log determinant on CVX

$A$ is an $N \times N$ complex matrix $W$ is an $N \times N$ complex matrix $C$ is an $N \times N$ complex diagonal matrix $u$ is a scalar $V$ is an $N \times N$ complex matrix, whose diagonal elects ...
1
vote
0answers
111 views

Confusion related to derivation of soft thresholding

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg ...
1
vote
0answers
114 views

Confusion related to optimization of log(det(X)) function

I have this confusion related to optimization of the log(det(X)) function. I didn't get how it implicitly maintains the constraint of X being positive definite. For eg if I have a matrix ...
1
vote
0answers
59 views

Suggestions for a reference-level text on optimization theory?

I'd be interested in knowing if anybody has suggestions on an advanced but still self-contained reference on optimization theory, centered around linear and convex problems. The key feature of my ...
1
vote
0answers
124 views

non-degenerate basic feasible of Polyhydron

I couldn't show this problem. Can somebody help me by this question? Consider a polyhedron $\{X \in \mathbb{R}^n | AX \leq b, X \geq 0 \}$ and a non-degenerate basic feasible solution $X^*$. We ...
1
vote
0answers
31 views

“Buzzword” for approximate gradients (that form a positive scalar product with the real gradient)

Let $\vec g(\vec x)\in\mathbb R^N$ be the gradient of a convex function $L: \mathbb R^N\mapsto \mathbb R$ and $\vec h(\vec x)$ such that $$ \vec h(\vec x)^T\vec g(\vec x) \geq 0\quad\quad \forall \vec ...
1
vote
0answers
50 views

Solution of a Quadratic Optimization Problem

Let $\mathbf{A_1}$ and $\mathbf{A_2}$ be two given $N\times N$ hermitian matrices. Then how do I solve the problem, \begin{align} ...
1
vote
0answers
25 views

I need a resource for basic convex optimization algorithms.

I'm trying to decide whether or not a certain CS problem can be solved in polynomial time. I've got it reduced down to a basic convex optimization problem, but I can't for the life of me find a good ...
1
vote
0answers
35 views

Basic questions about convex optimization

I have some basic questions about convex optimization. From finding sources online, I've seen that many algorithms (for example, Newton's method) describe themselves as $o(\frac{1}{\epsilon})$. ...
1
vote
0answers
21 views

Which methods of function continuation admit polynomial-time convex minimization?

The function $f$ maps the positive integer lattice in $\mathbb{R}^n$ (i.e. the vectors in $\mathbb{R}^n$ whose coordinates are all integers) to $\mathbb{R}$. We know that $f$ is convex. I want to ...
1
vote
0answers
29 views

A question about monotonicity

Is $$D(y_l)=\int_{-\infty}^{y_l}f_0(y)\mbox{d}y+\int_{y_l}^{y_u}e^{x\ln(1/L(y_l))}L(y)^{x}f_0(y)\mbox{d}y+\frac{1}{L(y_l)}\int_{y_u}^{\infty}f_0(y)\mbox{d}y$$ with ...
1
vote
0answers
158 views

Facets of the convex hull as solution of an optimization problem?

Given $N$ points $x_1, x_2, ..., x_N \in \mathbb{R}^n$, consider their convex hull $$\mathcal{C} = \text{conv}( \{ x_1, ..., x_n \} ) = \bigcap_{j=1}^{J} \{ x \in \mathbb{R}^n : \ A_j x \leq b_j \} ...
1
vote
0answers
92 views

Formulation of a problem as semidefinite programming

I would appreciate some help with this problem: $R$ is a positive semidefinite matrix $\in{R}^{n\times n}$, $A \in{R}^{n\times m}$. I need to formulate this optimization problem as semidefinite ...
1
vote
0answers
166 views

About Schur complement in a non-linear matrix inequality

I have the following matrix inequality which is nonlinear due to $M^TM$. In order to transform into an LMI, I apply the Schur complement, however I am not sure about the result. Can you tell me if ...
1
vote
0answers
58 views

Is it problematic when using Newton Descent with discontinuous Hessian?

Is there any side effect when applying Newton Descent to a convex function whose Hessian is discontinuous?
1
vote
0answers
159 views

Maximizing an inner-product over a convex set.

Let $x \in \mathbb{R}^N$ and let $K$ be a closed convex set in $\mathbb{R}^n$. Let $$ \widehat{y} = \textrm{arg} \, \textrm{max} _{\,\,y \in K} \langle x,y \rangle,$$ where $\langle \cdot, \cdot ...
1
vote
0answers
32 views

Confusion related to convexity and concavity of a problem

I was reading this paper http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf related to adaptive multi-hyperplane machine for non linear classification In that paper, they have mentioned about ...
1
vote
0answers
25 views

Can we express a SPD matrix $S$ in terms of $S^{2}$ in a different manner to solve a convex problem?

I have to find the Symmetric Positive Definite matrix $S\in \mathcal{M}_{m,m}$ that minimizes the function $f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ which has been proven to be convex in the ...
1
vote
0answers
114 views

maximize an objective function with an infinite component

Suppose I have the following maximization problem: $\log\det(\alpha K_p)-c\alpha$ with respect to $\alpha$ with $c$ being a constant and $m$ being the dimension of $K_p$. Here, one of the eigenvalues ...
1
vote
0answers
159 views

K.K.T. conditions, Lagrangian gradient not defined for zero.

When I write the K.K.T. conditions for the problem I have, I get the following expression for the gradient of the Lagrangian: $$\frac{\partial \mathcal{L}}{\partial x} = - \frac{\sqrt{x} + ...
1
vote
0answers
216 views

How to find $\kappa$ to minimize integral $I = \frac{1}{\kappa}\int\limits_{0}^{T} \mathrm{exp}\left(-f(\kappa,x)\right) \mathrm{d}x$

I am trying to find such value $\kappa \in (0,1)$ that would minimize the integral \begin{equation} \begin{aligned} I = \frac{1}{\kappa}\int\limits_{0}^{T} \mathrm{exp}\left(-f(\kappa,x)\right) ...
1
vote
0answers
109 views

Minimize a complex quadratic subject to two convex quadratic constraints

I have the following the optimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~&||\mathbb{x}^H\mathbb{u}||_2^2-2*Real\{ \mathbb{x^Hu}\} \\\ ...
1
vote
0answers
62 views

Parameterized convex optimization

I'm trying to formulate a game so that at Nash equilibrium I achieve supply equales demand. Then I ran into this problem. For all $i,$ $v_{i}\left(x_{i}\right)$ is concave in $x_{i}$. The value ...
1
vote
0answers
59 views

Closed form for Lagrange dual

Can Lagrange dual always be computed in closed form? Can you give me a simple example where the dual is not analytically computable?
1
vote
0answers
55 views

why is it important to have $\max_x \min_y f(x,y)=\min_y \max_x f(x,y)$?

I am currently trying to understand the minimax theorem of Von Neumann and the improved versions of this theorem. At any case we have the property $$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} ...
1
vote
0answers
297 views

Linear programming: writing a problem with artificial variables?

Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
1
vote
0answers
48 views

Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $$ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1
vote
0answers
47 views

General properties of an optimal solution of a convex program

How do we seek certain properties for a solution of a convex minimization problem. For example we want to make sure if the below objective has a symmetric optimal solution: \begin{equation} \min_X ...
1
vote
0answers
38 views

using the ellipsoid algorithm to find a poly time algorithm for the optimization problem

Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in $\mathbb{R}^n.$ Find $\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| ...
1
vote
0answers
136 views

Upper bound for L1-L2 optimization problem

I am interested in the following convex optimization problem: \begin{align*} \max & ||x||_1 \\ \text{s.t.} & ||x-a||_1 \le K \\ & ||b\circ x||_2 \le 1\\ & x \in R^n \end{align*} where ...
1
vote
0answers
95 views

minimum of the function over symmetric body

Let $X$ be a normed space. Let $K$ be centrally symmetric convex body with $M$ known vertices and with $Vol(K)=V$. We subdivide body $K$ be $M$ equal pieces, $P_i, i=1, \ldots, M$, such that each ...
1
vote
0answers
171 views

Efficient Algorithm For Projection Onto A Convex Set

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem: $\underset{p}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2 \;\; ...