Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
1answer
10 views

Matrix norm in the objective of an optimization problem

I am stuck with the following optimization problem from research. The optimization problem have the following objective function: $\|Q-H\|_\infty$. Here $Q$ is a PSD matrix and $H$ is a symmetric ...
0
votes
0answers
12 views

Minimizing the function with a log determinant and trace function?

I am trying to minimize the following argument, which is unbounded in case one of the eigenvalues of $A$ is equal to zero. $\arg min_{S} \log|S^H A S| - tr\{ \Sigma^{-1}S^HAS\}$ Let $A > 0$, ...
-1
votes
2answers
48 views

An exam`s points dilemma

On July 2 I have an exam, in this exam will be 40 questions in test with 5 variants of answer for each question. For each correct answer will be given +1 point. For each incorrect answer will be ...
0
votes
0answers
10 views

How to drive the membership function in fuzzy clustering nean

I am learning about Fuzzy c-means (FCM) which is a method of clustering which allows one piece of data to belong to two or more clusters. This method (developed by Dunn in 1973 ) is frequently used in ...
0
votes
0answers
16 views

Compressive sensing for complex matrix

I'm fairly new to compressive sensing, and I have been looking for a MATLAB implementation of the problem $$ A x = b $$ where $A$ is non square, $x$ is kind of sparse and all the numbers involved are ...
0
votes
1answer
18 views

Eliminate cases before calculting all KKT conditions

I have the following non linear programming to solve: $$\left\{\begin{matrix} \min & (x-3)^2 + (y-2)^2 \\ s.t. & x^2 +y^2 \leq 5 \\ & x+y\leq 3 \\ & x \geq 0\\ & y\geq 0 ...
0
votes
0answers
7 views

Find $\alpha$ which makes the problem have an optimal solution or none at all + dual problem LP

min $x_1 + \alpha x_2 $ subject to $4x_1+3x_2\leq29$ $x_1+x_2\geq4$ $x_1\leq5$ $x_2\leq7$ Find for which $\alpha$ the given problem has an optimal solution or no solution at all. Provide the ...
0
votes
1answer
15 views

multi objective optimization

Suppose we want to maximize two positive bounded objectives. A usual approach for this aim is to maximize a weighted sum of these two objectives. Now, my question is why not to maximize the product ...
1
vote
1answer
33 views

binary quadratic optimization problem

I am trying to solve the following binary quadratic program. $$ \min_{\Delta} \Delta^T H \Delta + c^T\Delta \\ \text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \Gamma ...
5
votes
3answers
58 views

Optimal approximation of quadratic form

Let $\mathbf{x}\in\Bbb{R}^n$ and $A\in\Bbb{S}_{++}^n$, where $\Bbb{S}_{++}^n$ denotes the space of symmetric positive definite $n\times n$ real matrices. Also, let $Q\colon\Bbb{R}^n\to\Bbb{R}_{+}$ be ...
2
votes
1answer
31 views

If $H$ is positive definite and $s^Ty>0$, then $s^THs-\frac{s^Tyy^Ts}{s^Ty+y^TH^{-1}y}\ne -1$

Let $H\in\mathbb{R}^{n\times n}$ be symmetric and positive definite $s,y\in\mathbb{R}^n$ with $s^Ty>0$ How can we show, that $$s^THs-\frac{s^Tyy^Ts}{s^Ty+y^TH^{-1}y}\ne -1\;?\tag{1}$$ ...
3
votes
0answers
26 views

Minimizing Area by Approximation

Suppose I have an increasing step function $E_c$ given by $$E_c(\phi) = \sum_{i=1}^n E_i \theta(\phi - \phi_i),$$ where $\theta$ is the Heaviside step function and $E_i$, $\phi$, and $\phi_i$ are all ...
0
votes
1answer
15 views

Maximization of quadratic form over complex unit cube

I am trying to find the maximum of a hermitian positive definite quadratic form $xQx^H$ (where $Q=Q^H$ and all eigenvalues of $Q$ are non-negative) over the complex unit cube $|x_i|\leq 1$, ...
1
vote
0answers
13 views

coin distribution problem to optimize

I have N users, where each user has a money request. There are T number of coins, these coins are to be assigned to the user in such a way that his request is fulfilled.Assume Each coin may have ...
0
votes
0answers
9 views

Prove that if $e \in \left ( S\to \overline S \right )$ when $\left ( S, \overline S \right )$ is a min-cut, then $f(e) = c(e)$

Given a min-cut $\left( S, \overline S \right )$, we define $\left ( S\to \overline S\right ) =\{\left (u\to v\right )|u \in S, v\in \overline S\}$ and $\left ( \overline S \to S \right )$ similarly. ...
0
votes
0answers
12 views

For which values of $c_1, c_2$ and $c_3$ is (1, 2, -2) a local minimum

Consider the problem $$\left\{\begin{matrix} \min & x^2 -2xy + 2xz +y^2 + 4yz + z^2 + c_1x + c_2y + c_3z \\ s.t & g(x,y,z)=-x^2 -4xy - 4xz -2y^2 -4yz - 2z^2 + x -y+z+4 =0 \\ \; & ...
0
votes
1answer
47 views

Minimal area of triangle

We have the points $A(2, 3-m), B(m+2, -1)$ and $C(m, 2-m)$. Where $m$ is a real number. Find $m$ for which the area of triangle $ABC$ is minimal. So I've tried to find the equation of line $BC$(the ...
0
votes
1answer
12 views

Constrained Optimization: $\min x_1$

Consider the problem $$\left\{\begin{matrix}\min & x_1 \\ s.t & x_2 \geq 0 \\ \; & x_2 \leq x_1^3 \end{matrix}\right.$$ It is asked to find the minimum and show why this does not satisfy ...
2
votes
4answers
84 views

Minimization on compact region

I need to solve the minimization problem $$\begin{matrix} \min & x^2 + 2y^2 + 3z^2 \\ subject\;to & x^2 + y^2 + z^2 =1\\ \; & x+y+z=0 \end{matrix}$$ I was trying to verify the first ...
0
votes
0answers
6 views

Gomory's cut typical running time until the constraint is fractional

I was considering the following problem. Say we are given an linear programming problem $$ \max c^Tx $$ $$ Ax \le b $$ $$ x \ge 0$$ Where instead I consider $i^{th}$ the optimal solution $X_i$ of ...
0
votes
0answers
9 views

what is the dual problem of finding chebyshev's center?

let $a_j$ $(j=1,...,m)$ be a set of points in $R^2$. The problem of finding Chebyshev's center is: min r s.t. $norm(x-a_j)<=r$ $(j=1,...,m)$ Where r is the maximal radius and x is the center ...
0
votes
0answers
13 views

Convex signal reconstruction for convex generator function?

Let $f : \mathbb{R} \mapsto \mathbb{R}$ be a convex (not affine) function and suppose that $y = f(x)$. We want to reconstruct the input $x$ for a given $y$, and the standard approach would be to ...
6
votes
2answers
125 views

Find the minimum value of $A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}$

Let $a, b$ and $c$ three positive real numbers such that $a+b+c=3$. Find the minimum value of $$A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}.$$ Here is my attempt. By symmetry we can assume that ...
1
vote
0answers
17 views

Is there only one set of KKT conditions for a given optimization problem?

Consider an optimization problem $$ \begin{align} \max_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad & g_i(x) \le0,\,i=1,\ldots,m\\ \quad & h_j(x)=0,\,j=1,\ldots,l\\ \end{align} $$ ...
0
votes
0answers
11 views

How to optimize a generalized trace problem in dimensionality reduction

I know how to solve this problem in dimensionality reduction. $argmax_{X}$ $Trace[XLX^T]$ with $XX^T=I$ ,where $L$ is symmetric, $X$ is unitary, and $I$ is identity matrix. But I'd like to know how ...
1
vote
0answers
10 views

closed form solution to best invertible matrix which minimizes product

Let $U, X \in \mathbb{R}^{n_1 \times r}$ and let $V, Y \in \mathbb{R}^{n_2 \times r}$. Consider the optimization problem $$ \begin{align*} \min_{A, B, \Sigma \in \mathbb{R}^{r \times r}} \left\{ \| ...
-1
votes
2answers
18 views

Determine vector which maximizes the given function

Determine vector x $\in R^3$ with $\|x\|^2=x^Tx=1$ which maximizes the function below $$ f(x) = 2x_1^2 +2x_2^2-x_3^2+2x_1x_2$$ If someone can show me how to tackle this problem then I have at least ...
-1
votes
0answers
10 views

How to solve “and-or” constrained optimization problems in MATLAB? [on hold]

The typical constrained optimization problem that I am facing is: minimize ||y-z|| (y is a given vector of say, length 10) subject to the following constraints on z: (1) z1 <= max(z2,z3,z6), (2) z3 ...
2
votes
1answer
130 views

If $a,b,c>0, a+b+c=3$, minimize $\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{3-c^3}{c}$ [duplicate]

Let $a,b,c$ be positive real numbers such that $a+b+c=3$. Find the minimum value of the expression $A= \frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{3-c^3}{c}$ I tried solving it, but I got nothing
0
votes
0answers
25 views

Will the result of this maximization problem be the same for the two considered cases?

Suppose I have $2$ options: option1 and option2. For each option we associate a quantity $q$ that changes each time $t$, namely $q_1(t)$ and $q_2(t)$. Let $\mathbf{q}=(q_1(t),q_2(t))$. The different ...
2
votes
1answer
15 views

Proving that a local maximum of a given bounded function is global.

I am studying a certain maximisation problem (coming from some sort of likelyhood estimations); after a number of generalisations I need to examine $$f(x_1, x_2,y) = a_1\ln x_1 +a_2 \ln x_2 + \ln y - ...
0
votes
0answers
17 views

Approximate inverse (or fast optimization) of non-linear least squares problem

Problem Statement Let ${\bf x}\in\mathbb{R}^N$ and ${\bf W}\in\mathbb{R}^{K\times N}$, ${\bf V}\in\mathbb{R}^{N\times K}$. We define $${\bf y} = f({\bf x}) = [{\bf V}[{\bf Wx}]_+]_+$$ where $[.]_+ = ...
0
votes
1answer
14 views

How to optimally cut kitchen worktops (countertops) from slabs of material

Given a number N of rectangular kitchen worktops, of variable dimensions to be cut from slabs of material of fixed dimensions Determine an optimal fit to minimise wastage and number of slabs used. ...
0
votes
0answers
23 views

Convex envelopes of bivariate functions

In order to convexify my nonlinear non-convex program I need convex envelopes for the function $(x/y)^2$, both x,y are positive. I am only aware of the convex envelopes of the type $xy$ from here ...
1
vote
1answer
22 views

Multivariable optimization- Nature of critical points when det of hessian matrix = 0

I'm struggling a bit with my multivariable optimization. Assuming the determinant of the hessian matrix ≠ 0 I have no issue, though when the det = 0 I get stumped. Example- $$f(x,y)=x^4+y^4-(x+y)^2$$ ...
0
votes
2answers
37 views

Optimization Problem: Fence with adjacent sides rather than opposing sides

I'm unsure if I got the following right on a test I just took: A farmer wants to build a rectangular fence using both wood and metal and wants adjacent sides to be of the same material. Metal costs ...
1
vote
1answer
96 views

Regarding Nesterov's smooth minimization

I am currently studying this Nesterov's paper for project purposes, and I am trying to figure out how the smoothing and the minimization algorithm works I have tried looking at the example ...
0
votes
1answer
39 views

Minimization involving equality constraints

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \underset{\mathbf{x},\mathbf{y}}{\text{minimize}} \hspace{4mm} \big(\left( \mathbf{y}^T ...
1
vote
1answer
28 views

The optimal function value in linear programming has analytic solution

Consider the following linear programming problem: $\min c'x$ subject to $Ax=b$ and $x\geq0$, where $A$ is $m\times n$ with rank$A=m$. The dual is $\max -b'v$ subject to $A'v+c=\lambda$ and ...
1
vote
1answer
37 views

Optimizing a function of a matrix

Let \begin{equation} \begin{aligned} W= & \underset{X}{\mathrm{maximize}} & & \log \left|X + K_1\right|- \alpha \log \left|X + K_2\right|\\ & \mathrm{subject \; to} & & 0 ...
1
vote
3answers
75 views

Maximize the following sum

Let $a, b, c, d, e$ be nonnegative integers such that $625a + 250b + 100c + 40d + 16e = 15^3$ . What is the maximum possible value of $a + b + c + d + e$? Quick arithmetic gives: ...
2
votes
2answers
44 views

How to determine a function of a matrix is increasing or decreasing

We know that the derivative of a function can be used to determine whether the function is increasing or decreasing on any intervals in its domain. If $f'(x) > 0 $ at certain interval I, then the ...
2
votes
5answers
446 views

Find the maximum possible area of a certain right triangle

I want to find the maximum possible area of a right triangle with hypotenuse $=10$. My approach so far: let $x,y$ be the lengths of the two sides adjacent to the right angle; then $$100=x^2+y^2$$ ...
0
votes
1answer
20 views

Functional Lifting in Optimisation - Reference Request

I'm looking to learn about the use of (functional) lifting applied to a non-convex optimisation problem to give a (larger) convex problem. Unfortunately, I'm having a great deal of trouble finding ...
1
vote
0answers
46 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in ...
0
votes
1answer
39 views

Optimization problem in flight scheduling

I found this question here The question is I wrote the LP problem as this: Let $x_{ij}$ be the maximum no.of flights between city i and city j. Let $a_0$ be the artificial link and $x_0$ be the ...
2
votes
1answer
26 views

optimization network models

This is a question from Wane Winston 's Book. I don't understand how to do this. I tried to do it this way but it doesn't seem to work. Let $C_{ij}$ be the cost of using box of i $ i>=j$ Then ...
0
votes
0answers
20 views

strengths and weaknesses of analytical method

I was wondering if anyone could suggest any books or paper that explain/discuss the advantages and drawbacks of analytical methods for optimization. Also, if we have a convex objective function ...
0
votes
0answers
34 views

What does $\frac{d^k h}{dx^k}$ mean in the context of vectors and regularization in machine learning?

I was watching a machine learning videos from the caltech course CS 156 and they have a slide where they talk about how radial basis functions (RBFs) can be derived from the following variational ...
1
vote
3answers
34 views

Finding extrema.

Find the minimum distance between point $M(0,-2)$ and points $(x,y)$ such that: $y=\frac{16}{\sqrt{3}\,x^{3}}-2$ for $x>0$ . I used the formula for distance between two points in a plane to get: ...