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

learn more… | top users | synonyms

1
vote
1answer
25 views

Inequality with three unknowns

Consider: \begin{equation} \Big(e^x-1\Big)\mathbb{1}_{(x\geq0)} \leq \lambda_1+\lambda_2e^x + \lambda_3x^2 \end{equation} where $\lambda_1$, $\lambda_2$, $\lambda_3$ are three unknown constants. By ...
0
votes
0answers
8 views

Does Slater's condition for both primal and dual imply compactness of dual solution set?

Consider a convex optimization problem (P) and its dual problem (D). If the solution set for (P) is compact and Slater's condition holds for both (P) and (D). Is the solution set for (D) compact? My ...
0
votes
0answers
11 views

Understanding ADMM: how is it applied to this particular problem?

While reading Boyd's paper on ADMM I encountered an issue. Consider the following problem: Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and ...
0
votes
1answer
22 views

Continuity of Parameterized Optimal Solution

Suppose for every $y$, $f(x,y)$ is strictly convex in $x$. Further, $f(x,y)$ is continuous in $y$. Let $\mathcal X$ be compact (in my problem, $\mathcal X$ is an interval). Can anyone suggest any ...
0
votes
1answer
17 views
1
vote
0answers
24 views

Prove Jensen Inequality holds for a function

Given function $$f:\mathbb{R}^n_{+} \rightarrow \mathbb{R}, \ f(x) = \sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}}$$ Show that for any $x, y \in \text{dom} \ f, \theta \in [0,1]$, ...
0
votes
1answer
17 views

What is the maximum of the following function?

Let $f(x,y) = \frac{xy^\alpha}{x+y},\alpha\in(0,\infty)$. How to compute $$\sup_{(x,y)\in[a,b]\times [0,c]}\frac{xy^\alpha}{x+y},$$ with $b>a>0$?
0
votes
1answer
17 views

Convex function (vector composition rule)

I'm looking at the Boyd & Vandenberghe slides on Convex Optimization. In slide 18, it applies the rules of vector composition on an example to say that it is convex. The example given is ...
0
votes
1answer
14 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
2
votes
1answer
41 views

Are posynomial functions convex?

I know that you can transform a posynomial function into an exponential function, which is convex. Does this imply that all posynomial functions are convex?
0
votes
0answers
10 views

Find the dual problem to a quadratic program

Consider the quadratic program: minimize $x_1^2 + 2x_2^2 - x_1x_2 - x_1$ subject to $x_1 + 2x_2 \leq u_1, x_1 - 4x_2 \leq u_2, 5x_1 + 5x_2 \leq 1$ Could anyone explain to me how to find the dual ...
1
vote
1answer
34 views

How can L1-sparse representation be formulated as linear programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
1
vote
0answers
23 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, ...
0
votes
0answers
6 views

Explain the dual problem to D-optimal design problem

Given the following D-optimal design problem $$ \text{minimize } \log \det (\sum_{i=1}^p x_i v_i v_i^T)^{-1}\\ \text{subject to } x \geq 0, {\bf{1}}^T x = 1 $$ Find the dual problem. I don't ...
0
votes
0answers
15 views

Is my proof correct? Convex optimization

There's a theorem that says that if $C \subset \mathbb R^n$ is a convex set, then $x^* \in C$ is the closest point in $C$ to $y \notin C$ if and only if $(y-x^*)\cdot(x-x^*)\leq 0$ for all $x \in C$. ...
0
votes
0answers
29 views

What non-convex functions be written as the $\min$ of multiple convex functions?

I am working on an optimization framework that can be used to optimize objective functions that can be written as the $\min$ of several convex functions. I was thinking about the generality of this ...
0
votes
0answers
20 views

Minimize $\|\mathbf{x-y}\|^2 $ subject to $x \in $ set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$

We are given the set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$ and a point $\mathbf{y} \in \mathbb{R}^n$. Our goal is to find point $\mathbf{\hat{x}}$ ...
2
votes
1answer
38 views

About a definition of “rank” of a matrix.

I am familiar with the definition of rank of a matrix as either (1) the maximal number of linearly independent rows or columns or (2) as the dimension of the image of the matrix. Another ...
1
vote
1answer
13 views

Log transformations of function domain and inequalities

