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
24 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
116 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
29 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
39 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
76 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
449 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
23 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
40 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
28 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: ...
1
vote
1answer
21 views

Complexity of finding M nodes in a graph to maximize the pairwise minimum distance between nodes

I want to know the complexity of finding a set of M nodes, $\{U_1,\dots,U_M\}$, in a given graph $G$, to maximize $d(U_i,U_j)$ over all pairs $i\neq j$, where $d(\cdot,\cdot)$ is the length of the ...
1
vote
1answer
30 views

Find min/max values of $f(x,y)=x^3-y^3+3xy$ in the set $K=[0,4]\times[-4,0]$

Find the biggest and the smallest values of the function $f(x,y)=x^3-y^3+3xy$ in the set $K=[0,4]\times[-4,0]$. So using partial derivatives we find that the critical points are $(0,0)$ and $(1,-1)$. ...
0
votes
0answers
31 views

Expected probability maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like $$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$ Here $f(k,x)$ is actually a probability coming from a ...
0
votes
0answers
20 views

Invex function? How can I show?

Let $\mathbb{S}^m_+$ and $\mathbb{M}^{(m,n)}$, respectively, be the closed cone of positive semidefinite matrices and space of $m\times n$-dimensional matrices. Define function $F$ as ...
0
votes
0answers
18 views

Estimate Beam and Ball Problem System Parameters

I'm trying to estimate the parameters of beam and ball problem model. In the problem we have output as ball position and input as gear rotation angle. The issue that i want to ask is that our ...
0
votes
3answers
33 views

What algorithm will maximize utility when assigning of students to practicum locations

I have the following problem: Students from a class of 150 are beginning practicum training. Students have the option of either staying in an urban centre for their practicum, or optionally, they ...
0
votes
1answer
47 views

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove $(1-\lambda)x + \lambda y \in S$ for $x=\lambda'y$, $\lambda' < 0$.

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. I've verified that $x,y \in S$ implies $(1-\lambda)x + \lambda y \in S$ when $x,y$ are linearly independent using Pythagoras and when ...
0
votes
1answer
18 views

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these. I want to compute all the extreme points of the set $P$ (polyhedron) in $\mathbb R^3$ ...
-3
votes
4answers
102 views

Maximum and minimum of $y = x^4 - 8x^2 + 3$ for $x \in [ -1 , 2 ]$ [closed]

I have an assignment for tomorrow and I am struggling with this. How can we find the maximum and minimum of $y = x^4 - 8x^2 + 3$ for $x \in [ -1 , 2 ]$?
1
vote
1answer
27 views

Multivariable Linear Optimisation

I've been stewing on a problem for a week or so. I'm trying to work out an optimisation problem. Similar to the basic linear optimisation problems we used to look at with two variables, but I'm ...
1
vote
0answers
19 views

Max-flow-min-cut using LP duality

https://www.cs.oberlin.edu/~asharp/cs365/papers/Approximation-ch12.pdf is a chapter from Vazirani that discusses max cut-min flow using LP duality. The binary min-cut problem is: \begin{align} ...
1
vote
1answer
41 views

Optimizing trigonometric equation

I've come across a problem from an old calculus textbook which goes like A tool shed, $250\space cm$ high and $100\space cm$ deep is build against a wall. Calculate the shortest ladder length that ...
0
votes
1answer
25 views

How do I show that the set $S$ in $\mathbb R^3$ defined by linear inequalities is a $3$-simplex?

