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

learn more… | top users | synonyms

1
vote
2answers
72 views

Analytically solving simple quadratic problem in single variable with boundary constraints

I want to solve the following optimization problem where $x$ is scalar variable. $$ \min_x \dfrac12ax^2 + bx \\ subject\ to:\ l\le x \le u $$ $ a > 0 $ therefore, this is a convex optimization ...
1
vote
1answer
73 views

Linear System with constrained solutions

After a model my problem I found a rectangular linear system : $$Ax=b$$ I can easely solve it with a least square with QR/SVD... But the model include constrains for each solution $x_i$, the $\vec{x}$ ...
1
vote
0answers
36 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
38 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
1answer
305 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
1
vote
0answers
40 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
14 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
1answer
129 views

Prove convexity of complicated rational function

Can anyone help me prove the convexity of this rational function? The man who proved the convexity of function used these facts. But I don't know this fact is correct or not. Here are the facts and ...
1
vote
0answers
46 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
49 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
39 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
109 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
66 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
25 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
1answer
67 views

Is this function involving matrices convex?

Let $X\in \mathbb{R}^{n \times n}$. Then, is the function $$ \text{Tr}\left( (X^T X )^{-1} \right)$$ convex in $X$? ($\text{Tr}$ denotes the trace operator)
1
vote
1answer
106 views

Convex conjugate of absolute affine function?

Let $f:\mathbb{R}^n \rightarrow \mathbb{R} \cup \{ \infty \}$ be a convex function. The convex conjugate of $f$, which we call $f^*$ is defined as $f^*(y)=\sup \, \left \{ \langle y,x \rangle -f(x) ...
1
vote
1answer
149 views

Characterization of Subset Sum via Linear Programming

I have a sample subset sum problem. Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$ Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$ such that 0 <= $y_1$ <= 1 0 <= ...
1
vote
0answers
203 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
99 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
100 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
96 views

why in Phase I of the simplex method, if artificial variable become nonbasic, it never become basic?

Does anybody has idea how to solve this problem ? "Show that in Phase I of the simplex method, if an arti cial variable becomes nonbasic, it need never again become basic. Thus, when an arti cial ...
1
vote
0answers
54 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
102 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
2answers
295 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
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
48 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
22 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
34 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
19 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
28 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
128 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
82 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
1answer
83 views

Convexity of product of elements from two convex set

Given two convex set $X\subseteq \mathbb{R}^N$,$Y\subseteq \mathbb{R}^{N\times N}$ Given a $x\in X$, is the set $\{z|z=yx,\forall y \in Y\}$ convex? If no, by adding what can force it to be convex? ...
1
vote
0answers
150 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
52 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
1answer
98 views

Some convex optimization questions

Is minimizing number of $\{{i : x_i \ne 0}\}$ subject to $Ax=b$ a convex problem? Why is it computationally hard? What is polar cone of $\{x \in \mathbb{R}^2:0\le x_1 \le x_2\}$? Are ...
1
vote
0answers
138 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
31 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
24 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
1answer
56 views

linear equivalent min{} constraint

Activities are assigned to venues. Each activity $a_i$ has maximum size $b_i$ and demand $c_i$. Each venue $v_j$ has maximum size $d_j$. An activity can be assigned to multiple venues, and we need to ...
1
vote
0answers
109 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
146 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
1answer
203 views

Convex Functions: Proofs

Let $f$ be a monotone nondecreasing function of a single variable which is also convex. Let $g$ be a convex function defined on a convex set $G$. Is it true that the composition of these functions ...
1
vote
0answers
193 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
1answer
259 views

Generalization of soft threshold operator?

For certain $\ell_1$-regularized optimization problems, a critical computational step is the soft threshold operator: $\mathcal{S}_t(x) = \mathrm{sgn}(x)\circ \mathrm{max}(|x|-t)$ where $\circ$ is ...
1
vote
0answers
86 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
58 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
50 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
252 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 ...