If I know that for some function $f$, the following is true for $x, y \geq 0$: $f(\log (x^a y^b)) \leq f(\log x)^a f(\log y)^b$ Can I make the claim that $f(x^a y^b) \leq f(x)^a f(y)^b$ If I ...
0
votes
1answer
45 views

Probability that max cos(φ)x + sin(φ)y according to uniform distribution = (8,5)

max $x_2$ subject to $x_1 - 2x_2 \le 0$ $2x_1 - 3x_2 \le 2$ $x_1 - x_2 \le 3$ $-x_1 + 2x_2 \le 2$ $-2x_1 + x_2 \le 0$ Optimal solution: (8, 5) --> $x_2 = 5$ Now assume that the objective is ...
4
votes
1answer
82 views
+50

Gradient of the dual function for a nonlinear program

I'm attempting to find a proof for a property from Floudas' Nonlinear and Mixed-Integer Optimization book. Consider a nonlinear optimization problem of the form \begin{align} \min_{{\bf x}}&\quad ...
0
votes
0answers
18 views

Convex problem with linear constraints

I wish to solve the following nonlinear program: $$\min_{\substack{x_i\ge 0\\x_1\le x_1+x_3\le x_2}}h_1 x_1+h_2x_2+h_3 x_3+k_1(\tau-x_1)^++k_2(\tau-x_2)^++k_3(x_2-x_1-x_3)^+$$ I have the KKT ...
-1
votes
0answers
40 views

Prove that $f(x,y) = x/(y^2+1)$ is convex

Suppose $f(x,y) = x/(y^2+1)$. I was trying to prove that this function is convex. So I took partial double-derivative and constructed the Hessian for this function. Here the Hessian is a 2 by 2 matrix ...
0
votes
1answer
18 views

Tracking a vehicle moving with uniform velocity?

Suppose there are three cell towers at three positions $P_1$, $P_2$ and $P_3$. A vehicle is moving at uniform speed along a straight line. Three towers are pinging the vehicle at certain ...
0
votes
1answer
20 views

How to show the Hessian matrix of such functions are positive semi-definite?

Let $f:R\to R$, $g:R^n\to R$. Thus $f\circ g:R^n\to R$. Now suppose $f$ is non-decreasing and convex while $g$ is convex. In additon, $f,g$ are of $C^2$. I want to show that their composition is ...
0
votes
2answers
15 views

why Quasiconvex function is not concave?

A quasiconvex function is a function whose all sublevel set are convex. I am curious to know whether a quasiconvex function is a concave function.
0
votes
0answers
21 views

Explicit solution for minimization over unit box with total budget constraint

I am trying to solve question 4.8, part (e) from Convex Optimization by Boyd. The problem is to find an explicit solution for the minimization problem: Minimize $\textbf{c}^T \textbf{x}$ subject to ...
-1
votes
0answers
32 views

Optimization Problem Solving [closed]

I have some ambiguity about mathematical optimization problem modeling and solving because I don't have much more mathematical skills. Basically, I am from computer science background much more in the ...
0
votes
1answer
34 views

Gradient of Least Squares function

I have trouble understand the gradient of equation 3.12 with respect to $W$. Tn is a scalar output variable, $\phi(x)$ and $W$ are $N \times 1$ dimensional. According to the book, the gradient ...
1
vote
1answer
53 views

Dual program is wrong. Authors claim is right.

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong. This is the primal Linear Problem: $$ \begin{array}{cccc} ...
0
votes
0answers
35 views

Showing λu + (1 − λ)v is an optimal solution

$$\max \quad c \cdot x \\ \mathrm{s.t.} \ Ax \leq b\\ x\geq 0 \\$$ There are two optimal solutions to the LP $u$ and $v$. How do I show that for $\lambda \in [0,1]$, $\lambda u + (1-\lambda)v$ is ...
0
votes
0answers
23 views

On the proof of corner points maximising or minimising a linear function over a bounded convex region

This proof says if $Z_P \ne Z_Q$, then $Z$ is maximised (or minimised, I guess) at one of the endpoints -- of what exactly? $\overline{PQ}$? So the maximum value of $Z$ occurs at either $P$ or $Q$? ...
0
votes
0answers
20 views

Can we relax the assumption of nonnegativity in this proof on convexity of a feasible region in a linear programming problem?