Consider the set $S$ in $\mathbb R^3$ defined by the inequalities: $x+y+z \ge 1$ $-x+y+z \le 1$ $x-y+z \le 1$ $x+y-z \le 1$ How can I show that $S$ is a $3$-simplex ? (Convex hull of $3 + 1$ ...
0
votes
1answer
97 views

How do I show that $B$ has an infinite number of extreme points, but no faces (sides) of dimension $1$ or $2$?

Let $B = \{ (x,y,z) \in \mathbb R^3 \mid x^2 + y^2 + z^2 \le 1\}$. How do I show that $B$ has an infinite number of extreme points, but no faces (sides) of dimension $1$ or $2$ ? I've been thinking ...
0
votes
2answers
24 views

Resolve this system:

Im tried to resolve this problem: $$\max\quad f\left( x,y \right) =xy\quad \text{s.a}\quad \begin{cases} x^2 +y^2+z^2 -1=0 \\ x+y+z=0 \end{cases}$$ Well, i form the lagrangian and the respective ...
0
votes
2answers
28 views

Minimum curve for the distance between two points at the plane

The problem is to determine the curve y=y(x) in the plane, the lenght of which is given by the functional: \begin{equation} I(y)=\int_{x_1}^{x_2}\sqrt{1+(y')^2}dx=\int_{x_1}^{x_2}F(x,y,y')dx ...
0
votes
1answer
22 views

For given mean $\mu$ of random variable X in [0,1], what is the probability distribution function $p(X)$ that makes $VAR(X)$ maximum?

Given the conditions $\int_{0}^{1} p(x)dx=1$, $\int_{0}^{1} xp(x)dx=\mu$ and $p(x)\ge0$ for $\forall x \in [0,1]$, What probability distribution function $p(x)$ makes $Var(X)$=$\int_{0}^{1} ...
1
vote
0answers
34 views

Determining the optimal cost through dynamic programming.

There are $n$ houses numbered $\{1, 2, 3, \dots, n\}$. The cost of laying a cable that serves houses $j, j+1, j+2, \dots, j+k $ is $f (j, k)$. One cable can serve a maximum of 10 houses. The ...
0
votes
1answer
16 views

reformulating an integer quadratic problem into a linear integer problem

I am trying to solve an optimization problem, in order to find an optimal runtime schedule for a machine. It involves one boolean variable $x_{t} \in \mathbb{\{0,1\}}$, that describes whetever the ...
1
vote
1answer
18 views

A clarification regarding dynamic programming.

This is a question regarding dynamic programming. The document to which I am referring is this (pg 325). It says that $$v_n(s_n)=\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$$ Here $v_n(s_n)$ is the ...
0
votes
0answers
35 views

The Hessian of the maximum of a function

I have an optimization problem where the inequality constraint is in the form of: $\min\limits_x f(x)$ subject to $\max\limits_{\zeta} g(x,\zeta) \leq 0$ where $x$ is the optimization variable. I ...
0
votes
1answer
36 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
1
vote
1answer
36 views

Simple question on maximizing a family of concave functions

Given $x \in [0,1]$, let $f_k(x)$ be concave function in $x$ for all $k= 0,1,...,N$. Is the following two maximization formulations equivalent? $$ \max_{0 \le k \le N} f_k(x) =?= \max \{f_0(x), ...
0
votes
0answers
40 views

Can I perform Maximum likelihood via optimization?

I have two $3 \times 3$ matrices $\mathbf{a}$ and $\mathbf{f}$. $\mathbf {f}$ is completely known to me. Also $a_{ij} \in [+1,-1]$ \begin{equation} \mathbf{f} = \left( \begin{array}{ccc} f_{11} ...
0
votes
1answer
11 views

Can a Convex QCQP Problem with an additional linear constraint be converted to a SOCP?

I have a quadratically constrained quadratic programming problem that I massaged into the form $$ \begin{aligned} & \underset{x}{\text{minimize}} & & x^T Q x \\ & \text{subject to} ...
0
votes
0answers
22 views

A length of fence encloses an area alongside a river — what is the optimal shape to maximize area? [duplicate]

You have $100$ meters of fence . There is a perfectly straight riverbank, much longer than $100$ meters, so you have plenty of room to work with. What is the optimal shape and dimensions that ...
0
votes
1answer
18 views

Optimization: maximizing nonconvex sum of product of constraints

I'm wondering if there is any way to convexify, approximate, and/or simplify the following problem. $\max. \sum_{k \in K} \prod_{i \in I} (a_{ik} x_{ik} + b_{ik})$ s.t. $x_{ik} \in [0,1]$ where ...
1
vote
0answers
31 views

How should I modify the initial guess for normalised version of an optimisation problem?

I am solving a large optimisation problem. The problem contains 500 decision variables and few hounderd constraints. Since the constraints are very tight and nonlinear, any random initial guess ...
5
votes
2answers
144 views

Minimum value of $\sqrt{\frac{a}{b+c}}+\sqrt{\frac{b}{c+a}}+\frac{24}{5\sqrt{5a+5b}}$

Let $a\ge b\ge c\ge 0$ such that $a+b+c=1$ Find the minimum value of $P=\sqrt{\dfrac{a}{b+c}}+\sqrt{\dfrac{b}{c+a}}+\dfrac{24}{5\sqrt{5a+5b}}$ I found that the minimum value of $P$ is ...
1
vote
0answers
17 views

Product expression maximization given 4 matrices as function of 2 column vectors

Hypothesis: - we are given 4 complex matrices denoted with $H_1, H_2, G_1$ and $G_2$. - the 4 matrices are not necessarily square so their size is $N$ by $M$. - we denote with $w_1$ and $w_2$ two ...
1
vote
2answers
25 views

A repository of constrained optimization test problems?

I am looking for a repository of constrained optimization problems with solutions. I want to find "benchmark" type problems to test my algorithm on and just trying to search for known problems ...
0
votes
0answers
31 views

What is topological learning?

I am getting this term topological learning in few places for example a reference is below at section 1.1.2: http://virenjain.org/thesis/VirenJainThesis_official.pdf Can anyone point out what ...
3
votes
0answers
67 views

How to solve the Few Scientists Problem (big word problem) in its general form?

I'm trying to figure out how to solve this word problem. I'm pretty sure it involves calculus or something even harder, but I don't know how to solve the general form. Let me start with the concrete ...
0
votes
0answers
35 views

Optimisation Problem for Pipe Nesting

I work in a company where we are supposed to produce and send pipes using trucks to buyers. Pipes of smaller diameter can be nested inside pipes of larger diameter while sending to minimize number of ...