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

learn more… | top users | synonyms

0
votes
0answers
181 views

Convex Functions on 2 variables over an interval

It is required to show that $f(x) = x_1x_2$ is a convex function on $[a,ma]^T$ where $a\ge 0$ and $m\ge1$.To show convexity we need to show that for $\lambda \in [0,1]$: $f(\lambda x + (1-\lambda ...
2
votes
1answer
60 views

Are all polytopes also convex hulls?

It seems, at least in the 2-D case, that all polytopes are going to be convex. Does this hold if the dimensions are increased?
2
votes
0answers
59 views

Prove that $\text{int}(\text{dom}(f))$ is a convex set.

Let $f$ be a convex function. I have to prove that $\text{int}(\text{dom}(f))$ is a convex set. (Be careful with $-∞$ )
27
votes
4answers
3k views

Please explain the intuition behind the dual problem in optimization.

I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply: 1) How ...
0
votes
1answer
102 views

Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
-1
votes
1answer
102 views

Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem: Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
1
vote
0answers
37 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| ...
0
votes
1answer
78 views

property of cones and their duals

I am reading Convex Optimization by Boyd and Vandenberghe (free at http://www.stanford.edu/~boyd/cvxbook/) and I am trying to justifying their assertion (p. 53) that if $K$ is a proper cone, $K^*$ is ...
2
votes
0answers
212 views

sufficient condition for KKT problems

For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that: "The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are ...
3
votes
3answers
913 views

Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
1
vote
2answers
157 views

What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...
0
votes
1answer
142 views

Matrix computations problem: rank, pseudo inverse,…

Suppose we are given two arbitrary $m \times n$ matrices, $A$, $B$, where we know $B$ has full column rank. Let $m>>n$. Can we always find a square $m \times m $ matrix $X$, such that $A=XB$? I ...
0
votes
0answers
149 views

Is positively weighted sum of eigenvalues of a matrix X, convex function of X?

Is positively weighted sum of eigenvalues of a matrix X, convex function of the matrix X?
3
votes
2answers
980 views

Why does a positive definite matrix defines a convex cone?

I've been working on convex optimization and got stuck. What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ? If I have a p.d matrix which ...
1
vote
1answer
115 views

Convex Combination of Hermitian Matrices

Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
2
votes
1answer
141 views

Positive values for a set of quadratic forms of Hermitian Matrices. (To find a set of vectors in which a hermitian matrix is positive definite)

Assume all matrices I discuss about are $N \times N$ and the vectors conform with dimensions. Consider the following set of Quadratic inequalities where all the matrices $A_i$ are hermitian. ...
3
votes
1answer
399 views

Lagrangian Multipliers

I have a fundamental question about Lagrange multipliers. Here it is: I have a function to maximize with respect to a parameter say $\theta$, subject to two constraints. Lets assume that the first ...
0
votes
1answer
27 views

unstable optimizer, stable objective

I am trying to minimize a convex objective numerically using gradient descent. I select the starting point randomly. I repeat the experiment multiple times. The optimal objective value I get each time ...
1
vote
0answers
130 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 ...
3
votes
0answers
211 views

Global optimum of sum of convex functions

Take two real differentiable convex functions, $f_1$ and $f_2$, defined on the unit interval $[0; 1]$. I want to find the global optimum of: $\min_{x \in [0;1]} af_1(x)+bf_2(x)$, for given $a, b \in ...
0
votes
2answers
41 views

Convexity of a function and constraint

Consider the quadratic function $f(x_1,x_2,x_3,x_4)=x_1+2x_2+4x_4+x_1^2+5x_2^2+3x_3^2x_4^2-4x_1x_2-2x_2x_3+2x_3x_4$. Is f a convex function? Consider a constraint defined using the above function f: ...
2
votes
4answers
353 views

definition of strongly convex

There are several equivalent definitions for strongly convex. For example, some literature said: A function $f$ is strongly convex with modulus $c$ if either of the following holds $$f(\alpha ...
0
votes
1answer
99 views

what math topic is this kind of example part of? or what is needed to understand how to solve it? [closed]

we 100000000 sets/locations. each set has, A = % chance of finding a cure (there are many different types of cures) for cancer B = time it takes to extract a cure to caner C = the optimal % chance (IN ...
1
vote
0answers
94 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 ...
0
votes
1answer
132 views

Parametric Linear Program: Continuous Solution?

Consider the parametric linear problem $$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$ $$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$ where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
0
votes
2answers
268 views

Numerical optimization with nonlinear equality constraints

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
1
vote
2answers
266 views

Gradient of Moreau-Yosida Regularization

Let $f(x):\Re^n\rightarrow \Re$ be a proper and closed convex function. Its Moreau-Yosida regularization is defined as $F(x)=\min_yf(y)+\frac{1}{2}\|y-x\|_2^2$ $Prox_f(x)=\arg\min_y ...
6
votes
4answers
700 views

Why is the affine hull of the unit circle $\mathbb R^2$?

In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $\mathbb R^n$ as $$\text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + ...
0
votes
2answers
343 views

Intuition behind gradient VS curvature

In Newton's method, one computes the gradient of a cost function, (the 'slope') as well as its hessian matrix, (ie, second derivative of the cost function, or 'curvature'). I understand the intuition, ...
4
votes
4answers
532 views

Summary of Optimization Methods.

Context: So in a lot of my self-studies, I come across ways to solve problems that involve optimization of some objective function. (I am coming from signal processing background). Anyway, I seem to ...
0
votes
0answers
126 views

MiniMax Theorem

Consider the compact sets $X \in \mathbb{R}^n$, $Y \in \mathbb{R}^m$, $A \in \mathbb{R}^n$, $M \in \mathbb{R}^{n \times m}$. For fixed $(\bar{a},\bar{B}) \in A \times M$, by the MiniMax Theorem we ...
2
votes
3answers
1k views

Trace of a quadratic function, Convexity

Is trace($XX^T$) a convex function of matrix $X$? A linear function of a quadratic should be convex, but I could not prove by definition.
0
votes
3answers
71 views

Membership based on maximum of a function over the set.

Let $S\subset \mathbb{R}^n$ and let $f(x)$ be a continuous function over $\mathbb{R}^n$. Furthermore, define $s_{\text{max}}:= \sup_{x\in S} \{f(x)\}$ and let $f(x)$ attain its minimum for at least ...
1
vote
1answer
148 views

Equality constrained norm minimization

In these slides (5) the dual function for the norm minimization problem: $$ \min_x \|x\| \quad \mbox{s.t.} \quad Ax =b $$ is defined as: $$ g(v) = \inf_x (\|x\| - ν^\intercal Ax + b^\intercal ν) $$ ...
0
votes
2answers
186 views

distance between a polytope point and a polytope vertex

How to find distance in between any polytope point to the closest vertex of the polytope (the verteces of the polytope are known)? How to find a distance from the farest polytope point to the closest ...
2
votes
1answer
67 views

Is this operator monotone?

Consider a convex optimization problem. $$\min_{u\in\Re^k} f(u)$$ s.t. $g_i(u)\leq0,\ i=1,\ldots,m$ Let ...
0
votes
1answer
108 views

How I can find an optimal solution for a model with concave-convex objective function?

My objective function is sum of three functions, 2 linear functions and a concave function ($1-\exp(x)$); constraints of my model are convex. How can I obtain optimal solution from this problem?
1
vote
1answer
161 views

Is concave quadratic + linear a concave function?

Basic question about convexity/concavity: Is the difference of a concave quadratic function of a matrix $X$ given by f(X) and a linear function l(X), a concave function? i.e, is f(X)-l(X) concave? ...
2
votes
0answers
86 views

How to get the initial ellipsoid in the ellipsoid method for solving optimization problem?

If what I assume is correct, assumption : for a maximization problem, we run a binary search over estimated values, starting with max estimated value, and narrow down to the feasible optimal value ...
0
votes
0answers
98 views

Iterative scheme for a nonlinear optimization problem

Let $\mathbb{PD}_3 \subset \mathbb{R}^{3 \times 3}$ be the set of the positive-definite $3 \times 3$ real matrices. For given $v \in \mathbb{R}^{3 \times 1}$, consider the function $f_v: ...
1
vote
2answers
446 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
2
votes
1answer
571 views

Lasso with linear constraints

I want to efficiently solve the following optimization problem: \begin{align} \min &\quad \left\|\mathbf{x}-\mathbf{x}_0\right\|_2^2 + \lambda\left\|\mathbf{x}\right\|_1\\ \text{Subject to}& ...
2
votes
0answers
70 views

Find a vector such that its matrix product is positive in every element

Given a matrix $A$ I want to find a vector $\vec{x}$ such that every element of $A\vec{x}$ is strictly positive. Also, the columns of $A$ do not span the full space, so if I were to just naively pick ...
1
vote
1answer
374 views

projected gradient method, multiple constraints

I am trying to minimize convex objective $f(X)$, for matrix $X$ s.t. $X\ge 0$ component-wise, and $X1^T = 1^T$. I want to use projected gradient descent. However, I only know how to project on ...
1
vote
1answer
246 views

What is a good technique to decide step size in sub-gradient method for dual decomposition?

I am looking at the following paper to implement dual decomposition for my algorithm: http://www.csd.uoc.gr/~komod/publications/docs/DualDecomposition_PAMI.pdf On Pg.29 they suggest setting the step ...
0
votes
0answers
302 views

Bivariate function maximization

I have a bivariate function like $ f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y} $ and I want to find its global maximum over a range of $ x \in [0, 200] \text{, ...
0
votes
2answers
178 views

Simple example where strong convexity is necessary over strict (or even regular) convexity.

I am trying to get a hold on exactly what strong convexity gives you over strict (or regular) convexity. Yes there are simple functions which demonstrate the difference between these ideas, but what ...
1
vote
1answer
25 views

In an engineering/optimisation context, does set $E$ have any special significance?

I am reading a paper about optimsation and the description, while mostly being a very good description, makes reference to some variables being in some set $E$. For example, it states that parameter ...
3
votes
2answers
283 views

Solving Linearly Constrained Quadratic Programming with Coordinate Descent

Does anybody have any idea about how to solve the following problem with Coordinate Descent? \begin{align} \min &\quad \mathbf{x}^{\top}P\mathbf{x} + b^{\top}\mathbf{x}\\ \text{Subject to}& ...
3
votes
1answer
282 views

Going in the direction of the gradient

First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$. Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$. Now my ...