Is the $\color{red}{\text{non-negativity constraint (see red box)}}$ used at all in the proof? If so, where? If not, does the proof then hold for a standard LP problem without the non-negativity ...
1
vote
0answers
19 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 ...
0
votes
1answer
28 views

Identify if optimization problem is convex or non-convex?

I have formulated optimization problem for building, where cost concerns with energy consumption and constraints are related to hardware limits and model of building. To solve this formulation, I need ...
0
votes
1answer
14 views

Optimization problem for non-symmetric normal cone inclusion or antiderivative of Ax+b

I have the following equation: $$ -(\mathbf{A}\mathbf{x} + \mathbf{c}) \in \mathcal{N}_{C}(\mathbf{x}) \qquad (1) $$ where $\mathbf{A} \in \mathbb{R}^{n\times n}$ is symmetric and positive definite, ...
1
vote
1answer
27 views

Duality and the Positive Lagrange Multiplier

Suppose I have the following optimization problem: \begin{align} \min &f(x) \\ & f_1(x) \leq 0 \\ & \vdots \\ & f_k(x) \leq 0 \\ & g_(x) = 0 \\ ...
0
votes
0answers
27 views

Number of optimas of product of convex functions

I am dealing with a function, which is a product of two strongly convex functions, and trying to determine the number of its local minimum. For example, I have $$H=f(x)\cdot g(x)$$, in which both $f$ ...
1
vote
1answer
29 views

Is closed convex set with finite number of extreme points convex polyhedron

I have this simple question related to convex set and convex polyhedron. As the content in the title, it's basically my question: Is closed convex set with finite number of extreme points convex ...
0
votes
1answer
17 views

How to interpret the regular condition in this theorem about cones in convex analysis?

Theorem:Let $K_1,\dots, K_m$ be convex cones in $R^n$ and let $K = K_1 \cap K_2 \cap \dots K_m$. If $K_1 \cap int(K_2) \cap \dots \cap int(K_m) \neq \emptyset$(regularity assumption), then $K^\circ = ...
0
votes
0answers
17 views

Connection between method of Lagrange multipliers and KKT conditions?

I understand that in general, the KKT conditions are not sufficient for optimality. However, if the primal problem is a convex optimization problem, then the KKT conditions are sufficient for ...
1
vote
1answer
47 views

Is $-\ln(1+e^x)$ a convex function?

Is $-\ln(1+e^x)$ a convex function? My answer book says no because its second derivative is $-\dfrac{e^{2x}}{(1+e^x)^2}$ but I am sure that it is incorrect. I have that the second derivative is ...
0
votes
0answers
11 views

uniform lower bound for convex combination of a sequence of positive semidefinite matrices

Assume: a sequence of positive semidefinite matrices $A_k^i\in M_{m,n}, m<n$, $i\in\mathcal{N}$, and they have the following property: $$\underline{a}I \leq A_k^i(A_k^i)^T\leq \overline{a}I.$$ ...
0
votes
1answer
25 views

Solving SVM classifier with two weight vectors

I am trying to implement a paper that basically proposes the following way to train two classifiers on some data with two types of labels. I do not know how to tweak existing solvers for SVM to do the ...
0
votes
1answer
20 views

Stopping criteria for gradient method

For numerically solving a smooth convex optimization $\min\{f(x): x\in S\}$ where $S$ is a closed convex set, we can apply some different algorithms: gradient method, accelerated gradient, proximal ...
0
votes
0answers
15 views

Slater point and Ideal Slater point

How do we show that an ideal slater point lies in the relative interior of the Feasible set (of a convex optimisation problem)?
0
votes
1answer
22 views

Does the non-expansion property of the projection operator hold for all definitions of norm?

For convex problem, of course. I vaguely remember this holds for weighted norm also. But I am curious if there are some general conclusions about what kinds of norm will fit in this framework?
1
vote
3answers
34 views

Minimum Enclosing Ellipsoid To Maximal Enclosed Ellipsoid

Given a convex body $K$ and an ellipsoid of minimal volume which contains $K$, find the maximal ellipsoid contained in $K$. I have tried to multiply the matrix by 4 (since the eigenvalues are the ...
1
vote
0answers
34 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 ...
0
votes
1answer
54 views

Is $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ concave? [closed]

I want to maximize the capacity function $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ with respect to $F$, subject to the constraints: (1) $\operatorname{trace} F \le Pt$ (2) ...